Amazon Interview Question for SDE1s


Country: United States




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

public static int divideWithoutOperator(int num, int divisor) {
		
		// handle case in which divisor is 0
		if (divisor == 0) {
			return 0;
		}
		
		
		int quotient = 0;
		
		int iterator = 1; 
		
		// to handle -ve numbers
		if (num < 0) {
			num = num * -1;
			iterator = -1;
		}
		
		while (num > divisor) {
			num = num - divisor;
			quotient = quotient + iterator;
		}
		
		return quotient;
	}

- Generation January 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is a bug is in the while condition.
The while condition should be while(num>=divisor)
Because for divisors which divide the number with a zero remainder, the quotient returned is 1 less.
After correcting the while condition to while(num>=divisor), the program would return the correct quotient for all possible sequence of number and divisor

- lks January 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the above code will not give correct result if divisor is negative

- Alok January 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int divideWithoutOperator(int num, int divisor) {
		
		// handle case in which divisor is 0
		if (divisor == 0) {
			return 0;
		}
		
		
		int quotient = 0;
		
		int iterator = 1; 
		
		// to handle -ve numbers
		if (num < 0) {
			num = num * -1;
			iterator = -1;
		}
		
		while (num > divisor) {
			num = num - divisor;
			quotient = quotient + iterator;
		}
		
		return quotient;
	}

- Generation January 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

generally sore will have a complexity of nlog(n) and search log(n). So it would be n log(n) log (n)

- nachiapan January 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Q2. after sorting the array, we can run the following code to make it O(n).

bool check(int * arr, int n) {
    // suppose arr is a sorted array
    int i = 0;
    int j = n-1;
    while (i < j) {
        int sum = arr[i] + arr[j];
        if (sum == n) {
            return true;
        }
        else if (sum > n) {
            j--;
        }
        else {
            i++;
        }
    }
    return false;
}

- Jason Lee January 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int divide(int number, int divisor){
      int custom= 0;
      while(number >=divisor){
            custom++;
            number= number-divisor;
         
      }
      return custom;
   }

Simple code to solve the problem dealing with ints.

- Anonymous January 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

question 1 can be solved with a right bitwise shift.

- Christian January 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Right bitwise shifting will divide given no. by power of 2. Bit shifting is definitely not the solution..
So, 100>>1 will be 100/pow(2,1) ie 100/2 = 50
100>>2 will be 100/pow(2,2) ie 100/4 = 25

- Amit Petkar January 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1.As for dividing two numbers, if we can not use "/", why not use "*" instead?
Take "a / b" as an example. We can do following steps:
(1)figure out the sign of the result: sign
(2)define a rough range of the result: [L, R]
(3)use binary search to find the result in the range, every time we only need to figure out the b * M, where M = (L+R)/2, and compare it with a to narrow the range.
Time complexity: O(log(a))
Space complexity: O(1)
following is C++ code:

bool div(int a, int b, int& res)
{
    if(b == 0) return false;
    
    //figure out the sign of result
    int sign = 1;
    if(a < 0){
        a = -a;
        sign *= -1;
    }
    if(b < 0){
        b = -b;
        sign *= -1;
    }
    
    //now a >= 0 and b >= 0
    if(a < b){
        res = 0;
        return true;
    }
    if(b == 1){
        res = sign * a;
        return true;
    }
    
    //now a >= b && b >= 2, so a rough range is [1, a/2]
    int L = 1, R = a >> 1, M, pro;
    while(L <= R){
        M = (L + R) >> 1;
        pro = b * M;
        if(pro <= 0){//multiply overflow
            R = M - 1; 
            continue;
        }
        
        if(a == pro){
            res = sign * M;
            return true;
        }
        else if(a < pro) R = M - 1;
        else L = M + 1;
    }
    res = sign * R;
    
    return true;
}

2. It can bd done by:
(1)sort out the array
(2)for each element do a binary search
Time complexity: O(nlog(n))
Space complexity: O(1)

- uuuouou January 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Q1: Use logarithms.

pow(2, log2(dividend) - log2(divisor))

. Complexity O(1).

- Some Young Guy January 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Q1)

public static int divide(int divisor, int dividend) {

	int quotient = 0;
	while (divisor <= dividend) {
	    dividend = dividend - divisor;
	    quotient++;
	}
	return quotient;
    }

Q2)

Method 1: Sort the array and then do the following (O(n log n)):
p=0,q=n-1;
while(p<q)
{
  if(a[p]+a[q]==k)
  {
      cout<<a[p]<<"\t"<<a[q];
      p++;
      q--;
   }
   else if(a[p]+a[q]>k)
      q--;
   else 
      p++;
}

Method 2: We can use set (O(n)):
public static void findTwoNumbers(int a[], int sum) {

	Set<Integer> set = new HashSet<Integer>();
	int count = 0;
	for (int i = 0; i < a.length; i++) {
		if (!set.contains(a[i])) {
			int remainder = sum - a[i];
			if (set.contains(remainder)) {
				System.out.println(++count + ") Found sum: " + sum + " = " + a[i] + " + " + remainder);
			}
			set.add(a[i]);
		}
	}
}

- thelineofcode January 06, 2014 | 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