Hi all
Recently I answered an interview and my client asked me following question

Suppose there is an array of size 'N' containing elements from 1 to N in any order, example
if there is array of size 5 then it will have elements {2,1,3,4,5} or {1,2,3,4,5}.

He wanted me to write a method which will detect a wrong elemnt if present in array. like if array contains {2,1,9,4,5} then I will have to written element 9
as wrong element becuse correct element should have been 3. Wrong element can be any number.

I followed following approach

He said OK on it but I felt like he was looking out for something different. I dint go for converting the array to some sorted data structure because that would have duplicated memory. Here since I am using Arrays.asList, same memory will be utilized.

Any more efficient algorithm suggestions ?

Good, Better, Best, Don't take rest until, Good becomes Better, and Better becomes Best.
Sidd : (SCJP 6 [90%] )

I had this logic in my mind but since question had sentence "Wrong element can be any number" your algorithm will fail if content of array is {3,2,1,2,5}.
Here element '2' present at index 1 or index 3 is invalid because there should have been element '4' which is missing.
My algorithm will detect such element.

Secondly can you please elaborate on "autoboxing issue" that you found in my algorithm.

Apologies. Method name should be returnWrongElement instead of returnMissing

Motive behind the algorithm is to return wrong element(i.e. element that is out of sequence) present in array.

Ramon,

I am aware of autoboxing, just wanted to know how it is effecting my algorithm . I don't think converting Integer to int will be a big overhead in my algorithm.

You could replace the List with a HashSet, as that has a somewhat faster way of checking for existence:
Now you will only need to loop through the array once (for adding) instead of for each element.

Another option could be to create a copy of the array, sort it, and check the wrong values

A small comparison in code complexity:
- your original code loops inside a loop, so it has complexity order O(N^2) where N is the size of the array.
- my first fix only loops only one level; the hash set lookup is O(1). The complexity is therefore O(N).
- the second fix first sorts the array in O(N*log N), then loops in O(N). The total complexity is therefore O(N*log N).

Have we understood the question correctly? I thought the idea was not to sort the array (if it's an array, why are we using Lists and Sets), but to find whether it has an element outwith the range 1 .. array.length. That can be done easily with a linear traversal, running in O(n) complexity.

Siddhesh Deodhar
Ranch Hand

Joined: Mar 05, 2009
Posts: 118

posted

0

Sorry if there was confusion. I will repeat question in different way.

if there is array {1,2,5,9,3}, my method should return element which is out of sequence. In this case its 9.

if array is { 2,1,2,4,5}, my method should return element that is out of sequence. In this case it is 2( position doesn't matters)

if there is array {2,1,5,3,4} my method should return 0, because all elements in sequence are present

Rob, i guess both, set and copy array methods will not work if array is {1,2,5,9,3}

Siddhesh Deodhar wrote:Rob, i guess both, set and copy array methods will not work if array is {1,2,5,9,3}

The Set method has one issue I overlooked; Set doesn't have the get method which I was still calling. It would also filter out the duplicate 2, so that solution is actually quite bad.

You're right about my copy array code not working correctly. That's because the check of "copy[i - 1] != i" is insufficient. There are three possibilities that should be filtered out:
1) copy[i -1] <= 0. It's out of range, so invalid.
2) copy[i - 1] > array.length. It's out of range, so invalid.
3) copy[i - 1] < i. This can only occur if copy[i - 1] <= 0 (already handled) or copy[i - 1] is a duplicate.

I've changed the guard to "copy[i - 1] < i || copy[i - 1] <= 0 || copy[i - 1] > array.length", and with your three inputs I get results 9, 2 and 0. Your original code returned 0 for the second element, as it missed the duplicate.

One more thing to think about - what will be returned if the array contains 0?

I believe the basic premise of the problem is that the array is supposed to contain positive integers only (though nowhere explicitly mentioned). If this is not the case, then we need to modify the suggested solutions a bit.

By the way, as Rob explained, the sorted-copy-of-array solution works and has a complexity of O(N*log N), due the sorting involved. The code piece I suggested above also works and has a lesser complexity of O(N) (which I believe would be the minimum one could achieve for the given problem).

define a set of rules to find out odd element from a given array. can you list out the rules?
<edit>
for example : {1, 2, 4, 8, 10} => add element is 1
</edit>

Rob Spoor wrote:You could replace the List with a HashSet, as that has a somewhat faster way of checking for existence:

While the HashSet has a much better speed in Big-Oh sense, for the example lists, its highly unlikely that it would actually be faster. A for-loop indexing through a small array is very fast. Just calculating the hashCode() of each value is likely to cost more than the for-loop. For 100 values, it probably is a wash. For lots of values, of course the HashSet is a big winner.