Hacker News Reader

Comment by Estragon | Hacker News Reader

It gave me a test concerning finding the "equilibrium index" of a sequence. It said to assume that the sequence is very long. (The question is repeated here: http://forums.sun.com/thread.jspa?threadID=676596&start=...) This problem seems underspecified, because it doesn't state whether you can iterate repeatedly over the sequence in question. If you can, it's easy. If you can't I'm not sure how to do it.

View on HN

I assumed that "sequence is very long" meant "the time (and space?) complexity of your solution matters". Iterating over the sequence x times doesn't change the time complexity, so long as x << n (i.e. it's O(n) whether x is 1, 2 or 3).

Unfortunately, revealing whether my assumption proved correct would give away how they assess the solution to this demo problem, which some might view as a spoiler.

EDIT: since people are posting actual solutions, I suppose mere analysis of the testing methodology is okay. My assumption was correct.

iterate repeatedly over the sequence in question

Does that ever seem like a good idea? The description suggests it may be a long list. That should give you a hint that you don't need to do this to solve the problem.

I'm pretty sure you have to iterate over it at least twice. I guess the specification is implicit in that.

The best case possible is to iterate the list once - you sum the list from left to right holding cumulative answers and if the final sum is zero, that index is a valid answer.

The worst case of the best algorithm is to iterate twice - firstly as above, and then again in the opposite direction, comparing values from the first iteration.

You can do whatever you want - it just has to return the correct result.

It isn't that difficult to solve, but I like the idea.

Reply on news.ycombinator.com