Siddhesh Deodhar

Ranch Hand

Posts: 118

posted 6 years ago

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 ?

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%] )

Siddhesh Deodhar

Ranch Hand

Posts: 118

posted 6 years ago

Hi Ramon,

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.

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.

Sidd : (SCJP 6 [90%] )

posted 6 years ago

Hi Siddhesh,

seems I misunderstood your interview question.

Anyhow, about autoboxing you can read at http://download.oracle.com/javase/1.5.0/docs/guide/language/autoboxing.html. It's the thing about automatic conversion from int to Integer and vice versa.

Cheers,

Ramon

seems I misunderstood your interview question.

Anyhow, about autoboxing you can read at http://download.oracle.com/javase/1.5.0/docs/guide/language/autoboxing.html. It's the thing about automatic conversion from int to Integer and vice versa.

Cheers,

Ramon

Siddhesh Deodhar

Ranch Hand

Posts: 118

posted 6 years ago

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.

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.

Sidd : (SCJP 6 [90%] )

posted 6 years ago

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).

See also http://en.wikipedia.org/wiki/Big_O_notation

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).

See also http://en.wikipedia.org/wiki/Big_O_notation

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

Campbell Ritchie

Sheriff

Posts: 53750

127

posted 6 years ago

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

Posts: 118

posted 6 years ago

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}

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}

Sidd : (SCJP 6 [90%] )

posted 6 years ago

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?

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?

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

posted 6 years ago

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).

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).

posted 6 years ago

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.

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.

With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |