Hacker News Reader

Comment by sethammons | Hacker News Reader

Decent examples. I'd like to toss another in that, years ago, a colleague gave a candidate. He thought of the question that morning in the shower.

Morse Code. All letters are combinations of one or more dashes and/or dots. Here is a sentence of Morse Code where the spaces are stripped. Decode it to get the original ASCII sentence.

He gave it and failed the candidate. Sounding like an interesting problem, some of us in the office tried it. Turns out that it is a very hard problem. You have to make a tree of possibilities and it is easy to accidentally make your solution O(n!).

Moral of the story is never give out a coding question that have not personally solved. Second moral: be open to out of the box solutions.

View on HN

I think that these kinds of interview quizzes are a generally terrible practice. I prefer to bring people in and have them pair with people on real things, that are really happening, that are entirely representative of the real work and the real team dynamics. All parties involved get a much, much better SNR out of arrangements like that. A bunch of contrived nonsense representative of nothing used as a measuring stick for hiring has always seemed nonsensical to me.

In any case, if one were resolute to pursue a practice like this, such as your colleague, then what they should have done is pick a problem they definitely don't know the answer to and then sit down and work it out actively in cooperation with the candidate. That would have been about a thousand times more useful as an interviewing activity.

Knowing the answer ahead of time makes the dynamic worse. Things will seem obvious that aren't when you already know the answer. It sounds like your colleague made things a degree worse by both not knowing the answer, but assuming that they did somehow intuitively.

> I prefer to bring people in and have them pair with people on real things, that are really happening, that are entirely representative of the real work and the real team dynamics.

That should be the most important test, but most of the daily realistic work is really a matter of practice. By testing it you really test how much practice with that particular toolchain and workflow the person had, not how smart or good programmer they are. Brainteasers are unrealistic and relying just on them is stupid, but they give you some insight in how good in quick thinking someone really is. If I was looking for a newbie to train, I'd always prefer someone who can't finish the real world test, but knows how to think technically, to the opposite.

Even if they don't know the tools or languages, which in our case they're almost certainly not going to (Rust, Agda, TLA+, etc.), you get to see how they interact with a situation where they need to be able to direct some of their own learning by seeing if they ask questions, if they can synthesize insights despite lack of deep familiarity, how they react to having naivety exposed, etc.

Most of the challenging work is collaborative problem solving, not exam proctoring, and it's important to see how a person interacts with that. You'll see how much direction they're likely to need, if they can navigate and contribute positively to team dynamics, and so on.

You don't happen to be working on cryptocurrencies do you? I'm surprised to hear of Agda being used in production.

We don't work on cryptocurrencies. Right now we work on automated testing & verification tools for "cyber-physical systems". Our target markets & customers often have safety-critical considerations.

We use Agda to create proofs for some of the components of our platform.

The only time I enjoyed these questions was when the interviewer didn’t know the answer either and we were just trying to solve it together.

The times I absolutely detest are when the interviewer writes down the problem and sits back for 30 minutes.

protip from someone in the trenches: until you have given the problem to many people in interviews and evaluated their responses to calibrate your judgement, problems like these serve only one purpose in an interview that is satisfying interviewers ego about how smart he is.

Completely agreed. Questions need to be calibrated. I start with a task that I can do in N minutes and give the candidate 3N minutes.

I've proposed (and been rejected) where I work that we have both high and underperformers go through mock interviews for their roles, to see if our interview questions could distinguish who was who.

I understand that this is going to be awkward, especially for the low performers, but at the moment I don't think our interview practices are based on anything. We ask questions and then later have a conversation about how and whether or not our questions revealed the presence of the attributes we were supposed to be assessing for and it feels very made up and make believe. Plus, people could be given incentives for going through the process and bonuses for passing the mock interviews to encourage them to try

If we could get people where we already knew how good or bad they were to rerun the interview process then we could start to figure out which questions and which evaluation methods were useful in separating good candidates from poor ones.

just make everyone in the company do it IMO, and let the managers distinguish who was an over/underperformer later on

Of course, you'll just find out that there's practically no correlation.. Some of the least useful teammates I ever had ended up at Google, and one of the best programmers I've ever met makes $10/hour at a fucking call center out in the middle of nowhere

