Ebay Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

Ingredients: Depth First traversal, a sentinel node.

void leaf_linking_traversal(Node* node, Node** prev_node)
{
    assert(*prev_node);
    if (node)
    {
        if (node->left == 0 && node->right == 0)
        {
            (*prev_node)->right = node;
            node->left = *prev_node;
            *prev_node = node;
        }
        else
        {
            leaf_linking_traversal(node->left, prev_node);
            leaf_linking_traversal(node->right,prev_node);
        }  
    }
}

void link_leaves(Node* tree_root, Node& sentinel)
{
    if (tree_root)
    {
        Node* list_back = &sentinel;
        leaf_linking_traversal(tree_root, &list_back);
        if (list_back!=&sentinel)
        {
            list_back->right = &sentinel;
            sentinel.left    = list_back;
        }
        else
        {
            sentinel.right = &sentinel;
            sentinel.left  = &sentinel;
        }
    }
}

- oos September 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You have given the ingredients, but recipe is not in english. Care to explain?

- Anonymous September 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

well, an element of a double linked list has two pointers: forward and backward. Think of a tree node's right pointer as forward and its left pointer as backward.

the algorithm consists in traversing the tree and appending leaves to the list as we encounter them from left to right.

you have a routine called leaf_linking traversal(...) which is in charge of this. It needs a pointer to a node to explore from, and a pointer to the back of the double-linked list to be construct.

in the first call to this routine, you pass the root as the current node and a pointer to the list's sentinel.

the depth first search performed by the routine knows it has found a leaf when the left and right pointers are both 0 (unassigned).

in that case, it performs the double-linking, and the current node (leaf) becomes the last element of the list. This change is reflected through re-assignment of the pointer *prev_node. It means that the next leaf in the tree is going to see the current leaf as the one it should double-link to.

when the traversal is over, you still have to double-connect the last element in the list to the sentinel, or double-connect the sentinel tp itself in case the tree was empty (routine link_leaves(...) does this).

- oos September 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think you can just do it by traversing the tree once. When you reach a leaf simply pass it to the routine which makes the list ( something like addToList(node)). This routine will return a head which will be the first node it receives.

- Noobie September 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does anyone know what "re-using the left and right pointers" mean?

- fz September 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

May be it means that if you have a sub tree like [Left] <== [Root] ==> [Right], then your algorithm should reuse these links for constructing the corresponding Doubly Linked List: [Left] <==> [Root] <==> [Right]

- rajarshi129 October 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void convert() {
		TreeNode head = null;
		TreeNode prev = null;
		convertT(root, head, prev);
	}

	private void convertT(TreeNode node, TreeNode head, TreeNode prev) {
		if (node == null) {
			return;
		}

		convertT(node.left, head, prev);
		node.left = prev;
		if (prev != null) {
			prev.right = node;
		} else {
			head = node;
		}
		TreeNode right = node.right;
		head.left = node;
		node.right = head;
		
		prev = node;
		convertT(right, head, prev);
	}

- Kevin March 09, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More