Amazon Software Development Engineer interview questions

Phone Interviews: 1) Least Common Ancestor of 2 nodes in a binary tree 2) Trim extra spaces in a given String. 3) Check whether given linked list is circular or not 4) Design a restaurant reservation system Face to Face: 1) System Design question . Implement "File" java class. He went deep in to the design specifics , asked me to design cache , handle parallel access , efficient data structures to do it etc.., 2) Integers are arriving at a rate of one on a socket stream. At any given time print k largest numbers. Describe an efficient algorithm and implement it in language of your choice. 3) Given a binary tree and an integer S , print all distinct paths from root to leaves which sum to S. Describe the algorithm and implement it. 4)Write a program to print the largest sub string which is a palindrome in a given string. He asked me to optimize it with O(n) solution 5) Given a list of nodes , Node class has fields value(of type integer) , next(of type Node) , other(of type Node) where next points to next node and other points to some arbitrary node in the list. Make a copy of the list. Describe an efficient algorithm and implement it.

How would you create an array given two sorted arrays.