Amazon Interview Questions Puzzles and Algorithms

Questions asked during amazon interview process.During both phone and personal.

### 1. Nth last.

How would you find the nth to last element in a linked list?

MyAnswer:

- push into stack
- Take two pointers: p1 and p2

Increment p2 until it points to the **N+1**th node after head. Now the two pointers are N nodes apart. Keep incrementing both p1 and p2 by one until p2 points to NULL. p1 will now be pointing to the Nth last element.

### 2. Card Shuffle

Explain algorithm to shuffle cards

for(int i = 0; i < N; i++) { int j = (rand()%(N-i)) + i; swap(&array[i], &array[j]); // void swap(Card*, Card*); swaps them }

This guarantees you're equally likely to put any of the N Cards in the first position, equally likely to put any of the N - 1 remaining Cards in the next, so on and so forth… Therefore all permutations are uniformly likely.

Of course, RAND_MAX (usually about 2^15) must be fairly large compared to N. Otherwise, you should use

int j = (int)( rand() / (RAND_MAX + 1.0) * (N - i)) + i;

here is a famous algorithm called the Knuth Suffle algorithm which solves this problem in O(n) time.

Let X1, X2,….Xn be the N cards to be suffled.

1. Set j = N

2. Generate random number R uniformly distributed between 0 and 1.

3. Set k = j*R + 1

4. Swap(Xk,Xj)

5. j = j-1

6. If j > 1, go to step 2

### 3. Jigsaw puzzle

Coding: Jig saw puzzle. What are the data structures? Assume you have some method which can tell you if two pieces fit together. How would you solve the puzzle, minimizing the number of times you have to call that function?

### 4. Parsing phone numbers

You have 50,000 html files, some of which contain phone numbers. How would you create a list of all the files which contain phone numbers?

5. Repeated element

How would you detect a repeated element in an integer array.

6. Smoothening the curve

Write a function to smooth out stock fluctuations.

7. Union

Given two sets, Write a function to provide the union of them.

8. Most viewed

Design an algorithm to calculate the most user viewed pages

9. Duplicates

Design an algorithm to find duplicates in an array.

10. BST Serialization

Design an algorithm and write code to serialize a binary tree.

### 11. Numbers with Sum

Design an algorithm and write code to find two numbers in an array whose sum equals a given value

hastable

key=number, value = sum-value;

if(sum-number) appears in Hashtable. got it;

else insert value also into hashtable;

12. Bits in Integer

count bits in an integer.

int BitCount (unsigned int u) { unsigned int uCount=0 ; for(; u; u&=(u-1)) uCount++; return uCount ; }

14. Random character from stream

assume your computer is reading characters one by one from a stream (you don't know the length of the stream before ending). Note that you have only one character of storage space (so you cann't save the characters you've read to a something like a strong). When you've finished reading you should return a character out of the stream with equal probability.

### 15. Print Tree

You have a tree (not Binary) and you want to print the values of all the nodes in this tree level by level.

BFS

void BFS(NODE *root) { if (!root)return; Queue q = new Queue(); q->Enqueue(root); do { NODE *curr = q->Dequeue(); print(curr->val); if (curr->left) q->Enqueue(curr->left); if (curr->right) q->Enqueue(curr->right); }while (!q->Empty()); }

### 16. Calculate an infix expression. This question later evolved into calculate a postfix expression

### 17. Reverse a linked list

eclare pointers curr, prev, next set prev = null; set curr = list_head; do loop set next = curr->next set curr->next = prev set prev = curr set curr = next; while curr != null

### 18. Write a function that returns a node in a tree given two parameters: pointer to the root node and the inorder traversal number of the node we want to return. The only information stored in the tree is the number of children for each node.

### 19.If you are given a number as a parameter, write a function that would put commas after every third digit from the right.

public static void foo (int num,int cnt) { if(num/10!=0) { //++cnt; foo(num/10,(cnt+1)); } System.out.print(num%10); if(cnt > 0 && cnt%3==0) System.out.print(","); }

#### reverse print a link list

void reversePrint(node *n) { if(n) { reversePrint(n->next); print(n->content); } }

### 20. find dup number for n+1 numbers from 1…n

Number = Sum - n*(n+1)/2

### 21. How do you determine the size of an object in Java?

java.lang.instrument.Instrumentation.getObjectSize(Object objectToSize)

Returns an implementation-specific approximation of the amount of storage consumed by the specified object.

http://forum.java.sun.com/thread.jspa?forumID=31&messageID=2806106&threadID=567886