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
Learn the 40 examples in TFA off by heart
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.
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?
Yea. I've purposely blown up opportunities because the interviewer was taking me on a gigantic dick measuring contest.
A recruiting agency, my big mistake was to talk to them and go there, ask me to do a pre-exam filled with brain teasers and 'here's the sequence, what is next' and various trick questions. I didn't bother filling it out. I laughed at them. When they asked me why I didn't fill out their test, I laughed and said they're not going to hire good talent this way. The recruiter's response was, "This has worked for them for many years." To which I responded, "Good for them, but this test is indicative of how big of an asshole my potential employer is and I have a 'I don't work with assholes policy'." Big fucking surprise, it was pretty mutual neither of us wanted to deal with our attitudes. :D
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.
They use contractors since they think it is bad for such people to receive good benefits.
Twitter supports and protects racists - by smearing their critics with the "Hate Speech" label.
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?
Being a contractor gets your foot into the door to demonstrate your abilities
No, that's the probationary period as a direct hire. To do so as a contractor is to give up any ground one might have.
Also, roasted duck and mac-n-cheese on Fridays is a killer combo at one of the cafeterias.
Had similar options as a directly-hired person for a certain East-Coast based media conglomerate.
Twitter supports and protects racists - by smearing their critics with the "Hate Speech" label.
"reverse a linked list in place,"
> use a double linked list. no need for any reversing.
"balance a binary search tree,"
> use self-balancing binary search tree
"find the missing number in an array"
> disallow empty slots in the array, throw a runtime exception if the caller passed null into the array
http://www.mueller-public.de - My site http://www.anr-institute.com/ - Advanced Natural Research Institute
I tend to use O(n) for assessing scalability, rather than for assessing bsolute suitability, which can usually be assessed when testing the quick/easy solutions. If you know the likely value of 'n' as the point when you plan to maintain the solution again, and know that the algorithm will perform acceptably, then that's OK. The real-life test is knowing when the algorithm will take too long to run, and planning for it by putting in a proportionate development effort.
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.
Code tests like these are here to stay for a while at least, anyway. They serve some sort of purpose, and, as a somewhat experienced programmer, sometimes it's fun to tackle an academic problem like these.
But, you go and practice your "kata", now what? You have some code, it does the job, but what will an interviewer actually think?
If you want some feedback on that, take your (working) code over to Code Review http://codereview.stackexchang... and have some objective folk critique it.
Practice without feedback is incomplete.
.. if only.
Aaaaand... you have pretty much indicated that I would never want to hire you, much less work with you.
You need to jump through some hoops to get a job. The recruiting agency was trying to determine whether you'd be willing to do so. Not to mention whether you had any basic intelligence to solve an analytic problem. They have their own reputation to protect. They don't want to advance a candidate unless they show some basic skills and temperaments that the client wants.
Put your ego away and play the game.
If it weren't for deadlines, nothing would be late.
Any company that dicks me around with asinine questions like this is a non-starter for me.
And not just me- a good friend of mine who is a very experienced DBA (18+ years of Oracle experience) walked out of an interview at Amazon a few years ago after they spent several hours fucking with him. Lots of bullshit questions and silly crap that any low-level DBS could answer.
Keep in mind that this was a guy who had worked at Bank Of America, Lockheed, AT&T, IBM, and other notable companies and he had always risen to the top. He knew his stuff and had a kick-ass track record.
Finally after several hours he told the Amazon people, "Look, hire me or don't hire me, but I don't have time for this nonsense."
They kept asking the "how many ping pong balls will fit in a suitcase"-type questions, and he finally stood up, thanked them for wasting his entire morning, and walked out.
They were stunned (WTF, how DARE he!) and they bugged him for days by phone and email to "come back and finish the interview so we can hire you".
He told them in no uncertain terms to "fuck off", and a week later he was working at Boeing as a Senior DBA.
He told me later, "I'd rather slide down a razor-blade banister into a pool of iodine than work with those pretentious fucks at Amazon".
Just cruising through this digital world at 33 1/3 rpm...
Fairly early on my interviewer spilled a little bit of food on their clothes. My instinct was to offer a napkin to help with the clean up. But this is where the comedy truly begins. This person didn't notice but instead turned things up a notch before I could do anything. There was no stopping either eating or the interviewing. Instead they continued simultaneously. Here's a handful of food, whoosh into the mouth while asking me questions about my current job. Down the hand goes back for more food, the questioning continues, the food unable to withstand the speech while in the mouth plops straight out back on the plate. Another handful and this cycle continues, food in mouth, the interviewer never stops talking to actually chew the food and it all inevitably falls out, back on the plate. I was utterly disgusted, tried to answer while not looking much like George would, knowing full well if I did look at this at this train wreck I'd probably vomit. The sight of half chewed food, almost bouncing back and forth between the interviewer's plate and mouth in a surreal ridiculousness.
Ahh, but that's not quite enough to qualify for Seinfeld. You need that little extra bit to put it over the top, Jerry is the master of that. Some how even though the food kept falling out of the mouth, with repeated tries it was eventually swallowed. I mistakenly thought it'd be ok to look now. Nope of course not, now my interviewer started licking their hand. No, not their fingers, the entire hand, repeatedly straight from wrist to fingertip. Some how I managed to get out of there without barfing everywhere. I was lucky, I'm certain many couldn't help but rubberneck this episode. Their eyes drawn moth like to the flame of utter repulsiveness.
If this was actually on Seinfeld I could see myself laughing at it. The seriousness when I started the interview that morning and yet how bizarrely it actually turned out, that would be one people would be talking about around the figurative water cooler for weeks. Of course it's not funny when something like this happens to you in real life. I was happy when they rejected me. I mean I should never work at a place that would actually employee someone like that. Hell, I can hardly believe it actually happened and yet it actually did. (I should have walked out right after that part but I'm a schmuck so I didn't. I still wonder if it was really a test of some sort.)
Did you know 80 to 90% of the moderators on slashdot wouldn't recognize a troll even if one dragged them under a bridge.
If you find TFA remotely interesting, I recommend you follow it up with "Cracking the Coding Interview" by Gayle Laakmann. Hell, I learned how to solve the Traveling Salesman problem using only directed cyclical graphs, and I don't even know what a graph is! I got a job at Google after I impressed the interviewers, and now I'm working on converting the the Android runtime to something called Java bytecode. Unfortunately, I haven't found a book called "Cracking the Java Bytecode", so I'm just making it up as I go along. That's because my Big O notation is n over infinity!
http://www.amazon.com/Cracking...
Bullshit.
Look at his "get_repeat_number" example.
He claims it to be O(n). But it's of course O(n log(n)), as the log(n) is both in the add as in the contains operation of the set. (if implemented efficiently).
When i am allowed to just assume every builtin runs in O(1), i propably could solve some NP-hard problems in reasonable time as well.