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.
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.
What does "re-tying backwards" mean?
After: a<-b<-c
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.
I must admit I didn't follow the bytecode too closely. So thanks for pointing that out.
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.
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.
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.
What's more likely, somebody figured the solution out to a problem that previously took over a decade in under an hour and then felt the need to brag about it to strangers on the internet; or somebody lied online to feel better about themselves. People are certainly more likely to assume the latter.
Certainly the Internet has made it more likely that you've run into it and heard the solution.
As I said, it was a very long time ago when I heard of the problem. I don't think it was in an interview, but I honestly don't remember the circumstances. I do remember being quite proud of myself, so I guess there's truly an element of bragging in my statement. Doesn't mean I lied though.
You settled for a). Typically of what geeks do ( yeah, I'm guilty of it too).
Anyway. you seem to be an outlier to being able to solve the problem without having being familiar with it before hand. Do you realize you are extraordinary? (FYI: I'm not saying that with sarcasm, you might indeed be "riddle" genius, or perhaps even a "real problem", problem solver)
But computer geeks ( we are talking about kind of people who code for 'fun') are not normal people. Their default is to take words' meaning literally, unless they have somehow (often painstakingly) managed to learn the ways of normal folks communicate.
I've always thought of myself as being pretty clever, but I'll bet many HN readers would say the same about themselves. "extraordinary" seems a little over the top, but thank you.
There are enormous implications to this seemingly harmless labeling of yourself ( not blaming you). I insist you are extraordinary, not merely 'pretty clever', not only based on my observation but also judging by other people's reactions to you your post.
Off the top of my head there are 2 implications that can be typically attributed to such traits ( and I'm not saying that you are particularly cause those implications, it's just typical):
- if someone like you is an interviewee for a programming position, your average Joe interviewer who asks you algorithmic questions ( or often some clever question) will not like the fact that you can easily solve the problems that you are presented with.
- If a person like you is an interviewer for a regular corporate programming position( which does not involve algorithms), the person is likely to pose problems of this nature to candidates for the job. When candidates routinely fail to solve those problems the person is left wondering why the candidate pool is so bad. To the interviewer the solutions seems so obvious ( or can be figured out easily) to someone who is just 'clever'.
And the industry complains how it cannot find people for CRUD programming jobs....
I told them I recognise this as FizzBuzz.
They told me I am overqualified.
I am not a recent college grad, and I don't encounter a lot of interesting algorithm problems in my work, so I had prepared by working through some leetcode problems. But I had worked through only "easy" and some "medium" problems because I had the impression they didn't ask the harder ones. I was able to recognize it as a BFS graph problem and gave the time complexity (and space complexity, IIRC), but I did not finish it on the whiteboard.
Live and learn. Maybe I'll have another go in six months. Can't argue with the money and the resume cred.
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.
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 )
Formal CS education requires good self-learning skills and is not a counter-indicator for self-learning.
(I agree with it being a mostly arbitrary criterion for evaluating a candidate.)
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.