The 'Trick' To Algorithmic Coding Interview Questions (dice.com) 208
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.
Alternate headline (Score:5, Funny)
Re:Alternate headline (Score:5, Insightful)
Re: (Score:2)
No offense, but why the hell would you want to work there without being an engineer and getting the stock options?
Re:Alternate headline (Score:5, Insightful)
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.
Re:Alternate headline (Score:5, Insightful)
You're shortchanging yourself with 2nd tier work. (Score:2)
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.
Re:Alternate headline (Score:4, Insightful)
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.
In other words, become a second-class citizen. (Score:2)
They use contractors since they think it is bad for such people to receive good benefits.
Re: (Score:2)
Re: (Score:2)
Memory is only wasted if it isn't used. Since the spec didn't call out any limitations on memory useage then that point is moot.
Re:Alternate headline (Score:4, Informative)
what is the alternative when we need an o(1) access time?
Insertion sort and infix trees work well. The allow you to make specific assumptions about the data you are traversing.
TL;DR? (Score:2)
Re:TL;DR? (Score:5, Informative)
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.
Sorting candidates. (Score:5, Insightful)
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.
Re:TL;DR? (Score:4, Insightful)
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.
Re:TL;DR? (Score:4, Insightful)
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.
Re: (Score:2)
I did my own initial code with the help of a comp sci grad. Eventually, we grew to the point where I was no longer able to do everything and things got increasingly complex - more than my ability, or were working in that direction. The first couple of hires came from people with a proven track record in a related field (they were in the transportation engineering realm - similar enough). After that, I had them sit in on the interviews - that's the person they'd be working with, after all. I also figured it
Re:TL;DR? (Score:5, Insightful)
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.
Re: TL;DR? (Score:2)
Yup
Re: (Score:2)
Not necessarily. You can google pretty much any answer. But often that's not enough.
In antivirus analysis, part of what you do is to disassemble trojans and find out what they do, and how they do it. You cannot google everything there. More importantly, you have to be able to spot and dissect "interesting" bits quickly because time is not on your side. And that requires you to know. Not to know where to look something up.
An example I often used to screen prospective applicants was this: You find this bit of
Re: (Score:2)
Re: (Score:2)
Well, I want to know if you will write decent code under pressure (as in, the second half of every coding project). Even small examples are enough to see whether you talked through the design and asked questions before diving in, whether errors are handled or even checked for, etc, etc. Coding style shines through even small problems (as long as they're nontrivial).
What you can't measure is the stuff the IDE really does for you. There's nothing worse than "compiler trivial pursuit" -style questions, alth
Re:TL;DR? (Score:5, Insightful)
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.
Re: (Score:3)
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.
That's nothing... (Score:5, Funny)
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.
Re: (Score:2)
Re:That's nothing... (Score:5, Insightful)
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?"
Re: (Score:2)
Were those keyboards, Model M, too?
Re: (Score:2)
So it's ok to duke it out during lunch break?
Comment removed (Score:3)
Re: (Score:2)
Re: (Score:2, Funny)
>> questions are all written in advance in the committee-based interview process, and anyone could potentially ask any kind of question. The twenty-two year old secretary could ask the interviewee [TOPIC], even if she has no idea what she even said
Did you just tell us that you work for CNBC?
Re: (Score:3)
performance under stress.
Why is "performance under stress" a relevant metric? I do almost all my coding alone in a quiet office, and can't imagine a realistic situation that would have someone looking over my shoulder and telling me to hurry up.
When I conduct interviews, I try to remove the stress. I give the candidate a test problem, and a quiet cubicle to work in. Then I come back in 30 minutes and ask them to show me their solution. If you only test them on a whiteboard, in front of a nitpicking audience, you are just weedin
Re: (Score:3)
Exactly. The interview is already stress. The interviewer doesn't realize that, because it's not their ass on the line.
Re: (Score:2)
Exactly. The interview is already stress. The interviewer doesn't realize that, because it's not their ass on the line.
And the most stressful kind of interview is a panel interview.
If you're interviewing for an on-your-feet kind of job, then a panel interview might make sense.
If you're interviewing for a position that requires creativity and craft, then leave someone alone for awhile with a problem.
Re: (Score:2)
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? Or the external webservice your code relied on decided to no longer exist or change APIs and management or your customers are dem
Re:not all sets have a solution (Score:4, Insightful)
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.
Re: (Score:2)
Fixed the fastest isn't always the more important. Sometimes you really need to knnow when things are going to be fixed to plan for other things.
Re: (Score:2)
Why is "performance under stress" a relevant metric?
At Google, everyone works at the speed of light, moves to a different cube every three months, and gains an average 27 pounds in weight from eating at the cafeteria (roasted duck and mac-n-cheese on Fridays is so good). Some people may find that stressful. Every company I worked at since Google claimed to have a faster pace work environment, but they were all slower than Google. I often find myself browsing the Internet for the rest of the day because I finished my work in the first five minutes.
Re: (Score:2)
Yeah? So what if your office is suddenly in the middle of a conflict zone and there's active gun fire in the office next door, huh?
Yeah, I thought so...
Re: (Score:2)
Wow, sooo correct.
I was wondering, do extroverts only hire extroverts, and introverts only hire introverts?
Having said that, I imagine there *are* jobs where being able to present on a white board in high-stress situations...not so common though, I'd wager.
It also puzzles me why recruiters (HR?) are so fussy about spelling and dressing smartly - unless those qualities are actually important for the position, which they're usually not very (documentation perhaps, and attention to detail too). My guess is it'
Re: (Score:2)
Well, that's why I said 'perhaps' - not because it isn't important, but that spelling and dress sense indicate a lack of it to any significant degree. I would argue that it almost always matters too...well, that you have to be *perfect* at it.
If it were important to be perfect at 'attention to detail' then almost all recruiters should never have been hired. They are so incredibly picky about typos and wot-not on CVs/resumes, and yet the job specs they put out are usually riddled with them; and worse, they'r
Re: (Score:2)
plenty of stressed out, angry, traders telling you to hurry up and make it work
If your company's work environment includes anger and yelling, then you certainly should test for that in the interview process. But in a company that values professionalism and reliable code, I don't see any point in testing for "performance under stress".
Re: (Score:3)
The last interview I had, one of the interviewers kept asking more and more esoteric questions with the specific goal of forcing me to say "I don't know." (I got the job, by the way.)
Re:not all sets have a solution (Score:5, Funny)
That's why when I go to interviews, the first question I get I just answer "I don't know", it saves a lot of time.
Re: (Score:2)
Ok, I underestimated you. ...
That was indeed funny!
And probably even the truth
Re: (Score:2)
who the hell has this in their brain that saying 'i don't know' is a BAD thing?
I'd rather have someone admit that they don't know everything than to try to fake it.
90% of the companies have zero clue how to interview. and it shows. the software quality is at an all time low and getting worse every day.
whatever you guys are doing, you are doing it 180degrees wrong. but you'll never admit it because .... ...you won't ever admit you don't know something!
perhaps I've been doing software for too long, but I'm
Re: (Score:2)
... performance under stress ...
Um... WHY? There's been a lot of studies showing that emotions dampen critical thought and vice versa. Give an engineer a problem then leave them alone until they come back with an answer.
Re: (Score:2)
Um... WHY? There's been a lot of studies showing that emotions dampen critical thought and vice versa. Give an engineer a problem then leave them alone until they come back with an answer.
Exactly, and while people will need different amounts of time, once you do this several times with the same people to eliminate flukes, you will identify two classes: One that comes back with a working solution most of the time and one that does not. The former are the good engineers and the latter are the bad ones.
Seriously, whether somebody takes a week or a month to solve a problem difficult enough that you cannot look it up does not matter much. The kicker is whether they can or cannot solve it. Coding
Re: (Score:3)
Not only that, when you have good data models, good interfaces, well-structured code etc. then a fix will be easy to do.
Re: (Score:2)
I had a job interview once where I swear the sequence of events was designed to test my reactions.
The manager had two people to interview, me and someone else. The interviewer came out 20 minutes past my scheduled time and said she was sorry, but she was delayed and would need another 15 minutes. When she came back out 20 minutes later, she spoke to the other candidate and then came to me and said that the other candidate (who was to be interviewed after me) had an appointment and would I mind waiting and
Re: (Score:2)
Heavy sigh. (Score:3)
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.
Re: (Score:2)
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.
Sorry to hear that. You will always dream about her. Finding new purpose is hard. I know.
Re: (Score:2)
yeah, my ex wife is a big part of the reason why I'm not debt-free and financially independent within my budget. Okay, I'm financially independent within MY budget. Not hers. Sorry you lost yours. Wish we could trade places.
Re: (Score:2)
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.
What does that even mean? You can traverse it left-first or right-first, but "inverted"?
Re: (Score:3)
If you aren't trying to directly marry Google and replace human emotions with feelings of corporate loyalty, you obviously have no place in the technological world of today.
Google is a sloppy kisser -- and their tongue algorithm is stuck in "beta".
Nerval's lobster is a Dice.com shill ... (Score:5, Informative)
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.
Re:Nerval's lobster is a Dice.com shill ... (Score:4, Informative)
He is a paid staff writer. Nerval's Lobster:=Nick Kolakowski[0]. There's a twitter profile that links the two, which I posted a good two or more months ago now.
[0]http://insights.dice.com/author/nick-kolakowski/
Re: (Score:2)
Honestly, make him an editor and give us a box to block stories from him.
It won't work. They have an "Ask Slashdot" category but the editors (Hi Timothy!) can't be bothered to or can't figure out how to post articles of that type in that category.
Summary (Score:3)
Be able to understand and evaluate Big-O notation and use hash maps and sets. Which if you don't already know, you should!
Not just google (Score:5, Informative)
Re: (Score:2)
But if you do this, in what way is it a viable test of your ability to think and reason about a problem? You're copy/pasting the answer from the Internet.
I guess that is the skill most-needed for software developers nowadays...
Re: (Score:2)
I often look stuff up in a book or on the net. Software developers should have good search skills, and the ability to use creative approaches to problems.
Ideally, you'd turn down jobs at the company that does that, but sometimes you really need the paycheck.
Re: (Score:3)
It could be argued that the fact the solutions are available on google makes them even more useful as interview questions.
They identify the potential employee as someone who walks into important meetings without even bothering to do basic preparation.
Re: (Score:2)
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.
If this is all the information I have about your programming ability, I never never want to work with you. Hopefully you have other redeeming skills as a programmer....
These problems are all solvable with second year knowledge of computer science.
Re: (Score:2)
These problems are all solvable with second year knowledge of computer science.
I think that's the problem for a lot of the candidates. They can hack some code together, but they don't have a solid computer science foundation.
That's my big concern with this push for code academies. They are teaching people to code, but are they teaching the underlying mathematics and computational theories?
Re: (Score:2)
but are they teaching the underlying mathematics and computational theories?
And let's be honest, those underlying theories are not super-hard. They take time to learn, but it's worth it because it can keep you from making some completely ridiculous programming mistakes.
Re: (Score:2)
Does the job description call for a programmer or a computer scientist? The two are not always interchangeable.
Re: (Score:2)
Re: (Score:2)
Don't be so harsh.
My second year is about ... oops, need a pocket calculator meanwhile to figure that ... 30 years in the past.
And frankly: I never had a programming problem that was covered by any education, may it be school, university or books. (And at that time most data structures we now have in libraries where already existans and taught in schools/universities)
If you want me to write an AVL tree (or black/red tree) I likely will need two days (if I can not google).
Re: (Score:2)
(And at that time most data structures we now have in libraries where already existans and taught in schools/universities)
Donald Knuth said that when he wrote The Art of Computer Programming, programmers were amazed that they could write their own linked lists. The idea had never occurred to them (because they were provided by libraries from the computer manufacturers). That was a long time ago, and yet there was still need for custom data structures, just as there is today.
Re: (Score:3)
Hm, today it is the other way around.
People are reinventing linked lists, not knowing that there is a library.
What you call 'custom data structure' might as well be a 'domain model'.
Actually I myself never stumbled over linked list libraries etc. before Rogue Wave started selling its data structure libraries and 10 years later the STL emerged.
Neither during my Pascal, nor my Modula II nor during my early C times (1987 - 1995) I ever had the option to use a general purpose library of data structures.
Well, th
Re: (Score:2)
What you call 'custom data structure' might as well be a 'domain model'.
Maybe.....when I think of a domain model, I think of a higher level design, that isn't concerned with the lower level implementation details. That is, the domain model won't particularly care if you use a linked list or an array list as long as it is sufficiently performant.
Re: (Score:2)
Of course cause that knowledge is always easily remembered.
I think so.
I haven't written a linked list in something like a decade, but I'm pretty sure I can figure it out if I have to.
Re: (Score:2)
So they hire on the basis of pompous ass-ery now?
Wise, including admitting when you don't know something, is so much better a top-tier engineering quality than fast.
Fast is completely irrelevant.
If you have to fix something in half an hour because your company just released some crap into production, you're all already doing it wrong.
Truly sad (Score:4, Interesting)
Mode of list of numbers (Score:3)
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.
Recognize the patterns (Score:3)
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.
Re: (Score:3)
You won't find a use for a mathematical tool you don't know how to use.
Doesn't this weed out the people you want? (Score:2, Interesting)
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?
Eh? (Score:3)
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.
Re: (Score:2)
These questions are stupid and pointless. Unless you're an academic most programmers had to learn these algorithms once to pass a class. After that they use libraries for the respective language they're programming in.
I'm not interested if you can pound out a quicksort from memory. I'm interested in whether or not you know how to use sorting and apply it correctly to do the damn job I'm hiring you for.
Show me your previous work. Demonstrate a program you wrote. Show me your code and explain it. That will te
Re: (Score:2)
Re: (Score:2)
In C++, my sorting algorithm is std::sort. I haven't had to know how to write a sort in fifteen years (when I adapted heapsort to make a modifiable priority quieue).
Re: (Score:2)
Re: (Score:2)
death in CS for half a decade .
I think you mean century.
The bulk of the sort and search work was pretty well solved by then end of the 1960s.
However due to the massive amounts of data being crunched by the likes of google these algorithms have undergone a bit a renaissance.
In the dawn of computing the data/ram ratio was massive. We didn't have gobs of either but RAM was expensive. In the late 80's through to the early 90's the ratio shifted dramatically. Outside of certain scientific computing domains your typical large data set rarely
Re: (Score:3, Insightful)
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 poss
Re: (Score:2)
His analysis is wrong (Score:3, Insightful)
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.
Re:His analysis is wrong (Score:4, Insightful)
Well-spotted -- from an AC too.
Actually the average or amortized time complexity of hashing insertion is much better than the worst case. In fact they're constant, provided you have enough space to make collisions rare. So the "use hashing for everything" trick is reasonable heuristic for many tasks, but of course not all of them. Knowing how to balance the concern about worst case against the concern about average case is a matter of judgment, which is frequently lacking in people who fetishize this stuff. There are times when a compact O(n^2) algorithm will outperform a complex O(n log(n)) algorithm for all relevant inputs.
Re: (Score:2)
Actually, the average case estimation is correct and is the most common. Your statement that hashing inserts and find are likely O(N) is O(log N) is not true at all. Two things, a perfect hash function for all integers of a given set is pretty trivial. Given than, O(1) worse case time is a given.
More generally, a cryptographic hash will (provably) have very few collisions, so it's not hard to create a hash table that really performs in constant time in all cases. The tradeoff is in space complexity
In this
Re: (Score:2)
Hashing is certainly not O(1). Everyone who has had sets larger than a couple of thousand elements should know that. It can be very efficient, though.
My answers (Score:2)
"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
These are stupid (Score:3)
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.
It has a place, but who checks your work? (Score:2)
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... [stackexchange.com] and have some objective folk critique it.
Practice without feedba
Re:I expect these in my next job interview but ... (Score:5, Insightful)
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.
How recent was your CPSC degree (Score:4, Insightful)
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.
Re: (Score:2)
I totally agree with you.
I like a lot about the prospect of working at some of these companies, but their interviews are completely useless, imo. Still, they do narrow the field, and I imagine that's something that needs doing.
Re: (Score:2)
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.