7 ms·

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.

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.

egdod 7y ago
Is the answer even well-defined? Seems like without spaces, there could be strings that decode to multiple possible (possibly nonsense) “sentences.”
- hnkain 7y ago
  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.
  - pbhjpbhj 7y ago
    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.
    - rdlw 7y ago
      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.
    - Stratoscope 7y ago
      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.)
      - deleted 7y ago
        [deleted]
- sethammons 7y ago
  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.
- saagarjha 7y ago
  No, Morse Code is not a prefix code.
  - joezydeco 7y ago
    Telegraph operators could do this in their heads in realtime!
    - dblotsky 7y ago
      They inserted spaces though, between characters and words. In this problem, all spaces are removed.
    - ben509 7y ago
      We also have to do that to decode speech. You can simulate the way people do it with a hidden Markov model.
  - Someone 7y ago
    “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)
    - hcs 7y ago
      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)
      - Someone 7y ago
        No, you didn’t.
OskarS 7y ago
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 :)
- sethammons 7y ago
  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.
  - OskarS 7y ago
    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.
hnkain 7y ago
I wrote a solution to this some time back: https://github.com/paulhankin/morse-decoder 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.
deleted 7y ago
[deleted]
amptorn 7y ago
Are you saying that he did not have an intended solution to the problem?
Sharlin 7y ago
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?
jgwil2 7y ago
I hope you guys gave the candidate another shot. And maybe an apology.
- HarryHirsch 7y ago
  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.
- insulanian 7y ago
  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.
- seanmcdirmid 7y ago
  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.
  - Non24Throw 7y ago
    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.
dblotsky 7y ago
This looks like the Post Correspondence Problem at first glance: https://en.m.wikipedia.org/wiki/Post_correspondence_problem https://en.m.wikipedia.org/wiki/Post_correspondence_problem.
- saagarjha 7y ago
  It’s similar, but in this case the decision is removed as it is given that a solution exists.
klyrs 7y ago
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.
- klyrs 7y ago
  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!
  - hwayne 7y ago
    > A sibling comment discussed most probable message Good luck finding that! Condensed morse code can be _bananas_. https://en.wikipedia.org/wiki/Telegram_style https://en.wikipedia.org/wiki/Telegram_style
kohtatsu 7y ago
I solved this two weeks ago as a joke: https://twitter.com/nomsolence/status/1228577284929421312 https://twitter.com/nomsolence/status/1228577284929421312 I think it's O(n!)?
emsal 7y ago
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?
- pmiller2 7y ago
  Not if you want the result to be syntactically correct English and semantically meaningful.
petermcneeley 7y ago
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 https://youtu.be/tSKEl6a-b_c
- dang 7y ago
  Please don't cross into personal attack in HN comments. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
  - petermcneeley 7y ago
    I replied on a whim from bed and cannot delete it now.
    - dang 7y ago
      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.
- twic 7y ago
  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.
  - petermcneeley 7y ago
    I totally agree with you it's just the story that is funny.
vanusa 7y ago
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?
- Thorrez 7y ago
  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.
  - vanusa 7y ago
    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.
    - Thorrez 7y ago
      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.
      - vanusa 7y ago
        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.
deleted 7y ago
[deleted]
DesiLurker 7y ago
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.
- sethammons 7y ago
  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.
- ALittleLight 7y ago
  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.
  - VRay 7y ago
    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
  - evanpw 7y ago
    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.
itronitron 7y ago
Is it safe to assume, although this happened years ago, that your employer was not Western Union?
im_down_w_otp 7y ago
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.
- ivanhoe 7y ago
  > 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.
  - im_down_w_otp 7y ago
    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.
dec0dedab0de 7y ago
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.
yters 7y ago
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.
oisdk 7y ago
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.
twiceaday 7y ago
Here is a small memoized recursive solution in Python [1]. It's pretty quick. [1] https://gist.github.com/pavelb/1d62e81b35d18fc1441ea59361b54d7f https://gist.github.com/pavelb/1d62e81b35d18fc1441ea59361b54...

egdod 7y ago

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

hnkain 7y ago
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.
- pbhjpbhj 7y ago
  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.
  - rdlw 7y ago
    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.
  - Stratoscope 7y ago
    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.)
    - deleted 7y ago
      [deleted]
sethammons 7y ago
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.
saagarjha 7y ago
No, Morse Code is not a prefix code.
- joezydeco 7y ago
  Telegraph operators could do this in their heads in realtime!
  - dblotsky 7y ago
    They inserted spaces though, between characters and words. In this problem, all spaces are removed.
  - ben509 7y ago
    We also have to do that to decode speech. You can simulate the way people do it with a hidden Markov model.
- Someone 7y ago
  “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)
  - hcs 7y ago
    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)
    - Someone 7y ago
      No, you didn’t.

OskarS 7y ago

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 :)

sethammons 7y ago
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.
- OskarS 7y ago
  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.

hnkain 7y ago

I wrote a solution to this some time back: https://github.com/paulhankin/morse-decoder 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.

deleted 7y ago

[deleted]

amptorn 7y ago

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

Sharlin 7y ago

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?

jgwil2 7y ago

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

HarryHirsch 7y ago
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.
insulanian 7y ago
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.
seanmcdirmid 7y ago
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.
- Non24Throw 7y ago
  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.

dblotsky 7y ago

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

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

klyrs 7y ago

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.

klyrs 7y ago
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!
- hwayne 7y ago
  > A sibling comment discussed most probable message Good luck finding that! Condensed morse code can be _bananas_. https://en.wikipedia.org/wiki/Telegram_style https://en.wikipedia.org/wiki/Telegram_style

kohtatsu 7y ago

I solved this two weeks ago as a joke: https://twitter.com/nomsolence/status/1228577284929421312 https://twitter.com/nomsolence/status/1228577284929421312 I think it's O(n!)?

emsal 7y ago

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?

pmiller2 7y ago
Not if you want the result to be syntactically correct English and semantically meaningful.

petermcneeley 7y ago

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 https://youtu.be/tSKEl6a-b_c

dang 7y ago
Please don't cross into personal attack in HN comments. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- petermcneeley 7y ago
  I replied on a whim from bed and cannot delete it now.
  - dang 7y ago
    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.
twic 7y ago
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.
- petermcneeley 7y ago
  I totally agree with you it's just the story that is funny.

vanusa 7y ago

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?

Thorrez 7y ago
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.
- vanusa 7y ago
  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.
  - Thorrez 7y ago
    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.
    - vanusa 7y ago
      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.

deleted 7y ago

[deleted]

DesiLurker 7y ago

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.

sethammons 7y ago
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.
ALittleLight 7y ago
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.
- VRay 7y ago
  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
- evanpw 7y ago
  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.

itronitron 7y ago

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

im_down_w_otp 7y ago

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.

ivanhoe 7y ago
> 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.
- im_down_w_otp 7y ago
  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.

dec0dedab0de 7y ago

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.

yters 7y ago

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.

oisdk 7y ago

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.

twiceaday 7y ago

Here is a small memoized recursive solution in Python [1]. It's pretty quick. [1] https://gist.github.com/pavelb/1d62e81b35d18fc1441ea59361b54d7f https://gist.github.com/pavelb/1d62e81b35d18fc1441ea59361b54...