Follow Slashdot stories on Twitter

 



Forgot your password?
typodupeerror
Get HideMyAss! VPN, PC Mag's Top 10 VPNs of 2016 for 55% off for a Limited Time ×
Programming

The 'Trick' To Algorithmic Coding Interview Questions (dice.com) 208

Nerval's Lobster writes: Ah, the famous "Google-style" algorithmic coding interview. If you've never had one of these interviews before, the idea is to see if you can write code that's not only correct, but efficient, too. You can expect to spend lots of time diagramming data structures and talking about big O notation. Popular hits include "reverse a linked list in place," "balance a binary search tree," and "find the missing number in an array." Like it or not, a "Google-style" coding interview may stand between you and your next job, so it's in your interest to figure out how to deal with it. Parker Phinney, founder of Interview Cake, uses a Dice column to break down a variety of example problems and then solve them. But it's not just about mastering the most common kinds of problems by rote memorization; it's also about recognizing the patterns that underlie those problems.
This discussion has been archived. No new comments can be posted.

The 'Trick' To Algorithmic Coding Interview Questions

Comments Filter:
  • by Nidi62 ( 1525137 ) on Friday November 06, 2015 @03:38PM (#50879229)
    Get a job at Google using this one weird trick!
    • by creimer ( 824291 ) on Friday November 06, 2015 @03:51PM (#50879315) Homepage
      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.
      • No offense, but why the hell would you want to work there without being an engineer and getting the stock options?

        • by tlambert ( 566799 ) on Friday November 06, 2015 @04:49PM (#50879737)

          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.

        • by creimer ( 824291 ) on Friday November 06, 2015 @05:05PM (#50879885) Homepage
          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.
          • 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.

        • by Darinbob ( 1142669 ) on Saturday November 07, 2015 @05:18AM (#50882197)

          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.

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

    • My thoughts exactly. Memorize a few basic loops and see if you can deliver Google the Big O? Welcome to our team.
  • Learn the 40 examples in TFA off by heart
    • Re:TL;DR? (Score:5, Informative)

      by lgw ( 121541 ) on Friday November 06, 2015 @04:20PM (#50879481) Journal

      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.

      • by tlambert ( 566799 ) on Friday November 06, 2015 @04:57PM (#50879815)

        I use problems related to real problems I've worked on in my career. I find that's a better way to reliably sort candidates.

        I find that the best way to sort candidates is to use a "sorting hat". Mostly I try to hire hire Ravenclaw. Unless it's a help desk position; then it's almost always a Hufflepuff.

      • Re:TL;DR? (Score:4, Insightful)

        by Spazmania ( 174582 ) on Friday November 06, 2015 @05:21PM (#50880039) Homepage

        The last time I was asked to work an algorithm on a whiteboard during an interview, I straight up said: I'm not comfortable tackling this in a 45 minute interview.

        I did not get the job, but I went on to get a better job where I was given hard problems and expected to actually think them before solving them, without any need for a frenetic rush.

        • Re:TL;DR? (Score:4, Insightful)

          by lgw ( 121541 ) on Friday November 06, 2015 @07:29PM (#50880817) Journal

          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.

          • by KGIII ( 973947 )

            I did my own initial code with the help of a comp sci grad. Eventually, we grew to the point where I was no longer able to do everything and things got increasingly complex - more than my ability, or were working in that direction. The first couple of hires came from people with a proven track record in a related field (they were in the transportation engineering realm - similar enough). After that, I had them sit in on the interviews - that's the person they'd be working with, after all. I also figured it

        • Re:TL;DR? (Score:5, Insightful)

          by TheGratefulNet ( 143330 ) on Saturday November 07, 2015 @01:45AM (#50881877)

          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.

      • 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

      • 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).
        • by lgw ( 121541 )

          Well, I want to know if you will write decent code under pressure (as in, the second half of every coding project). Even small examples are enough to see whether you talked through the design and asked questions before diving in, whether errors are handled or even checked for, etc, etc. Coding style shines through even small problems (as long as they're nontrivial).

          What you can't measure is the stuff the IDE really does for you. There's nothing worse than "compiler trivial pursuit" -style questions, alth

      • Re:TL;DR? (Score:5, Insightful)

        by Darinbob ( 1142669 ) on Saturday November 07, 2015 @05:58AM (#50882245)

        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.

        • by lgw ( 121541 )

          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.

  • by creimer ( 824291 ) on Friday November 06, 2015 @03:46PM (#50879285) Homepage

    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.

    • by tomhath ( 637240 )
      Use my awesome statistics background to make book on who will win?
    • by ClickOnThis ( 137803 ) on Saturday November 07, 2015 @01:14AM (#50881823) Journal

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

    • by antdude ( 79039 )

      Were those keyboards, Model M, too?

  • by nimbius ( 983462 ) on Friday November 06, 2015 @04:02PM (#50879391) Homepage
    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.
    • by TWX ( 665546 )
      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: (Score:2, Funny)

        >> questions are all written in advance in the committee-based interview process, and anyone could potentially ask any kind of question. The twenty-two year old secretary could ask the interviewee [TOPIC], even if she has no idea what she even said

        Did you just tell us that you work for CNBC?

    • performance under stress.

      Why is "performance under stress" a relevant metric? I do almost all my coding alone in a quiet office, and can't imagine a realistic situation that would have someone looking over my shoulder and telling me to hurry up.

      When I conduct interviews, I try to remove the stress. I give the candidate a test problem, and a quiet cubicle to work in. Then I come back in 30 minutes and ask them to show me their solution. If you only test them on a whiteboard, in front of a nitpicking audience, you are just weedin

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

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

      • by cdrudge ( 68377 )

        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 dem

        • by ShanghaiBill ( 739463 ) on Friday November 06, 2015 @06:20PM (#50880455)

          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.

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

      • by creimer ( 824291 )

        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.

      • by KGIII ( 973947 )

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

      • by dwater ( 72834 )

        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'

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

      • by SuperKendall ( 25149 ) on Friday November 06, 2015 @05:56PM (#50880325)

        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.

      • 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

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

      • by gweihir ( 88907 )

        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

    • by swb ( 14022 )

      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

      • by creimer ( 824291 )
        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.
  • by fahrbot-bot ( 874524 ) on Friday November 06, 2015 @04:03PM (#50879399)

    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.

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

    • by jafac ( 1449 )

      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.

    • by gweihir ( 88907 )

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

  • by gstoddart ( 321705 ) on Friday November 06, 2015 @04:06PM (#50879411) Homepage

    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.

    • by Anonymous Coward on Friday November 06, 2015 @06:31PM (#50880513)

      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/

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

  • by Dino ( 9081 ) * <john.holmes.deanNO@SPAMgmail.com> on Friday November 06, 2015 @04:11PM (#50879437) Homepage

    Be able to understand and evaluate Big-O notation and use hash maps and sets. Which if you don't already know, you should!

  • Not just google (Score:5, Informative)

    by Locke2005 ( 849178 ) on Friday November 06, 2015 @04:19PM (#50879471)
    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.
    • 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...

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

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

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

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

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

        • by creimer ( 824291 )

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

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

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

          • Hm, today it is the other way around.
            People are reinventing linked lists, not knowing that there is a library.

            What you call 'custom data structure' might as well be a 'domain model'.

            Actually I myself never stumbled over linked list libraries etc. before Rogue Wave started selling its data structure libraries and 10 years later the STL emerged.

            Neither during my Pascal, nor my Modula II nor during my early C times (1987 - 1995) I ever had the option to use a general purpose library of data structures.

            Well, th

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

  • Truly sad (Score:4, Interesting)

    by gnasher719 ( 869701 ) on Friday November 06, 2015 @04:33PM (#50879589)
    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.
  • by RoccamOccam ( 953524 ) on Friday November 06, 2015 @04:36PM (#50879613)

    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.

  • by JoeMerchant ( 803320 ) on Friday November 06, 2015 @04:38PM (#50879627)

    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.

  • by 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?

  • by wonkey_monkey ( 2592601 ) on Friday November 06, 2015 @04:55PM (#50879787) Homepage

    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.

    • by Xyrus ( 755017 )

      These questions are stupid and pointless. Unless you're an academic most programmers had to learn these algorithms once to pass a class. After that they use libraries for the respective language they're programming in.

      I'm not interested if you can pound out a quicksort from memory. I'm interested in whether or not you know how to use sorting and apply it correctly to do the damn job I'm hiring you for.

      Show me your previous work. Demonstrate a program you wrote. Show me your code and explain it. That will te

  • by Anonymous Coward on Friday November 06, 2015 @05:01PM (#50879855)

    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.

    • by hey! ( 33014 ) on Friday November 06, 2015 @06:33PM (#50880533) Homepage Journal

      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.

    • by ndykman ( 659315 )

      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

    • by tgv ( 254536 )

      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.

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

  • by gweihir ( 88907 ) on Saturday November 07, 2015 @12:23AM (#50881707)

    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.

  • Code tests like these are here to stay for a while at least, anyway. They serve some sort of purpose, and, as a somewhat experienced programmer, sometimes it's fun to tackle an academic problem like these.

    But, you go and practice your "kata", now what? You have some code, it does the job, but what will an interviewer actually think?

    If you want some feedback on that, take your (working) code over to Code Review http://codereview.stackexchang... [stackexchange.com] and have some objective folk critique it.

    Practice without feedba

My sister opened a computer store in Hawaii. She sells C shells down by the seashore.

Working...