All interviews are different, all candidates are different, all positions are different. The goal here is to provide some general questions to test engineering skills of candidates. These questions are common in recruiting process in technical companies like Google or Verisign.
How could you detect a loop in a linked list ?
It's say linked list, to be more precise you only have a pointer to the head of the list, and you know how to move to the next element of the list.
Of course you are not allowed to modify the list at all. And obviously you should try to propose an algorithm that do it in the most efficient way, let say you should try to target O(n).
In more programmer oriented : write a function A that take as parameter the first element of a List and return a boolean with value true if the given List has a loop, false otherwise. You know how to pass to the next element of the List : just call element.next.
For those who want to try to answer by themself, stop reading here.
One good answer is to have 2 iterators that walk through the elements of the List, but at different speed. One iterator move from 1 element per iteration, the second one move from 2 elements per iteration, and check if it meet the first iterator during it's move. How fast goes the second iterator can be configurable.
If at one point the second iterator (fast moving) meet the first one, there is a loop in the List. If the second iterator reach the end of the List, there is obviously no loop.
In pseudo code, it would be :
function A (head element of List list) return boolean :
it1 is initialized to the head element of list
it2 is initialized to the head element of list
while it2 has not reach end list
for number of element it2 will move
it2 move to the next element.
if the element of it2 is equal to the element of it1
there is a loop ! return true
it1 move to the next element
there is no loop. return false
As targeted, this algorithm will be on complexity of O(n), as the worst case is the last element looping to itself. When the last element loop to the first one, the algorithm will detect the loop in n / speed of the second iterator.
And finally, the memory footprint is very low.
What are the advantages of a LinkedList over an ArrayList ?
This question is more often ask in a different way : what are the
differences between a
LinkedList and an
ArrayList. But turning the question up side down like here is a bit more interesting. So what are the
advantages ?
The basic advantage of the
LinkedList is its O(1) insertion and deletion complexity for
any given element, while
ArrayList need to move back or forth the elements after the given element. Another advantage is the linearly increasing memory footprint of a
LinkedList, when
ArrayList memory (still linear but) increases by steps, and then perform sometimes costly memory copies. With such memory copies
ArrayList have an
amotized complexity in O(1), but this leads to non deterministic operations, which are unwanted when dealing with tight SLAs.
One more hidden advantage of the
LindekList is still in the topic of memory usage : it does not require to allocate blocks of memory, elements stored in
LinkedList do not require to be allocated in contiguous memory. Just notice that fragmentation of the memory is not always seen as good point.
