aspose file tools*
The moose likes Java in General and the fly likes Need suggestion on implementation Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Need suggestion on implementation" Watch "Need suggestion on implementation" New topic
Author

Need suggestion on implementation

Siddhesh Deodhar
Ranch Hand

Joined: Mar 05, 2009
Posts: 118
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%] )
Ramon Anger
Ranch Hand

Joined: Apr 19, 2011
Posts: 56

Hi Siddhesh,

maybe it was an autoboxing issue. I could think of the following code:



Cheers,
Ramon


Blackbelt on BlackBeltFactory.com.
Siddhesh Deodhar
Ranch Hand

Joined: Mar 05, 2009
Posts: 118
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.
Ramon Anger
Ranch Hand

Joined: Apr 19, 2011
Posts: 56

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
Siddhesh Deodhar
Ranch Hand

Joined: Mar 05, 2009
Posts: 118
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.

Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19784
    
  20

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


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40052
    
  28
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
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}
Aditya Jha
Ranch Hand

Joined: Aug 25, 2003
Posts: 227

Usually, I prefer not to give code piece as answers. However, given the confusion over the question, I suggest the following:


You can further extend this method to return all invalid values from the array.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19784
    
  20

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?
Aditya Jha
Ranch Hand

Joined: Aug 25, 2003
Posts: 227

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).
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

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>
Pat Farrell
Rancher

Joined: Aug 11, 2007
Posts: 4659
    
    5

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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Need suggestion on implementation