Techy: Questions - hints

Hints to questions asked in my earlier post Techy: Questions

1. The random function in Unix gives a number between 0 and RAND_MAX (which is fairly large). So starting with the 1st index as seed, call random function K-1 times with the seed for each call being the output of the previous call of the random function. Once these K numbers are available, sort them and iterate on the list using these numbers.
2. Try using a modification of the quicksort alogrithm, with the pivot at the kth item. Pivots in subsequent iterations will also be the kth item of the original list. The actual location of the pivot in the sublist will depend on the size of the sublist and of any sub lists which have smaller entries than the sublist under consideration.
   

Techy: Questions - 2

1. Given two linked lists. Find whether they converge or not.
2. If the lists converge then find the point of convergence
3. How to find if a rectilinear polygon is clockwise or anticlockwise, given the coordinates of all the points in order.

Umberto Eco’s Anti-Library

Interesting quote from Taleb's Black Swan

“The writer Umberto Eco belongs to that small class of scholars who are encylopedic, insightful, and nondull. He is the owner of a large personal library (containing thirty thousand books), and separates visitors into two categories: those who react with “Wow! Signore professore dottore Eco, what a library you have! How many of these books have you read?” and the others - a very small minority - who get the point that a private library is not an ego-boosting appendage but a research tool. Read books are far less valuable than unread ones. The library should contain as much of what you do not know as your financial means, mortgage rates, and the currently tight read-estate market allows you to put there. You will accumulate more knowledge and more books as you grow older, and the growing number of unread books on the shelves will look at you menacingly. Indeed, the more you know, the larger the rows of unread books. Let us call this collection of unread books an antilibrary.
We tend to treat our knowledge as personal property to be protected and defended. It is an ornament that allows us to rise in the pecking order. So this tendency to offend Eco’s library sensibility by focusing on the known is a human bias that extends to our mental operations. People don’t walk around with anti-resumes telling you what they have not studied or experienced (it’s the job of their competitors to do that), but it would be nice if they did. Just as we need to stand library logic on its head, we will work on standing knowledge itself on its head. Note that the Black Swan comes from our misunderstanding of the likelihood of surprises, those unread books, because we take what we know a little too seriously.
Let us call this an antischolar - someone who focuses on the unread books, and makes an attempt not to treat his knowledge as a treasure, or even a possession, or even a self-esteem enhancement device - a skeptical empiricist.”


After reading this piece, I don't fear the growing number of unread books in my collection. And it inspires me to buy more books and not wait till I have read all of the present unread set which I was doing till now.

India Tour of Austrailia 07-08: 3rd Test review

Siddhartha Vaidyanathan's pre-match article on the 3rd test match between India and Australia had an interesting comment:

"Despite all the portents India can take heart from one fact: they've recently pulled off surprises in bowler-friendly conditions abroad. Like in Headingley in 2002, Kingston or even Wanderers in 2006 and Nottingham last year, they have stood up and taken on the challenge."

When I had read this I I had hoped if there could be a repeat at Perth.
Post match it appears that India are on there way to win the pace battles in near future. And given the unpredictable nature of Indian team, I am now beginning to doubt there capabilities to win on pitches which are expected to help them. Look at what happened at Sydney and Melbourne earlier. Both places where India had a chance. But post Perth, one thing that I am confident about is that Indian pace battery is there to stay and has the potential to become world beaters in future.

Raise your sights

The article Cricinfo - Raise your sights, India by Peter Roebuck on the state of Cricket in India and what it should do next in Cricket is an interesting one. The arguments raised in it can easily be applied to personal life as well:

1. In the long run it was not the result that mattered but the response -- rise like a phoniex from the ashes is what they say
2. A newly formed nation relishes every achievement because they instil confidence and create identity. A mature country is not so easily pleased. Certainly, it does not live in the past. -- but it does remember it so as move forward in a better manner
3. Defeats have led not to rational introspection but to loud protest -- do not blame someone else but see what more you could have to done to win
4. Goals help to define actions -- no better truth than this one
5. extract every last drop of ability .... keep working, keep improving. -- the only thing constant is change

Offshoring

Interesting article on offshoring from Sramana -- Trend Radar 2008: Offshoring - Sramana Mitra on Strategy
A year back I would have disagreed with her, but with the learnings in the past one year, I think she is right on the count that in 5 years time the cost of living in Indian Metros would be comparable to that in the US.
However, if India has to stay on top then we have to develop ourselves into a product development industry rathar than a service industry. That would help India to maintain its niche in the IT industry.

And with lots of activities going on in Indian IT industry I have little doubt that India wont be able to make it.

Techy: Questions

Q1. Find k random elements from a very long linked list. The size of the list is not known.
[Update: if the size of the list is given then how does the answer change]

Q2. Find the kth smallest element from a list of integers.