adamhmc
BAN USER
Questions (2)
Comments (1)
Reputation 0
- 0of 0 votes
AnswersTwo integer arrays, write a function to out pairs of number.
- adamhmc
(The sequence is not important)
Ex:
input: [2,5,6,8,10,2,3,5] & [4,7,3,5,2,10,2,4] output:[2,2,3,5,10]
input: [2,2,2,3,4,5,6,7] & [2,2,5,5,7,10] output: [2,2,5,7]
I said saved the smaller array to hashmap (number as key, counter as value), and go through the larger array to generate pair by checking map.
Runtime: O(m) Space: O(n) ... m is larger array and n is smaller array
And, then he asked what if the device doesn't have much space to create map, then I said we should sort the array and use binary search.
Any better solution?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
I've asked the interviewer the range of numbers, he said that the range is just as large as the integer. Since I would say, if the range is smaller, we can use bucket sort or radix sort. However, it's not possible to do that.
- adamhmc January 23, 2011