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.

Comments

Alternate headline

[Nidi62]

Get a job at Google using this one weird trick!

Re:Alternate headline

[__aaclcg7560]

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.

Re:Alternate headline

[Anonymous Coward]

In real life hash tables have horrible cache behavior for large data sets, are wasteful of memory and are much slower than sorting for small data sets. The correct answer to performance problems depends upon the expected input data sets, but it is rarely a hash table

What happens when I bring an O(n) sort algorithm for integers to the hash tables are great because you can solve problems in O(n) time party? Note that if you can hash to an integer you can use the O(n) sort on the hashed values.

Please no more articles written by morons at Dice who could never pass a Google interview themselves. A guy who uses a dictionary to solve all performance problems should fail the interview.

Re:Alternate headline

[mrchaotica]

No offense, but why the hell would you want to work there without being an engineer and getting the stock options?

Re:Alternate headline

[tlambert]

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

[Anonymous Coward]

what is the alternative when we need an o(1) access time?

Re:Alternate headline

[__aaclcg7560]

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.

Re:Alternate headline

[tlambert]

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.

Re:Alternate headline

[MobileTatsu-NJG]

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

[Anonymous Coward]

Get a job at Google using this one weird trick!

Nervill's Lobster applied for a Job at Google, but you won't believe what happened when...

Re: Alternate headline

[ememisya]

My thoughts exactly. Memorize a few basic loops and see if you can deliver Google the Big O? Welcome to our team.

Re:Alternate headline

[Anonymous Coward]

In real life hash tables have horrible cache behavior for large data sets,

Bullshit. Depends on how often you access them. If you need ultra-low latency but not high overall throughput, the cache performance is negligible.

are wasteful of memory

Bullshit. Open-addressing (linear/quadratic probing) hash tables are extremely efficient.

and are much slower than sorting for small data sets.

Bullshit. Also, sorting addresses a different problem space than hashing. Are you completely daft?

The correct answer to performance problems depends upon the expected input data sets,

Correct.

but it is rarely a hash table

Actually, hash tables are often the correct answer.

Re:Alternate headline

[Anonymous Coward]

No. Insertion sort and infix trees are only faster than hashing when the entire array/tree data structure fits in a single cache line and the hash-table does not.

Re: Alternate headline

[Anonymous Coward]

Sorry but throwing around O(n) doesn't make you look very smart. For starters there is no O(n) sort algorithm unless the data is already sorted in which case you don't need to sort.

Re:Alternate headline

[Darinbob]

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.

Re:Alternate headline

[bluegutang]

So you work for a low-level salary in a high-expense market, and you justify it to yourself because lunch on Friday is tasty?

Re:Alternate headline

[__aaclcg7560]

As an I.T. support contractor in Silicon Valley, I get paid minimum wage — $50,000+ per year plus benefits and 20 paid days off — to fix other people's messes. Silicon Valley isn't that expensive if you're willing to live a very modest lifestyle.

TL;DR?

[ickleberry]

Learn the 40 examples in TFA off by heart

Re:TL;DR?

[lgw]

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.

Re:TL;DR?

[Spazmania]

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?

[lgw]

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:TL;DR?

[Opportunist]

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 code in a subroutine.

pop eax
inc eax
push eax
ret

What would you expect and how would you react to it. i.e. what would you do in the disassembler now? Or, if you're not running the debugger now but just have the disassembled code in front of you, what would you expect to see in some parts of the code and what would you expect to be "wrong" with that code?

