Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
3
of 5 vote

First Sort -> O(nlogn).
Then start from min end and then find (X-min) which costs O(logn).
In total, the cost will be O(nlogn)

- bluesky October 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

correct

- okaysh October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain with an example?

If the given array is not an arithmetic progression with common difference of 1 then how will you make sure that the result of X-min is within the array?

Sorted array 1,4,6,7 and X=5
Result: 4,1,-1,-2

- siva October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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);
	}

- coder October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
                }
            }
        }

- Xiang October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

#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);
}

- vishal October 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A clever way! One improvement: you need to prevent the given value X is twice of one integer in the array.

- fz October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good catch.. :)
Break should be when low>high instead low>=high.

- vishal October 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good catch.. :)
Break should be when low>high instead low>=high.

- vishal October 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anon October 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

anon in the question it says about pair not more then 2 element to be added to produce the result .in your case i hope its an NP complete problem.

- Anonymous October 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void pair(int a[], X)
{

int i = a[0];
int j = a[size-1];

while(i!= j)
{
if(a[i]+a[j] == X)
print (a[i], a[j]);
i++;
j--;
}

}

- NMB October 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 𝑻 𝒏 =𝚯(𝒏) .

- Mith October 06, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More