It's not good enough to test only the people who have already passed a similar test. It's easy to get a nonsense negative correlation, like more experienced people performing worse in their job, because the people with less experience that nonetheless got hired must have had some other factor that made up for it. That can result in a negative correlation in the already-hired pool even if there's a positive correlation in the potential-hire pool.

This is the same problem you see with people claiming that GPA or GRE scores have no or negative correlation with academic success.

I've come up with a few interview questions, and reviewed a few more. In my experience there's a ~decent rule of thumb for gauging difficulty and time required to solve a given problem.

A person in your company, after having read the problem and glancing at the rough description figures out a clean solution in time X. That's without the interview stress, knowledge of the problem domain, with the pacing of the problem laid out in writing. A well-performing candidate coming in cold, stressed from the interview setup and under time pressure will take 3X time to solve it.

So if it takes much more than 10 minutes for someone at your company solve your proposed interview question reasonably well, it's almost certainly too difficult.

I wrote a solution to this some time back: https://github.com/paulhankin/morse-decoder . It finds the most likely sentence based on n-gram frequencies and a dictionary, and runs a relatively fast dynamic program (it's been a while since I looked at the code, but I think linear if word lengths are bounded). Word list and n-gram frequencies aren't provided in the repo, although they're easy to find online.

This one's easy. Insert spaces between every blip and you've got a sequence of E and T. This should demonstrate to the proctor that the problem is ill-posed. Now the proctor is under examination: if they admit that the problem is garbage, they pass and you should stick out the interview. Otherwise, just walk away.

A sibling comment discussed most probable message; on further reflection, I suspect there's a dynamic programming algorithm for the shortest possible message... this problem could have some nifty angles to explore if done right. But only if you know that you're testing on how people work in the face of ambiguity!

> A sibling comment discussed most probable message

Good luck finding that! Condensed morse code can be _bananas_. https://en.wikipedia.org/wiki/Telegram_style

O(n!) is wrong. For an string of length n, there are n-1 gaps in it, and each gap could or could not hold a space, which gives you 2^(n-1) possibilities. The algorithm is at worst basically O(n*2^n). Exponential for sure, but not factorial.

As for solving it, back-tracking recursive descent does the job, though obviously there's not always a single correct answer.

This is not really a "trick question", this is just a regular programming challenge :)

Solve it and let me know :).

On the surface it feels relatively easy. Until you realize you can't tell one letter from another.

Is it "D" or is it "T" followed by the start of the next letter? "D" is equal to "TEE". But it could be "NE" also. One letter in and we are exploding. This is not counting nonsensical combinations like this being the start of "NL", but if that is a word boundary, then maybe it is ok.

Yeah, ok, though I'm not sure what that will prove. As I said, it's really just a case of writing a backtracking recursive thing. Here it is in prolog:

    letter(a, X) :- string_to_list("._", X).
    letter(b, X) :- string_to_list("_...", X).
    /* rest ommitted for brevity */
    letter(z, X) :- string_to_list("__..", X).

    morse([], []).
    morse(Morse, [Letter|Rest]) :-
        letter(Letter, Head),
        append(Head, Tail, Morse),
        morse(Tail, Rest).

Prolog is obviously excellent for this kind of thing since the backtracking comes built in, but it's not massively more complicated in other languages.

For "_.._", it gives you the following answers (I added some line-breaks):

    ?- string_to_list("_.._", L), 
       findall(English, morse(L, English), Answers).
    L = [95, 46, 46, 95],
    Answers = [[d, t],
         [n, a],
         [n, e, t],
         [t, e, a],
         [t, e, e, t],
         [t, i, t],
         [t, u],
         [x]].

I wasn't saying that it's not a good little problem. It's a lovely little problem, which you solve with recursive back-tracking! I wouldn't say it's a "trick question" though, it's just a regular programming challenge.

EDIT: Oh, I see what you're saying, do you mean "It's a trick question because there isn't necessarily just one answer"?

If so, then I misunderstood, I figured the challenge was "find all valid interpretations" of a certain morse code string. The fact that there could be more than one seemed fairly obvious to me.

"obviously" you should do this and the rank results under a language model (mainly joking)

edit: oooh and use beam search to limit the output size/time

My gut feeling is that you can solve this with dynamic programming faster than this.

There will be lots of ways to split any given prefix into letters. But all of them leave the same suffix. You don't need to repeat the analysis of the suffix.

