## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

Here was my solution:

public class Node
{
public Node left;
public Node right;
public Node parent;
public int value

public static Node findNext(Node n)
{

Node parent p=n.parent
if(parent == null)
return findNode(parent.left);

if(n==parent.left && parent.right == null)
return parent;
else if(n==parent.right && parent.right != null))
return findNode(parent.right);
}
}

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

int Find(struct Node *node)
{
if(!node)
return -1;
int res=-1;
struct Node *temp=NULL;
if(node->right)
{
temp=node->right;
while(temp->left)
temp=temp->left;
res=temp->data;
}
else
{
struct Node *parent=node->parent;
temp=node;
while(parent && temp==parent->right)
{
temp=temp->parent;
parent=parent->parent;
}
if(parent)
res=parent->data;
}
return res;
}

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

``````Node* InorderSuc(Node* fS){
if(!fS)
return NULL;
if(!fS->right && fS->Parent->left==fS)
return fS->Parent;
if(fS->right && fS->Parent->right==fS){
Node *succ=fS->right;
while(succ->left)
succ=succ->left;
return succ;
}
return NULL;
}``````

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

The tree doesn't look good. Here it is again

root: 7, left 5, right 11
5: left 4, right 6
4: left 2
11: left 9
9: right 15

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

``````/----15
/----11
|    \____9
7
|    /----6
\____5
\____4
\____2``````

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

this not a bst.. bst condition is violated at node with value 9.

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

@Danish:

The ascii tree figure is correct, no?

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

1. Find the root node. (This has to be done since you aren't guaranteed to start at the root)
2. Traverse the tree in search of the give value.
3. Return the values parent

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

it was told that visiting root node is unnecessary because for example the node in question might be most deep node in the tree.

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

The question is to find the inorder successor of the given node.
1. if the node has a rigth child then it is the next node.
2. else if the parent.data is greater than the node.data then it is the next node
3. else if the parent.data is less than the node.data
a) follow the parent till it is null or its data is greater
than the node.data.
i) if a parent node is found whose data is greater then it is the next node
ii) if it is null then there is no next node hence return null

``````if ( node.right !=null )
return node.right
else if ( node.parent.data > node.data )
return node.parent
else if ( node.parent.data < node.data ) {
temp = node.parent
while(temp !=null &&temp.data < node.data)
temp = node.parent
if(temp > node.data)
return temp
else if(temp==null)
return null
}``````

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

Almost correct but you missed one case in your 3.ii when you couldnt find a parent whose data is greater then it is the next node then stop at the node whose parent is NULL and now the successor is in right subtree(if it exists) so from root of tree(whose parent is NULL) traverse to the smallest in the right subtree and return that node. and there is changes to the psuedocode also

``````if ( node.right !=null )
return node.right
else if ( node.parent.data > node.data )
return node.parent
else if ( node.parent.data < node.data ) {
temp = node.parent
while(temp !=null &&temp.data < node.data){
node=temp
temp = node.parent
}
if(temp > node.data)
return temp
else if(temp==null){
if(node->right)
while (node->left){
node=node->left
}
return node
else
return null
}``````

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

Are you sure that your condition 1 is always true? Because in case of findNode(7) your algorithm will return 11 where the right answer is 9!

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

How you guys function deal with

"findNode(5) = 6" case

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

My bad. I havent checked for the special condition when the given node is root, in which case the next node will be the leftmost node in the right subtree. Sorry for the mistake. I think it wil work for every other case.

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

I think that if ( node.right !=null ) you need to do something like:

``````if ( node.right !=null )
{
Node temp = node.right;
while (temp.left != null)
temp = temp.left;
return temp;``````

}

say you have this BST:

``````9
/		\
4				10
/		\
1				7
/
6
/
5``````

and you run findNode(4) you should bet 5 which is goteen by going right once and then left until you can no longer go left.

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

``````public static Node search(Node node, int value) {
while (node != null && node.getValue() != value) {
if (value > node.getValue())
node = node.getRigth();
else
node = node.getLeft();
}
return node;
}

public static Node findNode(Node node, int value) {
Node _node = node;
if (node.getValue() != value) {
Node current = node;
while (current.getParent() != null) {
current = current.getParent();
}
_node = search(current, value);
}
if (_node == null)
return null;

if (_node.getRigth() != null) {
return min(_node.getRigth());
} else {
Node current = _node;
Node parent = current.getParent();
while (parent != null && parent.getRigth() == current) {
current = parent;
parent = parent.getParent();
}
return parent;
}
}

public static Node min(Node node) {
if (node == null)
return null;
Node cur = node;
while (cur.getLeft() != null)
cur = cur.getLeft();
return cur;
}``````

O(log(n)) complexity.

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

``````public Node next(){
if(right != null){
return right.min();
} else {
Node next = parent;
while(next != null && next.value < value){
next = next.parent;
}

return next;
}
}``````

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

``````class TreeNode {
int val;
TreeNode leftchild;
TreeNode rightchild;
TreeNode parent;

public TreeNode(int val) {
this.val = val;
leftchild = null;
rightchild = null;
parent = null;
}
}

public class Solution {

public static TreeNode findNode(TreeNode n) {
if (n == null) {
return null;
}
// root node
if (n.parent == null) {
return findLeftMost(n.rightchild);
}
// right child not null
if (n.rightchild != null) {
return findLeftMost(n.rightchild);
}
// right child is null, find next upper level
// n is leftchild
if (n.parent.leftchild == n) {
return n.parent;
}
// n is rightchild, which means n.parent has been fully checked
if (n.parent.rightchild == n) {
return findNode(n.parent.parent);
}
}

public static TreeNode findLeftMost(TreeNode root) {
if (root == null) {
return null;
}
while (root.leftchild != null) {
root = root.leftchild;
}
return root;
}
}``````

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

``````if the node has a right subtree, then the next element will be left most node in subtree
else if the node is the left child of the parent, parent is the next node
else if the node is the right child of the parent, find the first grandparent, to whose left, this node fall
else NULL``````

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

here is the solution I believe

1. first find the ultimate parent. ( while (tmp.getParent() !=null) node.getParent; )
2. Once you have ultimate parent , traverse the tree in inorder algo and get the next element, which would be desired node.

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

yeah your soln will not work. For example, it'll fail for next(6)=7.. you need to backtrack to grand parent...

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.