We pay for user submitted tutorials and articles that we publish. Anyone can send in a contribution
Learn MoreThat’s it, the 9th post of the series of programming job interview challenge is out and alive. 19 readers provided answers to job interview challenge #8, Pieter G was the first to provide a correct answer:
The fastest way I can come up with is to generate a finite state machine at initialization. The transitions between states would be defined by the records you look for in the pattern and one transition for an unmatched record. When the machine enters the goal state is should send the notification (how to most quickly do that I leave to someone else). When reaching the goal state the machine should not terminate but continue (else we may miss a occurrence).
You can see more details about the solution in those blog entries:
Those are the readers who provided a correct answers in comments:
Pieter G, Dirk, Josh Bjornson, Tim C, Timothy Fries, Tristan, Michael Mrozek, Edward Shen, Alex, Trinity, Antoine Hersen and Mark Brackett.
Again, as last week, the amount of incorrect answers is tiny and there is no major pattern in those answers, so I will not refer to them. But, if someone think that I misunderstood his answer, please leave me a comment about it.
This week’s question:
This question is about trees and it is very simple. It is a logical question so there is no need for code.
You have a tree (lets assume it is a binary tree, but it could be any king of tree), you need to provide an efficient algorithm to locate the one before last node in an In-order traverse (left -> root -> right). I am not looking for an O(whatever) answer because the worst case is always O(n) incase the tree is a list, so think about you solution carefully, we want a practical solution so O(n/2) (on a normal tree) is better than O(n). The tree is not sorted and there is no meaning to the values in the nodes, we want the location in the traverse. for example:
Here we would like to get the pink node.
As always you may post the solution in your blog or comment. Comments will be approved next week.
Good luck
Tags :
challengeIn OrderInterviewJobjob interviewNodequestionSortTraverseTree Copyright © 2012 Dev102.com
Breeze : Designed by Amit Raz and Nitzan Kupererd
Jonathan
Said on June 23, 2008 :
I think I’m missing something here — you want the node before the last one in an in-order traversal. Unless I’m forgetting the rules of an in-order traversal, your example would be: 43, 6, 345, 58, 94, 8, 33, 81, 1. The second-to-last node would be 81, not 1.
Wbat did I screw up here?
Amit
Said on June 23, 2008 :
You are definitely right!
My bad, I don’t know how I could miss it. I will change the Image
Thanks
Jonathan Gilbert
Said on June 23, 2008 :
This seems pretty simple to me. An in-order traversal can be reversed by simply following the right child first and the left child last. This produces a mirror-image. In this mirror image, the second-to-last from a regular traversal becomes the second item found. Thus, carrying a small amount of state with us so we know when to stop and return with what we’ve got:
class TreeNode
{
public int Value;
public TreeNode LeftChild, RightChild;
public TreeNode FindSecondToLastInOrder()
{
int skip = 1;
return find_second_to_last(ref skip);
}
private TreeNode find_second_to_last(ref int skip)
{
// Check the right child, if we have one.
if (RightChild != null)
{
TreeNode ret = RightChild.find_second_to_last(ref skip);
// If we’ve got something, skip went to 0 within the right child.
if (ret != null)
return ret;
}
// We’re yielding a node. Normally this would return it to some
// external consumer, but in this case, we simply count this node
// and return it if we’ve reached the desired count.
if (skip == 0)
return this;
skip–;
// Check the left child, if we have one.
if (LeftChild != null)
return LeftChild.find_second_to_last(ref skip);
// If we weren’t the last node in the in-order traversal and we
// don’t have a left child, return null to continue the hunt.
return null;
}
}
Kris Warkentin
Said on June 23, 2008 :
Assuming a binary tree I think we can do something like:
node = head
//traverse to rightmost node that still has
//children
while (node->right_child && has_children(node->right_child)) do
node = node_right_child;
//if the right child is a leaf it will
//be the last traversed node then
//the current node is second last
if(node->right_child)
return node;
//otherwise the current node is the last
//one in the traversal. The left tree
//will be completely traversed before
//the current node is visited therefore
//the last node in the left tree is
//second last overall
node = node->left_child
while(node->right_child)
node = node->right_child
return node;
Michael Mrozek
Said on June 23, 2008 :
Start with the root node. If the current node has a right child, check if the right child is a leaf node. If so, the current node is the penultimate node; if not, recurse this algorithm on the right child. If the current node does not have a right child, presumably it has a left (this problem is undefined for single-node trees since there is no concept of a “next to last” node in the traversal). Since the in-order traversal of the left child’s subtree will be followed (and concluded, since there is no right child) by the current node, the last node in the left child’s traversal will be the penultimate node in the main tree. To find the last node, make the left child the new current node, and then keep making the right child of the (new) current node the current node until it has no right child; the current node is the final node in the in-order traversal of the left child subtree, and the penultimate node of the main tree.
I know you said code isn’t required, but here’s short pseudocode to make sure the above was clear that you can feel free to ignore:
func findPen(node) {
if(node.hasRight()) {
return node.right.isLeaf() ? node : findPen(node.right)
} else if(node.hasLeft()) {
node = node.left;
while(node.hasRight()) node = node.right;
return node;
} else {
//? undefined
}
}
daniel gary
Said on June 23, 2008 :
obj = tree;
while(obj->right)
obj = obj->right
obj = obj->left || obj
Heiko Hatzfeld
Said on June 23, 2008 :
Hmmm
If I understood the question correctly, then I would do something like this:
- Go all the way right from the starting node, pushing everything on a stack
- at the end allow ONE left turn
- From the left turn go all the way right and push everything on the stack
- No way to turn right? We found the 2nd last node! push final node onto the stack
- output the stack…
This solution requiers no recursion
Michael Dikman
Said on June 23, 2008 :
My solution:
Find the last node: going maximum to the right (should not be more than log(n).
Then:
- If last node has left child then return findLastNode(leftchild) – log(n)
- Else If node has parent – return parent
- Else return finaLastNode(leftChild of parent of node)
Heiko Hatzfeld
Said on June 23, 2008 :
P.s.: If there is no “left” at the final right node, then dont push to the stack and “just” output the stack…
Jason Kikel
Said on June 23, 2008 :
The following assumes a starting tree with at least 2 nodes.
1. Find rightmost node for the tree. (Recursively move to the right child). Call this node ‘Rightmost’
2. If ‘Rightmost’ has no children move to its immediate parent and end.
3. Otherwise, find the rightmost node for the subtree with ‘Rightmost’s left child as root and end.
In Ruby:
def findRightmost(node)
if node.right == nil
node
else
findRightmost( node.right )
end
def findSecondLast(node)
rightmost = findRightmost( node )
if rightmost.right == nil
rightmost.parent
else
findRightmost( rightmost.left )
end
Edward Shen
Said on June 23, 2008 :
In order traversal seems to be for binary trees only. Since this is the case, i will claim that my tree splits its children down the middle, printing itself after the middle child if there is an odd number.
Traverse the tree starting from the root node, visiting the further right child for nodes traversed (rapidly making a vertical traversal). Once a node is found to have no children, do the following:
If node has 1 or 2 siblings, return the parent node. Otherwise return the sibling directly to the left.
Bill Budge
Said on June 23, 2008 :
case 1: if node has no left or right child, return null to indicate no answer.
case 2: if node has only a left child, from the left child, follow all right child links to last node in left subtree and return that.
case 3: otherwise node has a right child, apply this function recursively to right child. If result is non-null return result, otherwise return node.
Alex
Said on June 24, 2008 :
The following system is most easily described using a binary tree, but I’ll explain at the end how it can be adapted to any kind of asynchronous tree.
The key is to use a stack.
Given a node:
If the node has a right node, push current to the stack and recurse right.
If the node does NOT have a right node, but DOES have a left node, recurse left.
If the root node has no children, push the current node to the stack.
This set of rules will prevent you from bothering with branches of the tree which cannot contain
the second-to-last element, since if a branch has both children
Then, pop off the top element, and dispose of it.
Now the element at the top of the stack is the second-to-last node in an in-order traversal.
In order to adapt to an n-tree, instead of thinking of it as “left and right” children,
look for “second-to-farthest-right and farthest-right” children, and the algorithm will hold.
A more simplistic version (which is O(n)) is to just do a straight in-order traversal:
Given node:
If Possible, go left.
Process Current.
If possible, to right
and then do the same thing with the stack at the end: Pop off the top (disposing of it) and return the top of the remaining stack.
Alex
Said on June 24, 2008 :
Although my solution to the previous problem was also to use a Finite State Machine, I remain rather curious- You stated that “There is already a method to compare two binary records (O(1) complexity).”. Given that the FSA didn’t require comparing two records to eachother, was there a solution that utilized this rule? Or was this a red herring?
Hugh Brown
Said on June 24, 2008 :
Node secondLast(Node root)
{
boolean wentRight = true;
Node parent = NULL, current = root;
while (current->left && current->right)
{
parent = current;
wentRight = (current->right != NULL);
current = (current->right != NULL) ?
current->right :
current->left;
}
return (wentRight ? parent : current);
}
Shahar Y
Said on June 24, 2008 :
Hi Alex,
How would you know if you can move to the next state in the FSA? You have to compare the incoming record with a predefined record which defines the transition rules from the current state (in the FSA) to the next state.
leppie
Said on June 24, 2008 :
Traverse in reverse and get the second node?
Alex
Said on June 24, 2008 :
Ah, gotcha. I guess I was thinking of it in terms of analyzing the record itself for specific properties as opposed to predefined records- I was also thinking about the sequence definition in terms of “3 even ints in a row” as opposed to “2,4,6″, so checking for equality with a “2″ record didn’t gel in my head as being useful:D Thanks for the clarification.
Hugh Brown
Said on June 24, 2008 :
Okay, I have a shorter answer:
Node secondLast(Node root)
{
Node parent = NULL, current = root;
while (current->left && current->right)
{
parent = (current->right != NULL) ?
current : NULL;
current = (parent == NULL) ?
current->right : current->left;
}
return (parent != NULL) ? parent : current;
}
Mind you, there is a slight difference in semantics: now the code returns the root in the case that there is only one node in the tree. It still returns NULL for the case with 0 nodes.
configurator
Said on June 24, 2008 :
Unless I’m missing something, the solution is simple to define with pseudo-code.
I didn’t implement end-case checking (like an empty tree, etc.) to keep the code simple
// call with the root node
Node OneBeforeLast(Node n) {
if (n.Right != null)
return OneBeforeLast(n.Right);
else if (n.Left != null)
return n;
else
return n.Parent;
}
Michael Mrozek
Said on June 24, 2008 :
BTW, you tagged this entry differently from the others in the series, so it doesn’t show up on the list linked off each entry (http://www.dev102.com/tag/job-interview/)
Shahar Y
Said on June 25, 2008 :
Thank you very much Michael!!!
The tag was added.
Alex
Said on June 25, 2008 :
I realize now that I overengineered my previous answer- I went through a “what if we want third from last, or fourth from last? What if the position you want to return is passed as a parameter?” kind of headspace. That’s where the stack idea came from.
New and revised solution:
Standard in-order traversal of the tree (Recurse left, process current, recurse right), with the caveat that if the current node has both children (neither of which is null), skip the “recurse left” step: This prevents you from analyzing a branch that cannot possibly contain the second-to-last node. Keep two global variables, “prevnode, finalnode”, and at the “process” step, set prevnode=finalnode, finalnode=currentnode, where “currentnode” is your current position in the tree.
After going through the whole tree, “prevnode” will contain the “second to last” node you’re looking for.
The way to expand this to an n-tree is as follows. For a tree with n children, ignore all the children except the rightmost two children. Consider the second-to-rightmost child to be “left”, and the rightmost child to be “right”. Follow above algorithm.
Hugh Brown
Said on June 26, 2008 :
“How would you know if you can move to the next state in the FSA? You have to compare the incoming record with a predefined record which defines the transition rules from the current state (in the FSA) to the next state.”
I don’t understand this. The FSM defines a current state and a transition table to the next state given data. I’m not sure why you are saying you need lookback.
To answer this, “How would you know if you can move to the next state in the FSA?”: you need to map the current record onto an input type, look that up in the transition table of the current state, and enter the indicated state. In a language grammar, that would mean mapping a sequence of characters onto a token type (e.g. “that was a string” or “that was an integer”). In a regular expression, that means looking up the character directly in the table of state transitions (given the current state).
Shahar Y
Said on June 26, 2008 :
Hi Hugh,
“you need to map the current record onto an input type, look that up in the transition table of the current state”. Lets assume that the input type is string – how would you look up in the transition table of the current state? You have to compare the current record with the values in the transition table.
I wrote that as an answer to Alex, explaining why would you need to compare two records in the algorithm.
raj bhandari
Said on June 26, 2008 :
If I understand you correctly, you are just asking for a traversal algorithm to get to the second last node for an In-Order traversal? If so, here is my take on it:
start at root and set L2 = rootNode
WHILE L2->right != NULL
Do_Loop
L2 = L2->right
EndLoop
IF L2->Left != NULL
Return L2
ELSE
Return L2->parent
END
Hugh Brown
Said on June 27, 2008 :
I see. You’re thinking of a state transition table that is indexed by records, not integers, say. In that case, you would have to traverse down the accepting states, comparing the current record to that record to see which state to transition to next.
The FSMs I am most familiar with are ones generated by parser generators (YACC, etc.) and they are definitely indexed by integers. Operation there involves mapping a record to an integer (a NUMBER or a STRING or WHILE or COMMA or whatever terminals are in your grammar). I’ve never heard of an FSM indexed by a record but I’ll accept it’s possible.
Thanks for explaining.
sergio
Said on September 3, 2008 :
Node* find_before_last(Node* node) {
Node* currentSolution = NULL;
while (TRUE) {
if (node->right != NULL) {
currentSolution = node;
node = node->right;
} else if (node->left != NULL) {
currentSolution = node->left;
node = node->left;
} else {
break;
}
}
return currentSolution;
}