Programming trick questions
qntm.org
qntm.org
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.
...---...
In other words, SOS is sent exactly the way you wrote it, as if it were one long character:
...---...
... --- ...
___
SOS
For a trivial counterexample, consider an alphabet of
.-
..-
...-
A trivial example is the reverse:
_.
_..
_...
(Sorry if I've misunderstood your example)
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 :)
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.
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).
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]].
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.
edit: oooh and use beam search to limit the output size/time
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.
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 :)
:)
All this obsession with coding tricks in the interviews is just awful.
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.
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.
Good luck finding that! Condensed morse code can be _bananas_. https://en.wikipedia.org/wiki/Telegram_style
https://twitter.com/nomsolence/status/1228577284929421312
I think it's O(n!)?
Also, it was only a tiny bit over the line.
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?
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.
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.
I see it as mostly ignorance on the part of a single interviewer. Every large company has lots of ignorance. People aren't perfect.
It wasn't a matter of a "too-hard" question.
But of a recklessly and arrogantly posed question.
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.
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.
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.
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
This is the same problem you see with people claiming that GPA or GRE scores have no or negative correlation with academic success.
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.
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.
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.
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.
We use Agda to create proofs for some of the components of our platform.
The times I absolutely detest are when the interviewer writes down the problem and sits back for 30 minutes.
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.
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
["g","me","tn","tte"]
[1] https://gist.github.com/pavelb/1d62e81b35d18fc1441ea59361b54...
What I care about when I do interviews is how they organize their code. I want to see what people’s instincts and habits are, because that’s what’s going to determine the quality of 99% of the code they write.
I’d rather have someone who can come up with objectively good abstractions instead of writing one giant, unintelligible block of code than someone who can come up with something very clever on the spot to a totally esoteric problem.
Will not reverse composed ligatures, e.g. ﷺ is synonymous to صَلَّىٰ ٱللَّٰهُ عَلَيْهِ وَسَلَّمَ, but صَلَّىٰ ٱللَّٰهُ عَلَيْهِ وَسَلَّمَ with a LTR directional override is صَلَّىٰ ٱللَّٰهُ عَلَيْهِ وَسَلَّمَ while ﷺ remains as ﷺ.
Will not reverse 겁 into 벅.
Is AAVE a separate “language” from “standard English”? How about Creole? Is that French, English, or a distinct language?
Is Pennsylvania Dutch/“Low German” German or English?
What about Yiddish? Modern Yiddish is an entirely different beast from historical Yiddish.
Who is going to be defining the type for Greek? What region and point in history will they be using for a reference?
Does GermanString contain Eszett? If so, is it a separate code point or interchangeable with “ss”? Is there logic that defines when “ss” should be represented as an Eszett and when it should be rendered as “ss”?
No, I think Unicode is the right approach. You get all the code points you might need and logic for processing them as glyphs. Leave everything else up to the application.
So you can actually separate them if you want pretty easily
The issue brought up by the article is that neither makes sense. Reversing a string is not a semantically meaningful operation.
I do agree with the overall point; just thought this specific example was a bit odd.
Does the string-reversing function receive "English" and output "hsilgnE" or "lishEng"? What if the string matches no known words (e.g. alphanumeric passphrase)? What if the string represents a single syllable (e.g. "was")?
Thinking of strings as connected to vocalized syllables only makes sense with strings meant to represent syllables, sure, but even that can lead to counterintuitive results.
I know you weren't defending the idea of a string-reversing function, but your objection is not exactly grounded in principle, either. That is, when you ask
> Why would reversing 겁 into 벅 make sense?
one could easily say, why wouldn't that literal reversal of the phoneme make sense? I understand it doesn't, but that's the problem with Unicode reversing-functions.
BTW, you can reverse Unicode (in any UTF), so long as you don't really care about the semantics of the result -- if all you want to do is reverse the codepoints, you could. After all, it is an interesting programming interview trick question, though admittedly then "you can't really" answer is more fun because you get to talk about glyphs and ligatures and so on, and natural language, thus demonstrating your mastery to the person who was trying to trick you.
But instead Unicode has formatting and control code points and that complicates everything?
Is that the gist of it or is there more?
"Reverse" is just too ambiguous when dealing with Unicode.
110
11100
111110000
1111111000000
1111111111111000000000000edit: Not to mention that all 5 numbers are even, so a parity check could also help for odd number inputs (but it makes it slower for even numbers). I do not think that AVX has anything to offer here though.
Edit: And yeah, you need a fast popcnt here.
2^(p - 1)(2^p - 1)
((1 << p) - 1) << (p - 1)
(There are no odd perfect numbers in the range under consideration.)
However, the reason I said AVX is because it can be used for checking equality of 5 (well, 8) numbers simultaneously. This solution requires AVX2 and is probably faster than the optimized reference code.
// Copy x to all 8 elements.
__m256i a = _mm256_set1_epi32(x);
// Duplicate 6 because we need to fill all 8 elements.
__m256i b = _mm256_set_epi32(6, 28, 496, 8128, 33550336, 6, 6, 6);
// Check for element-wise equality.
__m256i c = _mm256_cmpeq_epi32(a, b);
// Check if any bytes are nonzero.
return _mm256_movemask_epi8(c) != 0;
Interestingly the compiler doesn't do this optimization, even though it could. So maybe I'm wrong. No real way to know without benchmarking, though.
But this is still dumb! lol.
(Yes I realize it would just be an iota function in c++)
return (x & 0xFE0000001 == 0) &&
(x == 6 || x == 28 || x == 496 || x == 8128 || x == 33550336):
bool isPerfect(uint64_t x) {
int ctz = __builtin_ctzll(x);
return ((0x40051056 >> ctz) & 1) && ((x >> ctz) + 1) == (uint64_t(1) << (ctz + 1));
}One I heard a while back: "You have a list consisting of every college student in the US. What's the fastest way to sort them by age in years?"
Are lawyers given tough questions and expected to come up with a clever response on the spot? Doctors given a list of symptoms? Teachers given a difficult student and told to teach them some concept from physics?
Serious question (albeit a bit facetious in my examples).
Nothing of the sort exists in the programming field. That, coupled with the high salaries, means fraud is a real problem when trying to hire programmers.
i think these are good. TELL the candidate they are trick questions. again, they are trivial. i was actually disappointed.
For more senior candidates, you definitely wouldn't want to waste everyone's time with brain teasers because if the high risk of a hasty rejection - a deeper probing into systems they've built and and designed in the past, with an angle on relevant problems for the business, along with the pair programming.
Surprise trivia / trick questions do not select for anything meaningful in respect to the day to day practices of any developer
If you were trying to hire a mechanic, would you first give them a sudoku puzzle to measure his "cleverness" (and then use that as a predictor of their car repair abilities)?
Q: Given V (the number of vertices), E (the number of edges) and L (a list of the edges) for a connected undirected graph, determine whether the graph is a tree.
----
A: It can be done in O(1) by: return V == E + 1
The number of vertices in a tree is always one more than the number of edges. We also know that the graph is connected, so it has to be a tree.
This culture needs to end. I don't spend my time at work solving puzzles, I spend time at work meeting with stakeholders, organizing meetings, discussing options and timelines. I spend my time coding and iterating, not wasting my time at puzzles.
I hate puzzles, because I like to do work that actually produces results (and isn't a measure of how smart one might be). Puzzles are a waste of time in my opinion, a much better proof of pudding would be a programming portfolio of things you've written (ie. Github).
If you need anything more advanced you should do an assignment to allow time for proper design and reasoning, otherwise you'll never be able to fully evaluate what the candidate really can do and how he/she approaches problems.
Any evaluation system have to be calibrated on a large enough pool of candidates, when you're building a company and start interviewing you don't really have the luxury of wasting the first dozens applications.
Today I tend to completely avoid programming questions, except to reject complete newbies.
I'd say use whatever language you want, even make one up, so long as you can explain parts where I might have questions. I didn't care about syntax, or performance, or cleverness -- just does it work. If they can't do that, you don't want them for a coding position.
(Obviously, this is a trick answer.)
Question two relies on the answerer knowing specific details about the distribution of perfect numbers, which isn't a "trick" in any meaningful sense. Either you know it or you don't. Contrast with "Are the arguments to memcmp() declared const in ISO C99?". Is that a "trick" question?
And question three is just senseless pedantry. It says that unicode symbols don't make "real" strings if you reverse their orders. Which is true, but not really what the question was asking. ASCII strings aren't "real" if you reverse their order either, because "real" is a human distinction that doesn't live at the data layer. It is certainly true that a reversed unicode string containing ligatures and combining characters is a VALID string per the unicode standard, which seems to meet the phrasing of the question as asked.
As far as the first one goes, you could go through some of the questions on https://codesignal.com/ . They're geared towards interview practice, but ignoring that they provide reasonable problems, a decent environment to write code in and after you get your solution accepted you'll be able to access other solutions to get new ideas. The aim here is just to learn how to think through a problem and allow your brain start to make connections that it wasn't making before.
(Unicode is not suitable for all uses, anyways. Unicode is very messy.)
int y = x ^ (x-1);
return x == y * (y+1) / 2 && ([comparison list]);
If you take it to mean a more abstract concept of a list of things that can be iterated and accessed by index, then the fastest implementation is O(1): build no data structure at all - just implement the iterator and index functions.
If you take it to mean physically manipulating atoms on a chip to be in a certain state, then you'll actually have to do something :)
https://docs.raku.org/routine/flip
$some-str.flip
join '', reverse $some_str =~ /\X/g
...
...
from grapheme import graphemes
"".join(reversed(list(graphemes(some_str))))
const gs = new(require('grapheme-splitter'));
gs.splitGraphemes(some_str).reverse().join('');
Other languages: try to find a binding for libpcre or libicu.
http://www.pcre.org/current/doc/html/pcre2pattern.html#Exten...
http://userguide.icu-project.org/boundaryanalysis#TOC-Charac...
Trick questions do not “show you how the candidate thinks” or whatever. Judging candidates on them is not acceptable.
Answer: O(1), since it could be written as one big lookup table from game state to optimal move. To get a nontrivial complexity class, you have to have some parameter that can vary, so e.g. the question "what's the time complexity of a program that plays perfect chess on an n-by-n board?" (assuming a suitable generalization of the chess rules is given) is much harder to answer.
By the same method, you can sort any finite sequence in O(1).. but then you don't really sort infinite sequences, do you? So I'm not sure this is a good trick question.