This question has an "a-ha" moment, but it is not required to solve the problem adequately. I wholeheartedly disagree with this statement:
> People like to pose puzzlers to “see how people think” but that’s nonsense in the case of puzzler questions. You can’t reason your way through a puzzler, that’s why it’s a puzzler
There are plenty of ways to solve this problem. They're not all optimal, of course, but you don't ask these questions to get the optimal solution, you ask these questions to understand how the person reasons about them.
This more falls on the interviewer than the candidate. It's upon the interviewer to encourage a dialogue about the problem and talk aloud through it.
Yes, some qualified candidates are bad at this. I'm sorry to hear that, but it can be practiced. Being good at interviewing can be learned. It's not terribly difficult. My number one pro-tip? Never do this:
> If you don’t have the a-ha moment in the interview, you won’t get it, and a good chunk of your brain will be devoted to thinking “oh shit I’m blowing this interview” rather than focusing on the question at hand.
Never think that you're blowing the interview. I got a job at Google and I know for a fact that I didn't get the optimal solution to some of my questions. It's not about the solution, it's about the process.
This is... debatable. It depends on what you consider a puzzler. I will tell you that I was asked questions similar to the one referenced in the parent article. It is a programming question that can be answered precisely with code, and that code can then be analyzed for time and memory considerations.
I was not asked silly questions like "how many golf balls could you fit in a school bus" or "how do you move a mountain 3 feet to the side". These are the types of questions he explicitly references in the article.
edit: I will also add that there are differences between eng and non-eng interviews. I'm not familiar with the non-eng process really.
I used to have a math puzzler that I'd ask. Almost nobody got it right. One guy got close, and we ultimately hired him. He asked for the full answer, and I gave it to him. He told me I was wrong. I pointed out that I had asked this question at least 50 times, and knew it in and out, and that he should reconsider. Then he sent me a spreadsheet proving that I was wrong. Whoops.
It's a question that checks intuition on probability and the law of large #s. I don't want to give too much more since I do pull it out on the very rare instance where someone is very bold about their stats knowledge.
I was in the position of that candidate before, and the interviewer refused to (do the analog of) letting me set up the spreadsheet, then vetoed me from the rest of the interviews.
To your credit, you are among the very few who would admit this kind of error and you likely took it gracefully.
But how many times did you ask this question without actually verifying that YOU could answer it? And what does that mean about your process for generating and grading interview questions? And why did it have to be the interviewee who told you?
Maybe interviewees should be more confident, but maybe interviewers should be a little less self-confident. This is a huge cultural problem for the industry, but it's right in our blind spot.
And we have to ask why there are less women in tech since it became dominated by erroneously self-confident, high-testosterone personalities who think that hiring people like themselves is a meritocracy?
Without getting into too many specifics (on rare occasions I pull it out again) it was a question of statistics and law of large numbers intuition. I was checking for how directionally correct people would be on the subject, with 3 parts of the question to see how deep they knew it. More about intuition than actual computation. There was a subtle error on how aggressively to apply the law of large #s.
How many times had I asked it? 50? I had a couple folks answer it like I thought it should be answered. He was the only who nailed it enough to catch the error too.
The reality is interview performance is very different than work performance. Interview questions test interviewing ability more than anything else.
Over time I've realized that the only reliable predictor of success is seeing people's work results first hand when they don't think they are interviewing. The danger is this too breeds issues of familiarity and lack of diversity, because one only hires from their narrow circle of the world.
This makes it very tough to make college hires. The only things I've seen that worked are "High enough" GPA (with "High enough" being higher on non-technical majors) and some sign that the student had to significantly multi-task (lots of extra curriculars, research, or working through school). Most 21 year olds don't have interview training, so it's a very bad way to pick them.
If you mess up, say so: "Oh, that's completely wrong. Huh. Ok, let's fix it." Again, these interviews are more about seeing how you reason about a problem. People make mistakes all the time - wrong assumptions, incomplete solutions, etc. What matters is what you do once you realize there's a problem.
In practice, you may lose even if the interviewer is wrong. I have. At some big-name companies.
Just for example, an interviewer at Apple was adamant that frequency can never be negative. Whatever happens to Fourier transform that integrates frequency from negative infinity to positive infinity.
Yeah, I think I once lost out on a Google interview in part because the interviewer lacked the math to follow my reasoning (also, they were attempting to get me to a different solution by applying criteria that my existing solution already adhered to better than what they wanted).
This may very well be, but there's not much you can do about it at that point but continue to try to fix the problem. If you can't be amicable about it with the interviewer, then either they don't want to work you or you don't want to work with them (probably both). Might as well make the best of it.
I don't have any trouble admitting I made a mistake when I notice it, it's recovering from it. At that point I think about how I messed up, what I should have done, and how bad the rest of the interview will go.
In every day life, this is not the thought process I go through if I make a mistake. But in an interview the stakes are higher, you'll be quickly discarded if you don't do well.
>> once I mess up during interviews, and it's all downhill from there
I have witnessed this. I was asked to write code for LRU cache [1]. I started out wrong, thinking that LRU caches "Least Recently Used" items (in other words, most recently used need to be discarded). It turns out that LRU cache "discards" LRU items. I wonder if the name is actually a misnomer.
I caught this extremely quickly though on the very first hint and then tried to confirm the definition multiple times, but the interviewer had mental blocks by that time, nodding his head without even listening to what I was asking.
Obviously if someone is lacking in confidence, is anxious or is a humble person, they should just learn not to be that person any more so they can get a Google job like you, the paragon of success.
Otherwise, they DESERVE to be judged as unqualified. That certainly follows.
Ha! I am hardly the paragon of success. You judge my words too harshly. I am simply pointing out that, yes, companies conduct interviews by asking coding questions. Yes, some of the questions are hard and don't have obvious optimal solutions. Don't panic just because you don't get 100%.
I've never been asked such a question, provided a sub-optimal answer, and been allowed to continue. Every single time, the next question then is 'Can you make it <faster|better|etc.>?' Maybe, but by this point, I already know this is a terrible place to work.
I've been in this exact same situation. And I was offered positions. I guess that's my point - I didn't always find the perfect solution. I was pressed to continue to think about the problem until whatever allotted time was up. I wasn't [entirely] judged based on my final solution; I was judged on my ability to reason about the problem and demonstrate competency in my coding abilities.
Come on, this is like the easiest problem you could have gotten during Google's, Microsoft's or Facebook's phone screening interview. If you can't figure it out in 10 minutes, then you should forget about working there.
I miss the old times when these puzzlers were asked during interviews. My theory is that you can recognize an excellent place of work with a great future when they actually ask you these sorts of questions as it attracts certain kind of excellent and creative people. I could see the "interestingness" of companies being shifted as they abandoned these questions, first Microsoft (picked up by Google), then Google (picked up by Facebook), like they were passing some kind of "greatness" token (MS->G->FB).
I was told at Google that I solved two problems like this during an interview that nobody solved before me in 15 minutes (one led to a super complicated math formula and dynamic programming, the other I solved optimally but differently to their solution, and provided an optimality proof based on discrete calculus). It was the greatest and most challenging interview in my life. I miss it, all interviews nowadays are just boring as hell :-/
What did you exactly prove during this interview?
That you know to write readable code?
That you are know to code in team?
Did you write any test case during this inteview?
Any docs?
I proved that my solution had optimal time complexity using discrete calculus, for a highly non-trivial problem that requires to come up with unexpected ideas under huge stress.
They saw my own open-space real-time software 3D rendering engine with texturing and shading (C++/Asm) at SourceForge already, they saw my own SQL server (many students at my first university were ripping it off for their own class projects in the next years so it was a mistake to make it open) as well as other projects I did prior to that interview so they were familiar with my coding style and quality.
Also, before that while working at SUN I did some work on a test suite with 10,000s of tests, many of them for SUN's own compliance with one of their standards, making sure it was executing on a distributed cluster every day for every branch they had in order to ship the best quality to customers. Many of these tests were for obscure cluster failure cases using custom bleeding-edge test frameworks. So the answer is no, I didn't write any test at Google interview, it wasn't required.
How can you prove you can code in a team during an one-on-one interview? At best you can give hints that you are willing to discuss stuff and change your progress on input from the interviewer and explore if there is any sort of chemistry between you two, which is about all you can do.
I really hate this kind of nitpicking, averaging everyone to a "normal" level, trying to find something wrong in someone because she or he goes against (IMO) lazy typical stereotype. Enjoy your mediocrity! Are there still hackers on HN?
My solution would have been: Simply have a wrapper around the linked list that keeps count of the elements (+1 for insert, -1 for delete, initialized with 0).
Traverse the list. If your traversal takes more steps than there are elements, you can stop it and conclude there's a cycle. I wonder how the interviewer would value this answer...
If I was interviewing you, I would point out that you're redefined the question: the question gives you a standard linked list, and you state that you want a wrapper-api around it. I would then ask you to try to find a solution that works for a bare bones linked list.
I would make a note that you did find one type of solution, of course.
edit: I would probably also ask why you created an api that even allows cycles, being as that you are defining control over adding and removing elements. Further, if you stated that your api explicitly allows cycles, I would ask why you don't simply mark them at insertion time and flag them, making the "detection" algorithm O(1).
As others noted you can't know how many elements there are supposed to be in the list. But you can guesstimate.
1. Take a guess about how much memory the program has allocated so far. If you can't, go with 2^48 = 281474976710656 bytes - the maximum you can do on a 64bit pc today.
2. Divide by the minimum size of a list entry.
3. Traverse the list until the end or until you traverse more elements than there ever could be.
In general though, as noted, you'll know if you're making a list that could possibly contain cycles due to exposing an interface that allows the creation of cycles. In that case, given that you want to be able to efficiently detect cycles, you'd make a special linked list implementation that does keep internal count of its size.
If you argued that many programming languages already provide list.size() or equivalent (more so if I told you "in a language of your choice" before), I'd swallow my pride and accept it.
Then I'd suggest you try the other way, but it's a perfectly good answer.
The problem is, in Java and probably many others, that method computes the size in linear time by traversing the list. The javadocs for java.util.LinkedList note that this was a decision taken so that splitting a list at an arbitrary node, etc. could be a constant-time operation.
The naive way to do it is just create a hashset that stores pointer to next, walk the linked list, and if you get a collision you have a cycle. The problem is that it requires O(n) memory, where the tortoise and hare method only needs O(1).
That's a great idea. I had another approach that assumed the entry addresses were aligned to 32/64 bit words in memory as structure's by default are. Then the next pointers will never have the ones or twos bit place set and can be used as a visited marker[1]. This gives a O(n) with a much smaller constant factor than the hair and tortoise.
Has anyone actually answered this question on the spot without help and without knowing it? Probably not without help, but then how do we judge the amount help given to an interviewer?
I have been going through my own crises of interview question. My go to question for interviews which I have asked of about half a dozen candidates so far, wasn't completely flubbed only once. The only people I know who gave the good answers besides myself were my boss and our intern from MIT during mock interviews. I have been grading the candidates not on being able to write the solution in code like I intended, but on being able to come up independently with bits needed for the solutions. This has been quite unsatisfactory. How do I know if my question is too hard, or if something else is wrong, like prescreening of candidates?
I have. I had help, but the process was just like any other problem. State constraints. Look for a violation of constraints. Sort of like proof by contradiction.
I can't remember the actual hints. I blitzed through 3 or 4 naive solutions first. My favorite was using tagged pointers to mark visited nodes. Eventually through a combination of hints and exploration I got to the idea of using two cursors. At that point it was a simple constraint about which cursor would be in front of the other and if there was a violation of that constraint it could only be because of a cycle.
It made for a good interview, but there was good chemistry between myself and my interviewer. Any question would have worked in reality.
Yes, I did figure it out. Actually, the answer I came up with was slightly different: it was pretty clear that I had to move the first pointer to get inside the cycle. Once I was inside, I thought the second pointer would need to move a lot to find the cycle, rather than just going two hops. So I proposed to advance the first pointer by n, and the second one by exp(n). Maybe it would go faster, who knows.
By the way, this was the question at my first interview ever, so I do remember it quite well.
PS: I interviewed many candidates since, and I would never ask such a question.
Can you tell us what that question is? Not details, but the general idea.
Me, I'd ask them this:
1. Write a function that takes a string of hex digits and converts them to a long (or equivalent in the language). Keep code minimal.
2. The opposite. Keep code minimal.
3. Write a function that reverses a UTF-8 encoded string (provide a good reference to the UTF-8 format), keeping combining characters in the reversed string in the same order they were in the original. I.e. aüç should be çüa, not ¸c¨ua. Assume the string of bytes is a proper utf-8 string, that only combining characters have to be order-preserved and that the only combining characters are the ones with unicode character codes in these ranges: (give them some standard ranges). Keep code minimal.
Anybody who can do these three things should be able to learn most any other tech stack you throw at them. If on the other hand you're looking for people with specific expertise with a given branch of computer science, then you need a different set of tests. The central question is - do you need a developer or a mathematician specialising in discrete mathematics. Those are two different sets of people, though they tend to overlap.
Yes, I had it during 1st phone screen with Microsoft, coding it in their interviewing system and I figured out the two pointer version without a prior knowledge.
I disagree with the author that this is a "puzzle question" that requires an "a-ha" moment. Quite the opposite, it is an easily solvable algorithmic question (maybe with a little guidance after the candidate suggest suboptimal solution). Also, the good thing from the candidate point of view is that it is the sort of questions you can prepare for.
The point is why do you need to prepare for and regurgitate these silly answers that you will almost assuredly never ever ever use in your day to day job?
+1 to that. Most programming jobs are about integrating a bunch of different technologies together to solve a business problem. In 20 years I've never written a linked-list or sorting algorithm for work yet interviews are increasingly narrowly scoped to algorithm questions. I've found that these questions are usually asked by young people because they are fresh out of school and have been led to believe that knowledge of algorithms is the most important consideration. Give them a decade of creating products based on css, html, node.js, nosql, yessql, etc and they will come to realize that programming is more about understanding what a customer needs and finding the most efficient way of delivering a solution. Ability to work with other, lead a team, write clearly, explain to customers the tradeoffs and costs of different solutions are actually way more important than knowing how to find a cycle in a linked list.
But how do I test all of that in 30min or less? Do I have to actually get to know the person, their work history and their strengths? Does that mean I have to read the resume before I enter the room?
Well one can prepare by memorizing a ton of algorithms and hope to get lucky and get asked the questions about those they happened to study or by actually studying up on what's relevant to the job, which random algorithms that can be looked up on Google most certainly is not. It's impossible to do both--it's difficult enough concentrating on one area.
I know which engineer I'd hire. Then again, I wouldn't ask such useless questions in the first place.
The article seems to imply that the turtle and hare algorithm is only valid solution for this problem, which is certainly not the case.
This problem can be also solved by building big set of already seen list nodes or adding bit to list nodes themselves. Whis is both something that everybody should be able to come up with and implement.
I think that this is in fact quite good interview question because while there is one non-obvious perfect answer, it also has some sub-optimal solutions that are pretty obvious and simple to implement.
Yeah - the article built it up and built it up, but when the question finally came up my thought was "wait, that's it?!"
If the interviewer asked the question and rejected anyone that didn't immediately answer with the tortoise/hare approach that's the fault of the interviewer, not the question.
You're right, though I think he's talking about the weird type of interviewer who expects candidates to know obscure, non-intuitive optimal solutions to these problems.
I once met an interviewer who liked to use the "reverse a string" question, except he was expecting candidates to know the XOR trick. Suffice to say few, if anyone, ever got past his "filter".
Primadonna interviewers who use interviews as ego-strokes are a problem in our industry. It's where the stupid "why are manhole covers round" questions came from, and it's where these hyper-optimized algorithms questions come from.
This was my first thought about how to solve it. It provably works in finite time. This ought to be a satisfactory answer in an interview, particularly if the candidate points out that it's unlikely to be The Optimal Solution. After which point, the appropriate follow-up question from the interviewers would be to ask what the time complexity of the algorithm would be in the worst case.
Agree. The anti-pattern here is expecting a specific answer for a question. The goal should be, "how does this candidate think through problems?" If they arrive at a logic solution and can critique it, then I would consider the question completed.
Some questions are better than others here, specifically ones that have many correct implementations and varying levels of optimal-ness. I'm a big fan of asking for Fibonacci implementations, for instance.
Since this question can have different correct implementations, then I would not consider it a bad question to ask.
It's upon the interviewer to be open to different answers, evaluate them fairly and ask smart follow-up questions. "Ok, so what's the complexity of your answer? Do you think it's possible to do better?" or "Compare your answer with this implementation".
I think an unreasonable question (ie, of a practical situation in which no one will ever find themselves) deserves an equally unreasonable answer:
Write a program that starts at the head of the list and in a loop follows the "next" pointer on the current list entry, halting when the pointer is null. Run the program and wait. If the program never ends, there's a cycle in the list.
I have had this problem in real life. I had a graph database, and I needed to find the end of a path in the graph. If the the path looped back on itself, my program would not terminate.
This occurred to me as well: the graph data model is one of the few areas in which you might practically need to address this problem. Again, however, a lot of these issues specific to the graph data model are open research questions and not really appropriate to an engineering interview.
Finding the loop in a graph is a much more valid scenario and any candidate aware of traversal algorithms will have a much better chance of dealing with it than finding loop in a LL.
> In this case, the generally “correct” answer is a tortoise-and-hare algorithm, where you have two pointers at the head of your linked list, one traverses the list two nodes at a time, and one traverses the list one node at a time; if ever the pointers point to the same node, you have a cycle somewhere.
I'm an extreme novice to programming. I don't fully understand this.
1) How can you traverse a linked list two nodes at a time? Is this just short-hand for "go to the next node, then go to the node after that, and call that one operation"?
2) If you can detect when two pointers are pointing to the same address, couldn't you solve the problem by traversing the list one node at a time, storing the addresses of each node in an array, and checking to see if the array contains any duplicate values at intervals?
The "tortoise" pointer does a standard traversal - one at a time. The "hare" pointer goes from one node to the next _and then the next_ - i.e. two at a time. If the hare hits a null node, there's no loop. If the hare hits a cycle, it will eventually run back into the tortoise and there's a loop.
I must have learned this algorithm in school, but completely forgot it. My naive implementation was 2), but this is the first explanation on this page that made Floyd’s cycle-finding algorithm click for me:) Now I can't unknow it - thanks for the clarity and concision!
With regards to (2), this is one way of solving the problem. However, your solution uses O(n) memory (where n is the size of the linked list), and the tortoise-and-hare algorithm uses only O(1) memory. Here's how it works: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_ha...
Complexity optimization is a generally useful skill.
"moving the goal posts" is called "every month at work, when you finish 1 task and then move on to another task, instead of going home and getting paid to rest on your laurels"
I don't think it has to be "wrong". If I were asking this question, and I was provided with "store them in a hash", I would say something along the lines of "that's a correct solution" and then add additional constraints.
"How you adapt in the face of additional constraints" is very much relevant to programming.
1) yes.
2) is ok (with a hash table instead of an array to have linear execution time), but doesn't run in constant space unlike 1), or you could mark the nodes when you visit them.
2) Yes, you could, and that is a valid way to discover a loop. However, consider that your linked list is already a store of the contents of the list. Rather than copying values out, you may as well use the list itself.
If you could assume that the loop contains all members of the list, then you could detect the loop by iterating through the list and checking to see if the node is the same as the head of the list. Unfortunately, the loop doesn't always point back to the head of the list, so you may have something like this:
1 -> 2 -> 3
| |
^ \/
5 <- 4
By maintaining two node references, and advancing one of them twice as quickly as the other, you are effectively doing the exact same check, but eliminating the problem that the loop may not include the head. In both tests, the separation between the two referenced nodes increases by one every time, but only in the second test is the "head" reference guaranteed to eventually be in the loop.
It's a bad question if you expect a quick, explicit answer. It's somewhat less bad if you're looking to have a conversation about how to solve problems the candidate hasn't seen before.
I've used an arguably "puzzle" question that was presented to me in an interview with some success -- the missionaries and cannibals problem. There are three missionaries and three cannibals that you must get across a river. The boat holds only you and one other person. The cannibals on either bank must never outnumber the missionaries on that bank. It's a good question to see if a candidate understands how to apply some basic computer science concepts. It can easily lead to a 30 minute discussion at the white board, with no need to get working code.
My favorite question is completely different. "What do you like best about your favorite programming language and what would you change about it if you could?" Anyone who doesn't see any flaws in their favorite language, particularly if it's Java, gets politely shown the door.
The problem with using this as a meta-question, is that someone who knows the answer may treat it as such.
That is, the person who comes to realize the canonical way of solving it may truly be brilliant and having been hinted and helped along the way came up with the solution, or he might have already known it and just played a metagame, assuming that's what you wanted.
Basically, you have four possible outcomes:
People who have never heard of it, don't come up with the canonical solution.
People who have heard of it and just blurt out the answer.
People who have never heard of it, but who come to realize it over the course of the interview.
People who have heard of it and who play it as a game, working towards it and then suddenly having an epiphany.
The first is interesting. The second you hopefully dispense with the question as being useful. The third would be a great hire, but is indistinguishable from the fourth, who you've learned nothing about except they know how to play your interview process. Which may or may not be the criteria you're looking for.
I was asked a puzzle question that I hadn't heard before. I answered it directly almost immediately. In a later interview with the CEO he asked if I had heard the problem before because the interviewers were sure I had with such a fast answer. I said I had not and just left it at that. Playing the whole thing back in my head, I think this cost me the job for "lying" to them. I might have been able to convince them on how quickly I got the problem if I had taken this as a questioning of my integrity.
"There are 128 chairs on a ski lift. You get on at the bottom, and ride it all the way to the top. On your trip up, how many do you pass on their way down?"
There may have been some distracting info of distances and speeds in there to make get you going in the wrong direction.
My experience with puzzlers is that average people like to feel superior for knowing the answers to a puzzle that someone else doesn't know. The people who can solve these easily are thrilled to find a puzzle they don't know the answer to. Then there is the group who can make a good puzzle.
Disagree: it's a terrible question. The answer (all of them) is something you either see or don't, and neither tells you much more than one bit of information about the candidate.
I'm not convinced; it at least tells you if the interviewee will rush to an answer that appears correct and say "All of them", or if they'll consider it a little more carefully and say "The rest of them". Or if they'll ask for a strict definition of what it means to pass a chair on the way up, to clarify whether or not you count the chair that you're riding on as one that you pass.
Wouldn't the answer be 127 of them? You're passing the one behind you as you get on at the bottom, and the one in front of you as you get on at the top.
I well my view if you walk to the base of the lift half on the chairs are on the up side leg half on the down you get on the one right at the bottom. so you pass all the chairs on the downward leg
Actually this is a simplification as the chairs slow down and bunch up at the bottom and top to make getting on and of simpler
> Actually this is a simplification as the chairs slow down and bunch up at the bottom and top to make getting on and of simpler
Yeah, this is the problem with the question that I noticed as well.
If you don't know what a ski lift is (grew up in the south and didn't have money for vacations as a kid), you might not even know how ski lifts work. In which case maybe you guess that the chairs are fixed and give the 127 answer. Ironically, you guessed wrong and got the correct answer.
If you do know how ski lifts work and assume the interview does as well, then you just look like an idiot.
I guess the lesson is to state all your assumptions (and also, don't ask these questions).
Something like happened to me once, someone asked me a riddle (it was: "you have a polynom of coefficients that are positive integers. I can give you the values of this polynom at integer points of your choice. Can you get all the coefficients by asking only two values?"). Somehow I got it very quickly, and was thinking in my head "oh man I didn't know I was that clever", but the guy thought I already knew the answer.
When I interview for data scientist positions I ask your favorite question, but with "programming language" replaced by "statistical analysis package". (There's overlap between the two sets; their intersection includes Python, with the SciPy stack being what it is now.) I honestly don't care what package they name; it's more a way to get them talking about how they use whatever package they respond with, which reveals quite a bit.
Or, at least, I think it does. I'd love to have data on which interview questions actually elicit signal-containing answers...
I really like the questions about programming languages. What's their favorite, just favorite language, features, etc. If the candidate says they've only ever used one, or they don't have any features they dis/like, that's a flag. If they point out a feature, you can use it to dive into a deeper discussion about something they say they know about.
> My favorite question is completely different. "What do you like best about your favorite programming language and what would you change about it if you could?" Anyone who doesn't see any flaws in their favorite language, particularly if it's Java, gets politely shown the door.
What about the poor people who've found a language that they actually like, and understand the tradeoffs that were made? I suspect I recently failed an interview for not having a good answer to that question, but really, what am I supposed to say? If I thought there were significant problems with my favourite language, I'd find a better one.
I don't ask for significant problems, just anything about the language that they would change if they could. A common answer when discussing Java is verbosity, for example.
I once voted -1 on someone for not having a good answer to this one a language that he had used for years. I regretted the vote later, as he turned out to be excellent.
Having said that, it does surprise me that people have a hard time with this. Certainly I hope that you like your chosen language and understand the tradeoffs being made, but that is the point of the question really. Surely you can reason about these tradeoffs and have a discussion in this area? If your language is Java and you talk about how you are ok with their decision on erasure because of the legacy concerns, that's a good answer. I may (or may not) agree, but it's still a perfectly good answer. :)
OTOH, it is strange to me that someone would have worked in a language for 10+ years and literally can't come up with anything that they dislike (even understanding the reasons for those limitations). No matter how good something is, it is hard to imagine working with anything (or anyone) for ten years without coming up with a few pain points.
> If your language is Java and you talk about how you are ok with their decision on erasure because of the legacy concerns, that's a good answer. I may (or may not) agree, but it's still a perfectly good answer.
I wouldn't feel comfortable answering "what would you change about X" with something I actually wouldn't change about X (though maybe I should).
(FWIW my language was Scala, and while I've only been using it for ~5 years there's very little I would change. The answer I gave was to use HLists rather than Tuples in the standard library, but that feels like a nitpick more than anything else)
Wikipedia [1] describes the cannibals and missionaries problem differently than you do. Particularly, there is no "you" who transports them, there are only 3 Cs and 3 Ms.
You must be stating the missionaries and cannibals problem incompletely. If only one person can fit on the boat at a time (which is essentially the case because you didn't say the person operating the boat is a missionary or cannibal, and you are implying that they must be operating the boat), it's provably impossible to solve. Wikipedia says you may have 1 or 2 people on the boat (as opposed to 0 or 1), which makes it relatively easy to solve as soon as you realize you can take people back that have already crossed.
The correct solution requires that you get out of the boat and put two cannibals on it. The statement that the boat holds "only you" and one other person very strongly implies that is not allowed.
Someone having a strong tool preference and thinking their choice of tool is good enough that it has no important downsides for their usage (and being aware of how to steer around pitfalls) is not automatically an incompetent programmer. Maybe it tells you that they chose their tool thoughtfully, it is a good tool for the usage, and they learned the tool well, and are enthusiastic rather than negative about it.
Most people who think they could improve a language don't have any background in programming languages, don't have a good nose for what would actually be an improvement, and would actually screw it up badly. Having declined to shave that yak for years hardly means that someone is incompetent. Are you interviewing people to create new general-purpose programming languages? Do you often build new programming languages as part of projects? If so, you must miss deadlines a lot.
It's incredible to me how interviewing is in the stone age: some guy gets assigned to interview people because it needs to be done, and how hard could it be anyway? Then he Googles questions to ask, which are more or less arbitrary, and grades them more or less arbitrarily. And the same guy who asks is the one who judges the quality of the question, which is tied up with ego and confirmation bias. Over time, he adjusts to his own taste, but is accountable to nothing else. You get a process which, at best, selects people who are like the interviewer, because the interviewer assumes he is good, so other good people have backgrounds and opinions (and demographics) like his.
It's the same process that 10-year-old boys at a skate park might use to judge whether a new boy is a "poseur." It depends as much on whether the judges think the new boy is like them or dresses correctly or whatever as on any meaningful evidence of ability.
I don't really have a favourite. I just go with the one that fits in with the team and if we need to choose one, try and find one that is a good match for the problem domain.
> With all of those hundreds and hundreds of minds, this problem remained open for 12 years.
A very good point. Some people just forget that while solution can look simple when it's already known, actually finding it can be extremely hard and more akin to invention breakthrough. So such question is more similar to asking to prove some difficult theorem really, than to anything else.
I am the guy who asks that question on every interview. You can hate on me now!
Let me clarify. I don't expect the candidate to get to the "a-ha" moment at all. I make my expectations very clear upfront so that the other side wouldn't panic. However, I expect to see how the candidate would approach the problem with the right attitude so I could get some insight of his/hers thinking patterns.
I personally wouldn’t mind if an interviewer asked me something in the lines of "how would you build a nuclear plant?", although I have no knowledge on the matter.
I completely disagree that this question is irrelevant. I can imagine this exact situation in compiler design where you have dependent types that can't have infinite loops (in pseudo-code where forward declarations are not needed or implied):
type a = b
type b = a
If a program has a structure like this with cyclic dependencies, then the compiler must be aware of this and break. (At least, I can imagine a situation where this could be a desired attribute.)
You are mixing up cyclical linked lists with loops in a graph. The reason why the question is bad stems from the fact that it's specifically about linked lists.
I could definitely be mistaken, but I don't see a difference between a linked list and a graph. They are two ways to represent the same thing. That being said, if he asked me to find cycles in a linked list, I might determine the adjacency matrix and check for loops:
"I could definitely be mistaken, but I don't see a difference between a linked list and a graph."
A linked list is a particular type of DAG (or at least DG). The relevant distinction between linked list and the general case is that a linked list restricts nodes to (zero or) one outbound edge. This is relevant to the problem at hand, because you only have one tortoise and one hare and so they can only follow one path.
Ok, that was poorly worded. What I mean is that a linked list can be thought of as a restrictive graph. I'm just saying I'd prefer to think of it as a graph. I could still be wrong. Is that kosher?
That's certainly kosher (though, nitpicking terminology, I'd say "restricted" rather than "restrictive").
That doesn't get around the original objection, though, which is that the restriction has to be exploited to get the algorithm in question, and thus the algorithm cannot be applied to the general case of graphs.
Having said that, certainly the ability to make use of restrictions provided by your domain is hugely valuable, and this should serve as a relatively familiar case.
Right. As a graph theorist might put it, a linked list is a directed graph with a vertex-disjoint path cover consisting of exactly one path. I.e., linked lists are specialized graphs. The tortoise-and-hare algorithm can be generalized to detect cycles in any connected graph, as long as a consistent traversal order is used.
I think it depends on how the graph is represented. With the "standard" representations, it would be O(n) space in the worst case, where n is the number of nodes in the graph. You'd still only need the 2 pointers, but the traversal itself would need to also remember which paths it has not yet visited. The worst case is when the number of paths is much larger than the length of any particular path. The best case (apart from the null graph) is equivalent to the linked list, where there is only one path in the cover.
I can imagine representing the graph as a list of paths, in which case the tortoise-and-hare algorithm is O(1) space, though the graph itself would be (potentially much) larger. Virtually every other operation on such a graph would take a performance hit, too.
There may be other factors I haven't thought of, but you're right that the generalized algorithm could not be as space-efficient as the special algorithm.
It's worth noting, though, that the original question poised in the article did not place an O(1) restriction on space.
Once in an interview I was asked to implement a synchronization mechanism between processes using shared memory. It turns out this is the petersons algorithm. I mean if I could solve this, I would be Peterson :) heck, even smarter because I would do it in 20 mins.
Hypothetically, if when asked this question in an interview I were to reply "I'd look up the canonical solution on the internet and just implement that. I have better things to keep in my brain than linked-list algorithms, and there's no way I'm going to beat decades of phd work off the top of my head", what would happen?
Obviously it depends on the job I was interviewing for. Let's assume I'm not angling for a position as lead on a distributed load balancing layer or something.
I suppose if they're looking to see my problem solving workflow then I'd look like kindof a dick. But then, as the article points out, so would they.
A great response would be to just say "hold on", whip out your phone and Google the answer, show it to them and finish up with "How long did it take your other candidates to complete that task? next..."
Point being, you're demonstrating initiative and, that old cliche, thinking outside the box. Think Will Smith in Men In Black.
Some interviewers might be impressed with your lateral thinking, others might be annoyed at your attempt to be a 'smart ass' and avoid the intention of the question. But that's always the problem with these type of interview questions, it depends so much on the expectations of the interviewer.
I think it would be funnier to silently transcribe the code from the phone to the whiteboard, and then just sit back down and look at them while you wait for a response.
My response would be, "OK, walk me through the code, show me how and why it works, or if it doesn't (code from teh Internets is buggy), fix it." Anything higher than a junior position requires maintaining code as much as, or more than, writing it.
Maybe this points to a better class of interview questions: the interviewer supplies the broken algorithm, the interviewee supplies the bugfix.
You're correct, but generally when critical thing X is broken and you need it working for the customer, you give it to your more experienced devs, not the college intern.
I did something like this recently. The question was more around increasing efficiency of an algorithm though, and on top of what you said, the other part of my answer was more like "I wouldn't waste my time as long as performance was acceptable until it became an actual problem at larger scale. I'd move on to shipping other features."
It felt that they were interviewing for a computer scientist despite advertising for a software engineer.
That's probably fine if you're going for a junior position where your job is to bang out code for designs that others have come up with.
But if you go up a few steps then suddenly the problems might not be that clearly defined and the set of possible solutions can be huge. A person who is constantly relying on Google to come up with solutions is probably not going to be that useful in design discussions.
I'm not defending the particular question, but on-your-feet problem solving is a real and valuable skill.
Oh I agree. That's exactly the stuff I keep in my brain instead of linked list algorithms, which have a mathematically proven optimal solution. Remembering them when I don't use them regularly would be a waste of brainpower which could be better used for solutions to business/UX/architecture problems, which one cannot solve with pure logic.
I am not so sure. It's not just about solving the problem, but sometimes it's also the willingness and mentality to tackle something that's outside your comfort zone, as well as the approaches.
For example, given the loop in linked lists question, even if a candidate is not able to solve it completely, a reasonable approach would be to break the general case to more specific, trivial cases, such as: what if the loop has known length, what if the loop starts at a known location, etc. Interview questions are not binary decisions, you can learn a lot from a candidate just by seeing how they respond to a question.
(Just to be clear, as this is a permanent and public record, I'm perfectly capable of doing this kind of thing. It's not really an unreasonable question to ask. I'm just being facetious because it's friday afternoon.)
I agree: the hard mental work is in recognizing that a fuzzy, client-provided problem description is merely a disguised form of a well understood problem -- ie, getting it to the point where you can google easy solutions at all.
But then in that case, the problem as given is still bad, because it gives that part away! If you want to test this ability, you shouldn't frame the problem in terms of linked lists. As another poster here suggested, you should ask something like "The customer gave a list of everyone and who they report to. How would you sanity check the hierarchy?"
That then requires the candidate to identify cycles as something they'd want to look for, and then this problem as a special case of "find a cycle in a linked list".
But that solves the problem no? its like when I needed to limit a tool I wore to so many api requests in an hour I knew I needed a queuing algorithm but I don't keep that in my head a couple of quick google queries and a quick look on CPAN problem solved.
One day interviewers will realize this. Caching into your mind what's one stackoverflow away can often be an invalid optimization.
>> Obviously it depends on the job I was interviewing for.
In my experience, it often does not depend on the job. Interviewers ask such things even if the job does not require it because ... ultimately because they are not good interviewers. If you get asked the question, the best bet is to just answer it or else the interview goes downhill from that point on.
Had that exact question given to me before, but it was in the form of a closed book "pre-screening" written test.
I simply put down my pen, walked out of the room and told the recruiter if this company was hiring based on these type of questions I would be a terrible fit :)
I had this in an interview (back '96). Came up with a linear time constant space solution: create a new node, push it on the front, reverse the list, check if the 1st node is the same one you pushed, if so it has a loop, otherwise it doesn't. The downside is you need to reverse again to get the original list.
Another answer is to mark nodes using the low bits of the next pointer. Also linear time, but also requiring clean up. I can see how not knowing c would cause people to think this question was somewhat unfair, but I didn't see it that way.
If your list is laid-out a contiguously in memory as structs with both next and prev ptrs, you can visit each member using ptr arith and switch the values without actually walking the list using next and prev. Ditto if there's an underlying data-structure involved such as an array.
You allocate an array of objects that contain pointers, then link them together. It does not have all of the typical benefits of a linked list (in particular, there's a hard max size and may require a fixed size, depending on just what you're doing to it here) but it does allow O(1) reordering elements for a list-order traversal, while also allowing a linear traversal through memory.
If the linked list has a loop, but you don't know it, how do you figure out the length of the list to allocate enough space for your array? How do you copy the list into the array without traversing the list? How do you traverse the list without hitting the loop and looping infinitely?
If you know that all the elements in the loop are already in the array then traversing it is easy. Of course, if you have an upper bound for the length of the list, there's an easier check...
I'm no fan of this particular interview question, but the article takes it too far. You can figure out tortoise-and-hare algorithm by reasoning (I'm pretty sure I did the first time I've seen the problem - although not in an interview setting). The key is to recognize that there's a very limited number of things you can do given all the constraints: moving pointers is pretty much the only tool you have.
If it indeed took 12 years for the algorithm to appear, it's likely because finding loops in a linked list isn't a very common problem, not because the algorithm itself is that hard.
Nor is the 12 years thing particularly good reasoning... By that thought process, it took humans hundreds/thousands/millions of years to develop a compiler, so how can I be expected to develop one over the course of 4 years in college? Or even over the course of my life?
Not exactly a valid analogy, because his start date isn't "the beginning of human history", rather it's the development of the linked list data structure, which is the first point at which humanity possessed sufficient knowledge and tools to figure out the cycle-detection algorithm.
Given that we didn't have the knowledge or tools necessary to make a compiler hundreds/thousands/millions of years ago, you'd have to bump up your start date considerably.
Sure, I stretched that too far. But hopefully the point is made. Then should we expect no students (or anyone) to be able to build a compiler (or os kernel) in any amount of time given the internet and whatnot? While I may be articulating this poorly, I think my fundamental issue with his point is solid.
Because over the course of 4 years in college you're provided with resources that explicitly teach you how to develop a compiler, a scenario which is entirely different from what happens in an interview.
I don't want to complain but one of the major culprits who conducts these kinds of interviews is Amazon. After going through their interview process, I'm of the opinion that they basically want you to memorize careercup, geeksforgeeks and leedcode and just spit it out in chunks at appropriate times during the interview.
If I do not know any better, the first thought that would come to my mind would be: "Wow, this company has really messed-up code base, and people here cannot even get linked-list done right. Do I really want to work here?"
After a 10 minute phone screener I now rely on a paid pair-programming session to identify good candidates. This is what you're going to hire them to do so why waste your time asking questions that at best form a poor approximation of their skills?
Tom Forsyth listed one of the reasons--when a storage is explicitly expressed. The other two that I can think of are for external linkage and non-constant expressions on the rhs. In the end, you really don't know without some introspection. It's up to the compiler. External linkage is one that will force storage, but in general const will require internal linkage and fold expressions accordingly (at least for primitives).
Edit: I would never expect anyone to actually remember or need to know that for an interview. It would be definitely something you would re-discover/discover because you had to run into it.
Technically in the context of an org hierarchy that would be detecting cycles in a directed graph, not a linked list cycle. I don't think the algorithm to detect cycles in a linked list applies to general graph problems, and the problem is much harder for graph cycles.
It's not a generic directed graph either, though - each node only has one outbound link. The sequence of parents for any given node is a linked list, and a cycle in that list is invalid. You certainly don't need to run tortoise and hare for every node path looking for cycles. There are other approaches, clearly - reachability analysis starting from each root node, for example.
But if I were to ask you to write a routine to find the root node for a given node based on that data, then ask you to guard that routine against finding yourself in an infinite loop or stack overflow, tortoise and hare would be a legitimate answer.
Just trying to make it clear that just because the question asks about linked lists, doesn't mean it's always about abstract data structures.
191 comments
[ 3.1 ms ] story [ 250 ms ] threadBut we can test for programming ability directly.
> People like to pose puzzlers to “see how people think” but that’s nonsense in the case of puzzler questions. You can’t reason your way through a puzzler, that’s why it’s a puzzler
There are plenty of ways to solve this problem. They're not all optimal, of course, but you don't ask these questions to get the optimal solution, you ask these questions to understand how the person reasons about them.
This more falls on the interviewer than the candidate. It's upon the interviewer to encourage a dialogue about the problem and talk aloud through it.
Yes, some qualified candidates are bad at this. I'm sorry to hear that, but it can be practiced. Being good at interviewing can be learned. It's not terribly difficult. My number one pro-tip? Never do this:
> If you don’t have the a-ha moment in the interview, you won’t get it, and a good chunk of your brain will be devoted to thinking “oh shit I’m blowing this interview” rather than focusing on the question at hand.
Never think that you're blowing the interview. I got a job at Google and I know for a fact that I didn't get the optimal solution to some of my questions. It's not about the solution, it's about the process.
http://www.nytimes.com/2013/06/20/business/in-head-hunting-b...
I was not asked silly questions like "how many golf balls could you fit in a school bus" or "how do you move a mountain 3 feet to the side". These are the types of questions he explicitly references in the article.
edit: I will also add that there are differences between eng and non-eng interviews. I'm not familiar with the non-eng process really.
But how many times did you ask this question without actually verifying that YOU could answer it? And what does that mean about your process for generating and grading interview questions? And why did it have to be the interviewee who told you?
Maybe interviewees should be more confident, but maybe interviewers should be a little less self-confident. This is a huge cultural problem for the industry, but it's right in our blind spot.
And we have to ask why there are less women in tech since it became dominated by erroneously self-confident, high-testosterone personalities who think that hiring people like themselves is a meritocracy?
How many times had I asked it? 50? I had a couple folks answer it like I thought it should be answered. He was the only who nailed it enough to catch the error too.
The reality is interview performance is very different than work performance. Interview questions test interviewing ability more than anything else.
Over time I've realized that the only reliable predictor of success is seeing people's work results first hand when they don't think they are interviewing. The danger is this too breeds issues of familiarity and lack of diversity, because one only hires from their narrow circle of the world.
This makes it very tough to make college hires. The only things I've seen that worked are "High enough" GPA (with "High enough" being higher on non-technical majors) and some sign that the student had to significantly multi-task (lots of extra curriculars, research, or working through school). Most 21 year olds don't have interview training, so it's a very bad way to pick them.
How do you that? Because that's all I ever think about once I mess up during interviews, and it's all downhill from there.
In practice, you may lose even if the interviewer is wrong. I have. At some big-name companies.
Just for example, an interviewer at Apple was adamant that frequency can never be negative. Whatever happens to Fourier transform that integrates frequency from negative infinity to positive infinity.
I have more examples. :-)
In every day life, this is not the thought process I go through if I make a mistake. But in an interview the stakes are higher, you'll be quickly discarded if you don't do well.
I have witnessed this. I was asked to write code for LRU cache [1]. I started out wrong, thinking that LRU caches "Least Recently Used" items (in other words, most recently used need to be discarded). It turns out that LRU cache "discards" LRU items. I wonder if the name is actually a misnomer.
I caught this extremely quickly though on the very first hint and then tried to confirm the definition multiple times, but the interviewer had mental blocks by that time, nodding his head without even listening to what I was asking.
[1] http://en.wikipedia.org/wiki/LRU_cache
Obviously if someone is lacking in confidence, is anxious or is a humble person, they should just learn not to be that person any more so they can get a Google job like you, the paragon of success.
Otherwise, they DESERVE to be judged as unqualified. That certainly follows.
Do you interview people to discover if they are good on the job, or just to discover if they are good at interviewing?
I miss the old times when these puzzlers were asked during interviews. My theory is that you can recognize an excellent place of work with a great future when they actually ask you these sorts of questions as it attracts certain kind of excellent and creative people. I could see the "interestingness" of companies being shifted as they abandoned these questions, first Microsoft (picked up by Google), then Google (picked up by Facebook), like they were passing some kind of "greatness" token (MS->G->FB).
I was told at Google that I solved two problems like this during an interview that nobody solved before me in 15 minutes (one led to a super complicated math formula and dynamic programming, the other I solved optimally but differently to their solution, and provided an optimality proof based on discrete calculus). It was the greatest and most challenging interview in my life. I miss it, all interviews nowadays are just boring as hell :-/
They saw my own open-space real-time software 3D rendering engine with texturing and shading (C++/Asm) at SourceForge already, they saw my own SQL server (many students at my first university were ripping it off for their own class projects in the next years so it was a mistake to make it open) as well as other projects I did prior to that interview so they were familiar with my coding style and quality.
Also, before that while working at SUN I did some work on a test suite with 10,000s of tests, many of them for SUN's own compliance with one of their standards, making sure it was executing on a distributed cluster every day for every branch they had in order to ship the best quality to customers. Many of these tests were for obscure cluster failure cases using custom bleeding-edge test frameworks. So the answer is no, I didn't write any test at Google interview, it wasn't required.
How can you prove you can code in a team during an one-on-one interview? At best you can give hints that you are willing to discuss stuff and change your progress on input from the interviewer and explore if there is any sort of chemistry between you two, which is about all you can do.
I really hate this kind of nitpicking, averaging everyone to a "normal" level, trying to find something wrong in someone because she or he goes against (IMO) lazy typical stereotype. Enjoy your mediocrity! Are there still hackers on HN?
I would make a note that you did find one type of solution, of course.
edit: I would probably also ask why you created an api that even allows cycles, being as that you are defining control over adding and removing elements. Further, if you stated that your api explicitly allows cycles, I would ask why you don't simply mark them at insertion time and flag them, making the "detection" algorithm O(1).
1. Take a guess about how much memory the program has allocated so far. If you can't, go with 2^48 = 281474976710656 bytes - the maximum you can do on a 64bit pc today.
2. Divide by the minimum size of a list entry.
3. Traverse the list until the end or until you traverse more elements than there ever could be.
In general though, as noted, you'll know if you're making a list that could possibly contain cycles due to exposing an interface that allows the creation of cycles. In that case, given that you want to be able to efficiently detect cycles, you'd make a special linked list implementation that does keep internal count of its size.
Then I'd suggest you try the other way, but it's a perfectly good answer.
The problem is, in Java and probably many others, that method computes the size in linear time by traversing the list. The javadocs for java.util.LinkedList note that this was a decision taken so that splitting a list at an arbitrary node, etc. could be a constant-time operation.
1.https://www.cs.purdue.edu/homes/cs240/lectures/Lecture-7.pdf
I have been going through my own crises of interview question. My go to question for interviews which I have asked of about half a dozen candidates so far, wasn't completely flubbed only once. The only people I know who gave the good answers besides myself were my boss and our intern from MIT during mock interviews. I have been grading the candidates not on being able to write the solution in code like I intended, but on being able to come up independently with bits needed for the solutions. This has been quite unsatisfactory. How do I know if my question is too hard, or if something else is wrong, like prescreening of candidates?
I can't remember the actual hints. I blitzed through 3 or 4 naive solutions first. My favorite was using tagged pointers to mark visited nodes. Eventually through a combination of hints and exploration I got to the idea of using two cursors. At that point it was a simple constraint about which cursor would be in front of the other and if there was a violation of that constraint it could only be because of a cycle.
It made for a good interview, but there was good chemistry between myself and my interviewer. Any question would have worked in reality.
By the way, this was the question at my first interview ever, so I do remember it quite well.
PS: I interviewed many candidates since, and I would never ask such a question.
Me, I'd ask them this:
1. Write a function that takes a string of hex digits and converts them to a long (or equivalent in the language). Keep code minimal.
2. The opposite. Keep code minimal.
3. Write a function that reverses a UTF-8 encoded string (provide a good reference to the UTF-8 format), keeping combining characters in the reversed string in the same order they were in the original. I.e. aüç should be çüa, not ¸c¨ua. Assume the string of bytes is a proper utf-8 string, that only combining characters have to be order-preserved and that the only combining characters are the ones with unicode character codes in these ranges: (give them some standard ranges). Keep code minimal.
Anybody who can do these three things should be able to learn most any other tech stack you throw at them. If on the other hand you're looking for people with specific expertise with a given branch of computer science, then you need a different set of tests. The central question is - do you need a developer or a mathematician specialising in discrete mathematics. Those are two different sets of people, though they tend to overlap.
The optimal one, no but I didn't try any further than the solutions I had.
The point is why do you need to prepare for and regurgitate these silly answers that you will almost assuredly never ever ever use in your day to day job?
I know which engineer I'd hire. Then again, I wouldn't ask such useless questions in the first place.
This problem can be also solved by building big set of already seen list nodes or adding bit to list nodes themselves. Whis is both something that everybody should be able to come up with and implement.
I think that this is in fact quite good interview question because while there is one non-obvious perfect answer, it also has some sub-optimal solutions that are pretty obvious and simple to implement.
If the interviewer asked the question and rejected anyone that didn't immediately answer with the tortoise/hare approach that's the fault of the interviewer, not the question.
I once met an interviewer who liked to use the "reverse a string" question, except he was expecting candidates to know the XOR trick. Suffice to say few, if anyone, ever got past his "filter".
Primadonna interviewers who use interviews as ego-strokes are a problem in our industry. It's where the stupid "why are manhole covers round" questions came from, and it's where these hyper-optimized algorithms questions come from.
Some questions are better than others here, specifically ones that have many correct implementations and varying levels of optimal-ness. I'm a big fan of asking for Fibonacci implementations, for instance.
Since this question can have different correct implementations, then I would not consider it a bad question to ask.
It's upon the interviewer to be open to different answers, evaluate them fairly and ask smart follow-up questions. "Ok, so what's the complexity of your answer? Do you think it's possible to do better?" or "Compare your answer with this implementation".
Write a program that starts at the head of the list and in a loop follows the "next" pointer on the current list entry, halting when the pointer is null. Run the program and wait. If the program never ends, there's a cycle in the list.
I'm an extreme novice to programming. I don't fully understand this.
1) How can you traverse a linked list two nodes at a time? Is this just short-hand for "go to the next node, then go to the node after that, and call that one operation"?
2) If you can detect when two pointers are pointing to the same address, couldn't you solve the problem by traversing the list one node at a time, storing the addresses of each node in an array, and checking to see if the array contains any duplicate values at intervals?
2) Yes you can do this but not in all languages.
"moving the goal posts" is called "every month at work, when you finish 1 task and then move on to another task, instead of going home and getting paid to rest on your laurels"
You want someone to answer a programming question within a particular set of boundaries, you set those boundaries.
"How you adapt in the face of additional constraints" is very much relevant to programming.
2) Yes, you could, and that is a valid way to discover a loop. However, consider that your linked list is already a store of the contents of the list. Rather than copying values out, you may as well use the list itself.
If you could assume that the loop contains all members of the list, then you could detect the loop by iterating through the list and checking to see if the node is the same as the head of the list. Unfortunately, the loop doesn't always point back to the head of the list, so you may have something like this:
By maintaining two node references, and advancing one of them twice as quickly as the other, you are effectively doing the exact same check, but eliminating the problem that the loop may not include the head. In both tests, the separation between the two referenced nodes increases by one every time, but only in the second test is the "head" reference guaranteed to eventually be in the loop.I've used an arguably "puzzle" question that was presented to me in an interview with some success -- the missionaries and cannibals problem. There are three missionaries and three cannibals that you must get across a river. The boat holds only you and one other person. The cannibals on either bank must never outnumber the missionaries on that bank. It's a good question to see if a candidate understands how to apply some basic computer science concepts. It can easily lead to a 30 minute discussion at the white board, with no need to get working code.
My favorite question is completely different. "What do you like best about your favorite programming language and what would you change about it if you could?" Anyone who doesn't see any flaws in their favorite language, particularly if it's Java, gets politely shown the door.
That is, the person who comes to realize the canonical way of solving it may truly be brilliant and having been hinted and helped along the way came up with the solution, or he might have already known it and just played a metagame, assuming that's what you wanted.
Basically, you have four possible outcomes:
People who have never heard of it, don't come up with the canonical solution.
People who have heard of it and just blurt out the answer.
People who have never heard of it, but who come to realize it over the course of the interview.
People who have heard of it and who play it as a game, working towards it and then suddenly having an epiphany.
The first is interesting. The second you hopefully dispense with the question as being useful. The third would be a great hire, but is indistinguishable from the fourth, who you've learned nothing about except they know how to play your interview process. Which may or may not be the criteria you're looking for.
"There are 128 chairs on a ski lift. You get on at the bottom, and ride it all the way to the top. On your trip up, how many do you pass on their way down?"
There may have been some distracting info of distances and speeds in there to make get you going in the wrong direction.
My experience with puzzlers is that average people like to feel superior for knowing the answers to a puzzle that someone else doesn't know. The people who can solve these easily are thrilled to find a puzzle they don't know the answer to. Then there is the group who can make a good puzzle.
Actually this is a simplification as the chairs slow down and bunch up at the bottom and top to make getting on and of simpler
Yeah, this is the problem with the question that I noticed as well.
If you don't know what a ski lift is (grew up in the south and didn't have money for vacations as a kid), you might not even know how ski lifts work. In which case maybe you guess that the chairs are fixed and give the 127 answer. Ironically, you guessed wrong and got the correct answer.
If you do know how ski lifts work and assume the interview does as well, then you just look like an idiot.
I guess the lesson is to state all your assumptions (and also, don't ask these questions).
Or, at least, I think it does. I'd love to have data on which interview questions actually elicit signal-containing answers...
What about the poor people who've found a language that they actually like, and understand the tradeoffs that were made? I suspect I recently failed an interview for not having a good answer to that question, but really, what am I supposed to say? If I thought there were significant problems with my favourite language, I'd find a better one.
Having said that, it does surprise me that people have a hard time with this. Certainly I hope that you like your chosen language and understand the tradeoffs being made, but that is the point of the question really. Surely you can reason about these tradeoffs and have a discussion in this area? If your language is Java and you talk about how you are ok with their decision on erasure because of the legacy concerns, that's a good answer. I may (or may not) agree, but it's still a perfectly good answer. :)
OTOH, it is strange to me that someone would have worked in a language for 10+ years and literally can't come up with anything that they dislike (even understanding the reasons for those limitations). No matter how good something is, it is hard to imagine working with anything (or anyone) for ten years without coming up with a few pain points.
I wouldn't feel comfortable answering "what would you change about X" with something I actually wouldn't change about X (though maybe I should).
(FWIW my language was Scala, and while I've only been using it for ~5 years there's very little I would change. The answer I gave was to use HLists rather than Tuples in the standard library, but that feels like a nitpick more than anything else)
[1]https://en.wikipedia.org/wiki/Missionaries_and_cannibals_pro...
Most people who think they could improve a language don't have any background in programming languages, don't have a good nose for what would actually be an improvement, and would actually screw it up badly. Having declined to shave that yak for years hardly means that someone is incompetent. Are you interviewing people to create new general-purpose programming languages? Do you often build new programming languages as part of projects? If so, you must miss deadlines a lot.
It's incredible to me how interviewing is in the stone age: some guy gets assigned to interview people because it needs to be done, and how hard could it be anyway? Then he Googles questions to ask, which are more or less arbitrary, and grades them more or less arbitrarily. And the same guy who asks is the one who judges the quality of the question, which is tied up with ego and confirmation bias. Over time, he adjusts to his own taste, but is accountable to nothing else. You get a process which, at best, selects people who are like the interviewer, because the interviewer assumes he is good, so other good people have backgrounds and opinions (and demographics) like his.
It's the same process that 10-year-old boys at a skate park might use to judge whether a new boy is a "poseur." It depends as much on whether the judges think the new boy is like them or dresses correctly or whatever as on any meaningful evidence of ability.
Will that do ?
A very good point. Some people just forget that while solution can look simple when it's already known, actually finding it can be extremely hard and more akin to invention breakthrough. So such question is more similar to asking to prove some difficult theorem really, than to anything else.
type a = b
type b = a
If a program has a structure like this with cyclic dependencies, then the compiler must be aware of this and break. (At least, I can imagine a situation where this could be a desired attribute.)
http://stackoverflow.com/questions/16436165/detecting-cycles...
This is at least very easy to reason about. However, if you are still right my thought process is just very wrong.
A linked list is a particular type of DAG (or at least DG). The relevant distinction between linked list and the general case is that a linked list restricts nodes to (zero or) one outbound edge. This is relevant to the problem at hand, because you only have one tortoise and one hare and so they can only follow one path.
That doesn't get around the original objection, though, which is that the restriction has to be exploited to get the algorithm in question, and thus the algorithm cannot be applied to the general case of graphs.
Having said that, certainly the ability to make use of restrictions provided by your domain is hugely valuable, and this should serve as a relatively familiar case.
But not in O(1) space, right?
I can imagine representing the graph as a list of paths, in which case the tortoise-and-hare algorithm is O(1) space, though the graph itself would be (potentially much) larger. Virtually every other operation on such a graph would take a performance hit, too.
There may be other factors I haven't thought of, but you're right that the generalized algorithm could not be as space-efficient as the special algorithm.
It's worth noting, though, that the original question poised in the article did not place an O(1) restriction on space.
For sure.
Obviously it depends on the job I was interviewing for. Let's assume I'm not angling for a position as lead on a distributed load balancing layer or something.
I suppose if they're looking to see my problem solving workflow then I'd look like kindof a dick. But then, as the article points out, so would they.
Point being, you're demonstrating initiative and, that old cliche, thinking outside the box. Think Will Smith in Men In Black.
Some interviewers might be impressed with your lateral thinking, others might be annoyed at your attempt to be a 'smart ass' and avoid the intention of the question. But that's always the problem with these type of interview questions, it depends so much on the expectations of the interviewer.
Maybe this points to a better class of interview questions: the interviewer supplies the broken algorithm, the interviewee supplies the bugfix.
I think that applies to junior positions, too.
It felt that they were interviewing for a computer scientist despite advertising for a software engineer.
Needless to say, we were mutually not a good fit.
But if you go up a few steps then suddenly the problems might not be that clearly defined and the set of possible solutions can be huge. A person who is constantly relying on Google to come up with solutions is probably not going to be that useful in design discussions.
I'm not defending the particular question, but on-your-feet problem solving is a real and valuable skill.
For example, given the loop in linked lists question, even if a candidate is not able to solve it completely, a reasonable approach would be to break the general case to more specific, trivial cases, such as: what if the loop has known length, what if the loop starts at a known location, etc. Interview questions are not binary decisions, you can learn a lot from a candidate just by seeing how they respond to a question.
But then in that case, the problem as given is still bad, because it gives that part away! If you want to test this ability, you shouldn't frame the problem in terms of linked lists. As another poster here suggested, you should ask something like "The customer gave a list of everyone and who they report to. How would you sanity check the hierarchy?"
That then requires the candidate to identify cycles as something they'd want to look for, and then this problem as a special case of "find a cycle in a linked list".
>> Obviously it depends on the job I was interviewing for.
In my experience, it often does not depend on the job. Interviewers ask such things even if the job does not require it because ... ultimately because they are not good interviewers. If you get asked the question, the best bet is to just answer it or else the interview goes downhill from that point on.
I simply put down my pen, walked out of the room and told the recruiter if this company was hiring based on these type of questions I would be a terrible fit :)
I've been places with tough interviews and incompetent developers and the opposite as well. One does not necessarily correlate with the other.
Another answer is to mark nodes using the low bits of the next pointer. Also linear time, but also requiring clean up. I can see how not knowing c would cause people to think this question was somewhat unfair, but I didn't see it that way.
If it indeed took 12 years for the algorithm to appear, it's likely because finding loops in a linked list isn't a very common problem, not because the algorithm itself is that hard.
Given that we didn't have the knowledge or tools necessary to make a compiler hundreds/thousands/millions of years ago, you'd have to bump up your start date considerably.
Edit: I would never expect anyone to actually remember or need to know that for an interview. It would be definitely something you would re-discover/discover because you had to run into it.
Here's a file a customer sent you that describes their organizational hierarchy:
Is this a valid hierarchical tree? Okay, it's not exactly the same problem, but it's certainly similar...But if I were to ask you to write a routine to find the root node for a given node based on that data, then ask you to guard that routine against finding yourself in an infinite loop or stack overflow, tortoise and hare would be a legitimate answer.
Just trying to make it clear that just because the question asks about linked lists, doesn't mean it's always about abstract data structures.