Bala Krishna

Ranch Hand

Posts: 95

posted 11 years ago

I was asked this question recently in an interview. The interviewer wanted to know how to get the intersection of two unsorted arrays. My answer was to use the brute-force approach - for each element in one array, check if the element exists in the second array by looping thru it. He asked for a better approach, and my answer was to construct a binary search tree using the first array and do a look up with the elements in the second array. He didn't seem satisfied. Are there any better ways of doing this? TIA.

Ryan McGuire

Ranch Hand

Posts: 1142

9

posted 11 years ago

The brute-force method takes O(m*n) time (an O(m) linear search n times).

Your second method takes O(n * log m) time (an O(log m) search n times).

You could sort both arrays, then step through them both simultaneously. This would take O(log m + log n) tme for the sorts and O(n+m) time for the search.

Originally posted by Bala Krishna:

I was asked this question recently in an interview. The interviewer wanted to know how to get the intersection of two unsorted arrays. My answer was to use the brute-force approach - for each element in one array, check if the element exists in the second array by looping thru it. He asked for a better approach, and my answer was to construct a binary search tree using the first array and do a look up with the elements in the second array. He didn't seem satisfied. Are there any better ways of doing this? TIA.

The brute-force method takes O(m*n) time (an O(m) linear search n times).

Your second method takes O(n * log m) time (an O(log m) search n times).

You could sort both arrays, then step through them both simultaneously. This would take O(log m + log n) tme for the sorts and O(n+m) time for the search.

Jason Liao

Ranch Hand

Posts: 59

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 11 years ago

Well, the second way is O(m log m) to sort, plus O(n log m) to search. Ryan's third way is O(m log m + n log n) for the sorts, and O(m + n) to step through afterwards. Regardless, there's no requirement here to sort at all, and so the factor of log m can be avoided by forgetting about sorts or binary trees, and just using a hashtable of some sort (e.g. HashSet), such that the whole process is O(m) to store the first array, and O(n) to check the contents of the second. The only disadvantage I see is that this takes more memory as the hashtable would be a separate structure, and sorting would allow you to use the existing array. As long as memory isn't a major issue, I'd use a hashtable here.

[ June 08, 2006: Message edited by: Jim Yingst ]

[ June 08, 2006: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, *Twister*

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 11 years ago

Also, it may be worthwhile (in the context of an interview) to verify some assumptions. Are the values in each array unique? If not, then if one array contains value 0 twice, and the other contains it three times - does the result need to contain 0 twice, or is once enough? If it needs to be twice, my solution above can be modified slightly to handle it - it's just a bit more work. The main thing is to find out just what the requirements really are in this case.

"I'm not back." - Bill Harding, *Twister*

Ryan McGuire

Ranch Hand

Posts: 1142

9

posted 11 years ago

OOOooooppps! Thank you for reminding me of that.

Along those lines...

Big O complexity (for time or memory) is more meaningful when array sizes are fairly large and/or the code will have to run often. If m and n are both less than 100, say, it would probably be "better" to spend 15 minutes to program the brute force method that runs in 500 ms than to double the programming time in order to cut run time to 100ms. On the other hand, if the arrays each have a million elements, then some engineering might make sense.

Another option: you could write each array out to a file, call 'sort' on the command line for each and then call 'comm -12' on the files to find the lines they have in common.

Originally posted by Jason Liao:

The complexity of sorting algorithm is O(mLOG(m)), not O(LOG(m)!!!

OOOooooppps! Thank you for reminding me of that.

Along those lines...

Big O complexity (for time or memory) is more meaningful when array sizes are fairly large and/or the code will have to run often. If m and n are both less than 100, say, it would probably be "better" to spend 15 minutes to program the brute force method that runs in 500 ms than to double the programming time in order to cut run time to 100ms. On the other hand, if the arrays each have a million elements, then some engineering might make sense.

Another option: you could write each array out to a file, call 'sort' on the command line for each and then call 'comm -12' on the files to find the lines they have in common.

Bala Krishna

Ranch Hand

Posts: 95

posted 11 years ago

Thanks for your responses. Jim, I tried to paste here some thing you wrote.

My understanding is that with a HashSet/Hashtable, lookup operation is O(1) (for most cases). Can you please elaborate on why you think it's O(n) for the look up on the second array?

To be more specific, if we do an O(1) operation n times, will the complexity be the same as O(n)?

O(n) to check the contents of the second

My understanding is that with a HashSet/Hashtable, lookup operation is O(1) (for most cases). Can you please elaborate on why you think it's O(n) for the look up on the second array?

To be more specific, if we do an O(1) operation n times, will the complexity be the same as O(n)?

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 11 years ago

Each individual lookup is O(1), yes, and each individual insertion is also O(1). However m insertions are O(m), and n lookups are O(n).

If we're programming in, say, C/C++, and with no useful (relevant) libraries available, I agree. If it's Java (and if we're not banned from using standard libraries), the existence of HashSet and HashMap makes my solution

[ June 09, 2006: Message edited by: Jim Yingst ]

**[Ryan]: If m and n are both less than 100, say, it would probably be "better" to spend 15 minutes to program the brute force method that runs in 500 ms than to double the programming time in order to cut run time to 100ms.**If we're programming in, say, C/C++, and with no useful (relevant) libraries available, I agree. If it's Java (and if we're not banned from using standard libraries), the existence of HashSet and HashMap makes my solution

*easier*to program, I think.[ June 09, 2006: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, *Twister*

Jason Liao

Ranch Hand

Posts: 59

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

Alex Walker

Greenhorn

Posts: 2

posted 7 years ago

I realize that I'm kind of bringing this thread back from the dead, but I ran across this problem myself and I'm really trying to understand how best to implement the HashTable solution and why it's more efficient than the brute force approach. I came up with the class below, but I'm still a bit unclear on how this is more efficient.

Thanks,

Alex

Thanks,

Alex

posted 7 years ago

It's more efficient because you have to do less stuff. Lets say you have 5 elements in the first array, and 6 in the second. you may have to do up to 30 comparisons (comparing each element in the first with each element in the second). As the size of the two arrays go up, the total number of comparisons goes up exponentially. 10 and 10 would require 100 comparisons. 20 by 20 would require 400 comparisons. By the time you get to 1,000,000 by 1,000,000, the number of comparisons becomes HUGE - over a billion comparisons..

However, if you build a has out of one, that is linear. 10 elements takes 10 insertions. 20 elements takes 20 insertions. 1,000,000 elements takes 1,000,000 insertions. You then do lookups of the second array. again, 10 elements takes 10 lookups. 20 takes 20. 1,000,000 take 1,000,000.

The point is not to determine which is faster for a specific size arrays. The point is to determine which will slow to a standstill if the size of the arrays increase.

Doing brute force on arrays of size 2 and 3 will possibly be faster than building the hash table. However, if you coded the brute force and started it running, you could probably then design, code, test AND run the hastable version on 10^6 by 10^6 before the brute force finishes.

However, if you build a has out of one, that is linear. 10 elements takes 10 insertions. 20 elements takes 20 insertions. 1,000,000 elements takes 1,000,000 insertions. You then do lookups of the second array. again, 10 elements takes 10 lookups. 20 takes 20. 1,000,000 take 1,000,000.

The point is not to determine which is faster for a specific size arrays. The point is to determine which will slow to a standstill if the size of the arrays increase.

Doing brute force on arrays of size 2 and 3 will possibly be faster than building the hash table. However, if you coded the brute force and started it running, you could probably then design, code, test AND run the hastable version on 10^6 by 10^6 before the brute force finishes.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters? |