Hacker News Reader

Comment by _Lemon_ | Hacker News Reader

> In my opinion, the biggest problem with the google-style interview (other companies do the same thing) is that you can practice and get better at it. In fact, you can probably improve how well you do so much that even a mediocre developer can come out looking very good.

While this is true, isn't quite unlikely? Why not just invest the time into becoming a /good/ developer.

>"How can you detect loops in a singly-linked list without modifying nodes / keeping accounting information around?"

What do you mean by "accounting" information?

In the real-world I'd probably just brute-force it and keep around a set of elements already gone over. However I couldn't imagine ever having a need for that as I'd (and hopefully anyone I was working with) stick to the standard push_back functions available or that I created. So it shouldn't come about...

I feel I've missed something here, so care to elaborate on the answer?

View on HN

>"How can you detect loops in a singly-linked list without modifying nodes / keeping accounting information around?"

What do you mean by "accounting" information?

The usual way to state this problem is, "How can you detect loops in a singly-linked list without modifying nodes and using O(1) data."

The answer is that you start with 2 pointers to the beginning of the list. Then follow the pattern of advancing the first twice, and the second one once. You have your answer when the first reaches the end, or the first and second point at the same spot.

There are a lot of problems with a trick like that. And it is true that if you've seen the problem before, you're going to be at an advantage. So practice a few of them to get use to the form. But there are enough such problems out there that it is significantly easier to become a good developer than to learn a broad enough selection of them to have a good chance of getting through a set of interviews off of memory.

While this is true, isn't quite unlikely? Why not just invest the time into becoming a /good/ developer.

It might be unlikely for people applying to google, but I can attest that people will memorize what they think are details that will make them sound like they are competent to get through an interview.

The software development industry is one where you can really make it into a position with decent pay by bullshitting, and then surf the wave of nothing-getting-done-because-of-corporate-policy for a while, while making yourself appear like a magic technology man if you really feel like it. This probably isn't going to happen as much with a company whose hiring process is filled with competent software engineers (but there's also the opposite problem...)

It sounds like hell to me, but I'm concerned with writing code and feeling intellectually fulfilled, not just with making stacks of cash.

What do you mean by "accounting" information?

In the real-world I'd probably just brute-force it and keep around a set of elements already gone over.

That is what is meant by accounting information - keeping track of the elements in the list you've visited.

I believe the generally accepted answer for this question is to use two iterators, one moving faster (two elements at a time) than the other (one element at a time). If there is a cycle in the list, at some point the two iterators will be pointing at the same node. Otherwise, the iterators will reach the end of the list, meaning no cycle exists.

Reply on news.ycombinator.com