Riverbed Interview Question
Software Engineer / DevelopersCountry: United States
@eugene.yarovoi: Thanks.
public static int[] sumNums(int[] array, int targetSum) {
if(array == null) return null;
int n = array.length;
if(n < 2) return null;
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i < n; i++) {
int num = array[i];
int diff = targetSum - num;
if(set.contains(diff)) {
return new int[] {num, diff};
}
set.add(num);
}
return null;
}
We can sort the input array and then do a scan from both ends. O(nlogn) + O(n) = O(nlogn) time complexity. O(1) space.
- vijay January 14, 2012