Bloomberg LP Interview Question Financial Software Developers
Why do we need a doubly linked list? Isnt a circular (singly )linked list suffice?
We dont need to traverse backwards, all we need to do is increment the counter and move forward and when the counter reaches 3, remove the element and reset the counter and countinue the same again.
The question is not complete. What will happen once the count of the people is less than 3? Does the count wrap around? In that case a circular linked list makes sense.
If on the other hand, we stop once the count is less than 3, a simple bool array will do. If the person still in the game, the corresponding element will have value 'true' and if not, 'false'.
I think linked list is enough, because you can calculate the index of element to be actually deleted without iterating over the whole list again and again.
In each round, if number of remaining people is greater or equal to 3, then remove the 2nd element in the linked list(index start from 0).
If number of remaining people is less than 3, then remove (n % 3 - 1)th element.
Until there is only one element left.
Circular Double Linked list
- Anonymous January 18, 2011