Amazon Interview Question
SDE1sCountry: United States
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
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;
}
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;
}
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)
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]);
}
}
}
- Generation January 06, 2014