I see peoples' opinions here generally falling into one of two camps. The standard way interviews are conducted are either good or bad. I think it's important to consider both the good and bad elements, and then come to a conclusion about what to do in order to move the collective interview process in a better direction. To note, I've never gone through a traditional technical interview, so take what I'm saying with a grain of salt. Let's look at the example in the given in the blog post, write an algorithm to find the Kth highest value in a binary tree. Now my data structures and algorithms are a bit rusty, so assuming that I remember the correct definition for node height, I believe the solution looks something like the following.
data Tree a = Tree a (Maybe (Tree a)) (Maybe (Tree a)) deriving Show
-- Assuming k=1 Means the highest node, k=2 means second, etc...
-- Note this solution successfully puns non-positive k's
-- to return Nothing
kHighest :: Int -> Tree a -> Maybe a
kHighest 1 (Tree a _ _) = Just a
kHighest k (Tree _ (Just l) (Just r)) =
case (lRes, rRes) of
(Just x, _) -> Just x
(_, Just x) -> Just x
(_, _) -> Nothing
where
lRes = kHighest (k - 1) l
rRes = kHighest (k - 1) r
kHighest k (Tree _ (Just l) _) = kHighest (k - 1) l
kHighest k (Tree _ _ (Just r)) = kHighest (k - 1) r
kHighest _ (Tree _ _ _) = Nothing
Barring some fundamental misunderstanding of the problem (entirely possible), the evaluation criteria is not that the solution is exactly correct and covers all edge cases. The evaluation criteria is does the solution show fundamental knowledge about properties that are used to classify things as tree-like, and does it use the common idiom (decomposition into smaller sub-problems) that is used to process tree-like data.
In my opinion, the common criticism that interview questions hold no similarity to day-to-day software engineering problems, holds no water. Yes, you will not directly re-write the tree data type every day in your job. However, you deal with recursive data definitions that require solution by decomposition _multiple_ times a day. If you are not dealing with problems that fall under that category, then you should think hard about which problems you see that could be framed as such because I guarantee you're missing a few.
The beauty of the tree as a data structure is that it captures a common set of algebraic properties. Even when other data structures don't exactly fall under said algebra, the concepts to reason about them are reused (note the early language that specifically said "tree-like").
The point of drawing interview questions from your data structures and algorithms course is not to test you on remembering arcane minutia from 5+ years ago but to see your fundamental reasoning skills within the domain of computer science.
I might be mistaken (and I'm no Haskell expert) but I believe your solution is based on a misunderstanding of the problem.
> Find the Kth highest value in a binary search tree
Your code seems to return _any_ node that is at level K. Where K is 1 for the root node, 2 for its children, 3 for its grandchildren, etc.
But unless I'm mistaken, by the wording of the problem, it's looking for the concretely K highest value, in sorted order. Not "highest in the tree". So if a binary search tree has values (1, 3, 5, 8, 13) the algorithm is supposed to return 8 when K=2, _regardless_ of how the nodes are structured. (E.g. Even if it's unbalanced and 8 is the root node.) Because 8 is the 2nd highest value contained by the tree.
Sounds like a harder puzzle than your interpretation...
I love posting things to the internet that end up being wrong :).
I think this is an interesting look at ambiguity in wording for computer science terminology. In my mind, height or highest always means node height. The term largest should be reserved for numerical measurement. See the next paragraph for a good example.
Correct me if I'm wrong, but the k highest interpretation with an unsorted tree sounds like a simpler problem. If the tree is unsorted, you must traverse the entire tree, sort the result, and then you have your answer. The more challenging problem sounds to me to be what happens when the tree is already sorted. Interestingly, I think the solution for this problem makes my point better than the original problem. Look at how buildHeights breaks the sub problems down. The height (size) of a value in a node at a given level (height) is a function of the heights (sizes) of sub-trees. I included a main method, so you can run the code and not mentally parse it :). What's interesting to me is the commonality in structure between the two solutions despite the problems asking for radically different things.
Note, I probably could not have come up with this solution in the amount of time allotted in an interview because it took a while to find a solution that properly showed problem decomposition.
import qualified Data.Map as Map
data Tree a = Tree a (Maybe (Tree a)) (Maybe (Tree a)) deriving Show
buildHeights :: Tree a -> Map.Map Int a
buildHeights (Tree a Nothing Nothing) = Map.singleton 1 a
buildHeights (Tree a (Just l) Nothing) =
Map.insert 1 a lRes
where
lRes = Map.mapKeys (+1) (buildHeights l)
buildHeights (Tree a (Just l) (Just r)) =
Map.unions [rRes, lRes, curRes]
where
rRes = (buildHeights r)
maxRight = maximum $ Map.keys rRes
lRes = Map.mapKeys (+ (1 + maxRight)) (buildHeights l)
curRes = Map.singleton (1 + maxRight) a
kHighest :: Int -> Tree a -> Maybe a
kHighest k t = (buildHeights t) Map.!? k
main = do
let tree = (Tree 4
(Just (Tree 2
(Just (Tree 1 Nothing Nothing))
(Just (Tree 3 Nothing Nothing))))
(Just (Tree 6
(Just (Tree 5 Nothing Nothing))
(Just (Tree 7 Nothing Nothing)))))
in do {
putStrLn $ show $ kHighest 1 tree ;
putStrLn $ show $ kHighest 2 tree ;
putStrLn $ show $ kHighest 3 tree ;
putStrLn $ show $ kHighest 4 tree ;
putStrLn $ show $ kHighest 5 tree ;
putStrLn $ show $ kHighest 6 tree ;
putStrLn $ show $ kHighest 7 tree ;
putStrLn $ show $ kHighest 8 tree ;
}
In my opinion, the common criticism that interview questions hold no similarity to day-to-day software engineering problems, holds no water. Yes, you will not directly re-write the tree data type every day in your job. However, you deal with recursive data definitions that require solution by decomposition _multiple_ times a day. If you are not dealing with problems that fall under that category, then you should think hard about which problems you see that could be framed as such because I guarantee you're missing a few.
The beauty of the tree as a data structure is that it captures a common set of algebraic properties. Even when other data structures don't exactly fall under said algebra, the concepts to reason about them are reused (note the early language that specifically said "tree-like").
The point of drawing interview questions from your data structures and algorithms course is not to test you on remembering arcane minutia from 5+ years ago but to see your fundamental reasoning skills within the domain of computer science.