7 ms·
I understood this was about finding a cycle in a linked list. I wish I could understand the code part. But the writing part was pretty brilliant. On another no
by geebee 7y ago
I understood this was about finding a cycle in a linked list. I wish I could understand the code part. But the writing part was pretty brilliant.
On another note, I only wish my technical interviews were so simple. People talk about weeding out those who can’t program but finding a cycle in a linked list is a prerequisite to the prerequisite for passing the google interview questions I was expected to do in 45 min at the whiteboard.
- saagarjha 7y agoFWIW, I don’t particularly like this interview question since it’s dangerously close to a riddle. Sorting, graph traversal, and other algorithms are well covered by undergraduate computer science curriculums, but this algorithm is basically impossible to come up with unless you know it already and it’s not even something that you would “know to know”…
- SamReidHughes 7y agoThere are other simple algorithms you could come up with that have the same big-O.
- saagarjha 7y agoI’d be happy to hear about them if you know any!
- SamReidHughes 7y agoTake the naive n^2 algorithm, but test only the nodes whose distance from the start is a power of two.
- saagarjha 7y agoThis seems just as magical as the original algorithm. Do you have insight as to why it works and what though process is necessary to arrive to it?
- gunnihinn 7y ago> This seems just as magical as the original algorithm. If you do a "change of coordinates" the original algorithm becomes trivial: If you know that any loop in the list doesn't begin after the node you're on, you can just mark where that is, run ahead, and check if you ever come back. In the general case, "change coordinates" so that with every step, the origin advances one step. Now you'll eventually be in the previous case.
- SamReidHughes 7y agoIt's an act of logification.
- pps43 7y agoIterate over the list, re-tying it backwards as you go. If you reach the end, there's no loop. If the order is important, you can re-tie again, still in O(N) time. If you end up at the head, there's a loop.
- saagarjha 7y ago> Iterate over the list, re-tying it backwards as you go. What does "re-tying backwards" mean?
- pps43 7y agoBefore: a->b->c After: a<-b<-c
- smcl 7y agoWhat if you end up at head+1, not head?
- pps43 7y agoHow would you end up there? With a loop, head+1 would point to head after the first pass, so you'll end up at the head. With no loop, head+1 would only be passed once.
- lolc 7y agoFun and really dirty solution! I would never come up with this because I would not dare to modify a passed data structure unless this was the purpose of the procedure. One could use that answer to gauge the humour of the interviewer :-) For me the expected reaction of a peer to this would be "Cute! Now explain the problems I could encounter when using it." If they can't deal with some fun, well, their loss.
- pps43 7y agoIf you can't modify the original list, you can create another as you iterate. But that will require extra O(N) memory, so is worse than the textbook solution with two pointers.
- jfoutz 7y agosince it's java, you have access to a Set. add each node to the set if it is not present, O(1). A bit more aggressive, check System.Runtime.heapSize() calculate how many nodes can fit in the heap, and subtract 1 for each element visited. Still O(1) With lower level access, recognize that pointers are always powers of 2, so go ahead and tag that pointer (p = p | 1, if *p & 1, it's a cycle.) you'll build up a stack, and have to fix the tagged pointers, but also O(1). I dunno. the double advance is a cute trick, but if the fast moving pointer doesn't do the check, you can easily spin into an infinite loop. It's not a _hard_ problem. You just have to keep your wits about you. Lots of ways to solve it.
- saagarjha 7y ago> add each node to the set if it is not present, O(1). Not in space complexity. > A bit more aggressive, check System.Runtime.heapSize() calculate how many nodes can fit in the heap, and subtract 1 for each element visited. This one will take quite a while… > recognize that pointers are always powers of 2, so go ahead and tag that pointer They're not always, and this is also technically uses extra space.
- taurath 7y agoI’ve had it in 2 interviews. I got better positions at better companies.
- geebee 7y agoactually, that's a good observation - this question depends a lot on knowing one specific solution to a problem. It really is an old "riddle", as was amusingly observed in the line: "Tim retells an old riddle, though he does not know its origins, and has the words wrong." I knew this was going to be a good one when I read that line, had me chuckling within the first few minutes.
- mark-r 7y agoNot impossible, I did it the first time I heard the problem. That was many years ago.
- mark-r 7y agoI don't know why this was downvoted - it only takes a single counter example to invalidate an absolute claim like "impossible". Of course I can't prove I independently reinvented the tortoise-and-hare algorithm, you'll have to take my word for it. But it should be obvious that somebody did it or it wouldn't be well known today.
- Jagerbizzle 7y agoI think what folks are implying here is that the 'somebody' who initially came up with this likely didn't do so in a 55 minute whiteboard session.
- Jach 7y agoOther people are implying that named algorithms, especially those named after someone famous, are somehow more special/difficult. Sometimes they are, but often they aren't. "Linear search" for instance is the name given to the easy idea of: iterate through an array until the value == search value or you hit the end. Most candidates could do this, though they might sweat a bit if you said "find x by implementing linear search" as the name for such a straightforward idea might not be known. They might have trouble writing proofs about its properties, which is where I imagine a lot of supposed scariness comes from. (i.e. "This approach looks correct but I haven't proved it yet." Academics aren't satisfied with just a test suite, or "looking at it".) My favorite named-after-a-person one like this is Dijkstra's algorithm, which he claimed to have come up with in 20 minutes on the back of a napkin. If we suppose the average professional engineer is at most 3x slower/less brilliant than Dijkstra, it's not that unreasonable to imagine someone could reproduce the design on a whiteboard in a full hour... Of course I don't buy that assumption, nor do I think it's a good problem or good idea to have as an interview filter even if it was true. (While I enjoy the occasional programming puzzle, I hate that they're lazily used to evaluate people in interviews so at least I avoid ever giving pure algorithm puzzles for interviews.) Nevertheless I agree with Mark that it's not "basically impossible" to come up with a good algorithm for many classes of algorithms and problems. I do wonder though how many people who could reinvent tortoise+hare without seeing it explicitly before would then be able to reinvent the teleporting turtle optimization right after.
- pcwalton 7y agoYeah, it's a terrible interview question because it's just trivia. It's one of those things where the best response may be "I know this problem. It's called tortoise and the hare. Do you still want me to do it on the whiteboard?"
- porknubbins 7y agoYeah seems like theres somewhat of a debate over whether you should say “I know this one” on an interview, which I generally would not, but most linked list questions are so much trivia its like you either know it or you don’t. Contrast with a graph problem that I immediately know requires dfs but I can never remember the details so I can honestly put on a convincing show of working them out.
- yakshaving_jgt 7y agoFWIW, a company once FizzBuzzed me in an interview, but with the words Fizz and Buzz substituted with parts of their company name. I told them I recognise this as FizzBuzz. They told me I am overqualified.
- xena 7y agoI got it but called SnoopDawg once. I miss California.
- bfrog 7y agoAh yes the dreaded overqualified reasoning
- 52-6F-62 7y agoOof. Note to self, don't display too much [basic] knowledge in interviews...
- logfromblammo 7y agoNext time I do a FizzBuzz, I'm going to add a printline("duck") to the beginning, just to see if anyone tells me, "That looks great. Just one thing--get rid of the duck." If they don't, I'm walking out.
- seanmcdirmid 7y agoMost LeetCode questions like this are just riddles, especially at the moderate+ range. You either studied the question and know the answer or haven’t but could figure it out in a day or say, but not 45 minutes. And studying these questions have no value outside of acing interviews. But at least they know the interviewee cares enough to cram for the interview.
- Gibbon1 7y agoI never have had to suffer these types of interviews. But I keep thinking, the problem was thought up and answered with a lot of work by someone smarter than anyone in the room. And they want to see if the victim can cough up the answer like a trained monkey? What does that prove exactly.
- 52-6F-62 7y agoI can only come to the conclusion that it shows you think like they do (or at least can change to do so)—for better or for worse?
- taneq 7y ago> Sorting, graph traversal, and other algorithms are well covered by undergraduate computer science curriculums, but this algorithm is basically impossible to come up with unless you know it already and it’s not even something that you would “know to know”… Even a lot of the "basic algorithms" taught in undergrad courses would be gnarly to invent on your own without clues in less than an hour. There's a reason they're named after famous computer scientists. If they were easy, we wouldn't bother teaching them.
- Infinitesimus 7y agoI think it's an open secret that you're expected to have seen and practiced similar questions. Perhaps unintentionally showing that these companies are more interested in you showing that you care about algorithms tricks you will realistically never use there than being a productive engineer (which is a pretty hard thing to measure )
- geebee 7y agoI have a cynical take on this. They want to see if you can afford the time it takes to front load data structures and algorithms in short term memory. This is an excellent indicator of whether you have other demands (such as parenting) or even just outside interests that would interfere with your devotion to the job.
- rco8786 7y agoYea, that’s pretty cynical. It maybe had an inkling of truth when the companies in question were wee startups. But working at FANG companies these days affords a pretty nice work-life balance.
- stevula 7y agoIt’s also a great indicator for whether you already have a job or not. If you do have a job, you probably don’t have as much time to cram for interviews. Not a great thing to select for, in my opinion.
- underwater 7y agoI have a similarly cynical take. It ensures successful candidates have studied a formal CS degree, and haven't "just" come in from a bootcamp or are self taught. It's not deliberate, but does ensure that exclusive FAANG jobs remain the domain of the privileged.
- indigochill 7y agoEven as a self-taught guy I don't agree with this take. I do get hung up on technical interview trivia, but that's because I refuse to load my brain with useless interview trivia. If I was going to play the game, there are plenty of special-purpose resources available that I could cram before an interview. There are also resources like Anki through which I could use spaced repetition to load it into longer-term memory.
- mav3rick 7y agoGoogle will never ask rote questions
- codingslave 7y agothey already do, people just memorize a ton of algorithms then hope to get the right questions, and boom theyre hired. Rank and file at these tech companies really are not that impressive
- komali2 7y agoAlmost every question I got in my Google interview for frontend in 2018 was either rote, or reduced down to a rote algorithm.
- pjc50 7y agoThey interview thousands of people a year. They're going to reuse questions a lot.
- patmcguire 7y agoI'm trying to find the original source for this, but there's a quote I've seen about how finding a cycle in a linked list used to regarded as a FizzBuzz like test. It came of age when most people worked in C - if you worked in C for a year you'd know that cold. I wonder how much the technical question approach isn't so much wrong as it is testing for things that matter much less now. There don't seem to be many questions about concurrency and distributed systems in this kind of interview, or at least not good ones. Everything now is "it depends" and the hard solutions are about ten lines of code for ten pages of problem explanation.