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.
The easiest way to get a job at Google is to become a contractor and skip the tricky interview questions. Only engineers and management are full-time employees with stock options. Everyone else is a contractor. I've done help desk, inventory and data center at Google.
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
No offense, but why the hell would you want to work there without being an engineer and getting the stock options?
Because you still get a lot of the benefits, as well, even though you explicitly don't get all of them, since companies are required to not treat contractors exactly the same as employees, including having limited terms of employment, and "air gaps" in employment history with the company. But it's not like you don't get the food, or access to most of the athletic stuff, etc..
Plus, you get to hang out with very smart people, and, if you impress them, it's possible that they will pursue you for full time employment. Even without that, however: you get to put "Google" on your resume.
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.
If you're not one of the cool kids at [high school | college], you're not going to be an engineer at Google. Being a contractor gets your foot into the door to demonstrate your abilities. Also, roasted duck and mac-n-cheese on Fridays is a killer combo at one of the cafeterias.
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.
So you've never coded something that worked fine until it went into production on that one machine that was slightly different then your dev and staging machines?
I have been in situations like that occasionally. Never did it involve someone standing over me, shouting, or telling me to "hurry up". That is unprofessional and counter-productive. My boss knew that the problem would be fixed fastest if he gave me clear directions, a quiet place to work, and then left me alone with no interruptions.
Actually, if they add in "and the list of numbers is really long", then the fact that you know the numbers are all in the range from 1..1000 means that you can do a lot better than "the standard library function". The standard library function is an O(N lg N) sort, because it can't make any assumptions about the inputs (and your high school algorithms class can happily prove that N lg N is as good as it gets for arbitrary input lists which only support a comparison operator). If you know the range of possible numbers in your list is "small relative to the length of the list", then you use can use radix sort, which is O(N), and thus is going to beat the pants off of the generic sort.
If you don't know that standard library sort functions are N lg N, and that when you know a lot about the input list you can occasionally do better than that, then google probably doesn't want to hire you.
The difference between a bad engineer and a good one is that the bad one rolls their own when they could have used a standard function. The difference between a good engineer and a great one is that the great one knows the limitations and edge cases of the standard functions, and can sometimes do better when it matters. You are unlikely to be getting an interview at google at all if you are a bad engineer, so this question is designed to separate the good from the great.
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?
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?"
You have been modded mostly Funny, but you deserve +5 Insightful.
The way to respond to a provocative question like that is to ask another question that bounces it back. That makes the question go away. I heard a similar piece of advice years ago about responding to the question "How are you with handling difficult co-workers?" The suggested answer was "Are you thinking of someone in particular?"
If it weren't for deadlines, nothing would be late.
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."
In my experience, stock options are a pain. Work 3 to 5 years, earn an extra ten thousand dollars overall from the options. It is rare to make a ton of money from options. Always get the salary up front. And don't let the options tie you down if you don't like the job, because I've seen people stick around depressed hoping that their big bonus will come in next year.
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.