You could avoid repeating the analysis by memoising the result. But when you're memoising results from leaves of a search tree, that's a hint that you're close to a dynamic programming approach.

It depends a little bit on what the acceptable answer is. If it's "stream/generate a list of possible strings", then the length of that list is probably O(2^n), so the fact that my recursive descent thing is exponential doesn't actually matter that much asymptotically. If you memoized it, the memo structure caching the suffixes would become massive and you'd spend just almost as much time looping the results from it as you would just walking down the tree, so you might as well save yourself the memory and just walk down the tree. Like, the length of the cached answer is more or less the same as the runtime of just doing the recursion, so you're not actually saving much of anything by memoization, and you're wasting a whole lot of memory.

I guess you could instead return some kind of fancy "prefix DAG" containing all possible strings, and that would be faster. But then you're just making the caller walk that tree instead of you doing it yourself, so you're really just shuffling the runtime around, not really saving much.

However, if the answer is "count the solutions", then yeah, memoizing would speed it up MASSIVELY. That's a good little Project Euler style problem, actually (though not a terribly tricky one), because you could make the input large enough that naive recursive descent wouldn't work. I haven't quite thought through what going full-on DP and turning the recursion upside down would do, but I assume it would work just fine.

But given that the number of possible solutions is a massive O(2^n) (probably, anyway), that puts a floor on the runtime you can't algorithm your way out of. Might as well go with the cheap recursive descent. I think, anyway :)

No if you're just counting you can definitely do it faster than 2^n time. I believe you can do it in linear.

That looks like an O(fuckit!) problem.

