We pay for user submitted tutorials and articles that we publish. Anyone can send in a contributionLearn More
That’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.
Tags :challengeIn OrderInterviewJobjob interviewNodequestionSortTraverseTree
Copyright © 2012 Dev102.com
Breeze : Designed by Amit Raz and Nitzan Kupererd