WearyMonkey
BAN USERIf the array is ordered, then you don't need the 'if (set.contains(current.next))' check. So it would be more efficient that way.
When it is not ordered, imagine the scenario:
list: A-B-C-D
array: B, A
So the block count is 1.
Loop over B, add 1 to count
Neither A or C (prev/next) are in the set so don't decrement count.
Count is now 1
Loop over A, add 1 to count (now 2)
A.next (B) is in the set, so decrement count
Count is now 1 again
Another example which closes a gap:
list: A-B-C-D
array: A, C, B
So the block count is 1.
Loop over A, add 1 to count
A.next (B) is not in the set so don't decrement
count is now 1
Loop over C, add 1 to count (now 2)
Niether B or D (prev/next) are in the set, so dont decrement
count is now 2
Loop over B, add 1 to count (now 3)
B.prev (A) is in the set, so decrement count (now 2)
B.next (C) is in the set, so decremetnt count (now 1)
count is now 1
count++ should be blocks++, don't know how to edit sorry.
Also if we are able to mark (e.g. add seen variables to them) the nodes, we don't need the set.
Thanks Lucas :)
Just one more thing. I realised if the array IS ordered, this simple solution requires no Set:
Because the block parts will be stored next to each other in the array as well.
- WearyMonkey June 04, 2013But if I was asking this interview question, the array would be unsorted ;) Or another interesting follow on question would be, 'How do you sort an array of linked list nodes?'.