Amazon Placement paper 2011

1)You are given a function getInorderSuccessor which takes a BST (Binary Search Tree) as it's parameter. Every node has an extra pointer "next" , which is intialized to null, fill next with node pointers which represent Inorder Successor.


In a binary tree, inorder successor of a node is the next node in inorder traversal of the binary tree. Inorder successor is NULL for the last node in inorder traversal.


In BST, inorder successor of an input node can also be defined as the node with the smallest key greater than the key of input node. So, it is sometimes important to find next node in sorted order.


2)You are given a function printKDistanceNodes which takes in a root node of a binary tree, a start node and an integer K.  Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted order. Distance can be upwards or downwards.

Example:

Sample Input:

Root node: 5
Given start node: 8
Distance (K): 1

Sample Output:

5
6
9

3)SDE Technical Test - October
Back to Question List
Time Remaining: 00:06:46

    In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn].


    PS: Doing without using extra memory would fetch more points
    Sample Testcases:

    Input #00:

    {1,2,3,4,5,6,7,8,9,10,11,12}

    Output #00:

    {1,5,9,2,6,10,3,7,11,4,8,12}

    Explanation:

    Here as you can notice, the array is of the form
    {a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4}

4)Given a single linked list with an additional pointer to a random node (which can also be NULL), clone the list and return it.

Example:

One arrow points to the next element, while the other points to the 'random' element. If there is only one arrow out of a node, it points to the next node. Clone and return the head of the new list alone.

Note: Your code will not be considered for evaluation if you just return the input list as the cloned list.