Tag Archives: Amazon

Amazon attempts

1st Amazon attempt (Cape Town):

  • Kadane’s Algorithm
  • 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
  • Circular linked list
    • 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)
  • Kadane’s Algorithm
  • 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

* * * * *


Leave a comment

Filed under Interviews

Amazon interview preparation

Tree formation:

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

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

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

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

Geeks for geeks (Update: Feb 15, 2013)







LeetCode must read problems:





http://www.leetcode.com/2010/09/printing-binary-tree-in-level-order.html [Done]

http://www.leetcode.com/2010/09/determine-if-binary-tree-is-binary.html [Done]

http://www.leetcode.com/2010/09/printing-binary-tree-in-zig-zag-level_18.html [Done]

http://www.leetcode.com/2010/10/print-edge-nodes-boundary-of-binary.html [Done]


http://www.leetcode.com/2010/11/largest-binary-search-tree-bst-in_22.html [Done]


http://www.leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html [Done]


http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-ii.html [Done]

GeeksForGeeks data structure link:

Cool questions:

http://www.geeksforgeeks.org/forum/topic/given-inorder-and-postorder-traversals-construct-a-binary-tree [Done]


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]);
    } else if (data[i] >= high) {
      swap(data[i], data[--q]);
    } else {

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