# Tag Archives: Amazon

## Amazon attempts

1st Amazon attempt (Cape Town):

• Implementation of HashTables
• Difference between new and malloc

2nd Amazon attempt:

Online test questions:

• LCA
• Delete duplicate nodes in Linked List

1st telephonic:

• Generate excel column names (A, B,… , Z, AA, BB,… , ZZ, AAA,…)
• Find square root of a number without using sqrt()

2nd telephonic:

•  Print if there exists a path with sum equal to K
• Print the path
• Return only True or False

1st onsite:

• isBST
• Number of nodes in the loop
• First node that is circularly linked
• Rope puzzle

2nd onsite:

• In a BST find two numbers with sum K
• Array return index of number from where left and right sum are same

Amazon third attempt:

Onsite written test:

• Find if a given LinkedList is palindrome or not
• Given an ‘ascending sorted’ and rotated array find the index of the given number
• Next largest number in a BST when a node is given

1st onsite:

• Distance between given two nodes in a binary tree (Upon hearing about LCA, wanted a solution for finding it in O(n) time and O(1) space)
• In an array, delete a number if there exists greater number than it, on its right side

2nd onsite:

• Delete duplicate elements in a string
• Do this in O(1) space and O(n^2) time complexities
• Do this when resulting string can be in any given order (O(n) time and O(1) space)

3rd onsite:

• Data structure that supports insertion, deletion and searching in O(log n) time
• Vertical sum in a binary tree
• In a gven 2 D array with sorted rows, sort the whole matrix

* * * * *

Filed under Interviews

## Amazon interview preparation

```Tree formation:

class Node
{
public:
Node(value) { nValue = value; pLeft = pRight = NULL; }

Node* pLeft;
Node* pRight;
int nValue;  // or any other data
}

class Tree
{
public:
Node* pRoot;
Tree() { pRoot = NULL; }

Node* search(int value); //...
void createLeaf(int value); //...
// ...
}```

Geeks for geeks (Update: Feb 15, 2013)

http://www.geeksforgeeks.org/find-the-minimum-distance-between-two-numbers/

http://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/

http://www.geeksforgeeks.org/check-if-each-internal-node-of-a-bst-has-exactly-one-child/

http://www.geeksforgeeks.org/majority-element/

http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/

http://www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/

http://www.leetcode.com/2010/04/how-to-determine-if-point-is-inside.html

http://www.leetcode.com/2010/04/rotating-array-in-place.html

http://www.leetcode.com/2010/09/fun-with-bit-operations.html

http://www.leetcode.com/2010/09/number-of-1-bits.html

http://www.leetcode.com/2010/11/stack-that-supports-push-pop-and-getmin.html

http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html

http://www.leetcode.com/2011/05/determine-if-two-rectangles-overlap.html

http://www.leetcode.com/2011/08/reverse-bits.html

http://www.geeksforgeeks.org/forum/tags/data-structures
Cool questions:

Diameter of tree: http://www.geeksforgeeks.org/archives/5687 [Done]

Three way partitioning: ( low and high are the numbers you want to partition by. p and q are regular quick sort counters. Check anything lower than low and swap it with the number placed at p and increment p, parallely, check anything more than high and swap it with the number placed at q and decrement q

```void threeWayPartition(int data[], int size, int low, int high) {
int p = -1;
int q = size;
for (int i = 0; i < q;) {
if (data[i] < low) {
swap(data[i], data[++p]);
++i;
} else if (data[i] >= high) {
swap(data[i], data[--q]);
} else {
++i;
}
}
}

2 way partitioning:

Low = 0 , High = n-1
A[low] = 0.. Lo++, 1.. A[lo]><A[high] & low++ & high--

3 way partitioning:

Low = 0, Mid = 0, High = n-1
A[mid] = 0.. a[low]><A[mid] & low++ & mid++, 1.. mid++, 2.. a[mid]><a[high] & mid++ & high--```

1 Comment

October 20, 2012 · 10:28 am