## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 3 vote

Not possible with a balanced bst. It is impossible to decide the path at root which to take in this case. It needs to be a complete bst instead for a O(lgn) solution.

Comment hidden because of low score. Click to expand.
0

In case of complete bst we can utilize the property of having n depth and 2^n-1 elements as :

``````int getnode(struct tnode *root,int n,int k)
{
if(root==NULL)
return -1;
if(n/2 +1 == k)
return root->val;
if(n/2 + 1 > k)
return getnode(root->left,n/2,k);
return getnode(root->right,n/2,k-n/2-1);
}``````

n here is total nodes in tree

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can augment the BST where each node will store the size of the left sub-tree as well as the size of the right sub-tree. So at each node if N>size(left_sub-tree) traverse the right sub-tree. Otherwise traverse the left sub-tree. If you go to the right sub-tree then you'll have change N to N - size(left_sub-tree) -1 .

Comment hidden because of low score. Click to expand.
0

this is not alllowed

Comment hidden because of low score. Click to expand.
0

Not allowed? What kind of shit is this? I feel like swearing.. !@#

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just some random thoughts:-

As its given that BST is balanced, we can follow below approach:-
1)Find the depth(logn), let n is depth, call a function foo on root and pass depth as well
foo(root, n, k)
2)Total no of element is 2^n -1, no of nodes in left and right subtree each is 2^(n-1) - 1
3)if k = 2^(n-1), you found the ans, return the current node
4)else if k > 2^(n-1), search in right subtree foo(root.right, n-1, k - 2^(n-1))
5)else search in left subtree, foo(root.right, n-1, k )

Let me know if you see any issue in approach.

Comment hidden because of low score. Click to expand.
0

Exactly my thought, yet it it works only when the tree is a full binary sort tree. This is code in C++:

``````TreeNode* getNthNodeOfFullBST(int n, TreeNode* p, int height, TreeNode* parent, int parentIndex)
{
//get the order of node p
int index = p == parent->left ? parentIndex - (1 << height) : parentIndex + (1 << height);
if(index == n) return p;
return getNthNodeOfFullBST(n, n > index ? p->right : p->left, height - 1, p, index);
}
TreeNode* getNthNodeOfFullBST(TreeNode* pFullBST, int n)
{
if(n < 1 || pFullBST == NULL) return NULL;

//get height of the full BST
int height = 0;
TreeNode* p = pFullBST;
for(; p->left != NULL; p = p->left) ++height;
if(n > (1 << (height + 1))) return NULL;//there are less than n nodes at all

//get the order of root
int index = 1 << height;
if(n == index) return pFullBST;
return getNthNode(n, n > index ? pFullBST->right : pFullBST->left, height - 1, pFullBST, index);
}``````

Comment hidden because of low score. Click to expand.
0

Damn you guys were quicker ;-)

``````public class TreeLookup<T extends Comparable<T>> {

public T determineNthElement(final Node<T> root, final int nThElementPosition) {

T retVal = null;

if (root != null) {
retVal = determineNthElement(root, nThElementPosition, determineTreeHeight(root));
}
return retVal;
}

private T determineNthElement(final Node<T> root, final int nThElementPosition, final int treeHeight) {

final int singleBranchChildCount = ((int)Math.pow(2, treeHeight) - 2) / 2;
T retVal = null;

if ((singleBranchChildCount == 1 && (singleBranchChildCount) == nThElementPosition) ||
(singleBranchChildCount != 1 && (singleBranchChildCount + 1) == nThElementPosition)) {
retVal = root.getValue();
} else {

if (singleBranchChildCount >= nThElementPosition) {
retVal = determineNthElement(root.getLeft(), nThElementPosition-1, treeHeight-1);
} else {
retVal = determineNthElement(root.getRight(), nThElementPosition-1, treeHeight-1);
}
}
return retVal;
}

private final int determineTreeHeight(Node<T> root) {

int height = 1;
while (root.getLeft() != null) {
root = root.getLeft();
height++;
}
return height;
}
}``````

But this proof of concept (at least mine) don't work for all balanced tree. For this type of tree it will work:
15
8 20
6 10 18 22

type of tree it won't work:
15
8 20
6 10 18 22
9

Comment hidden because of low score. Click to expand.
0

How is finding depth o(log n) for BST?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Every time the search will only half the elements, so running time will be O(log(n))
You can hold this information in the node so totalChildUnderRootAtIndex() should run in O(1) time

Here is a code snippet.

public int findNthSmallest(int[] T, int n, int rootIndex)
{
if (n > T.length -1) {
return -1;
}
int totalLeftChildsAtRoot = totalChildUnderRootAtIndex(2*rootIndex,0,T);
int totalRightChildsAtRoot = totalChildUnderRootAtIndex(2*rootIndex+1,0,T);

if (n == totalLeftChildsAtRoot + 1) {
return T[rootIndex];
}
else if(n < totalLeftChildsAtRoot + 1)
{
//Search in left sub tree
return findNthSmallest(T, n, 2 * rootIndex);
}
else
{
//Search in teh right Sub Tree
return findNthSmallest(T, n-(totalLeftChildsAtRoot + 1), 2 * rootIndex+1);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Count the number of nodes in the left half of the BST which is O(lg n). If this count >=k then the kth smallest element is on the left side, so search the left half else search the right half.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

public void visit(Node* root, int& number,int n) {
if(root == null) return;

visit(root->left,number,n);

if(number == n) {
cout<<root->value;
return;
}
number += 1;
visit(root->right,number,n);
}

int number = 0;
visit(root,number,3);

Comment hidden because of low score. Click to expand.
0

Mhhh looks for me like an O(n) solution (DFS), no?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Why not just do an inorder traversal of first n nodes amigo?
In order traversal always gives you numbers in increasing order, so you'll get the first n numbers

Comment hidden because of low score. Click to expand.
-1
of 1 vote

that is O(n)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.