Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

Again with format

public static boolean findSum2(int[] a, int sum) {
        if (a.length == 0) {
            return false;
        }
        Arrays.sort(a);

        int i = 0;
        int j = a.length - 1;
        while (i < j) {
            int tmp = a[i] + a[j];
            if (tmp == sum) {
                System.out.println(a[i] + "+" + a[j] + "=" + sum);
                return true;
            } else if (tmp > sum) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }

- Gerry September 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you prove that this works. I am having a hard time convincing myself that we dont miss something...

- Tom September 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool FindNumbers(std::vector<int>& A, int sum, int& num1, int& num2)
{
// if don't want to use extra space
// then sort vector using std::sort
// and use binary search below in loop instead of find
std::set<int> s(A.begin(), A.end());
for each(int x in A)
{
int y = sum - x;
// vector::
std::set<int>::iterator it = s.find(y);
if ( it == s.end())
continue;
num1 = x;
num2 = *it;
return true;
}
return false;
}

- Anonymous September 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is one problem in solution.
e.g. sum = 10
and input array = {1, 3, 5, 7, 2}
Above algo will return 5 and 5 which is not correct

- Anonymous September 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean findSum2(int[] a, int sum) {
if (a.length == 0) {
return false;
}
Arrays.sort(a);

int i = 0;
int j = a.length - 1;
while (i < j) {
int tmp = a[i] + a[j];
if (tmp == sum) {
System.out.println(a[i] + "+" + a[j] + "=" + sum);
return true;
} else if (tmp > sum) {
j--;
} else {
i++;
}
}
return false;
}

- Gerry September 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can also be solved in order of n by using a boolean array of length equal to highest number in the input list..

iterate through each number and:

1. set the flag of that location (the current number) in bool array to "true".
2. subtract this number from the sum.
3. check on the location of the result of step 2, to see if it is a true.
- if yes, we have found the pair, exit.
- if no, continue iterating

- Harleen September 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

It woud work only for positive numbers. Array indexes cant be stored as negative

- veerf1 September 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

It woud work only for positive numbers. Array indexes cant be stored as negative

- veerf1 September 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

(1) First find the smallest no. in the array.
(2) add it to every element in the array.
(3) add it to the sum to be found also. i.e let sum += (2 * smallest)
(4) Construct a dictionary (dict) with elements as keys.
(5) Iterate through the array as follows:
for i = 1:length(a)
{
tsum = sum - a[i];
if(tsum > 0 && dict[tsum].exists())
{
print a[i] - smallest;
print tsum - smallest;
}
dict[a[i]] = true;
}

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

Steps:
1) Sort the array in nlog(n) time.
2) If sum of first and last element is == given number. Bingo !!
3) Else if sum is greater, do sum of first and second last element and check.
4) Else if sum is less, do sum of second and last element and check.
Repeat step 3 and 4 until you find the given sum OR the given number lies between the sum of previous computation and present computation, in that case sum does not exists. :)

- Abhishek September 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'll make some improvement.
after sorting,
2) use smallest and largest sums to check if the number is within the range.
3) binary search.

- joey September 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Insert the elements into hashtable.

While inserting x, check if I-x already exists. O(n) expected time.

stackoverflow.com/questions/4895405/checking-if-2-numbers-of-array-add-up-to-i

- IsAs October 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question was also asked in a Google Interview (1st Telephone interview).

- Devilfish October 26, 2011 | 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