willberman

I haven't come to a personal conclusion on how I feel about the morals of it all, but you have to marvel at the feat of engineering.

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 ;
         }

I just tried, and I can only use my adblocker to block the element that requests I login. My scrolling is still stopped, and I can't see anymore of a user's photos. Am I missing something?

Instagram only allows you to see a portion of a user's photos before forcing you to login. It does this on both mobile and browser.

I'm not a big application design junkey, but it's behavior like this that makes me appreciate the simplicity of hacker news. A few standard concepts implemented in their most basic form. No changes in the name of more user engagement.

I understand that Reddit and Instagram's primary motive is to make money, but these sorts of "features" remove me from their pool of potential customers.

I'd like to see a move towards a purely data based web where I get to choose how the data is displayed. I know a semantic web paired with a standard set of user interface components chosen by the user wouldn't be as profitable as the current internet, but I would prefer it.

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.

FWIW. This is an absolutely awful coding challenge for an interview especially in a 2-hour setting. The challenge requires building off of implementation details for a few very specific technologies. Interviews are supposed to test for general problem solving capabilities within some domain of competence. Unless the job was specifically to work on a go language server, and that was your aforementioned domain of competence, I see no rationale for using this programming challenge to determine employment.

Because it looks like Lex is reading comments here, I would suggest that an adequate compromise for going into more technical detail on podcasts might be to link to external resources and cover them in a more high level on the actual podcast itself. It’s my general belief (admittedly experience based) that rigor is best developed in isolation; however, the podcast format is great for developing a high level intuition.

Keep up the good work lex. The quantity of content you put out at the level of quality you do is very impressive.

About a year ago, a similar sentiment hit me very hard. I was in a situation where I had actually checked all the boxes I wanted to check. My boxes didn’t involve working at FAANG, but they weren’t insignificant. I was very confused why I wasn’t happy.

There’s a very good short story by Alastair Reynolds called Understanding Space and Time. The protagonist is the last human alive. He finds his purpose in understanding the universe. Even once he completes this goal, he must go on living his life.

It may sound trite, but I tell people to put themselves in that position. What would you spend your time doing if you were the last human alive? Now obviously you don’t do that verbatim, but I think it should be an influential datapoint on your choice of career path.

The best news is that if you’re a half decent technical mind with a half decent network, the odds of you ever starving are quite low (not including dependents. That’s a different story). As a result, you have ample opportunity to carve out whatever corner of the universe you want for yourself :)

I generally like a lot of what Thiel says, but people need to be very careful about being heretical for the sake of being heretical. I find a lot of people (myself included) have a tendency to pretend some mainstream way of doing something is wrong for the sake of having some insight that everyone else missed. However, there is generally, at a minimum, some wisdom of the crowds.