Back
Since someone broached the topic of job interview questions, I thought I'd
throw one out there that I had on the interview to my current job, 5-6
years ago. (I guess I did okay.)
It's a bit computer science-y, but it does have a strong math background to
it as well. I'll try to give a brief overview of the CS elements.
Suppose you have a (linked) list of elements, such that each element had a
pointer to the 'next' member or an 'end of list' marker. The 'next'
element is in fact allowed to be a 'previous' element in the list to form
rings. This means your list could look like:
[] -> [] -> [] -> [] -> EOL
or
[] -> [] -> []
| |
^ []
| |
[] <- []
or even
[] <-> []
Your task, should you choose to accept it, is to find an algorithm which
determines if the list ends (reaches an EOL marker) or continues forever.
For the requirements below, O(x) is 'Big O' notation. This means that the
governing formula's largest term is 'x'. For example, a simple quadratic
ax^2+bx+c is O(x^2). N refers to the number of elements in the list. To
do a simple 'walk' of the list (visit each node in turn) is an O(N)
fuction, since you hit N different elements. An O(1) function means it is
constant, like dividing a number by 2.
Here are the catches:
a) Any algorithm will suffice
b) Your solution must use no more than O(N) operations and O(N) memory
c) Your solution can use any number of operations, but can
only use O(1) [constant] memory. In other words, your use of memory must
be fixed regardless of the size of the list.
d) Your solution must use no more than O(N) operations and O(1) memory.
These are in increasing difficulty. I'm told that no one has ever gotten
the answer to (d) in an actual interview setting. (I do know the
solution.)
Good luck!
Nice problem! It's very similar to a problem I was planning on posting, so
I'm going to bite my tongue on this one. :-) I'll post my variation after
all is said and done, so that I don't inadvertently give anything away.
This riddle was popular 8 years ago in my University. :)
I thought that I completely forgot the solution, but it seems that not
completely, because I was able to reconstruct it without much problems.
I don't have a time to reconstruct (a), (b) and (c) now, it should be easy,
I think. So I only reconstructed the solution for (d). :-)
P.S. I think it may be better to always set meaningful subjects.
Solutions for (b) and (c) are fairly obvious, but it took me a little
longer to come up with a solution for (d). I'll not post it yet, though,
in case others want to try it.
So, does anyone want to post their solution? :-)
Tom
One solution for (d) is to walk the list with two pointers A and B. For
each 2 steps that A advances, have B advance one step. If A ever points to
the same location as B after 1 or more iterations, then there is a loop and
the list "continues forever".
My solution is essentially the same as Jason's. Since the slower pointer
(B) will never hit the same element twice, we have O(N) time.
How about this solution for (d). Reverse all pointers in-place. :)
I.e:
head -> node1 -> node2 -> NULL
is converted to:
head <- node1 <- node2 NULL
Now, if you ever encounter "head" again, this means there are loops, if you
come to NULL, there are no loops.
I leave it to you to prove that this algorithm works. You will want to
travel again and reverse all links, i.e. to restore the original list.
h -> a -> b >>> h -> a <- b
^ | becomes | ^
| v <<< v |
d <- c d -> c
We traveled and reversed the first link twice (because of loops) and all
other links in this case are walked reversed once. We came to head, this
means there are loops. Now, just travel the resulting list again and
reverse all links in the same way, this restores the original list.
This solution uses 2 * N steps (time) and one running pointer (memory).
Nice Mikhael, I was hoping there would be another neat solution, and you
provided it. :)
I'm actually surprised nobody has been able to solve part (d) of this
problem in an interview setting.
Mikhael's solution just gave me an idea for an extension to this puzzle:
For linked lists with a loop, find the total number of unique list
elements, N. I think it's possible in time O(N) and memory O(1). Feel
free to post your solution when you find it.
The solution I knew was the double pointer 'race' (single and double
increment). The pointer reversal is quite ingenious. :-)
As for why anyone wouldn't get it in an interview situation, it's a bit
hard to come up with something like that on the fly while holding a marker
in your hand up at a white board. With a bit of thought, sure. :-)
I'll need to ponder the new problem some. :-)
Tom
To find N, simply extend the "race" algorithm like so:
1. Start at A = B = head
2. Advance A two nodes for each node B advances, until either A = EOL or
A = B, counting the number of nodes each has traversed (call this a and
b, respectively)
3. If A = EOL, then N = a, and we are done
4. If A = B, then advance A until we reach B again, counting the nodes
along the way (call this c). This gives us the number of nodes in the
loop.
5. To get the number of nodes in the portion of the list outside of the
loop, set A = head and advance A by c nodes. Now set B = head, and
advance A and B until A = B, counting the nodes along the way (call
this d).
6. N = c + d
I like Jason's way of getting N. The solution I had in mind isn't nearly
as clean. (My way is: First apply the "race" algorithm; let b=number of
nodes before 'm', where 'm' is the node where the 2 pointers first match.
Then invert the directions of the pointers within the loop, starting at
'm', counting c=number of nodes in the loop. Then start from the head of
the list and find 'm' again, counting d=number of nodes before 'm'. If
b=d, then N=b+c; otherwise N=(b+c+d)/2. Then you have to re-invert the
pointer directions in the loop to get the original list back.)
Jason's solution is more intuitive as well as cleaner. Nice.