Dharam
BAN USEROkay..here is another one..in O(k.x) time and O(k+x) space.
where x = k in worst case, but in average case , x will be of order O(1).
The idea is to traverse the matrix in such a way that we encounter kth element directly.
a.) Maintain two sets Set A and Set B.
Initially, set A = { NULL }, Set B = {NULL}
Set A == elements which we have seen till now.
Set B == neighbours of the elements of Set A,in sorted order using insertion sort.
b.) Set A = {a[0][0]} , Set B = { Neighbours of a[0][0], i.e a[0][1] , a[1][0] } ;
c.) if sizeof(set A) == k ), return kth element from Set A.
d.) else move minimum(Set B) to set A .
e.) Insert neighbours ( neighbours(a[x][y]) = {a[x][y+1] ,a[x+1][y],a[x-1][y],a[x][y-1]) of minimum(Set B) to Set B[use insertion sort]. As Set B will be of small size, you can assume that insertion sort will be fast and will do the ordering in O(1) time.
In the above example:
Set A Set B
{NULL } {NULL}
{2} {4,5}
{2,4} {5,6,7}
{2,4,5} {6,7,8}
{2,4,5,6} {7,8,15}
{2,4,5,6,7} {8,15}
Here...k == 5 , so stop and return 5th element of Set A i.e, '7'
@steve: "totally10 Million个entry" ---> what do you mean by this? is the dictionary sorted in increasing order of keys?
As the data is huge(~ 10 GB),I guess, the interviewer is looking for some reader-writer sort of solution(assuming he wants to edit the entries too...)
As we need to take binary decisions...what if we create a tree based on the output of the function API provided.
a.) start with any element as root.
b.) if next team lost the match with the root team, insert it into the left of the root
c.) if next team won the match with the root team, insert it into the right of the root
d.) keep inserting the teams with the above scheme(for root->left or root->right)
Print the in-order traversal of the tree !!
@Rajanikant,
Consider this case 1->2->3->4->5->6->7->6.
n = 7;
k = 5;
With what you said.. n - 2k = -3 ; now this negative number does tell you something that a.) loop has very short length and slow pointer probably has not entered the loop when fast pointer completes one cycle, but it certainly does not tell you the meeting node as you explained. or does it??
If you omit this condition, the problem becomes very simple. I guess, later or sooner the interviewer would ask you to add this condition as well.
- Dharam January 09, 2014