This is actually a pretty easy example of code obfuscation and I dare say that most people who claim to have more than a passing knowledge in trojan analysis have seen this bit of code more than once. Even if not, I would expect someone who claims to know how to read disassembled code (and without that knowledge you needn't apply for this position) to come up with a sensible answer within a minute or two. Yes, even if this is the first time he sees this particular set of instructions.

There are such questions for most positions you might want to fill. There are some "standard" problems for most job positions. From database engineer to game engine designer. There are standard tasks that should be back-of-hand level for someone claiming to be experienced in the matter. And yes, I would expect such a person to answer such standard questions pretty much immediately. Without googling first. Yes, you can google most questions.

You just don't have time to do so in a professional environment!

Re:TL;DR?

[Anonymous Coward]

My problem with an algorithmic challenge like in the summary is there is already optimized code libraries that do this sort of thing. Why would I rewrite it, debug it, and support it? Would my work be used by any other team? Nope, they have to know how to balance a binary search tree, too!
I'd love to ask: has nobody at your company been able to solve this problem yet? Oh, they have? Then why in the world is it an interview question if I will never have to do it?
I also prefer asking real world problems because that's what I have to solve every day.

Re:TL;DR?

[KGIII]

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 was more likely that they could tell me if the person would be a good hire than I could judge for myself. They did, indeed, ask for programming examples on a giant pad of paper that sat on an easel. This would have been the early/mid 1990s.

Re:TL;DR?

[Spinalcold]

What about other 'best practices' in coding. Big O is important to think about but it isn't the only thing you should hired or not upon, even in coding. Tidiness and documentation should also be looked at, I don't see how a timed 'exam' would allow the interviewer to see these things. Especially since some people code very differently when timed, or some people clean up the code after they are done and some do it right from the start (what do I know, I'm a very amateur coder).

Re:TL;DR?

[TheGratefulNet]

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?

[jhoger]

Yup

Re:TL;DR?

[lgw]

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, although getting the most common library calls right is important.

Re:TL;DR?

[Darinbob]

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: TL;DR?

[Anonymous Coward]

Full ack on your post. Cv inflation is real indeed and it is a direct result of all these HR bozos who don't have a clue on hiring and thus revert to key word filtering. Reward keywords, keywords you shall get...

I find that even candidates with some actual coding experience lack fundamental problem solving skills if the problem is just a bit out of their realm. More often than not they end up throwing hypothesis around what might be the cause instead of sitting down and analyzing step by step until the root cause is identified and a remedy can be planned and implemented. Apparently the monte carlo method of programming is alive and kicking...

Btw Winning six sigma awards is easy. Just do nothing. Producing no results yields no mistakes, boom, six sigma award.

Re:TL;DR?

[joss]

It depends on the job. Some jobs it's not relevant, other jobs it is. For a general purpose programmer, the more they understand the better.

Sure, a library for the common problems already exists, but if you can't provide a reasonable stab at the standard stuff yourself, then you have no chance of solving the unique problems that you may run across. Also, if you're familiar with the algorithms used for standard operations: reverse, random shuffle, sort, that kind of thing, then you will recognise when aspects of your problem already have solutions.

You may as well ague there's no point teaching kids to add and subtract by themselves because they can use a calculator.

Re:TL;DR?

[Anonymous Coward]

Well, I want to know if you will write decent code under pressure (as in, the second half of every coding project).

If a project is not delivered on schedule you failed at your job as a manager. You should be fired. Every project that I have been part of required people with programming skills and critical thinking skills. Unfortunately most of the project staff were capable of neither. How does it feel when the project is in peril of failure due to failure to deliver and you have been tasked with implementation because the idiots sucked up to management? It sucks. You get silence or told you're not a team player.

Re:TL;DR?

[lgw]

a project is not delivered on schedule you failed at your job as a manager. You should be fired.

Fortunately, I'm not a manager - any company where the manager does the technical part of an interview has already failed.

Your wishes about how projects should go aside, your job happens in the real world, flawed as it is. And your co-workers have to live with the code you write under pressure.

Re:TL;DR?

[lgw]

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.

Re:TL;DR?

[NoImNotNineVolt]

Hi. I'm an EE (who learned to code long before college) that's had a decent career writing code for almost ten years now, currently employed writing mostly Java and Python in the world of data analytics. Being a bit (but only a bit) of a hardware nerd, I've always hoped the EE background would help me land a job working with microcontrollers, coding assembly or C, maybe even on robotics or avionics projects, something my inner 12-year-old would appreciate.

What's up with embedded development? At least here in the NY/NJ area, there's a nearly total absence of embedded development positions, from what I've seen. I don't know if it's a saturated market or if the industry just tends to other areas of the country/world, but outside of the telecommunications industry, I've only come across a single open position anywhere near here in the last year. It was at a medical device company, which seemed interesting enough, but the pay was half of what I make just being a mindless Java/Python person. Do you have any familiarity with the industry, perhaps relevant to this region, that you could share? Are there any geographic hotspots for this type of employment where I might have better luck finding different sorts of opportunities along these lines (either US or EU)? Or, alternately, is embedded development even still worth trying to get into? It seems (to an outsider, at least) that a lot of this work may have left the West. Is that accurate, to any extent?

Re:TL;DR?

[cthulhu11]

The thing is, that Google -- and moreover Amazon -- do not ask these questions of those who code for a living. They ask them of *everyone* applying for a tech position. One Amazon interview started off with someone unrelated to the position I was interviewing for demanding that I write code to come up with a list of English words from adjacent letters in an n-by-n matrix. Because you totally need to do that on a daily basis when writing a kickstart template. When Facebook tried the same thing, I told them I was no longer interested.

Re:TL;DR?

[Darinbob]

I'm in Silicon Valley so I don't know what's up in other parts of the world. Even here it's spotty as it's become a hotbed of social startups rather than real engineering, but every company selling a device needs some embedded development.

That's nothing...

[__aaclcg7560]

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:That's nothing...

[Anonymous Coward]

No wonder you're not management. The correct answer is to fix the outcome, then take bets.

Re:That's nothing...

[Anonymous Coward]

"If two of your coworkers were having a fist fight out in the hallway, what would you do?"

If Fallout 3 taught me anything, it's that the correct answer to this question is THE OVERSEER.

Re:That's nothing...

[tomhath]

Use my awesome statistics background to make book on who will win?

Re:That's nothing...

[Anonymous Coward]

My workplace had two engineers, go to party, and both them thought they had clicked with the same chick. They ended up having a fistfight in the main hall of t workplace fighting over who was to continue dating her. Management came in with a customer, were horrified, and added a clause in the employment contract, "There shall be no fight fighting in any public area of the building during regular work hours'.

Re:That's nothing...

[Opportunist]

So it's ok to duke it out during lunch break?

Re:That's nothing...

[ClickOnThis]

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:That's nothing...

[antdude]

Were those keyboards, Model M, too?

Re:That's nothing...

[__aaclcg7560]

Regular keyboards. I once handed a keyboard to a supervisor and told him I thought it was broken. He took the keyboard with both hands, slammed it against the edge of a bench table, and sent every key on the keyboard flying. His manager came through the door and asked him if everything was okay, he told him that he verified that the keyboard was broken and handed it back to me. Just another typical day at the video game office.

Re:That's nothing...

[antdude]

Hahaha. They should had used Model M keyboards. Those rarely break. ;)

Re:That's nothing...

[goose-incarnated]

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?"

What do you do if they answer with "yeah, me"?

Re:That's nothing...

[tehcyder]

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?"

But a half-decent interviewer will be aware that you have dodged the question.

I expect these in my next job interview but ...

[Anonymous Coward]

I almost certainly will not pass however ...

They would be almost pointless to assess my suitability for any work I have done in the last 20 years primarily programming ...

I have had to optimize beyond the metric "can someone else read this" maybe 4 times to meet goals and the solution was generally obvious even in those cases.

Re:I expect these in my next job interview but ...

[Altus]

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.

Oh look...

[Anonymous Coward]

Another Dice post...with a useless article (it goes without saying that you should alread know about hashes/dictionaries/sets/associative arrays).

not all sets have a solution

[nimbius]

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.

Re:not all sets have a solution

[TWX]

That approach doesn't work here. The 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 to describe how to troubleshoot a spanning-tree failure that has taken down a building, even if she has no idea what she even said, let alone what the possible solutions are.

Re:not all sets have a solution

[xxxJonBoyxxx]

>> 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:not all sets have a solution

[ShanghaiBill]

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 weeding out the introverts, not the bad programmers.

Re:not all sets have a solution

[preaction]

Exactly. The interview is already stress. The interviewer doesn't realize that, because it's not their ass on the line.

Re:not all sets have a solution

[Anonymous Coward]

Go program at a trading company; no quiet coding time in an office, plenty of stressed out, angry, traders telling you to hurry up and make it work better/faster / generate more money.

Re:not all sets have a solution

[cdrudge]

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.

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 demanding that it be fixed yesterday? Or you have a deadline of today but the code just isn't ready?

You may not literally have someone looking over your shoulder telling you to hurry up, but I have a hard time imagining a corporate programming job that doesn't have times where "performance under stress" isn't an issue.

Re:not all sets have a solution

[mrchaotica]

Basically, just keep throwing out answers until they get bored and move on. never say, 'i dont know' or 'i cant.'

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

[knightghost]

... 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:not all sets have a solution

[swb]

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 being interviewed second.

By the time she actually interviewed me, the interview took place maybe 90 minutes after it was scheduled. It was all so grossly unprofessional that I swear it was only done as a test.

Re: not all sets have a solution

[Anonymous Coward]

I won't hire someone who won't admit they dont know the answer to something in an interview. Several hard questions have the sole purpose of analyzing how you answer. The answer itself doesn't matter.

Re:not all sets have a solution

[Anonymous Coward]

Ideally, yes. But that isn't what happens in the rela world.

Re:not all sets have a solution

[SuperKendall]

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:not all sets have a solution

[Anonymous Coward]

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.

It's exactly that kind of thinking which results in a 0-day vulnerability sitting around in a Production system for 6 months while Management waits for the engineers to come back with an answer.

Re:not all sets have a solution

[Anonymous Coward]

The secretary is a mtf transgender person in the midst of trying to live in her chosen gender. While still living as a male, she was also a secretary, but it would now be inappropriate to refer to her as "he".

Re:not all sets have a solution

[Anonymous Coward]

You are a jackass. Think about that.

Re:not all sets have a solution

[ShanghaiBill]

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:not all sets have a solution

[Anonymous Coward]

In other words: work in a terrible environment and hate what you do, all while helping people siphon off the meager retirement savings of Americans.

Re:not all sets have a solution

[__aaclcg7560]

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:not all sets have a solution

[__aaclcg7560]

I got stranded in a receptionist-less lobby of a busy biogenetic research company for 90 minutes. People kept coming and going, smiling at me in passing. The recruiter kept calling me everything 15 minutes to ask where the hell I was for this interview. Someone approached me and asked for my name. The hiring manager in a lab coat assumed that I was a venture capitalist because I wore a business suit and tie. After the interview and a tour of the labs, I met the CEO who was dressed in blue jeans and T-shirt. I didn't get the job because I was "too rich" for them..

Re:not all sets have a solution

[ShanghaiBill]

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:not all sets have a solution

[Anonymous Coward]

no you always say I don't know but I know how to research it.

Re:not all sets have a solution

[angel'o'sphere]

Ok, I underestimated you.
That was indeed funny!
And probably even the truth ...

Re:not all sets have a solution

[Anonymous Coward]

So you're telling us Google hires people who don't know how to ask for additional work or how to help out their co-workers when you have some spare time. Everyone there is only in it for themselves and everything else be damned?

Re:not all sets have a solution

[Anonymous Coward]

No, that kind of thinking prevents the 0-day vulnerability from existing in the first place. When you have time to do things properly, you do them properly.

Re:not all sets have a solution

[Anonymous Coward]

That's a really weird anecdote. One of the strangest I've heard actually.

Re:not all sets have a solution

[Anonymous Coward]

This. At any decent company, if the shit has hit the fan, your co-workers will be supporting you, and management will be supporting you, whether that means extra hands or just being left the fuck alone. And it won't be your ass on the line if you're the engineer, because a whole host of people will have been involved in designing, developing, testing, deploying, and managing all of the above, and any major the-client-is-pissed mistake means that either someone high up has fucked up, or there's something more generally wrong with processes that needs fixing. And, at a decent company, the high-up better-paid guy both knows it's his responsibility AND is canned for major fuck-ups.

Of course, this is all how it should be. I've worked at places like that, and places very much unlike that. But I know which of the two sorts of places still exist in recognisable form...

Re:not all sets have a solution

[Anonymous Coward]

Close, Newscorp (eight years and counting).

Re:not all sets have a solution

[KGIII]

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:not all sets have a solution

[dwater]

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's more about pride and/or power-craziness. Perhaps it's also a sign of laziness, since they usually get too many applications and they have to par them down somehow. Either way, IMO, it certainly doesn't do the company any good to hire people based on such things.

Re:not all sets have a solution

[gweihir]

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 is not speed-thinking, unless you do really low-quality stuff.

Re:not all sets have a solution

[gweihir]

Not only that, when you have good data models, good interfaces, well-structured code etc. then a fix will be easy to do.

Re:not all sets have a solution

[Anonymous Coward]

You've never had your boss's boss override his/her wisdom and decide to hover over you until you got it fixed?

Re:not all sets have a solution

[Anonymous Coward]

Which is why only the most secure software is produced by programmers who have someone constantly standing behind them, yelling at them to stop thinking and hurry up with the product.

Re:not all sets have a solution

[Actually, I do RTFA]

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:not all sets have a solution

[ClickOnThis]

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:not all sets have a solution

[plalonde2]

Attention to detail almost always matters. Knowing you're going into an interview you should be paying attention to the details. Failing to do so is a red flag.

Re:not all sets have a solution

[TheGratefulNet]

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 sick and tired of the bullshit games that companies play during interviews. coding used to be fun and we used to take pride in our work. now, its all about 'velocity' and agile and speed. all the things that are toxic to quality designs and implementations.

Re:not all sets have a solution

[dwater]

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're often technically dubious too (IMO).

Re:not all sets have a solution

[angel'o'sphere]

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?
No idea about the parent. But no, I for my part did not.
My teams only had very low rates of defects in production ... I never had a bug caused/written by myself in production.

However I'm working as a DevOp right now and the organization is a night mare.

They not even can manage that the staging machines run the same data base version as the production machines.

The staging machines run in the same network as production. Why is that so? Wellllll .... you have to make sure that "developers" can not push code from development towards production, right? So you separate the networks. But: you need to be able to pull code from the final QA stage to production "as a developer". So ... somewhere they lost complete track how to organize dev/test/qa/prod networks and the whole thing is a complete mess. Needless to say: it is a bank, and is owned by one of the largest banks in my country, the largest bank actually I believe.

Re:not all sets have a solution

[angel'o'sphere]

Lesson learned: don't wear a suit and a tie for an interview in the software business.
And even I can grasp that sneakers don't suit to a suit ;D

Re:not all sets have a solution

[Anonymous Coward]

I enjoy how you assumed the secretary is female. Not calling you a bad person - but you may want to think about that a bit.

Shut up, you fucking fucktard.

Re:not all sets have a solution

[__aaclcg7560]

Not Google. Most companies I worked for after Google don't have enough work to keep me busy. If I start doing the work of two or three other people, management might decide to lay those people off. Either management keeps me busy or I'm browsing the Internet because there's nothing else for me to do.

Re:not all sets have a solution

[tehcyder]

no you always say I don't know but I know how to research it.

"I don't know, but I can Google it".

That's what kids say when you ask them something like "when was the Second World War?"

If I was interviewing someone I would not be impressed with that answer.

Heavy sigh.

[fahrbot-bot]

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:Heavy sigh.

[Anonymous Coward]

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.

Re:Heavy sigh.

[fahrbot-bot]

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".

Re:Heavy sigh.

[careysub]

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:Heavy sigh.

[jafac]

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:Heavy sigh.

[gweihir]

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:Heavy sigh.

[Anonymous Coward]

famously quipped about being rejected from Google after being unable to invert a binary tree.

Would probably be me too.

Don't feel bad. It's not actually possible. You a tree isn't linear, how could it possibly be "inverted"? You could invert it if you were working with DRAWING a tree.

They most likely meant "recursively swap left and right nodes" except that stating that gives you the solution. Or the guy just misstated the problem. It's a stupid problem anyway. Balancing a binary tree is a good toughie, but just arbitrarily swapping nodes is stupid.

Nerval's lobster is a Dice.com shill ...

[gstoddart]

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 ...

[Anonymous Coward]

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:Nerval's lobster is a Dice.com shill ...

[Fnord666]

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.

Step 3: Be Dice and drive clicks to yourself

[Anonymous Coward]

Step 4: Profit.

Summary

[Dino]

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

[Locke2005]

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.

Re:Not just google

[preaction]

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:Not just google

[phantomfive]

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:Not just google

[Anonymous Coward]

Umm... I managed to solve two such problems in my Google interviews with time to spare. Neither problem had I seen before, so I'm sorry but your claim is wrong. I now work for Google.

Re:Not just google

[h4ck7h3p14n37]

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:Not just google

[mrprogrammerman]

Of course cause that knowledge is always easily remembered. Unless your creating standard libraries probably not. I will agree, thought, that the interview shouldn't be your first introduction to computer science fundamentals.

Re:Not just google

[Anonymous Coward]

These problems are all solvable with second year knowledge of computer science.

Bingo, we have a winner.
That's exactly what they are testing for- basic knowledge that any CS grad ought to have. If you're self-taught and you don't "get" this kind of thing, then you need to spend some time self-learning the basics. People don't understand that a large part of CS fundamentals is developing the ability to use a standard mathematical language to communicate with... you might be some kind of genius programmer but companies like Google don't have just one Genius. They have many, and it's often more important to be able to communicate with the others than it is to be a one-man show.

Re:Not just google

[phantomfive]

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:Not just google

[phantomfive]

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:Not just google

[__aaclcg7560]

Does the job description call for a programmer or a computer scientist? The two are not always interchangeable.

Re:Not just google

[khellendros1984]

The problems are all solvable with some basic CS, yes. But you have half to 3/4 of an hour in which to do the problem with someone looking over your shoulder while keeping up a stream-of-consciousness patter so that the interviewer would understand my thought process while writing. I don't do well trying to think and speak at the same time, and I don't do well being watched and critiqued. The easiest way through that kind of interview question is to rehearse it beforehand, for me.

Re:Not just google

[david_thornley]

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:Not just google

[angel'o'sphere]

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:Not just google

[phantomfive]

(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:Not just google

[Stormy Dragon]

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:Not just google

[presidenteloco]

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.

Re:Not just google

[angel'o'sphere]

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, there was a small exception. zApp, a GUI library for portable GUI software development. They had around the same time macro based C++ 'template libraries' for common data structures.

Only since about ten years ago I started to rely on off the shelf general purpose date structure libraries, in Java.

I wrote my own subset of the STL, though around 1993-1995 but that was merely focused around generic algorithms in lists ... not really a challenge. In other words, (facepalm), even when I considered myself bleeding edge state of the art hard core C++ super developer: I actually never did something more complex than doing MI with template linked lists that took an enum as template param (considering 'data structures' ... not algorithms)
However I was very good in boiling down code to minimum amount of lines with inheritance, templates and generic algos.m,

Re:Not just google

[phantomfive]

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:Not just google

[angel'o'sphere]

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.
True, but that depends in the end on what algorithms you are using (need to use) on those lists.

Walk away

[Anonymous Coward]

The correct solution to this question is to get up, state in a not so condescending "Are you serious?" and then thank them for their consideration and walk away.

No serious interviewer would ever ask this question, because the answer is to simply GOOGLE the answer. All these algorythms have well known, well understood answers, and NO serious coder should EVER be re-inventing the wheel from scratch. PERIOD. We don't code in a vacuum, so asking me to do it just to prove I can in is kinda insulting at best.

Re:Walk away

[Anonymous Coward]

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

Re:Walk away

[ClickOnThis]

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.

Re:Walk away

[Anonymous Coward]

They don't want to advance a candidate unless they show some basic skills and temperaments that the client wants.

Not sure who you deal with, but my experience of recruiters is that they have no bloody clue about what the client actually wants. All they want is to make their commission, so employ the shotgun approach with as many tenuously-linked candidates as possible in the hope someone gets the gig. I've yet to see any evidence a recruiter examines anything more than keywords on a CV/resume, and they can't even get that right most of the time.

the trick...

[Anonymous Coward]

... Is to do enough of these kinds of problems before your interview to be able to recognize them.

Seriously, by now you should know: to get the job you're going to have jump through some hoops that involve solving problems you haven't really thought about since 1st year university. This is especially true if you want to work for a valley startup staffed by new grads from the farm - its not interviews, its quals. Besides the interviewer probably doesn't know shit about project planning or telling a product manager to piss off, so couldn't ask you about that anyway.

Its like prepping for a test. Study pass the test, and then do your actual job.

Yes, this sucks, but its the way it is. I haven't reversed a singly linked list in real code since some time before the millennium... but I've been asked about it.

Truly sad

[gnasher719]

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.

Re:Truly sad

[angel'o'sphere]

O-calculus is not used to describe effort for a problem, it is used to describe the efficiency of a certain solution/algorithm to that problem. Hence we have plenty of different sorting algorithms with plenty of different O-terms.

Mode of list of numbers

[RoccamOccam]

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.

Re:Mode of list of numbers

[Anonymous Coward]

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.

I think
it
supports

angle open
Bee
Arr
close angle.

Re:Mode of list of numbers

[RoccamOccam]

Right. Sorry, I didn't quite explain. I had the line break part figured out, but I couldn't put the proper indentation in with a non-breaking space. So, if I'd written the def as two lines, it wouldn't be proper Python code. The one-line version is proper, however.

Re:Mode of list of numbers

[Anonymous Coward]

What do you mean
    when you say
        it doesn't support
            non-breaking spaces?

Just wrap it in a code tag and it works fine.

Re:Mode of list of numbers

[dwater]

Hrm, I thought the author was quite clear that the code was pseudo-code, and, while written in python syntax, was purposefully generic and avoided anything that required any python knowledge.

Re:Mode of list of numbers

[RoccamOccam]

What do you mean when you say it doesn't support non-breaking spaces? Just wrap it in a code tag and it works fine.

test test
testtest
Aha - the non-breaking space has to be followed by a space, for it to be recognized! That's certainly weird.

Re:Mode of list of numbers

[RoccamOccam]

Well, once you add in the ability to use a dict object (which he did for his "correct" solution), then you've gone beyond the traditional capability of pseudo-code.

Re:Mode of list of numbers

[dwater]

Hrm, perhaps you have a point. TBH, I didn't find the article particularly enlightening, irrespective of python/pseudopod.

real system engineers use .sort()

[Anonymous Coward]

It is rather interesting corporations are using low level bit manipulation as a guage for an enterprise full stack engineer. I have done assembly in the past and if you tried to test me on it now, I would just laugh and walk away. I was good at it but I now longer think in terms of low level patterns. I just use .sort() there is to much to know in order to maintain low level patterns in the human mind in a meta driven distributed transactional domain environment. Memorizing low level patterns is a waste of brain power. Knowledge is dust, knowing is everything.

So if HR wants to hire a bit twiddler (not that theres anything wrong with that) keep on doing what you are doing. On the average, low level bit twiddlers (not that theres anything wrong with that) do not do well in systemwide distributed transactional concurrent collection, distribution patterns used in financial, manufacturing, transportation systems. This is from direct experience dealing with this issue for over twenty five years.

Ask me to slam a million transaction messages through a digital transaction pipeline and distribute it to a transactional pipeline => split and endcode to a real time analysis engine and I will make it so. Ask me to write a bubble sort routine and this interview is over. I will not work for an organization that is so short sited, I would rather drive a truck acrros country.

Recognize the patterns

[JoeMerchant]

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:Recognize the patterns

[Boronx]

You won't find a use for a mathematical tool you don't know how to use.

Re:Recognize the patterns

[Anonymous Coward]

I hate professors like that.
If you'd wanted to make trouble for him you could have reported him, since he unfairly graded you.
Unless his exam explicitly stated that you had to solve at least one of the Greens equations or whatever, he wouldn't have a foot to stand on.
Or do professors in the USA just get to randomly assign grades to students because they don't like them? (never did understand that ABCD system)

Re:Recognize the patterns

[Anonymous Coward]

I had an esoteric maths class ...[which] had covered 3 concepts, 2 which I had mastered, plus Green's functions. I ... 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 .

As someone who teaches math at the university level, I approve of that outcome. One of the reasons professors are given so much power is to handle edge cases like this. I occasionally get students who work the technicalities like this, and it seems to me that it's great practice for them if they want to be a lawyer or a bidder on federal contracts, but short-sighted if they want to become a mathematician or physicist. You're not going to get too far in quantum mechanics without knowing Green's functions.

You personally may not have found a use for much, if any, of what you learned in your differential equations class but the demand that earning an A be associated with understanding all the concepts in it is quite reasonable. For other students, that grade would be used to determine how prepared they are for higher level (an, may I say, even more esoteric) classes in math, physics, etc.

To your credit, you seem more amused than bitter about the whole thing, and I do enjoy your story.

Re:Recognize the patterns

[angel'o'sphere]

clap clap clap

Re:Recognize the patterns

[JoeMerchant]

Greens functions are for deriving solutions to previously unsolved diff-eqs. 25 years of medical and scientific R&D work (commercial sector) have presented me a single need to solve a differential equation with anything other than successive approximation.

Just knowing that Greens functions exist would prompt me to figure them out, if the need ever arose. I've had a few esoteric mathematical challenges over the years that were worth sitting down and deriving a complex solution for. For what it's worth, that class was a bum steer from my advisor, the other two techniques taught in it (can't remember the names anymore, related to closed loop integration around singularities on Gaussian surfaces, IIRC) were even more useless than Greens, absolutely never came up in my practice - even though I had them mastered in 1988.

Doesn't this weed out the people you want?

[Anonymous Coward]

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?

dictionary with O(1)?

[Anonymous Coward]

That's a first.

Eh?

[wonkey_monkey]

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:Eh?

[mrprogrammerman]

They typically don't allow you to use std library functions on those questions. That's why it's a good idea to refresh up on your sorting algorithms before the interview.

Re:Eh?

[Anonymous Coward]

First thought: standard library functions!

Somebody had to write that standard library function, lad. If you're only good enough to glue together other people's library functions, you're not good enough for Google (or pretty much anywhere else, really).

Re:Eh?

[Anonymous Coward]

No! First thought: standard library functions!

This. A million bajillion times.

Any dipshit that rolls his own when there's a perfectly valid standard function is fired. So. Fired.

The same goes for standard date/time handling and probably a few other "basics". I'm getting there on logging and database access, too. I still give those a conditional pass because there are far more configuration issues at play, and sometimes a custom bit of code is warranted for those things.

Re:Eh?

[Chalnoth]

At least not ones that allow a candidate to avoid the problem completely. However, I don't think that "implement this standard library function" is a common interview question these days.

Re:Eh?

[Anonymous Coward]

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.

Re:Eh?

[Anonymous Coward]

At least not ones that allow a candidate to avoid the problem completely. However, I don't think that "implement this standard library function" is a common interview question these days.

Say what? atoi(), itoa(), strrev(), etc. are common for warmup questions for college hires.

Re:Eh?

[david_thornley]

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:Eh?

[Anonymous Coward]

And then the requirements change slightly and no one has time or knows enough about that section of the code to remove the radix sort and replace it with a generic one. The generic answers are better in the long run and are more maintainable. Knowing the domain is everything.

Re:Eh?

[jrumney]

If only I had a million dollars for every time I had to write my own time handling because the library was crap. The number of libraries that restrict timezones to +/-12 hours, or hardcode the assumption that daylight saving starts early in the year and ends late in the year, or even hardcode the US rule for changeover dates is astounding.

Re:Eh?

[Greyfox]

Really? Google may want algorithm people, but I'd be looking for people who knew their tools and could use them effectively. I'd be overjoyed if I were interviewing a C programmer and they used the qsort standard library call to sort some shit, rather than reinventing a wheel that's been done to death in CS for half a decade.

Re:Eh?

[Xyrus]

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 tell me a whole lot more about your skills and capabilities than whether or not you can dust off the cobwebs and roll your own sort.

Re:Eh?

[calque]

I wrote a program in Pascal in high school that allowed you to sort random numbers using almost any algorithm, as an animated bar graph. I'm sure many other people have done similar things, (I was inspired by a QuickBasic program with more limited choices) but I really was fascinated by the visual effects of different methods. But ever since, I never have and probably never will have to write a sort professionally. The only information that I really retain is that every sort function should have n log n run time in the worst case, and be stable. On the other hand, implementing a binary search is something I have found the need to do, repeatedly. And most Computer Science 101 questions are, face it, age discrimination. After 20 years, nobody remembers the stuff they haven't used since graduation.

Re:Eh?

[calque]

The difference between n log n and n is not nearly as important as the difference between n log n and n^2. Think about scaling the problem size by a million. It's nice to have the skills to optimize code, but it's also nice to know better than to do it prematurely, or at the expense of other tradeoffs. I would rather work with someone who can instantly understand what's appropriate, rather than someone constantly looking for artificial ways to prove their superiority.

Re:Eh?

[vovin]

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 exceeded ram by an order of magnitude. Heck sorting 30k employees by name while not blinding fast with a poor choice of algorithm is still plenty fast on whatever flavor of qsort shipped with your standard library ... and since the entire problem space is in ram there is no reason to know anything more about the details.

Now when you can only hold 1% or less of your primary keys in ram ... then sorting it becomes interesting again, sort of, because you have to back digging up those old sorting schemes or re-invent them.

Re:Eh?

[Anonymous Coward]

Just use your phone to google the answer during the interview.

Re:Eh?

[angel'o'sphere]

First of all: calling a library function is not solving the problem.
Secondly: you missed the array of numbers in the range 1..1000 part. That is O(n) solvable and trivially with a few dozen lines of low level C or any other language.
Thirdly: a hash map is a library class again, and not really useable for such a simple problem. Why the funk would you hash over a small set of values if you can simply make an array?

Re:Eh?

[angel'o'sphere]

That is wrong, radix sort is O(n log n).
In special cases it is O(w n) where w is the word size of the integers.
Hint: https://en.wikipedia.org/wiki/...

Re:Eh?

[Greyfox]

Yeah. I really feel like we've forgotten a lot in the last couple of decades (Trying to get my units right this time heh heh.) I had to audit the source code to the original AT&T awk back in the '90's, and it's really the only time I've ever seen Lex (I forget if they also used Yacc) used in a non-academic setting. I've seen a lot of really bad attempts to tokenize strings in C and Java since then, that would have worked a lot better with C and Lex. DSLs are all the craze these days, but people would rather implement a bad one with Ruby or Groovy rather than use tools that were actually designed to do that sort of thing.

Also, although no actual AI came of the AI research in the '70's and '80's, a lot of really cool solutions around machine learning and reasoning were found. Again, I've seen very poorly implemented attempts to do similar types of things in recent code. Those problems were solved ages ago, but the programmers were not even aware of that.

This guy hits the nail on the head.

Sorting candidates.

[tlambert]

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:Sorting candidates.

[Anonymous Coward]

Management is, of course, Slytherin. Oh, excuse me, misspelled that - I mean, management is slithering.

Re:Sorting candidates.

[Anonymous Coward]

you just made this thread worth reading

capcha: keeper

Re:Sorting candidates.

[Anonymous Coward]

No love for Gryfindor or Slytherin?

- Malfoy Potter

I usually prepare for only confuscious questions

[Anonymous Coward]

Q: Man who stand on top of toilet?

A: is high on pot

You're hired!

His analysis is wrong

[Anonymous Coward]

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

[hey!]

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:His analysis is wrong

[Tammuz]

Exactly correct! An article claiming to explain how to answer questions involving run-time complexity shouldn't have such obvious mistakes in its analysis of run-time complexity.

(Yes, constant-time can be achieved by preallocating a fixed hash table, but that's not the same as using an arbitrary set insert/retrieve and since it permits collisions and is inherently bounded. It solves only a subset of the described problems.)

Mostly the dice article illustrates how the author is a poor person to look to for advice in that type of interview.

Re:His analysis is wrong

[ndykman]

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 case, using a hash table is indeed the best solution. Your claim that hashing insert and find aren't O(1) is focusing on a basic level of understanding of hash tables. Modern implementations avoid non-constant performance with rebalancing, open addressing schemes and so on.

Re:His analysis is wrong

[tgv]

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.

Re:His analysis is wrong

[Anonymous Coward]

In reality in many cases, hash tables are used out of convenience to get something sufficiently fast - even though access from/to the same objects occurs multiple/many times, and direct references could be set up once, eliminating the overhead of the hash beyond the first initialization.

It feels like this laziness/convenience makes todays software on modern hardware feel the same (performance wise) than old software on hardware available 20 years ago.

Re:His analysis is wrong

[Anonymous Coward]

> The tradeoff is in space complexity
Seems like an important little detail that you just put there like it's nothing.

Re:His analysis is wrong

[Anonymous Coward]

First -- I didn't say hashing wasn't the best choice. It probably is the best choice, except for very specific circumstances.

I said that his analysis was wrong -- and so is yours. Here is why:

All hash functions have collisions. The worst case for hashing is when all elements hash to the same value. We can argue about how likely this is (very unlikely given a good hash function), but it is *possible*.

Please show me how "rebalancing, open addressing schemes" avoid having a linear time (or O(log N) if you are hashing into balanced binary trees) operation when all elements hash to the same value. They don't.

Therefore, the worst case is as I've suggested. And, as I said, we *expect* hashing operations to be constant time, but they are certainly not O(1).

Optimization: measuring or thinking about it?

[Anonymous Coward]

Turns out that sorting for the mode O(nlogn) is 10x faster than hashing O(n)
Another fail for Big-O notation in the real world.

Details here:
missingbytes.blogspot.com/2015/11/optimization-measure-performance-versus.html

Really? That's how you tell who is talented?

[Anonymous Coward]

Seems pretty irrelevant to me. I'm still not sure how to tell who is a good programmer and who is not, I can only tell you that most programmers out there are absolutely fucking useless.

Trick? Either you know it or you don't... apk

[Anonymous Coward]

See subject: One of the toughest (& shortest) I ever had was for MS' "crash debug dump analysis team" -> http://developers.slashdot.org...

(4 questions way back in 2003 while I worked for CableVision & they came to ME oddly with those questions which I KNOW I had right on 3/4 & I sent it back in 3 languages - but, I guess, not "right enough"... oh well!)

I didn't "make the mark" THEN, 14++ yrs. ago... bet I would now though. Oh well... I don't HAVE to work anymore & instead, imo, "got TRULY smart" & decided to work for myself instead.

Back then? I would've LOVED to work for MS, & especially @ the OS architectural levels... now?? I'm not so sure anymore - iirc, they've implemented a "FEAR BASED" criteria system where even IF/WHEN you have a room full of polymaths & geniuses, only the "Top 10%" make it... stupid!

APK

P.S.=> That's when you get 'smart' (I should've done this ages before it but the "infamous they" say you don't acquire wisdom until you're @ least 50 (which iirc, is part of the basis for presidential candidates age as well) - I got mine if what I did stands for anything, @ about 44++... apk

Parker!

[Anonymous Coward]

You're awesome!

In other words, become a second-class citizen.

[sethstorm]

They use contractors since they think it is bad for such people to receive good benefits.

How recent was your CPSC degree

[presidenteloco]

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:How recent was your CPSC degree

[dwater]

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.

You're shortchanging yourself with 2nd tier work.

[sethstorm]

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.

My answers

[devent]

"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

H1B

[Anonymous Coward]

H1B?

O(n): is for scalability guesses

[MessyBlob]

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.

Re:My answers (fail)

[Anonymous Coward]

Great but the implication of reversing inplace is to reuse the existing data structures, not reallocate a new kind of data structure.
The presumption is you can not change the "linked-list" data layout, just simply reverse the list inplace.

Basically you need to readahead one entry, and iterate over list maintaining the readahead data before you overwrite that points with the previous.
At the end you set the head of the list pointer to the last pointer processed (or null when list was empty).

All done in a single pass, and the only read-access is pointer sized data within each structure, and immediately write back a different value to it, plus read/write access to the pointer to the head of the list. No change of data layout, size, etc... just a reversed list in a single pass.

These are stupid

[gweihir]

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.

Re: These are stupid

[Anonymous Coward]

Yeah them googlers generally are the we now it all ye know nothing so be quiet type. Attitude matters imho and that is just not a sicially acceptable manner. It will pass once we send them off on the first of three spaceships, please you smarties go on, we'll follow... 42

It has a place, but who checks your work?

[gus goose]

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.

Re: no, YOU are wrong

[Anonymous Coward]

See: Erik Demaine 's lecture

tl;dw: There actually are hashing algorithms with proven O(1) deterministic query and O(1) w.h.p. "with high probability" (which means "with probability of 1 in the limit") expected update.

My response

[Anonymous Coward]

... to algorithmic questions like these, i.e. of theoretical interest not of practical importance, is quite simple: that's an interesting question, and indeed I would be able to solve it if I was stuck on a island without access to the internet where I will find hundreds of libraries or at least some documentation on all kinds of solutions to this very problem. Some of which I would probably be able to recall from looking it up previously, even in my 25+ years of experience writing code I have hardly ever come across a situation where it actually mattered to implement this myself. Because quite frankly solving problems that have been solved before is, well, with all due respect not very smart and for the most part not very challenging either. If you kids would like to take a pisaing contest about who knows more, we can do that, sure, I suggest we choose topics in turn and see where we get after say 3 rounds, Now, if you have questions that are actually of practical interest, like some challenge you guys are currently working on, I'll be happy to indulge in how I would approach the problem. Otherwise I suggest we stop here and safe us all the trouble of thinking about readily solved problems. Life is just too short.

No, just NO

[JustAnotherOldGuy]

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".

Re:No, just NO

[null etc.]

I interviewed at Microsoft, Google, Amazon, Intuit, etc. back in the day, and they were all some particular variation of nerd-arrogant.

Microsoft asked me, "How many ping pong balls would fit in an airplane?" I answered, "3X, where X is the number of bugs in Windows 2000." I didn't get the job.

Amazon asked me, "How many ping pong balls would fit in an airplane?" I answered, "That depends upon whether I use your head as a hammer to flatten each ping pong ball first." Guy was an asshole. I didn't get the job.

Google asked me, "Why are manhole covers round?" I answered, "So they can roll downhill and maim people." I didn't get the job.

Finally, I got a job at ADP. Now I fuck with those companies by screwing up their employee paycheck amounts every fourth cycle.

Re:No, just NO

[JustAnotherOldGuy]

I like the way you think. :)

Dream job?

[Anonymous Coward]

I went through the Google interview process a few years ago, and these questions were interesting in the sense they involved knowledge I hadn't needed in over a decade since I graduated. However, as someone who has conducted many developer interviews, I realised they sucked as a selection technique: they didn't test understanding, practical ability, real world experience, or even a passion for development. It was like doing a school exam, where you just need to memorise facts and figures. No personality or creativity is permitted, because it's not part of the marking scheme. The whole process put me off wanting to work there, and I ended up turning them down.

I can top that

[NotSoHeavyD3]

I had an interview that was straight out of Seinfeld or something. I had a lunch interview. We went to the cafeteria, got something to eat and then went to a conference room so they could interview me while we ate lunch. Simple, right?

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.)

Read the book

[null etc.]

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

[allo]

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.