Amazon

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?

1. push into stack
2. Take two pointers: p1 and p2

Increment p2 until it points to the N+1th 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());

}
```

### 17. Reverse a linked list

```eclare pointers curr, prev, next

set prev = null;

do loop
set next = curr->next

set curr->next = prev

set prev = curr
set curr = next;
while curr != null
```

### 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.