Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
public static void printPairs(int []a,int x){
HashSet<Integer> h= new HashSet<Integer>();
for(int i=0; i < a.length-1; i++){
h.add(a[i]);
}
for(int i=0; i < a.length-1; i++){
if(h.contains(x-a[i])){
System.out.println(a[i]+" "+(x-a[i]));
h.remove(x-a[i]);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a={1,2,3,4,5,6,7,8,9};
printPairs(a,9);
}
There's no need to do 2 loops - one should be enough. Here's C#:
public static void FindSumPairs_Hashtable(int[] nums, int target)
{
Dictionary<int, int> ht = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++)
{
int factFamily = target - nums[i];
// Add to hashtable, factFamily as key, index as value
if (!ht.ContainsKey(factFamily))
{
ht.Add(factFamily, i);
}
// In case factFamily is same as current element
// e.g. -5, -4, -6, -3 looking for -10. We should not print (-5,-5)!
if (ht.ContainsKey(nums[i]) && i != ht[nums[i]])
{
Console.WriteLine("Sum {0} found: ({1} + {2}) at indices ({3}, {4})", target, factFamily, nums[i], ht[nums[i]], i);
}
}
}
#include<stdio.h>
void printPairs(int a[], int size, int x){
int i;
int low = 0;
int high = size-1;
for(i=0; i < size; i++){
if(a[low] + a[high] == x){
printf("%d %d\n",low,high);
low++;
}
else if(a[low] + a[high] > x)
high--;
else if(a[low] + a[high] < x)
low++;
if(low >= high)
break;
}
}
void main() {
//works for sorter array
int a[]={1,2,3,4,5,6,7,8,9};
printPairs(a,9,7);
}
gr8 solution ... but having a hard time following the question and the solution u posted
if a={-3,-2,-1, 1 ,3, 4 ,5 ,7, 11}
and printPairs (a, 9 ,9)
soln isnt suppose to be -->
7 + 3 + -1
7 + 5 + -3
7 + 4 + 1 + -3
...
...
...
Different pairs which sums up to 9
The strategy of Hash Table is used here.
The Key, Value pairs are stored in a hash table.
Consider an unsorted array S[1…n] . (Assuming they are non-negative distinct numbers)
Consider Query x = Sum of two elements in S[]
Algorithm:
for i in 1 to length[S]
key[i]=S[i] //Each element in the array when traversed is stored in key
value[i]=x-S[i] //the difference is stored in the value
for k in 1 to i
if(value[i] == key[k]) //finding if any key exists for a value
return(key[k],key[i])
The keys “key[k] and key[i]” are the two elements that sum to a query x.
Each step here takes a constant time of Θ(1) for comparing the key and value in the hash table.
Therefore, the Overall accesses in this strategy is given by 𝑻 𝒏 =𝚯(𝒏) .
First Sort -> O(nlogn).
- bluesky October 03, 2012Then start from min end and then find (X-min) which costs O(logn).
In total, the cost will be O(nlogn)