Google does not have just one hiring committee, and anyone can be on hiring committees if they want to and one of the committees has a need of new members (IE it's not invite only).
So this is like saying "ex-Python-dev mailing list member".
Actually, it was invite-only when I was there. But that's sort of besides the point. It's irrelevant whether or not it's an "honor" to be on the hiring committee. The point is that being on the hiring committee does give you some insight as to why people tend to get rejected. Without being on the hiring committee, you really only see why you're rejecting people -- smaller sample size, biased, less diversity of questions, etc. But, for hiring committee members, you see the results of many people's interviews.
I'm on 3 of our hiring committees, and i've been at google for over 6 years. It hasn't been invite only for as long i've been here, AFAIK. Either that, or I was secretly invited!
It is irrelevant whether it's an honor, but as to whether it gives you insight, you are generally right but you did miss an important point:
The vast majority of people who are "members" of a given hiring committee often don't show up every week.
A lot, in fact, show up never, but are still members.
(for example, they were part of it years ago and nobody removed them, they got asked, said yes, never actually did anything, etc)
So while you are correct that it does give you some insight if you actively participated, simply being a "member" of a hiring committee is a necessary but not sufficient condition to say that you have that insight.
That doesn't seem to be a point missed so much as one that's obvious and generally unnecessary to state fully qualified descriptions of everything in casual conversation.
A lie of omission would apply if you state a selection of true facts and ignore other ones so as to make yourself look better than you are.
In this case, I'm stating that I was a hiring committee member and not saying that I attended regularly, when I in fact did. This is not a lie of omission. At worst, you could accuse me of not offering additional qualifications.
I was in Seattle / Kirkland, and it was invite only there. I showed up every week (as did the vast majority of the Kirkland HC).
But, yes, I could have been more extensive in my credentials. Unfortunately, "How to Crack the Toughest Coding Interviews by ex-Google engineer, ex-Google hiring committee member who showed up every week, ex-Apple dev, ex-Microsoft dev, author of Cracking the Coding Interview, and author of The Google Resume" was a bit too long :).
You can also crack the toughest coding interviews by being a good coder who has created cool things and completed some challenging coding projects. You could also review the stuff you learned in algorithms right before your interview.
I'm not worried about losing a potential job because I couldn't crack some obscure mind puzzle.
You can be an excellent coder and suck at interviews. This post has nothing to do with hard skills about algorithms, and everything to do with how you present your work. A lot of good coders might miss out on jobs they want because this is an unusual situation they werent prepared for.
A very fair point about talent at doing a job and talent at explaining the job in interviews. The term interview technique is like exam technique and in that is something that abstracts from doing the actual job. Unless that job entails interviewing people. With that this is probably a better read.
Alot of people who fall into the boat of being good coders with social skills of dead fish often have a hard time. One appraoch is to create some wonderous application and get broaght out, recruitment that way. Or in the process, end up refining there social skills to the stage that not only can they interview ok but are running there own company.
Coding interviews should be done via a shared terminal/IDE screen and chat windows, that approach would be more realistic to some. But I'm one of those people who don't socialise too well at times, interviews/exams, that type of thing.
I've interviewed a lot of people (at Microsoft). I don't claim to be good at it, I think that I do OK, but that's why one interviewers opinion should never be the be all.
I've definitely encountered people who were clearly good, and equally clearly sucked at interviewing, as an interviewer I had to ask myself the question "why?"
I encountered the following cases (among others)...
The ill-prepared - This may come down to background, some candidates didn't seem to know that they should prepare for an interview - this can be excusable, but in a world where advice about this is one web-search away is increasingly tough. Usually (but not always) this is a barrier to recommending hire.
The chronically nervous - This is always at least 50% my fault. I believe in asymmetric responsibility, as the person with more "power" in the situation, I feel part of my job is to help a candidate past their nerves; if this means my interview is entirely spent putting them at their ease to (potentially) do better with the next person in line, so be it. This has rarely been a barrier to recommending a hire.
The arrogant - "I can't believe you asked me such a demeaning coding question when I'm applying for a senior role, clearly my resume tells you all you need to know about my coding chops" - sorry, if I can't pierce this, no hire.
The inarticulate - often in this case the code speaks, even if the candidate can't, I usually associate this with nerves, sometimes it is language issues, sometimes stress sensitive speech impediments. I'm pretty sympathetic to this if the code speaks, but communication is part of the role so this is always a judgement call.
Can't code on a whiteboard - I'm inclined to call this ill-prepared, you should expect to have to do this coming into the interview, but I do get that this is equivalent and opposite from "inarticulate" - I will take a coherent and detailed description of a solution as being nearly as good as the whiteboard code, but there is a bottom line, you have to be able to show me your ability - sometimes one really insightful question or observation is all that it takes...
In more recent interviews, companies I've worked at have had the candidate sit at a laptop and essentially pair program with the interviewer.
This avoids avoid that artificial write code as fast as you can with a whiteboard marker situation. Granted, it's not their regular dev setup and it's probably an unfamiliar keyboard and trackpad, but it seems to be better than the alternative.
I interviewed with one of the company where the first two screening round consisted of pair programming (in person, on university campus) on my own laptop. I think that was the best way to conduct interviews. Much better than the phone screens.
As an interviewer, it always surprised me how little people would prepare for an interview.
For every interview I have done as an interviewee I have studied what I am likely to be asked, what their interview technique is, boned up on the language(s) in question, and tried to think of some interesting questions to ask the interviewer (the last one also includes learning as much as I can about the company and its history). I think these are the basics any interviewee should do - that's just the bare minimum for the big guys. For Google I was pulling out dusty old CS books and revising CS theory and that was still just barely enough preparation.
Meanwhile I've given interviews for a C++ position where the candidate hasn't even had a quick brush up on C++ recently. I've had candidates who do C++ as their JOB and not know how to initialize memory, someone describe "polyformic" behavior, and had a good 75% not know at all how virtual functions work. It blows me away.
I've never studied for an interview. I guess I have some internal feeling that you should hire me based on what I know...not what I crammed for the night(s) before an interview.
Or maybe it's confidence? I don't know. I've been programming professionally for over 10 years. I think I should be able to sit down and work out almost any problem in an interview.
I've definitely been to interviews where I ran into issues and didn't get offers, but I've also been to interviews where I ran into problems and did get offers.
I guess, in my gut, I feel like studying for an interview is cheating a bit. It might not be the right outlook, but it's something I can't shake.
I think this is an interesting one, I might make a distinction between studying and preparing. Working through some interview questions as an exercise in intentional practice provides a different type of preparedness from trying to cram CS theory that you don't truly grok. I think that the former helps you manage the unfamiliar interview scenario better, the latter can lead to you digging huge holes when you start talking about something that you don't know much about.
There is also a difference between an experienced industry hire - as you say, if you've been doing this for 10 years you can go into an interview and show them a pretty good picture of what they are getting - and a less experienced or campus hire, where what is important might be an expression of potential - the practice helps with letting the interviewer see that, if your interview is the first time you've tried to code at a whiteboard, or solve a problem with someone trying to push you to the edge of your comfort zone, then you are doing yourself a disservice.
I have, however, encountered candidates who just didn't know, they didn't go to a top school (or indeed any school), they haven't worked in this environment, they don't have any understanding of what to expect - even the simple web-search that would have warned them requires some level of a priori knowledge - not every candidate has that - I suspect most of these candidates do badly, but just watching how someone learns through a day of interviews tells you something, that higher level bit about learning when in over your head is one of the most valuable.
ok, one question: certainly you guys are great coders to be in working in these companies, but is every single person there for sure going to give the best possible answer to these questions every single time if asked?
Interviews work both ways - what questions do you ask them?
One I used to ask was do you have IS9002/BS5750, but that was 15 years ago and there are better questions to ask. A good question is also sometimes better than a good answear as it shows you understand things from another perspective and have the ability to ask questions instead of blindly accepting what you are told all the time if your unsure.
So what are your favorite questions and not how much TAX did the company pay type questions, the ones that give you lots of wonderous information and yet still puts them on there toes a bit as well if they are weak in some area's of managment/running the company of methodology. I asked what Q&A methodologies do you use in a interview once for a company called RIM; Was not a great answear. My question about IS9002/BS5750 was one which showed how well organised the company was at the job in hand and how well documented the role was. The answear tells you what kind of mess your getting into and also if you should be asking for more money (danger money if its somebodies spagbowl code/system :).
So what questions as a programmer do you ask the company in an interview, that is applying for your service. Anybody have one they care to share?
Now ticketing, that reminds me of the ITIL standards and reamedy fun (slang for nightmares). If a company has ITIL I always ask them what proactive support measures do you have in place, always a good question that as ITIL is in essence more reactionary/event driven and as such does not lend itself well by design for catering for proactivity. I was in a server room once, smelt burned solder type smell, traced to a server that smelt like something had blown. All services/diagnostics/monitoring checked out fine and indeed it was working fine. I wanted to plan a changing of the server/have a hot standby ready for it being proactive as literly something smelt wrong. Alas the ticketing system did not alow such a ticket to be rasied as the server was not faulty and there was no issue showing. Two days later that very server failed, turned out PSU had died and taken out the raid controller on the motherboard in the process. The impact of this was more work than had it not been proactivly addressed. That is why when they say ITIL, then I fear how it is implemented and as such ask how do they proactivly deal issues. At the very least they should have root cause analysis mentioned, idealy they will sing all about there great Q&A processes and how that is all catered though open to suggestions.
Your right about the canned marketing responses, most of those forget the interview is a two-way process sadly and deem any question you ask as a waste of there time, that is a sign you should take note of.
You have to be more sneaky. Rather than asking something as generic as
>What's it like working here?
ask them
>What do you like the most about working here?
If they give you something like "the stability" or "the high pay" those are generally bad signs. Better signs would for example be "the great people I get to work with every day" or "the autonomy to get to choose what I work on".
Very true, looking at the types and state of the cars in there car park and haveing a chat with the smoking cabals outside fire exits is often a easier way to get a answear to some degree.
But indirectly asking questions is the way and it is those clever ways that are the types of questions i'm realy interested in, like my question about ISO/BS standards, it opend them up to so much more than a simple yes and no and gives you insight into other area's. Like working conditions, are they documented well, badly, not at all, do they even know about those standards, is it something there looking at (often crops up that last answear on many area's sadly).
Is the pay individual perofmance based or team based and is it limited/capped in that if I do 200% better am I capped at some rate of inflation % rise anyhow. I also like to ask about problems, what was the worst day like this past year and why and how likely is that to happen again. That tells you alot about so many area's and also opens them up into telling you how it is as well as allowing you to highlight your relevant skills and chip in with did you try this or that at the right times, even if you agree and play noddy whilst they talk.
One I always ask is can I have a look around the office, the area were I would be working if I was to be offered a position. That is useful in guaging there interest as if they are not interested they will come up with a reason why they can't do that, if they are keen for that you can see what your dealing with and also get a good feel from the way others have there desks decorated. Be they anal, stuffed south park toys, simpsons posters, collection of 2600 mags. Those type of things, you can get a feel on many levels from that.
Asking them how long they have been there is another good one, longer the better, but if they sound bitter then you can take that as not a good sign as well. Though if there two hyper only been there few months then they are sadly not realy able to give you a a true picture, so again take advantage of there hyper still all new to me as well fun happy time mood and take a look around.
Or you can ask it along the lines of, what changes good and bad have you experienced in your working enviroment over your time here. If they can't list something in either then I'm usualy wary, most will at least complain about the canteen or some change, even if cheaper coffee. Though if there is no good changes and no bad changes they can think of then it does sound like it could be a boring company.
That's a nice play on the "What are you biggest strengths and weaknesses" interview question, in reverse. The only problem with that -- as we've been conditioned over the years of being asked this stupid question -- is to list a strength as a weakness (http://jobsearch.about.com/od/interviewquestionsanswers/qt/w...) so you don't actually get much meaningful information (other than maybe subtle red flags, like "stability" or "benefits are good", as someone mentioned).
If they are being dicks and I'm certain I don't want to work with them, I would ask a coding interview question back. It was a while ago, but still got an offer this way :)
The 100 questions article does mention Joel's test. I think the Joel test is mostly obsolete (it is 12 years old after all), but the obsolete parts of it can usually be fixed with either a more precise or more fuzzy question that the 100 questions may offer you so you don't need to come up with it on your own. e.g. on hallway usability tests, I think you learn more from a general "do you test the UI for usability?" which may indicate hallway tests, A/B testing, alpha or beta users, or even a response of "No, we know what works and the user will love it (and bend to our will if they don't) and companies that imitate us will get sued".
A good way to ask questions is to use them conversationally. For example:
interviewer: What is Cassandra useful for?
interviewee: It's useful as a highly-available database if you can denormalize your data. What are you guys using Cassandra for?
interviewer: Well, we're using it to...
interviewee: Interesting. How's that working for you guys?
This not only can get you some valuable information to make your decision, but also looks confident as you're exercising some control over the interview. You just have to be careful not to derail the interview with this technique, or you'll come off cocky and arrogant.
I ask some questions about test coverage, coding standards, code reviews.. I'm sometimes more interested in whether I get the same answers from different people or not than the particulars.
I always ask for an example of a technical or tools decision that was made. I'm usually looking to see whether decision-making is well distributed or things get bottlenecked by a manage or lead.
Probably most of all I pick at how the organization decides what to build. I'll ask about features or products that have been sunset or rehashed, how requirements are discovered and communicated. How prioritization works. One of the easiest ways to get red flags here when applying for a spot on a team is to ask everyone I interview with what the team is currently working on. A large variety of answers makes me nervous.
Oh, and also big points off for "Yes" to the following:
- Do you have an exchange server?
- Do you have a sales team?
- Is the person who makes the purchase decision for your product your primary user?
If customers need to call in and speak to engineers or other non-business people to negotiate sales, that sucks. Having inbound sales people is a vital part of any good mid-sized company.
If you need humans to sell things, then of course I agree that you ought to have a sales team. I would just rather work somewhere that doesn't need humans to sell things.
The problem I have with sales is that they're often very good at what they do. Once you have sales, you have two products. Your sales folks, and the thing people think they're paying you for. It gets hard to know which one is failing, or worse.. succeeding.
At some point if your company is any good, you WILL need humans to sell things. People will want to call in for more information, and the job of the person taking that informational call is to convert them. Unless you're Google where you don't give a hoot.
Not everyone is secure with a "F you, sign up online or else" policy. Good salespeople with domain expertise can be exceedingly helpful at introducing direction to the company - not just automatons who sell things.
Essentially it seems to build down to knowledge of data structures and the ability to use them in concert to develop solutions on a whiteboard. There's more to it than that, but being able to code without an IDE is critical.
The "choo choo choo" people make my skin crawl. Not sure why. It could be subconscious because everyone I've met in life who did that was not good for my career to associate with them.
A few days ago I finally realized why they said I'm not good enough at big-O to play with them (despite saying my coding was excellent). For some reason I had a mental block that day and wanted to implement hash tables as prefix trees every single fucking time.
I have no idea why. Of course I know a hash table is O(1), but for some reason, that day, I kept trying to convince everyone it should be O(N) (N=length of key) because it's implemented as a prefix tree in the background.
Hm? Hashing is O(N) unless it's oblivious to some bits. Though the prefix tree part is optional, yes. :-) Better luck next time.
(For some reason programmers really love tries / prefix trees when answering on stackoverflow and such. I'd like to understand why -- tries are neat, but you don't see them nearly as much in actual use.)
> Hashing is O(N) unless it's oblivious to some bits.
O(N) only makes sense when you agree on what N means. When using big-O notation, always make sure you agree on the base N values you want to work with. In this case, it sounds like you interpreted N as the number of bits to hash, in which case yes, any sensible hash algorithm has to look at all the bits so it'll use an O(N) algorithm. However, the post you replied to talked about hash tables, a structure used to implement (among other things) maps from keys to values. For such a structure, N refers to the number of items stored in the table; hash tables have the rather unique property of supporting O(1) insertion, removal, and lookups (modulo amortization arguments about the size of the table).
Well put. I'd like to add that, while hashing time is proportional to the key length, in practice it's very, very fast for all non-enormous keys, at least on modern processors. Compare with the cost of pointer-chasing in a tree, and hashing time starts to look pretty constant-ish.
(Yes I'm handwaving around the details. So is everyone who talks about big-O notation in connection with real software.)
Just my two cents,
Well hash tables might be O(1), but depending on the circumstance they are used in, how they handle collisions, implementation details and the quality of the hashing algorithm they can see real world performance that is not O(1). Inserting into a hash table can cause the hash table to expand, if the hash table is too small you will get collisions, etc. etc. Some choices of hash functions are actual O(n) instead of O(1). Sometimes hash tables are not appropriate due to the memory requirements. You get the idea.
I actually like people to point these things out, even if the amortized cost is constant in lots of real world usage. When talking about time complexity I appreciate attention to detail, rather then just hand waving and saying its constant. My answer is always, 'well it depends'.
Be careful though, back up your answers in a way that shows you do know what you are doing. Otherwise you can come off as blowing smoke.
Truly understanding writing performance critical code is a black art, and you need to understand more then just the big O of some common algorithms. Showing that you know that performance and complexity are hard and you know there are hidden costs that can bite you and tradeoffs you have to take into account shows maturity.
But the answer most certainly isn't "Well I don't know _exactly_ how python does dictionaries, but I would implement them with a prefix tree and there is nothing better". Which is roughly the answer I gave, in different settings. To five interviewers.
> Some choices of hash functions are actual O(n) instead of O(1)
I think you're getting your n's confused. O(n) in the context of a collection applies to the size of the collection, not the size of the keys. Nearly all hash functions for strings are O(n) in the size of the string. This doesn't mean the hash table is O(n) for lookups.
My point is the whole process needs to be taken into consideration when talking about performance and runtime complexity. If you just use the address of an object for the hash, that has a implication to performance. If you choose a cryptographic function, that has another implication. If you use something like cityhash, that has yet another.
If you use rehashing or a linked list to handle collisions that has another impact on the performance depending on what is going on.
If you choose to auto grow the hash table upon a certain number of collisions, this is another thing you have to worry about.
The process of lookup might use a precalculated cache of the hash code calculation if it is expensive and sacrifice some memory for this storage.
My point of all these examples is that the simple runtime of the collection isn't the whole story and lots of crap can happen under the covers. We stand on the shoulders of giants, but we have to know what weaknesses and strengths we are exploiting. While just picking the right data (or wrong) structure makes a huge impact, you need a lifetime of experience to really know what matters, and what the trade off of one or another is in a given scenario. Hard to test for that intuition and I always like people that interview with me that start talking about these sorts of issues.
A hash table lookup is O(n), where n is the number of elements in the table. They have amortized constant time lookup (i.e. constant time in the average case).
If you use a balanced tree instead of chaining or probing, sure. But, of course, nobody ever does that in practice, because the complexity isn't justified by the theoretical gains.
Point was, worst-case time complexity isn't constant. I'd be happy to see more people get that right in interviews.
Hash tables, in general, have average constant time lookup. Only some hash tables have amortized constant time lookup.
An amortized bound is a bound on the total cost of a sequence of operations. Loosely speaking, it guarantees that you can't keep hitting the worst case indefinitely. An average bound is averaged over all possible inputs, but doesn't protect you against hitting the worst case over and over.
“Describe how you would implement the tinyurl.com website.” preferably without realising you have the technical skills to do far better on your own than wage-slaving yourself for us.
Consultants are asked case studies. Writers are asked to write something (or submit writing samples). Actors are asked to audition. And programmers are asked to program.
Why shouldn't you validate if a programmer is, in fact, a good programmer (which is a mix of many things, including intelligence)?
Because for programmers what they are asked to do in the interview can (and often is) very different from what they have to do on the job.
Unless your job is to reverse strings on the whiteboard.
whiteboarding perfect syntax, delving into absurd language minutia and "gotchas", f'ing around w/ brain teasers while an interviewer introduces behavioral stressors (sighs, ticks, etc.) to see how i problem solve "under pressure" ...is all bullshit.
so yeah, ask me to program. i mean, srsly program. let's hack together for an afternoon; hell, let's do a full day of paired programming to knock out a small bug in your code base. you'll learn a hell of a lot more about what i know, how i communicate, steps i take when i do when i don't know something, and what my processes are. this soft, inter-engineer-social stuff is overlooked over far too often; i wan't to work with people who will amplify my process and abilities, and in turn i'll amplify theirs. smarts don't count for enough.
I don't think this approach would scale, due to the time investment required. It also suffers from making it hard to compare one candidate to another in a fair way, unless you have everyone fix the same bugs. Having a bunch of canned bugs to be fixed doesn't seem much better than asking a CS puzzle.
I am not saying that programmers should not be validated. Interview questions that are like IQ tests that depend heavily on single spark of inspiration are poor validators of determining productive programmers.
Actually, how well people do on one of these questions seems to correlate strongly with how well they do on others, so saying that each question depends strongly on a single spark of inspiration is kind of misleading. Where do those sparks of inspiration come from? And why do some people seem to vary so much in their ability to conjure them up on demand?
"whiteboarding perfect syntax, delving into absurd language minutia and "gotchas", f'ing around w/ brain teasers while an interviewer introduces behavioral stressors (sighs, ticks, etc.) to see how i problem solve "under pressure" ...is all bullshit."
Agreed. That would be bullshit. And those are bad interviewers if they do any of that. Companies like Microsoft, Google, Amazon, and Facebook don't do that, as a general rule. I'm sure you could find bad interviewers at any company though.
Alright. Let's assume we have this guy, we'll call him a... oh, I dunno, a salesperson. And there are all these cities he must visit to sell his wares. BUT, oh-ho, there's a catch! Let me tell you how many times he can visit each city...
Of the 4, only one is asked to do what they do during the interview. Event writers submit existing copy. Or at the very least, prepare it ahead of time before submitting it. Actors auditioning know what they are auditioning for before hand. They can prepare.
Programmers, however, must take a test. It's not an interview, it's a test. Pass or fail (regardless of what people say), it's a test. It's a test of which you have little preparation for. You hope that what they are looking for is what you can provide. What they are asking for is what they will test for (this is fairly often not the case).
Another piece of advice: Think carefully and don't assume that the obvious algorithm is the best one. Interviewers will usually be satisfied if you notice that they're describing an instance of 3SUM and give them the obvious O(n^2) solution; they'll be impressed if you notice that the problem they're describing is actually a dense special case and can be solved faster using an FFT-based convolution.
Indeed, sometimes the question is silly and you should not be afriad to question it. I was once asked about video conferencing in detail for some task and explained that recording via VCR and sending the output via tape would be more suitable and cost effective for what they were trying to use it for. You have to look at the initial question and peel of the layers until you find the reason for the question and then you can address the true problem. Sometimes somebody will ask how to computerise this and you will ook at it and sometimes find yourself asking how does it work now and again sometimes saying that what they have is already better or as good as a computerised system to that problem.
In this cube land question you can answear, how are you defining the centre and just revering that process will already give you the code you require. What they are doing you don't know so you have to ask, may be they are trying to reinvent a wheel and with that the best answear may be how to draw a circle as there question is flawed. This is the problem with made up interview questions, if they are based upon real world experience then you get a good question that you can truely answear. You may have a better answear or approach which with them having lived it, makes enough sence to know you would of saved them 2 days debugging that problem and thats from a quick chat walking of the street. If it is a made up question then your approach and alternative answear can be missed and ignored and your genius is not appreicieated.
Perhaps they're assuming that the cube is a set of integral points and they want you to count lattice paths. This is trivial in 2-space (e.g., give me the number of paths that go from (0,0) to (5,5) by going only up or right one point with each move (that is, each move is either (0,1) or (1,0))). However, I vaguely recall counting lattice paths in 3-space being a wickedly hard problem with no known polynomial time solution. Could be completely wrong on that, though, and don't feel like looking it up just now.
You could of course write a program that would solve it (trivially), but it might take exponential time :)
Of course, the phrasing doesn't say they have to be lattice paths, so perhaps we can say a countably infinite number of paths of we're only considering integral (or rational) points and have no direction invariant. Uncountably many if we're allowing the reals. Still uncountably many if we allow the reals and have a directional invariant. We reach the realm of a finite solution if it's a finite set of points and we have a directional invariant or another constraint (e.g., the path might be prohibited from visiting any given point more than once). Most of these are still completely intractable as far as I know :)
I assumed it was intentionally ambiguous (like a lot of problem statements in practice), to see how the interviewees respond. There are a few interesting interpretations, some of which are obviously exponential time, infinite time, or impossible (ie uncountably many solutions).
In n-space the problem is almost as easy as in 2-space if you can only go in forward in each dimension. If you can go in both directions and you want to find the number of non self intersecting paths, the problem is hard even in 2-space (as far as I can tell). If you allow paths to be self-intersecting, then the count is obviously infinite. Note that the actual interview question asks you to list all paths, not count them.
To count paths in 2-space from (0,0) to (5,6), you have the operations "X++" and "Y++" which go right and up, respectively. Each increasing path from (0,0) to (5,6) has to be some permutation of 5 times X++ and 6 times Y++. So the count is (5+6)!/(5!6!) where the exclamation mark denotes factorial. This extends to higher dimensions by adding an additional operation "Z++". Then the count to go from (0,0,0) to (5,6,7) is (5+6+7)!/(5!6!7!).
You're assuming that all movement must be in one of three directions, but in general, you can go in six directions -- forward or backward along the x, y, and z axes. Your cubic-time DP algorithm doesn't solve the self-avoiding walk problem, which I think is what jsolson vagely recalls.
I wasn't assuming, I was following what the OP wrote: "by going only up or right one point with each move (that is, each move is either (0,1) or (1,0)))" for 3D.
If you follow the links, this was asked to someone interviewing for a job on the Windows team who then posted it to an interview question aggregator, so it's likely that the actual phrasing of the question was lost.
But as best as I can tell, they're considering each 1x1x1 space to be a node like a Rubix cube, and they want a list of all possible paths from the center node to the surface. I imagine that half of the question is making sure that the interviewee presses for details, because there's plenty of problems I see with the question right off the bat. If n is even, there's no single center node, so where does the algorithm start? Can the algorithm traverse diagonally by edges, or only by adjacent faces? Not to mention that there's an infinite number of possible paths for some values of n, assuming paths can cross themselves, for the same reason that there's an infinite number of paths from my front door to my car if I feel like walking in circles for a while.
The first thing I thought was , this may be a trick question, since there are an infinite number of paths from the center to the surface. I think the problem statement needs a bit more detail.
I got that book. While the questions and answers are useful, in my experience this book alone is nowhere near enough to get prepared for a Google interview (not that the author claims that).
I studied CLRS's Introduction to Algorithms and a couple of other books for about 2 months. Even then I could not answer the hardest questions during the onsite interview. And if you cannot come up with an optimal algorithm for a given problem, all of the items mentioned in the article (communication, clear coding, testing) don't really matter.
>And if you cannot come up with an optimal algorithm for a given problem, all of the items mentioned in the article (communication, clear coding, testing) don't really matter.
That's just not true and if any company is only interested in whether or not I can generate a correct answer under pressure in 20 minutes, then I'm not interested in working for you.
You seem to be disagreeing with something I haven't said.
I'm simply describing my experience interviewing at Google: I didn't give an optimal solution to a couple of problems, and didn't get an offer. So I infer that the other items mentioned in the article don't matter as much for getting a job at Google.
You also did not wear a pink and blue striped hat, and did not get an offer. And yet, you seem to not connect your failure to wear a pink and blue striped hat with your failure to get an offer.
I'd suggest you read the section in the article about how you're evaluated. Yes, how optimal your solution is matters -- of course it does. This doesn't mean that you have to get an optimal answer though. You have to do better than the majority of candidates (maybe ~80% of candidates).
For some problems, being in the top 20% of candidate will mean getting the optimal solution. In other cases, it may not. The optimal algorithm might be trivial, and it might be more about coding skills. In another problem, it might be totally unrealistic to expect that a candidate needs to get the optimal algorithm.
Additionally, you seem to assume that since (according to you) getting the optimal answer is necessary, that it must also be a sufficient condition. That's obviously false. It's entirely possible that a candidate needs to get the optimal answer AND implement it well, in which case these other factors come into play.
> You also did not wear a pink and blue striped hat, and did not get an offer.
I don't understand the point of this quibbling.
Say I was asked 30 questions; I missed 3 of them and didn't get hired. It's a reasonable to assume that these 3 questions were considered important in the general assessment.
> You have to do better than the majority of candidates (maybe ~80% of candidates).
I know, I said I read your book. ;-)
But that doesn't substantially change the story, it means it's likely other candidates got the optimal solution or got closer to it.
Of course this is all based on my self-assessment, since Google doesn't provide any sort of feedback post-interview. But I'm pretty confident that I went well in the other questions. 4 out of 5 interviewers were pretty nice in giving feedback during the interview, even if indirectly. E.g. they'd ask progressively more involved questions on the same topic, so I more or less knew when I had answered the previous questions correctly.
> Additionally, you seem to assume that since (according to you) getting the optimal answer is necessary, that it must also be a sufficient condition. That's obviously false.
No, I haven't made any such assumption. I only assume that getting the optimal answer was the "high bit" in my case.
Apparently this works for Google, and unlike other people who have failed to get the grapes, I don't call them sour.
You weren't just asked 30 questions. You were asked 30 questions and evaluated on dozens of other non-answer based factors.
Imagine: I walk in, get 27/30 and then proceed to be a sexist bigot who says I refuse to work on a team with gays or women and I decide to start claiming that you have to get 100% to get hired.
I'm not saying you did something like that, but you're just automatically assuming that that question was the pinnacle of your rejection and not the other things listed.
I mean, unless you've been implicitly implying that you're a perfect interviewer minus the 3/30 you missed...
"Say I was asked 30 questions; I missed 3 of them and didn't get hired. It's a reasonable to assume that these 3 questions were considered important in the general assessment."
That would be true if those answers were assess on a strictly correct / incorrect basis AND those were the only things you were assessed on. Neither of those are true though in this case.
It's very possible that the questions where you didn't get an optimal answer you actually did very well on. And that there are other questions where you got the optimal answer, but it took you too long or you made too many mistakes in coding. Or you just came off as arrogant. Who knows?
I've seen many many candidates make similar assumptions to yours -- thinking they bombed specific interviews, when in fact they did very well on those. You might be correct about why you got rejected. But it's even more likely that you're wrong.
But this is absolutely true: getting the optimal solution in all interviews is not a necessary and sufficient condition.
It's not uncommon for interviewers to ask a few warm up/intro questions and then proceed to more advanced questions--so if you didn't get a few questions right, you may simply have missed some easy ones, so they didn't ask you the hard ones. This would leave you the impression that you "almost" made it, when in fact you may not have come close.
Not by a long shot. I'd love to work at a place like Google and would probably do just fine, but I'm 100% certain I'd never make it through the gauntlet. And I've been coding 25 years longer than the kids doing the interviewing.
I think I've been a victim of ageism here in the SF bay area. One member of a group met me in person, and we had a positive experience during the coding interview. (I look young for my age.) I gave him some Python code that solved his problem, as well as a version optimized for common prefixes and another that gave the same tally by user as well as the total aggregate. Note I am not primarily a Python coder, and it's not what I would've been hired for, but it's a good language for quick coding and it looks like its own pseudocode.
The next two members of his group never met me, so all they know about me is the sound of my voice and facts on my resume, and during the phone interview they came across like they thought I was some dimwitted old duffer and that I was Googling the answer because I was doing stuff on my own command line. The guy in charge told me to stop coding, because as he said, "You will take too long and never get done," [1] even though I've been coding in dynamic environments for 15 years, and so my problem solving techniques are all oriented around very rapid iteration. So he effectively disarms me, then proceeds to be the annoying kind of smarmy pair programmer and tell me everything I'm doing wrong as I'm coding. (All of which I could catch if you just let me at it.)
Just a few minutes after the interview, I send him running code, then correct code that solves his problem. (So he's wrong! - [1]) He was probably some fresh-faced kid out of school who doesn't understand other than a C/Java workflow.
The lesson I've learned over the years, is that an organization that interviews you incompetently is one that you don't want to work for anyways.
EDIT: Another thing that really irks me about this interview, was that they sprung a relational data modeling problem on me. That has almost nothing to do with what I'd be hired for, and most importantly they left out the key premise: They're looking for a generalist who can just hop in and do whatever. (Which I can do, as well as being methodical and researching the problem first.) So basically, they're looking for some fresh-faced kid like them who's fearless because they don't have the experience to know that your first model is going to suck. If they had let me know this premise: "we just want to see how you handle just getting something done" versus "we're going to grade the quality of your ER modeling" then I would have done that part totally differently.
Exactly the kind of group I don't want to work for.
I've been in interviews where I felt like the interviewer went a little power-hungry with the situation.
For example:
Interviewer: "How you implement this calculator program?"
Me: "Well I would try to read a number...."
Interviewer: "HA! You cannot assume the type of input"
Me "Okay, fair enough... does the input reflect a valid math expression?"
Interviewer: "Of course, why would you ask such a question."
In the moment I really felt like the (relatively young) interviewer way trying to lead me in the wrong direction, and then when I realized I needed to make no assumptions, criticized me for trying to clarify other parts of the problem.
I didn't get that job, but after that experience I was hardly disappointed.
I've been on interviews like that. Its a double edged sword. if you assume the worst about the input in the first place you're screwed. If you don't they'll bring it up later.
Sounds like a good solution would be to think about it while you create your solution, and when the bring it up, say somethint to the effect of "Yeah, I thought of that while I was working on it; you'd just do x and it's fixed."
You say you are a victim of ageism, but I don't see much in this story to support that conclusion. The interviewer apparently thought you were cheating... or at the very least he was incompetent to recognize the quality of your code. But those are totally different from discriminating against you because of your age.
It sounds like you had interviews from irritating doofuses that thought they were brilliant. I don't know if it was ageism, but it sounds like could have been that you weren't doing things exactly as they were so they were unable to recognize your talent. (And they were to arrogant to look at it from another viewpoint.)
Personally, I don't really get this type of interview. For one it sounds like they've pretty much standardized it for all developers with little insight into how a new candidate might fit into an existing team best.
Also, it simply does not reflect in anyway what it will be like to work there or what it will be like to work with that person. One key reason is that the interviewer asks questions they already have the answer to and that unbalances things and results in an inaccurate analysis.
In real life, none of the people in the room would have the answers and they'd all be working together to solve the problem.
These people come and interview all day. The team would be better off just having that person tag along with them and work on real problems together all day.
Has anyone read the book put out by the blog post author? I thought the post was well written, and would like to know if the book is worth getting as well...
Her "Crack the Coding Interview" book basically is an expansion of that blog post, goes into more details, includes a lot of problem sets of different types and various strategies for attacking each one.
I like using it to study for interviews. It's not sufficient by itself, but will get you 75% of the way there.
*Disclaimer: I'm 3 degrees of separation away from the author. :p
Man, I wouldn't do well in these interviews except for the tinyurl.com question. Who thinks at the level of binary tree implementations? I know what they are and how to use them and I had to could remember and implement one, but I don't remember having ever needed to implement one from scratch.
The interview questions I ask are more around problem solving and thinking out of the box but I deal at the web application level not building compilers, databases, etc.
The binary tree thing is simpler than it sounds; don't be faked out by the fact that it involves binary trees. You can traverse a binary tree from the root to any node, and record the nodes on that path. Do so for each of the two nodes, then compare the two sequences, looking for the first node that is common to both of them. You can do this in O(lg n) if the binary tree is balanced, or O(n) if it is not. And if this sounds complicated in words, just draw a picture and it'll suddenly look simpler.
I'm kind of surprised at some of the negative comments people have towards these styles of interviews.
I'm a current student still going through the interview process with Seattle / SV / Austin companies (big and small).
Every interview is the same:
- review resume
- 0-2 behavioral questions
- 1-3 technical questions covering design, data structures, algorithms, sometimes language specific (usually pointers)
Here are two recent questions asked of me this past week:
1. How would you detect the largest sub array (i.e. max sum of adjacent numbers) given an example array:
[ -1, 5, 2, -4, 6, 3, 9]
2. Given N cubes painted 1-6 sides (duplicate colors on a single cube is possible), what's the largest stack you can build such that all faces on each side are the same color? The stack is 1 cube wide and deep, solve for height.
Maybe wherever you're employed / looking for a job doesn't ask these type of questions. Congrats. However it doesn't change the fact that these questions are the norm for top tier US tech companies, and a quick glance at GlassDoor.com will corroborate.
Their effectiveness (or lack thereof) is up to the hiring companies to decide. Seriously, hot companies get flooded with applications (I believe Google gets >100k annually). They don't have time to sit down with you and pair program for an entire day, especially as a 1st or 2nd round screening.
> 1. How would you detect the largest sub array (i.e. max sum of adjacent numbers) given an example array:
That's a fun one. The obvious solution is O(n^2), but there's a less obvious way to do it in O(n). (I'm not giving spoilers, because this actually is fun to solve.)
I've been doing lots of interviews lately. Most of the coding questions have been fun, and I've learned. Some have been just plain strange - they seem like well intended questions in a specific context (which I'm not aware of). Those are the hardest.
I've noticed the strange ones seem to be coming from people that aren't prepared to be interviewing. So just a word of advice (and I'll elaborate with a blog post soon) to interviewers, please prepare ahead of time. I'm interviewing you too.
Asking the most abstract or complicated question possible probably won't help you find the people you're looking for.
I'd like to ask a question to google interviewers: when someone does not manage to get the best possible solution to a few questions, do you people chat together saying things like "he's not like us"?
143 comments
[ 9.0 ms ] story [ 214 ms ] threadSo this is like saying "ex-Python-dev mailing list member".
It is irrelevant whether it's an honor, but as to whether it gives you insight, you are generally right but you did miss an important point:
The vast majority of people who are "members" of a given hiring committee often don't show up every week. A lot, in fact, show up never, but are still members. (for example, they were part of it years ago and nobody removed them, they got asked, said yes, never actually did anything, etc)
So while you are correct that it does give you some insight if you actively participated, simply being a "member" of a hiring committee is a necessary but not sufficient condition to say that you have that insight.
Lies of omission and all that.
In this case, I'm stating that I was a hiring committee member and not saying that I attended regularly, when I in fact did. This is not a lie of omission. At worst, you could accuse me of not offering additional qualifications.
But, yes, I could have been more extensive in my credentials. Unfortunately, "How to Crack the Toughest Coding Interviews by ex-Google engineer, ex-Google hiring committee member who showed up every week, ex-Apple dev, ex-Microsoft dev, author of Cracking the Coding Interview, and author of The Google Resume" was a bit too long :).
I expect the "newer" offices (relatively, of course) may not have this issue.
I'm not worried about losing a potential job because I couldn't crack some obscure mind puzzle.
Alot of people who fall into the boat of being good coders with social skills of dead fish often have a hard time. One appraoch is to create some wonderous application and get broaght out, recruitment that way. Or in the process, end up refining there social skills to the stage that not only can they interview ok but are running there own company.
Coding interviews should be done via a shared terminal/IDE screen and chat windows, that approach would be more realistic to some. But I'm one of those people who don't socialise too well at times, interviews/exams, that type of thing.
I've definitely encountered people who were clearly good, and equally clearly sucked at interviewing, as an interviewer I had to ask myself the question "why?"
I encountered the following cases (among others)...
The ill-prepared - This may come down to background, some candidates didn't seem to know that they should prepare for an interview - this can be excusable, but in a world where advice about this is one web-search away is increasingly tough. Usually (but not always) this is a barrier to recommending hire.
The chronically nervous - This is always at least 50% my fault. I believe in asymmetric responsibility, as the person with more "power" in the situation, I feel part of my job is to help a candidate past their nerves; if this means my interview is entirely spent putting them at their ease to (potentially) do better with the next person in line, so be it. This has rarely been a barrier to recommending a hire.
The arrogant - "I can't believe you asked me such a demeaning coding question when I'm applying for a senior role, clearly my resume tells you all you need to know about my coding chops" - sorry, if I can't pierce this, no hire.
The inarticulate - often in this case the code speaks, even if the candidate can't, I usually associate this with nerves, sometimes it is language issues, sometimes stress sensitive speech impediments. I'm pretty sympathetic to this if the code speaks, but communication is part of the role so this is always a judgement call.
Can't code on a whiteboard - I'm inclined to call this ill-prepared, you should expect to have to do this coming into the interview, but I do get that this is equivalent and opposite from "inarticulate" - I will take a coherent and detailed description of a solution as being nearly as good as the whiteboard code, but there is a bottom line, you have to be able to show me your ability - sometimes one really insightful question or observation is all that it takes...
This avoids avoid that artificial write code as fast as you can with a whiteboard marker situation. Granted, it's not their regular dev setup and it's probably an unfamiliar keyboard and trackpad, but it seems to be better than the alternative.
For every interview I have done as an interviewee I have studied what I am likely to be asked, what their interview technique is, boned up on the language(s) in question, and tried to think of some interesting questions to ask the interviewer (the last one also includes learning as much as I can about the company and its history). I think these are the basics any interviewee should do - that's just the bare minimum for the big guys. For Google I was pulling out dusty old CS books and revising CS theory and that was still just barely enough preparation.
Meanwhile I've given interviews for a C++ position where the candidate hasn't even had a quick brush up on C++ recently. I've had candidates who do C++ as their JOB and not know how to initialize memory, someone describe "polyformic" behavior, and had a good 75% not know at all how virtual functions work. It blows me away.
Or maybe it's confidence? I don't know. I've been programming professionally for over 10 years. I think I should be able to sit down and work out almost any problem in an interview.
I've definitely been to interviews where I ran into issues and didn't get offers, but I've also been to interviews where I ran into problems and did get offers.
I guess, in my gut, I feel like studying for an interview is cheating a bit. It might not be the right outlook, but it's something I can't shake.
There is also a difference between an experienced industry hire - as you say, if you've been doing this for 10 years you can go into an interview and show them a pretty good picture of what they are getting - and a less experienced or campus hire, where what is important might be an expression of potential - the practice helps with letting the interviewer see that, if your interview is the first time you've tried to code at a whiteboard, or solve a problem with someone trying to push you to the edge of your comfort zone, then you are doing yourself a disservice.
I have, however, encountered candidates who just didn't know, they didn't go to a top school (or indeed any school), they haven't worked in this environment, they don't have any understanding of what to expect - even the simple web-search that would have warned them requires some level of a priori knowledge - not every candidate has that - I suspect most of these candidates do badly, but just watching how someone learns through a day of interviews tells you something, that higher level bit about learning when in over your head is one of the most valuable.
Thanks
Internal interviews can be a real eye-opener.
One I used to ask was do you have IS9002/BS5750, but that was 15 years ago and there are better questions to ask. A good question is also sometimes better than a good answear as it shows you understand things from another perspective and have the ability to ask questions instead of blindly accepting what you are told all the time if your unsure.
So what are your favorite questions and not how much TAX did the company pay type questions, the ones that give you lots of wonderous information and yet still puts them on there toes a bit as well if they are weak in some area's of managment/running the company of methodology. I asked what Q&A methodologies do you use in a interview once for a company called RIM; Was not a great answear. My question about IS9002/BS5750 was one which showed how well organised the company was at the job in hand and how well documented the role was. The answear tells you what kind of mess your getting into and also if you should be asking for more money (danger money if its somebodies spagbowl code/system :).
So what questions as a programmer do you ask the company in an interview, that is applying for your service. Anybody have one they care to share?
Do you use git?
How do you do ticketing?
What's it like working here?
In my experience engineers at big companies will not give you an answer to those, but canned marketing responses. I don't know why.
Your right about the canned marketing responses, most of those forget the interview is a two-way process sadly and deem any question you ask as a waste of there time, that is a sign you should take note of.
>What's it like working here?
ask them
>What do you like the most about working here?
If they give you something like "the stability" or "the high pay" those are generally bad signs. Better signs would for example be "the great people I get to work with every day" or "the autonomy to get to choose what I work on".
But indirectly asking questions is the way and it is those clever ways that are the types of questions i'm realy interested in, like my question about ISO/BS standards, it opend them up to so much more than a simple yes and no and gives you insight into other area's. Like working conditions, are they documented well, badly, not at all, do they even know about those standards, is it something there looking at (often crops up that last answear on many area's sadly).
Is the pay individual perofmance based or team based and is it limited/capped in that if I do 200% better am I capped at some rate of inflation % rise anyhow. I also like to ask about problems, what was the worst day like this past year and why and how likely is that to happen again. That tells you alot about so many area's and also opens them up into telling you how it is as well as allowing you to highlight your relevant skills and chip in with did you try this or that at the right times, even if you agree and play noddy whilst they talk.
One I always ask is can I have a look around the office, the area were I would be working if I was to be offered a position. That is useful in guaging there interest as if they are not interested they will come up with a reason why they can't do that, if they are keen for that you can see what your dealing with and also get a good feel from the way others have there desks decorated. Be they anal, stuffed south park toys, simpsons posters, collection of 2600 mags. Those type of things, you can get a feel on many levels from that.
Asking them how long they have been there is another good one, longer the better, but if they sound bitter then you can take that as not a good sign as well. Though if there two hyper only been there few months then they are sadly not realy able to give you a a true picture, so again take advantage of there hyper still all new to me as well fun happy time mood and take a look around.
Always a good one. I also like a variant on this if they profess to practice agile development:
>How do you implement the agile process?
More times than not, it's a waterfallesque implementation.
Every big company uses Remedy. Some just dress it up a little.
Someone asked me that once, and I thought it was a great question, so I stole it.
interviewer: What is Cassandra useful for?
interviewee: It's useful as a highly-available database if you can denormalize your data. What are you guys using Cassandra for?
interviewer: Well, we're using it to...
interviewee: Interesting. How's that working for you guys?
This not only can get you some valuable information to make your decision, but also looks confident as you're exercising some control over the interview. You just have to be careful not to derail the interview with this technique, or you'll come off cocky and arrogant.
I always ask for an example of a technical or tools decision that was made. I'm usually looking to see whether decision-making is well distributed or things get bottlenecked by a manage or lead.
Probably most of all I pick at how the organization decides what to build. I'll ask about features or products that have been sunset or rehashed, how requirements are discovered and communicated. How prioritization works. One of the easiest ways to get red flags here when applying for a spot on a team is to ask everyone I interview with what the team is currently working on. A large variety of answers makes me nervous.
Oh, and also big points off for "Yes" to the following: - Do you have an exchange server? - Do you have a sales team? - Is the person who makes the purchase decision for your product your primary user?
>Do you have a sales team?
If customers need to call in and speak to engineers or other non-business people to negotiate sales, that sucks. Having inbound sales people is a vital part of any good mid-sized company.
The problem I have with sales is that they're often very good at what they do. Once you have sales, you have two products. Your sales folks, and the thing people think they're paying you for. It gets hard to know which one is failing, or worse.. succeeding.
Not everyone is secure with a "F you, sign up online or else" policy. Good salespeople with domain expertise can be exceedingly helpful at introducing direction to the company - not just automatons who sell things.
And did you miss a negative in your last question?
From Google:
http://www.google.com/about/jobs/lifeatgoogle/hiringprocess/
From MIT:
http://courses.csail.mit.edu/iap/interview/materials.php
Steve Yegge's well-known advice:
http://steve-yegge.blogspot.com/2008/03/get-that-job-at-goog...
Essentially it seems to build down to knowledge of data structures and the ability to use them in concert to develop solutions on a whiteboard. There's more to it than that, but being able to code without an IDE is critical.
He says:
Don't say "choo choo choo" when you're "thinking".
God damn it. Now I'm going to have to fight the urge to do that during interviews!
EDIT I suddenly got it. They're doing long exhales. I think my kids might do this when they're pretending to work. Then again, they are kids.
A few days ago I finally realized why they said I'm not good enough at big-O to play with them (despite saying my coding was excellent). For some reason I had a mental block that day and wanted to implement hash tables as prefix trees every single fucking time.
I have no idea why. Of course I know a hash table is O(1), but for some reason, that day, I kept trying to convince everyone it should be O(N) (N=length of key) because it's implemented as a prefix tree in the background.
Idiot.
(For some reason programmers really love tries / prefix trees when answering on stackoverflow and such. I'd like to understand why -- tries are neat, but you don't see them nearly as much in actual use.)
O(N) only makes sense when you agree on what N means. When using big-O notation, always make sure you agree on the base N values you want to work with. In this case, it sounds like you interpreted N as the number of bits to hash, in which case yes, any sensible hash algorithm has to look at all the bits so it'll use an O(N) algorithm. However, the post you replied to talked about hash tables, a structure used to implement (among other things) maps from keys to values. For such a structure, N refers to the number of items stored in the table; hash tables have the rather unique property of supporting O(1) insertion, removal, and lookups (modulo amortization arguments about the size of the table).
(Yes I'm handwaving around the details. So is everyone who talks about big-O notation in connection with real software.)
I actually like people to point these things out, even if the amortized cost is constant in lots of real world usage. When talking about time complexity I appreciate attention to detail, rather then just hand waving and saying its constant. My answer is always, 'well it depends'.
Be careful though, back up your answers in a way that shows you do know what you are doing. Otherwise you can come off as blowing smoke.
Truly understanding writing performance critical code is a black art, and you need to understand more then just the big O of some common algorithms. Showing that you know that performance and complexity are hard and you know there are hidden costs that can bite you and tradeoffs you have to take into account shows maturity.
But the answer most certainly isn't "Well I don't know _exactly_ how python does dictionaries, but I would implement them with a prefix tree and there is nothing better". Which is roughly the answer I gave, in different settings. To five interviewers.
I think you're getting your n's confused. O(n) in the context of a collection applies to the size of the collection, not the size of the keys. Nearly all hash functions for strings are O(n) in the size of the string. This doesn't mean the hash table is O(n) for lookups.
If you use rehashing or a linked list to handle collisions that has another impact on the performance depending on what is going on.
If you choose to auto grow the hash table upon a certain number of collisions, this is another thing you have to worry about.
The process of lookup might use a precalculated cache of the hash code calculation if it is expensive and sacrifice some memory for this storage.
My point of all these examples is that the simple runtime of the collection isn't the whole story and lots of crap can happen under the covers. We stand on the shoulders of giants, but we have to know what weaknesses and strengths we are exploiting. While just picking the right data (or wrong) structure makes a huge impact, you need a lifetime of experience to really know what matters, and what the trade off of one or another is in a given scenario. Hard to test for that intuition and I always like people that interview with me that start talking about these sorts of issues.
Point was, worst-case time complexity isn't constant. I'd be happy to see more people get that right in interviews.
An amortized bound is a bound on the total cost of a sequence of operations. Loosely speaking, it guarantees that you can't keep hitting the worst case indefinitely. An average bound is averaged over all possible inputs, but doesn't protect you against hitting the worst case over and over.
And only people like developers would put up with being tested like lab mice in this manner for a job.
Why shouldn't you validate if a programmer is, in fact, a good programmer (which is a mix of many things, including intelligence)?
so yeah, ask me to program. i mean, srsly program. let's hack together for an afternoon; hell, let's do a full day of paired programming to knock out a small bug in your code base. you'll learn a hell of a lot more about what i know, how i communicate, steps i take when i do when i don't know something, and what my processes are. this soft, inter-engineer-social stuff is overlooked over far too often; i wan't to work with people who will amplify my process and abilities, and in turn i'll amplify theirs. smarts don't count for enough.
Comparing candidates is irrelevant. You just want N hires that can contribute in your environment.
Agreed. That would be bullshit. And those are bad interviewers if they do any of that. Companies like Microsoft, Google, Amazon, and Facebook don't do that, as a general rule. I'm sure you could find bad interviewers at any company though.
Programmers are almost never asked to program. They are asked to solve 50-year old CS problems on a whiteboard.
It always comes down to exercises from CLR lightly dressed up.
Programmers, however, must take a test. It's not an interview, it's a test. Pass or fail (regardless of what people say), it's a test. It's a test of which you have little preparation for. You hope that what they are looking for is what you can provide. What they are asking for is what they will test for (this is fairly often not the case).
What is a path through a cube? This seems like some weird combination of graph theory and geometry.
In this cube land question you can answear, how are you defining the centre and just revering that process will already give you the code you require. What they are doing you don't know so you have to ask, may be they are trying to reinvent a wheel and with that the best answear may be how to draw a circle as there question is flawed. This is the problem with made up interview questions, if they are based upon real world experience then you get a good question that you can truely answear. You may have a better answear or approach which with them having lived it, makes enough sence to know you would of saved them 2 days debugging that problem and thats from a quick chat walking of the street. If it is a made up question then your approach and alternative answear can be missed and ignored and your genius is not appreicieated.
You could of course write a program that would solve it (trivially), but it might take exponential time :)
Of course, the phrasing doesn't say they have to be lattice paths, so perhaps we can say a countably infinite number of paths of we're only considering integral (or rational) points and have no direction invariant. Uncountably many if we're allowing the reals. Still uncountably many if we allow the reals and have a directional invariant. We reach the realm of a finite solution if it's a finite set of points and we have a directional invariant or another constraint (e.g., the path might be prohibited from visiting any given point more than once). Most of these are still completely intractable as far as I know :)
To count paths in 2-space from (0,0) to (5,6), you have the operations "X++" and "Y++" which go right and up, respectively. Each increasing path from (0,0) to (5,6) has to be some permutation of 5 times X++ and 6 times Y++. So the count is (5+6)!/(5!6!) where the exclamation mark denotes factorial. This extends to higher dimensions by adding an additional operation "Z++". Then the count to go from (0,0,0) to (5,6,7) is (5+6+7)!/(5!6!7!).
I think you can easily write the recursion:
Leave out the term with x-1, y-1, or z-1 for the edge cases for x, y, and/or z equal to zero.With that in hand, it is easy to compute all values bottom up, starting with those where x+y+z = 0, 1, 2, etc.
Definitely fewer than (x+y+z)^3 values to compute, all of them in O(1) (disregarding cases where the numbers become bignums)
Generalization to any number of dimensions seems easy, too.
A closed form solution, that might be harder.
http://en.wikipedia.org/wiki/Self-avoiding_walk
Basically, yes, self-avoiding paths.
This was basically a brief aside in her honors undergrad algorithms course, so the topic was a bit beyond what I was prepared for at the time :)
Counting self-avoiding walks is hard in 2D, too (http://oeis.org/A007764)
But as best as I can tell, they're considering each 1x1x1 space to be a node like a Rubix cube, and they want a list of all possible paths from the center node to the surface. I imagine that half of the question is making sure that the interviewee presses for details, because there's plenty of problems I see with the question right off the bat. If n is even, there's no single center node, so where does the algorithm start? Can the algorithm traverse diagonally by edges, or only by adjacent faces? Not to mention that there's an infinite number of possible paths for some values of n, assuming paths can cross themselves, for the same reason that there's an infinite number of paths from my front door to my car if I feel like walking in circles for a while.
I studied CLRS's Introduction to Algorithms and a couple of other books for about 2 months. Even then I could not answer the hardest questions during the onsite interview. And if you cannot come up with an optimal algorithm for a given problem, all of the items mentioned in the article (communication, clear coding, testing) don't really matter.
That's just not true and if any company is only interested in whether or not I can generate a correct answer under pressure in 20 minutes, then I'm not interested in working for you.
I'd suggest you read the section in the article about how you're evaluated. Yes, how optimal your solution is matters -- of course it does. This doesn't mean that you have to get an optimal answer though. You have to do better than the majority of candidates (maybe ~80% of candidates).
For some problems, being in the top 20% of candidate will mean getting the optimal solution. In other cases, it may not. The optimal algorithm might be trivial, and it might be more about coding skills. In another problem, it might be totally unrealistic to expect that a candidate needs to get the optimal algorithm.
Additionally, you seem to assume that since (according to you) getting the optimal answer is necessary, that it must also be a sufficient condition. That's obviously false. It's entirely possible that a candidate needs to get the optimal answer AND implement it well, in which case these other factors come into play.
I don't understand the point of this quibbling.
Say I was asked 30 questions; I missed 3 of them and didn't get hired. It's a reasonable to assume that these 3 questions were considered important in the general assessment.
> You have to do better than the majority of candidates (maybe ~80% of candidates).
I know, I said I read your book. ;-)
But that doesn't substantially change the story, it means it's likely other candidates got the optimal solution or got closer to it.
Of course this is all based on my self-assessment, since Google doesn't provide any sort of feedback post-interview. But I'm pretty confident that I went well in the other questions. 4 out of 5 interviewers were pretty nice in giving feedback during the interview, even if indirectly. E.g. they'd ask progressively more involved questions on the same topic, so I more or less knew when I had answered the previous questions correctly.
> Additionally, you seem to assume that since (according to you) getting the optimal answer is necessary, that it must also be a sufficient condition. That's obviously false.
No, I haven't made any such assumption. I only assume that getting the optimal answer was the "high bit" in my case.
Apparently this works for Google, and unlike other people who have failed to get the grapes, I don't call them sour.
Imagine: I walk in, get 27/30 and then proceed to be a sexist bigot who says I refuse to work on a team with gays or women and I decide to start claiming that you have to get 100% to get hired.
I'm not saying you did something like that, but you're just automatically assuming that that question was the pinnacle of your rejection and not the other things listed.
I mean, unless you've been implicitly implying that you're a perfect interviewer minus the 3/30 you missed...
That would be true if those answers were assess on a strictly correct / incorrect basis AND those were the only things you were assessed on. Neither of those are true though in this case.
It's very possible that the questions where you didn't get an optimal answer you actually did very well on. And that there are other questions where you got the optimal answer, but it took you too long or you made too many mistakes in coding. Or you just came off as arrogant. Who knows?
I've seen many many candidates make similar assumptions to yours -- thinking they bombed specific interviews, when in fact they did very well on those. You might be correct about why you got rejected. But it's even more likely that you're wrong.
But this is absolutely true: getting the optimal solution in all interviews is not a necessary and sufficient condition.
I gave my question to an algorithms professor and he didn't get the optimal answer.
Needless to say, I don't expect candidates to get the optimal answer.
The next two members of his group never met me, so all they know about me is the sound of my voice and facts on my resume, and during the phone interview they came across like they thought I was some dimwitted old duffer and that I was Googling the answer because I was doing stuff on my own command line. The guy in charge told me to stop coding, because as he said, "You will take too long and never get done," [1] even though I've been coding in dynamic environments for 15 years, and so my problem solving techniques are all oriented around very rapid iteration. So he effectively disarms me, then proceeds to be the annoying kind of smarmy pair programmer and tell me everything I'm doing wrong as I'm coding. (All of which I could catch if you just let me at it.)
Just a few minutes after the interview, I send him running code, then correct code that solves his problem. (So he's wrong! - [1]) He was probably some fresh-faced kid out of school who doesn't understand other than a C/Java workflow.
The lesson I've learned over the years, is that an organization that interviews you incompetently is one that you don't want to work for anyways.
EDIT: Another thing that really irks me about this interview, was that they sprung a relational data modeling problem on me. That has almost nothing to do with what I'd be hired for, and most importantly they left out the key premise: They're looking for a generalist who can just hop in and do whatever. (Which I can do, as well as being methodical and researching the problem first.) So basically, they're looking for some fresh-faced kid like them who's fearless because they don't have the experience to know that your first model is going to suck. If they had let me know this premise: "we just want to see how you handle just getting something done" versus "we're going to grade the quality of your ER modeling" then I would have done that part totally differently.
Exactly the kind of group I don't want to work for.
For example:
In the moment I really felt like the (relatively young) interviewer way trying to lead me in the wrong direction, and then when I realized I needed to make no assumptions, criticized me for trying to clarify other parts of the problem.I didn't get that job, but after that experience I was hardly disappointed.
There's a lot of information in tones of voice.
Also, it simply does not reflect in anyway what it will be like to work there or what it will be like to work with that person. One key reason is that the interviewer asks questions they already have the answer to and that unbalances things and results in an inaccurate analysis.
In real life, none of the people in the room would have the answers and they'd all be working together to solve the problem.
These people come and interview all day. The team would be better off just having that person tag along with them and work on real problems together all day.
I like using it to study for interviews. It's not sufficient by itself, but will get you 75% of the way there.
*Disclaimer: I'm 3 degrees of separation away from the author. :p
Mine would probably more practice with recursion, dynamic programming, graph theory.
The interview questions I ask are more around problem solving and thinking out of the box but I deal at the web application level not building compilers, databases, etc.
I'm a current student still going through the interview process with Seattle / SV / Austin companies (big and small).
Every interview is the same:
- review resume
- 0-2 behavioral questions
- 1-3 technical questions covering design, data structures, algorithms, sometimes language specific (usually pointers)
Here are two recent questions asked of me this past week:
1. How would you detect the largest sub array (i.e. max sum of adjacent numbers) given an example array:
[ -1, 5, 2, -4, 6, 3, 9]
2. Given N cubes painted 1-6 sides (duplicate colors on a single cube is possible), what's the largest stack you can build such that all faces on each side are the same color? The stack is 1 cube wide and deep, solve for height.
Maybe wherever you're employed / looking for a job doesn't ask these type of questions. Congrats. However it doesn't change the fact that these questions are the norm for top tier US tech companies, and a quick glance at GlassDoor.com will corroborate.
Their effectiveness (or lack thereof) is up to the hiring companies to decide. Seriously, hot companies get flooded with applications (I believe Google gets >100k annually). They don't have time to sit down with you and pair program for an entire day, especially as a 1st or 2nd round screening.
That's a fun one. The obvious solution is O(n^2), but there's a less obvious way to do it in O(n). (I'm not giving spoilers, because this actually is fun to solve.)
I've noticed the strange ones seem to be coming from people that aren't prepared to be interviewing. So just a word of advice (and I'll elaborate with a blog post soon) to interviewers, please prepare ahead of time. I'm interviewing you too.
Asking the most abstract or complicated question possible probably won't help you find the people you're looking for.