I've literally called such problems I've received in interviews O(shitty) or O(don't do that).

Unfortunately you have failed this regular programming challenge.

I hope you guys gave the candidate another shot. And maybe an apology.

Too late. It's an interesting problem, he'll have talked about it with his colleagues and they'll have come to the same conclusions, it's a tough nut. They will conclude correctly that the company is full of arrogant assholes that have no idea what they are talking about.

Exactly, an apology! It almost sounds like the goal was to find something that a candidate doesn't know. How about finding the things the candidate knows and basing the further discussion on top of that.

All this obsession with coding tricks in the interviews is just awful.

A lot of the dev interview process relies on luck. Sometimes you just get a crappy interviewer (inexperienced, naive, or just malicious), and things won’t go well regardless of your own abilities.

In fact, beyond a certain level of competence, interview results are mostly about luck. Sometimes you get a nice set of interviews, sometimes you don’t. Some companies will at least not reject you out of hand for one bad interview slot, but most companies are just so overwhelmed with unreliable signal that they’ll tank you for any kind of hint at incompetence.

It’s a pretty wild situation.

I’ve been given offers from Google, been rejected by random web shops, and everything in between, all within the same year.

The Dunning-Kruger effect is put on steroids during tech interviews.

There’s this pretense that the interviewer is smarter than the interviewee, and an expectation that the interviewee will abide by that pretense as a show of respect.

That pretense leads interviewers to being unnecessarily ambiguous, and especially leads them to asking overly complicated questions. If you’re an insecure engineer, this allows you to impress your coworkers in the meeting afterward with your complicated question. You can act as if it would have been easy for you, the other engineers in the room won’t disagree because they want people to think they’re smart too, and one thing will be made very clear to everyone: You are smarter than the candidate, and the company is very lucky to have you.

It also leads interviewees to fake equivocating and feigning ignorance, and is overall a strong recipe for unconscious or deliberate bias based on the personal and professional insecurities of both parties.

From the other side of the table, when you’re the one interviewing candidates, you spend an absolute minimum of 90% of your time screening and interviewing people who are so bad that it literally hurts on an emotional level to interact with them. You develop compassion fatigue, like a nurse in an ER, and it’s very easy to find yourself in a place where you assume the worst of every candidate and don’t even care anymore if they fail.

The results of these interviews are influenced far more heavily by the interviewers than by the person being interviewed, in my opinion. And most companies (nearly all in fact) have literally no mechanism by which they grade the quality or subjectivity of their interviewers.

This sounds about right. At some level, LeetCode can filter out the completely inept bottom fairly quickly, but then it becomes really useless, it is really not much better than fizbuzz in that regard.

I think the problem is inherently pretty difficult. Also extremely ambiguous. Here's a solution I put together in Haskell:

    encode :: Char -> [Bool]
    encode 'a' = [False, True]       
    ...
    encode 'z' = [True , True , False, False]
    
    data Trie a
      = Trie
      { payload :: Maybe a
      , false   :: Trie a
      , true    :: Trie a
      }
      
    insert :: [Bool] -> a -> Trie a -> Trie a
    insert xs v = foldr f b xs
      where
        b t = t {payload = Just v}
        f False k (Trie e f t) = Trie e (k f) t
        f True  k (Trie e f t) = Trie e f (k t)
        
    table :: Trie Char
    table = foldr (uncurry insert) (fix (\t -> Trie Nothing t t)) [ (encode c, c) | c <- ['a'..'z'] ]
        
    newtype Parser a b = Parser { runParser :: [a] -> [(b, [a])] } deriving Functor
    
    instance Applicative (Parser a) where
      pure x = Parser (\xs -> [(x,xs)])
      (<*>) = ap
      
    instance Monad (Parser a) where
      xs >>= f = Parser \s -> do
        (x,s') <- runParser xs s
        runParser (f x) s'
      
    instance Alternative (Parser a) where
      empty = Parser (const [])
      xs <|> ys = Parser (\s -> runParser xs s ++ runParser ys s)
      
    instance MonadPlus (Parser a) where
      
    eoi = Parser \case
      [] -> [((),[])]
      _ -> []
      
    char = Parser \case 
      (x:xs) -> [(x,xs)]
      [] -> []
    
    morse :: Parser Bool String
    morse = go table
      where
        go t = (go . bool (false t) (true  t) =<< char)
           <|> msum (fmap (\x -> fmap (x:) (go table <|> [] <$ eoi)) (payload t))
    
    decode :: [Bool] -> [String]
    decode =  map fst . runParser morse

The output is pretty much unusable, though. For the string "me", for instance, there are 4 possible parses:

    ["g","me","tn","tte"]

For the string "hello", there are 19796.

I solved this two weeks ago as a joke:

https://twitter.com/nomsolence/status/1228577284929421312

I think it's O(n!)?

Did your colleague think that Morse code is a prefix code? Or did he simply not think at all about what exactly he was asking?

I know its not the point but think the right answer is to ask questions to better understand the use case. what language is being used?, what is the nature of the message?, who is sending it? Is there a format? do we have a log of manually decoded messages?

I could see not hiring someone if they didnt try to ask stuff like that.

As a way to weed out people who just fill requirements without questioning if the requirement actually solves the problem.

Here is a small memoized recursive solution in Python [1]. It's pretty quick.

[1] https://gist.github.com/pavelb/1d62e81b35d18fc1441ea59361b54...

Is it safe to assume, although this happened years ago, that your employer was not Western Union?

Are you saying that he did not have an intended solution to the problem?

While a global solution is NP complete since Morse code is not prefix free, there's probably a decent heuristic approach that maximizes matching of existing english words.

If, in addition to the Morse Code associations with letters, you have a dictionary of permitted words, this becomes a fairly straightforward DP, does it not?

Not if you want the result to be syntactically correct English and semantically meaningful.

My fav part is "he gave it and failed the candidate". Where do you work? Is it at a college? Is it this college https://youtu.be/tSKEl6a-b_c

Please don't cross into personal attack in HN comments.

https://news.ycombinator.com/newsguidelines.html

I replied on a whim from bed and cannot delete it now.

No worries, it happens. Especially when the intention was jovial but the literal comment doesn't transmit that.

Also, it was only a tiny bit over the line.

I think this is a great problem to give someone, but the output you measure is the approach they take to it - are they methodical, logical, insightful, etc - not whether they solve it. Evaluating someone on the latter is indeed deeply incompetent.

I totally agree with you it's just the story that is funny.

He gave it and failed the candidate.

After which the CEO personally and profusely apologized to the candidate. And offered a hefty per-diem consulting fee in compensation for this cynical (if not outright juvenile) waste of their precious, irreplaceable time.

Right?

I don't see why the CEO needs to be involved. Why not have the recruiter apologize to the candidate and offer another interview?

Candidates know that there is always a chance they will be rejected for reasons outside their control (e.g. there was only 1 opening and a better candidate applied), so if the candidate agreed to the interview without a consulting fee, I don't think it's necessary to give one.

Why not have the recruiter apologize to the candidate and offer another interview?

When it's a minor screw-up -- sure, have the recruiter apologize.

When it's a major fuck-up of this scale -- reflective of both arrogance and incompetence on the company's side -- then the CEO needs to apologize.

It's really quite simple actually.

In my view the CEO is for major business decisions and company direction. I don't see a single interview with a too-hard question being that. Any large company will be conducting hundreds of interviews with too-hard questions every day. I've seen many blog posts about them on HN.

I see it as mostly ignorance on the part of a single interviewer. Every large company has lots of ignorance. People aren't perfect.

I don't see a single interview with a too-hard question being that.

It wasn't a matter of a "too-hard" question.

But of a recklessly and arrogantly posed question.

The arrogance here seems to be from misjudging the difficulty of the question. That is, it seems largely rooted in ignorance.

As for reckless, there's a wide variety of how much time people will spend preparing a question before an interview. Some people will spend days preparing a question. Others will just pick something off a list and ask it. I don't think everyone would agree that just thinking of a question is reckless. We also don't know how much time sethammons's coworker was given to prepare. Maybe he was told about the interview Monday evening, and had to conduct it Tuesday morning.

The arrogance here seems to be from misjudging the difficulty of the question.

I see it as coming from a mindset that says it's OK to pull some "nifty" problem out of his head at the last minute -- in this case, literally between lathering his toe jam and rinsing his buttcrack -- and feed it to candidates without having it properly vetted first.

Or even, for that matter, sitting down and thinking about it for a couple of seconds. To me at least -- right off the bat, the core assumption they made about this problem was highly suspect, just from the fundamentals.

In short - they didn't just make a mistake; they were throwing caution to the wind. On the basis of an apparent view that candidates are a dime a bushel, and their time is more or less infinitely expendable.

That is - the mindset that so many companies following the current penchant for on-the-spot technical interviewing seem deeply beholden to.

Is the answer even well-defined? Seems like without spaces, there could be strings that decode to multiple possible (possibly nonsense) “sentences.”

In particular, E is . and T is -, so you can trivially decode any sequence of dots and dashes to strings containing only E and T.

Surely "decoding" means returning the text that was encoded. You can't trivially decode it, you can provide a candidate solution, that's entirely different; the point of sharing this was it's not possible to decode because there's no unique solution.

    ...---...

you can guess it's EEETTTEEE, but the decoding is SOS, that was the plaintext I started with.

Yes, and even a simple string like "...---..." has 200 possible solutions, including "VTTIE", "3NI", and "SMB". Especially for longer inputs, there's no way to guess which one is right.

SOS is an interesting case, because it is a Morse "prosign", which means it is sent as one continuous stream of dits and dahs without any pauses between the letters we use to represent it.

In other words, SOS is sent exactly the way you wrote it, as if it were one long character:

  ...---...

It is not sent as three separate letters like this:

  ...  ---  ...

To indicate this special treatment, prosigns are normally typeset with a bar over the connected letters, something like this:

  ___
  SOS

(I used underscores above the letters here; if they render as separate underscores, imagine that they all run together.)

Exactly. Hence the moral of don't give a problem you have not solved yourself. Similar to the reverse a Unicode string from the article.

No, Morse Code is not a prefix code.

Telegraph operators could do this in their heads in realtime!

They inserted spaces though, between characters and words. In this problem, all spaces are removed.

We also have to do that to decode speech. You can simulate the way people do it with a hidden Markov model.

“Prefix code” is sufficient for the problem to be well-defined, but I don’t think it is necessary.

For a trivial counterexample, consider an alphabet of

   .-
   ..-
   ...-

(And yes, it isn’t uniquely solvable in the case or Morse code, as shown by the counter example A = ET)

That's a prefix code, they're defined by no code word being a prefix of another (so if you put them in a trie the code words only appear on leaves).

A trivial example is the reverse:

  _.
  _..
  _...

Which can be decoded by, at worst, reversing the string first.

(Sorry if I've misunderstood your example)

No, you didn’t.

This looks like the Post Correspondence Problem at first glance: https://en.m.wikipedia.org/wiki/Post_correspondence_problem.

It’s similar, but in this case the decision is removed as it is given that a solution exists.

Reply on news.ycombinator.com