Slashdot Mirror
The 'Trick' To Algorithmic Coding Interview Questions (dice.com)
Nerval's Lobster writes: Ah, the famous "Google-style" algorithmic coding interview. If you've never had one of these interviews before, the idea is to see if you can write code that's not only correct, but efficient, too. You can expect to spend lots of time diagramming data structures and talking about big O notation. Popular hits include "reverse a linked list in place," "balance a binary search tree," and "find the missing number in an array." Like it or not, a "Google-style" coding interview may stand between you and your next job, so it's in your interest to figure out how to deal with it. Parker Phinney, founder of Interview Cake, uses a Dice column to break down a variety of example problems and then solve them. But it's not just about mastering the most common kinds of problems by rote memorization; it's also about recognizing the patterns that underlie those problems.
Get a job at Google using this one weird trick!
The only thing necessary for evil to triumph is for it to be pitted against a slightly greater evil
When I had an interview at Accolade, which got bought up by Infogrames and became the new Atari, I got asked the following question: "If two of your coworkers were having a fist fight out in the hallway, what would you do?"
I blurted out, "Does that happen a lot around here?"
My interviewers laughed. I got the job and worked there for six years. I've seen game controllers and keyboards destroyed in fits of rage, but no one ever got into a fist fight out in the hallway.
The correct answer to the question is to take bets.
If the interviewer is worth their salt the idea usually isn't to see if you can get to the best possible, most efficient manner, but rather to see how you approach the problem. Do you solve the actual problem, are you good at understanding the implication of your design (figuring out what is slow or less than optimal about it, understanding the impact of set size on an performance). How do you approach optimizing the function you have created, are you stuck in one mindset or are you willing to pull back and try an entirely different approach to get a better result.
Some jobs require this kind of coding but you are right, most of the time you don't have to have the optimal solution, readability matters as well, usually more than ideal performance. Often that will come up as part of the discussion but for a lot of these problems, efficient solutions are often just as readable as the naive ones.
"In America, first you get the sugar, then you get the power, then you get the women..." -H. Simpson
some of these are algorithmic wankery designed solely as an observational tool to judge your approach to problem solving and performance under stress. They cant be solved, and are an utter waste of time in your presented future role, but from an HR standpoint your reaction is important. You can generally spot these if a manager asks the question instead of a more qualified technical contact on your meeting schedule. Basically, just keep throwing out answers until they get bored and move on. never say, 'i dont know' or 'i cant.'
for systems engineers, its typically some fluff question like how to build a datacenter in literal hell, or how to handle wireless voip QoS in a flying rape crisis icecream truck.
Good people go to bed earlier.
You can expect to spend lots of time diagramming data structures and talking about big O notation. Popular hits include "reverse a linked list in place," "balance a binary search tree," and "find the missing number in an array."
Ya, I hate these kind of interview "tests". I and my brain don't work like that, solving specifics in detail on the spot.
From TFA:
Not long ago, Max Howell, the author of Homebrew (software that basically every engineer with a Mac uses), famously quipped about being rejected from Google after being unable to invert a binary tree.
Would probably be me too.
Like it or not, a “Google-style” coding interview may stand between you and your dream job. So it’s in your best interest to learn how to beat it.
Ya, my dream job is "independently wealthy", which I am -- or, at least, I'm debt-free and financially independent within my budget indefinitely, so I'm good to go. Of course, I'd give it all up to get my wife back - she died in 2006. (I had my dream and now she's only in my dreams...) In case anyone is wondering, I do still work - to support my teammates (who rely on me and need their jobs) and because I don't know what else to do.
It must have been something you assimilated. . . .
And once again Nerval's Lobster posts a story which links to a dice.com story.
Seriously, not one story ever accepted from Nerval's Lobster doesn't point to dice.com, which pretty much means he's a paid staffer whose stories get promoted to click-whore for dice.com.
Honestly, make him an editor and give us a box to block stories from him.
But stop pretending he's getting accepted because of any other reason than shilling for dice.
Lost at C:>. Found at C.
Be able to understand and evaluate Big-O notation and use hash maps and sets. Which if you don't already know, you should!
That's not what I meant.
Amazon also uses coding tests like this, generally based on binary trees. Like an idiot, I didn't google "Amazon code tests" ahead of time and pre-solve all of the possible code tests, because I was given one and sucked at it, only to later find it was one of the listed ones. So, note to the wise: google the code tests for the company you're applying for and pre-do the possible solutions. I'd also note that these take a lot longer to solve than the company implies it should take, especially if you want to set up tests to prove your answer is correct.
I've abandoned my search for truth; now I'm just looking for some useful delusions.
Learn the 40 examples in TFA off by heart
I've worked at several companies that do this style of interview, and interviewed well over 100 people this way. Any question you can just Google the answer for is a stupid interview question - though is may be used for a phone screen, where the real test is: can you code at all, not can you solve it.
I use questions where everyone who codes for a living will get the answer eventually, and measure how quickly it was solved, how good the code is, were errors and corner cases thought through, and so on. I use problems related to real problems I've worked on in my career. I find that's a better way to reliably sort candidates.
Others use very difficult questions where they don't expect most people to solve them without hints. I don't like that approach myself. For those questions, learning the algorithms common to these questions (which go in and out of fashion) is good practice.
Four I'd refresh myself on before an interview are:
* Code some graph-exploration with backtracking, like a maze explorer
* Remember how A* works, and code it (or at least be able to code a breadth-first search without pause)
* Look up how O(n) median (or k'th element) works, and code it (median problems used to be in fashion, and array-partitioning of some sort is ever popular)
* Radix sort and hash tables - it seems the sub-O(n*log(n)) sorting question and related search questions never die
Questions to gauge your comfort with recursion and pointers are also common, but you really shouldn't have to practice those. (Pattern matching in strings used to be another popular question, but I haven't heard of anyone using that for a long time now).
The good questions will be stuff there's no way to practice for, but I've found those four to be just generally good practice to knock the rust off the stupid algorithmic stuff that only comes up in job interviews - but practice on a whiteboard, not a keyboard.
Socialism: a lie told by totalitarians and believed by fools.
I picked a random problem off the list called 4-sum, read it, it obviously had a solution in O (n^2 log n), and the bloody website claims O (n^3). They should be ashamed.
The author used Python for his example and suggested using a Dict to solve the first problem, so presumably we have the Standard Python Library at our disposal:
from collections import Counter
def get_mode(nums): return Counter(nums).most_common(1)
This will give the mode and the count. I don't think the author's solution (14 lines) would get you the job!
Normally, I wouldn't make it one line, but the Slashdot Editor Window doesn't seem to support a proper code block and also doesn't support non-breakings spaces.
So, I had an esoteric maths class once where the prof handed out all past final exams as study tools. The exam was pre-announced to be "answer 5 questions of your choosing from 9 given." The class had covered 3 concepts, 2 which I had mastered, plus Green's functions. I doubled down and bet that the prof wouldn't put 5 Green's functions questions on the test, and he didn't - exactly. 4 questions were on the 2 skills I had mastered, so I answered them quickly and easily. 4 more were explicit: solve using Greens' functions - which I skipped. The final question was a differential equation which simply asked: "What is the solution to: blah + blah / x + blah / x^2 = 0 ?" which I recognized from a past exam which solved "blah * x^2 + blah * x + blah = 0" I solved it "by inspection" and demonstrated the correctness of the solution. Still got a B in the class instead of an A, even after scoring 100% on a final exam that had a median class score below 50% - discussed it with the prof later, and he said "you still don't know how to use Green's functions, do you?" "Obviously not, didn't seem they would be required for the final." B for cleverness, for the A you'd need to learn the archaic skill that has been ground to fine talc and recorded in tables of solved differential equations that were mostly developed and published by 1900. 25 years later, still haven't had a use for Green's functions.
Seems to me that places like Google are crawling with kids who have learned all the esoteric CS algorithms and theories and already applied the hell out of them. Do they really need more people with the same skillset? Homogeneity isn't competitive in the long run.
These interviews seem to weed out the people you want - those who can see deeply into a problem and create an elegant solution. And select the people you don't want - those who are good at bluffing. So I don't get it. If you did this sort of interview, you'd wind up with ... the steaming pile of Android code Google has now. Oh, I get it. Maybe Google should rethink their approach?
Problem 1: Mode
Given an array of numbers, return the mode—the number that appears the most times.
The article goes on to propose two blindingly stupid and overly-complicated solutions which I can't imagine anyone ever even considering, before finally proposing the bleedin' obvious correct solution.
Problem 2: Missing Number
Given an array of numbers where one number appears twice, find the repeat number.
Well, you've just failed the "name the problem" part of the interview.
Problem 3: Sorting
Given an array of numbers in the range 1..1000, return a new array with those same numbers, in sorted order. There may be repeats in the input array. If there are, you should include those repeats in your sorted answer.
First thought: hash maps!
No! First thought: standard library functions!
qsort(<arrayname>,<size>,sizeof(<elementsize>),compare_function);
<?php sort($array); ?>
And so on.
systemd is Roko's Basilisk.
I use problems related to real problems I've worked on in my career. I find that's a better way to reliably sort candidates.
I find that the best way to sort candidates is to use a "sorting hat". Mostly I try to hire hire Ravenclaw. Unless it's a help desk position; then it's almost always a Hufflepuff.
I tried commenting on the dice article but it didn't work.
His analysis is wrong here: "They have O(1)-time insertions and lookups (on average)." and therefore here: "This takes O(n) time, which is the optimal runtime for this problem! And we unlocked it by exploiting the O(1)-time insertions and lookups that dictionaries give us.".
Hashing insert and find are not O(1). They are likely O(N) or O(log N) depending on the implementation. We expect constant time, but worst case is not constant.
Therefore, the algorithm he's shown is O(N^2) or, maybe, O(NlogN). It is expected to run in linear time and most of the time it probably will.
An explanation like this leads to people using hashing when they shouldn't -- ie. when they *require* an upper bound.
I would rank a candidate that understood the distinction above one that didn't -- and since he's trying to help people, he should get it right.
The last time I was asked to work an algorithm on a whiteboard during an interview, I straight up said: I'm not comfortable tackling this in a 45 minute interview.
I did not get the job, but I went on to get a better job where I was given hard problems and expected to actually think them before solving them, without any need for a frenetic rush.
Moderating "-1, Disagree" is simple censorship. Have the guts to post your opinion.
I will never work again at a company that doesn't screen programmers with some sort of difficult coding questions during the interview process. The last time I did, the place was full of people who couldn't code for shit (but had very impressive resumes). I hate "puzzle" questions, but proving you can code something non-trivial and being judged on the quality of that code seems to me to be the most objective and fair way to judge a candidate's technical ability.
Socialism: a lie told by totalitarians and believed by fools.
That's really all these stupid things are assessing.
I've forgotten all the details about b-tree implementation (and R+ trees for spatial data, and, and, and...) but that shouldn't matter, as long as I know general programming principles and quality aspects, and know how to methodically go about looking up the details from appropriate sources, then copying and modifying existing code.
Design creativity, and pros/cons design decision tree exploration, and getting the gist of some fundamental programming concepts (like complexity, maintaining simplicity, refactoring, encapsulation, importance of good naming, importance of good comments etc) should be much more important skills than rote memorization of some 50 year old algorithm.
Companies should be much more interested in what you have already programmed, when you had a month or more to do it, and time to concentrate and research and refine, than what you can program under duress before the USS Enterprise falls into the black hole right ahead.
Where are we going and why are we in a handbasket?
I went through a Google interview, and I thought the questions were really stupid. I think I gave them quite a few answers that likely were wrong in their eyes, because I had too much experience with the subjects. For example, when they asked me how to do a hash-function, clearly expecting one of the standard (pretty bad) constructs. I told them to use the functions by Bob Jenkins, or, if there was time, a full-blown crypto hash. Now, I have filled hash-tables with 100 million elements and got collision chains up to 200 elements long with the STL hash function, but only 30 with SpookyHash by Jenkins. And if there is a spinning disk access in there, the 10us or so a crypto-hash costs you is not a problem either, and the randomization will be excellent under all conditions. But my impression was that they though I was evading the question because I did not really know how this works. That s a pretty bad fail on their side. There were several more. I think the real problem was that I had actual hands-on experience with almost everything they asked me, while they expected me to work though the questions from the data they gave me.
The problem hence is that these questions prefer people with some, but not too deep knowledge or actual experience. As soon as you know more, your chances of failing increase. That is really stupid.
Incidentally, I know a few ex-Googlers now and I am pretty glad they did not hire me. Many people there are not nearly as smart as they think they are and the 20% time is more of a way to press even more working hours out of employees. They kept pestering me for a few years to re-interview, until I told them, sure, no problem, my daily fee is $1600 and I will be happy to do more interviews if you pay for my time. That finally go the message across.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
speed coding is a sign of youth, and to be honest, I am bored by kids who are at google and think they know everything.
speed is the WORST metric you can use to measure coders and programming skill. in my 35 yrs writing code, I never ONCE had to code while being timed. not a single god damned time. its stupid, it shows that you have no idea what real programming is like and it ends up being an agist test. younger kids, fresh from school are filled with algorithms and nothing else. those of us who have been away from school for decades not only don't care about memorizing algs, but realize that its the dumbest use of greymatter. we realize that anything that is memorizable is also searchable (online or in books) and its a total waste of your brain to store crap there that is easily found in ref material.
google: please just fix your fucking bugs in android and stop trying to show off how 'great' you are. maybe you can fix the year old VPN bug in android 4.4? maybe you can fix other bugs that languish? maybe you can STOP eol'ing things people use and actually support the code for longer than your summer fling.
and for the record, I've never once had to redo an already done linked list library or tree library. total waste of time to reinvent wheels. google bores me with their 'brain teasers'. I don't like to waste time on your so-called 'challenges'. and that goes for any other company that thinks that timed tests are, at all, relevant in software engineering.
--
"It is now safe to switch off your computer."
I used to ask the harder stuff, but I am finding extremely few people who can do simple coding. They all look good on paper though. But today's programming is all about knowing how to do function calls to pre-built libraries. Especially CS graduates, they're just awful at programming at a low level. The EE people won't know what big-Oh notation means but they know how to read and write code that implements data structures. So ya, reverse a list, it's stupidly simple but I'm amazed at how many people list C/C++ on their resume who can't figure that out. Or they say "there are libraries to do that" (ya, but what if you're core dumping in that library and it's your job to fix it quickly). We've got enough idea people who sit around doing nothing, it's good to have people who can do stuff.
I mean even if someone does not know the answer, how come they can't even imagine an answer? How come they're having trouble just setting up a loop, or they miss all the obvious corner cases? These are questions that everyone who codes in C for an embedded system should know the answers to. I don't want to hire someone with 10 years of C experience only to have me end up tutoring them in C.
There's a lot of resume inflation out there. They'll like 5 years of working with ARM, and yet know nothing about ARM. 5 years of writing device drivers and yet not know how to clear a bit in a register. But they'll list all 27 source code control systems they've ever used, every CPU they've ever seen, and point out that they they won the six sigma award at their previous company.
Yep - I learned long ago that no matter what's on someone's resume, never bring them in without a phone screen where they do some simple coding. So many people can't code at all.
The difficulty at the low-level stuff is why Java became so popular - you can hire people who don't get pointers and bit-bashing but can still get work done.
Socialism: a lie told by totalitarians and believed by fools.