Tuesday, February 23, 2010

Amazon Interview questions

I recently had an interview for internship by Amazon . Here i'm posting the questions asked during that . There were about four questions , out of which one was coding .

1) Consider you have a list of 2n+1 elements. n elements in the list have one duplicate. Give the algo to find the remaining unique element(the element without duplicate) ? { Eg: array 5 2 4 4 2 1 5 : here 1 is the unique element }

Modify the algo , if we have many elements without duplicate ? { Eg: array 5 2 4 4 1 7 2 3 5 here 1 7 and 3 are unique ie without duplicates }

2) Consider a singly linked (non circular ) list . Give the algo to find the pointer to the k'th element from the last , in a single iteration through the list .

3) Consider you have an array . the elements are arranged as in increasing order till a peak element , and from this element onwards it decreases..Give the algo to find this peak element .{ Eg: array : 2 3 4 5 6 3 2 1 : here 6 is the peak element. }
Modify your algo to take care of multiple peak elements . { Eg: array 2 3 4 5 6 3 2 1 5 8 9 2 1 here we peak elements are 6 9

Coding :
Write a definiton for the function with prototype given below:
Reversal(pointer to head of list, an integer k )
This function takes a list and an integer k, and reverses the first k elements of list and return a pointer to the head of new reversed list .