## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

``````int Mul(int a,int b)
{
int ans=0;
int sign= ((a^b)>>31);
a=abs(a);
b=abs(b);
while(b)
{
if(b & 0x01 )ans += a;
b >>= 1;
a <<= 1;
}
return sign?(~ans+1):ans;
}``````

Comment hidden because of low score. Click to expand.
0

I am not sure whether it works for negative numbers..I.e. try Mul(-11, -11), expected result is 121...

Comment hidden because of low score. Click to expand.
0

thanks for pointing it out! i fixed the code to work for negative number,

Comment hidden because of low score. Click to expand.
0

cool way to find the sign !

Comment hidden because of low score. Click to expand.
0

Woah, I just did this in my head. How the hell did that work...

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

The question said no multiplication operation, so doing

``return sign?-ans:ans;``

is using the -1 * ans isn't it?

Shouldn't it be

``sign ? ~ans + 1 : ans``

Comment hidden because of low score. Click to expand.
0

Is negating something considered multiplying by the compiler?

And yes,

``~ans +1``

should correctly flip the sign as well.

Comment hidden because of low score. Click to expand.
0

corrected as suggested by bunnybare

Comment hidden because of low score. Click to expand.
0

A good optimization here is to use the smaller of a and b as the loop index (i.e. swap a and b if b < a). For large values of a/b, you can optimize this even further by doing it in log(N) time if the interview allows you bit shifts. Something like this:

``````if a == 0: return 0
if a == 1: return b
half_a = a >> 2
rem_a = a % 2
sum_half_a = sum(half_a, b)
if rem_a == 1:
return b + sum_half_a + sum_half_a
else:
return sum_half_a + sum_half_a``````

Comment hidden because of low score. Click to expand.
0

Trivial:

``exp(ln(a) + ln(b))``

Comment hidden because of low score. Click to expand.
0

are you gonna implement exp and ln for complex numbers?

Comment hidden because of low score. Click to expand.
0

Michael's being a little bit snarky, but if we're gonna assume our computer's too crippled to do multiplication, why wouldn't we break out the slide rule? ;)

Comment hidden because of low score. Click to expand.
2

To convert from positive number to negative number, the following should work, correct?

number = 0 - number;

Comment hidden because of low score. Click to expand.
0

This is cool, the only issue I see is overflow.

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

``````int multiply( int a, int b) {
if (a==0 || b==0)
return 0;
int sign = 0, result;
if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
sign = 1;
}
int a1 = abs(a);
int b1 = abs(b);
while (b1--) {
result + = a1;
}
if (sign) {
return result/(-1);
} else {
return result;
}
}``````

Comment hidden because of low score. Click to expand.
0

This won't work for negative numbers.

Comment hidden because of low score. Click to expand.
0

Can you check now..
updated after .<--> comment.

Comment hidden because of low score. Click to expand.
0

Yeah now it will work...Good job sjain...

Comment hidden because of low score. Click to expand.
0

You are not allowed to multiply or even divide. If you could use divide you could simply use res = a/(1/b);
:)

Following does it with no multiply or divide and with least possible iterations.

``````private static int multiply(int a, int b) {

if(a == 0 || b == 0)
return 0;

int res = 0;
int absA = Math.abs(a);
int absB = Math.abs(b);
if ((a > 0 && b > 0)  || (a < 0 && b < 0)) {
a = absA;
b = absB;
}
if( absA > absB) {
while(absB > 0) {
res+=a;
absB--;
}
} else {
while(absA > 0) {
res+=b;
absA--;
}
}
return res;
}``````

Comment hidden because of low score. Click to expand.
0

The question does not say that you can't use divide. So I guess 1/a/b solution might be OK.

Comment hidden because of low score. Click to expand.
0

@ Simpleone: Your code has a bug, try passing in (-1, 1) or (-1,2) and it will return a +ve integer. Just tweaked your code and verified that it works, changed return type to double to avoid overflow on int.maxvalue. Updated code is in c#. Edited - just for the heck of it added a way to do the same for an array of values.

``````protected internal static double Multiply(int a, int b)
{
if (a == 0 || b == 0) return 0;
double res = 0;
int absA = Math.Abs(a);
int absB = Math.Abs(b);

if (absA > absB)
{
while (absB > 0)
{
res += absA;
absB--;
}
}
else
{
while (absA > 0)
{
res += absB;
absA--;
}
}
if ((a > 0 && b < 0) || (a < 0 && b > 0))
{
res = -res;
}
return res;
}

/// <summary>
/// Method that receives an integer array and returns the product without using mutliply or divide operators.
/// </summary>
protected internal static double MultiplyArray(int[] a)
{
if (a.Length == 0 || a.Contains(0)) return 0;
int iNeg = 0;
int iPos = 0;
int iL = a.Length;
for (int i = 0; i < iL; i++)
{
if (a[i] < 0) iNeg++;
else iPos++;
a[i] = Math.Abs(a[i]);
}
Array.Sort<int>(a);
double res = a;
for (int i = 1; i < iL; i++)
{
res = Multiply((int)res, a[i]);
}

if (iNeg!=iPos)
{
res = -res;
}
return res;
}``````

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

``````public class Solution {
public static int multiply(int a, int b) {
if (a == 0 || b == 0) {
return 0;
}
if (b == 1) {
return a;
}
boolean positiveFlag = true;
if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
positiveFlag = false;
}
a = Math.abs(a);
b = Math.abs(b);

if (a < b) {
a ^= b;
b ^= a;
a ^= b;
}

int ret1 = multiply(a, b/2);
int ret2 = multiply(a, b%2);
if (positiveFlag == false) {
return -(ret1+ret1+ret2)
}
else {
return ret1+ret1+ret2;
}
}

}``````

Comment hidden because of low score. Click to expand.
0

Well you are getting the right result but what was the reason for doing all these computations? Can you please explain.

Comment hidden because of low score. Click to expand.
0

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Multiply
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(Multiply(11,11));
}

private static int Multiply(int a, int b)
{
int result = 0;
while (true)
{
if (b == 1)
{
result = result + a;
break;
}
else if((b % 2) != 0)
{
result = result + a;
}

a = a + a;
b = b / 2;
}
return result;
}
}
}``````

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

``````int multiply(int a, int b)
{
if(b == 0)
return 0;
if(b > 0)
return a + multiply(a, b-1);
if(b < 0)
return (-a) + multiply(a, b+1);

}``````

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

This works for both positive, both negative and a case where one is negative and positive number. Do check.

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

ex: x*y
int RES = 0;
for(int i = 0; i<x;i++)
{
RES += y;
}

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

``````int multiply( int a, int b )
{
if( a==0 || b==0 )
return 0;
return (a/(1.0/b));
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

Lucky Fellow to get this question

int Multiply(int number, int multiple)
{
int num=number;
while(multiple--)
number=number+num;
retrun number;
}

Comment hidden because of low score. Click to expand.
0

don't forget about handling negative numbers..

Comment hidden because of low score. Click to expand.
0

Lol

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

/**
*
* PropertiesFor the natural numbers, integers, fractions, and real and complex numbers, multiplication has certain properties:

Commutative property : x*y=y*x;
The order in which two numbers are multiplied does not matter;
Associative property : (x*y)*z=x*(y*z);
Expressions solely involving multiplication are invariant with respect to order of operations;
Distributive property : x*(y+z) = x*y+x*z;
Holds with respect to multiplication over addition. This identity is of prime importance in simplifying algebraic expressions:
Identity element : x*1=x;
The multiplicative identity is 1; anything multiplied by one is itself. This is known as the identity property:
Zero element : x*0=0;
Any number multiplied by zero is zero. This is known as the zero property of multiplication:
Zero is sometimes not included amongst the natural numbers.
There are a number of further properties of multiplication not satisfied by all types of numbers.
Negation : x*-1 = -x;
Negative one times any number is equal to the opposite of that number.
-1*-1=1;
Negative one times negative one is positive one.
The natural numbers do not include negative numbers.
Inverse element
Every number x, except zero, has a multiplicative inverse, , such that .
The natural numbers and integers do not have inverses.
Exculding folating and complex numbers mulitple
*/
public static long mulitple (int a, int b){
long mulitplicationResult = 0;
boolean isPositiveResult = false;
// Retrun zero if any one input has zero
if (a == 0 || b==0){
return mulitplicationResult;
}
//Sign calculation of result
if( (a<0 && b<0) || (a>0 && b>0) ){
isPositiveResult = true;
}else{
isPositiveResult = false;
}
//Converting -ve values of the input into +ve
if(a<0) a=(~a+1);
if(b<0) b=(~b+1);
//For example: 3 multiplied by 4 can also be calculated by adding 3 copies of 4 together.
while( b>0 ){
mulitplicationResult += a;
b--;
}
return isPositiveResult?mulitplicationResult:(~mulitplicationResult+1);
}

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

suppose we have a , b
1) First produce arr where arr[i]=i*a , (1<=i<=9). we can do it with 9 addition.
2) For each digit in b[i]=k add i zero on right-side of the arr[k] and add them to each other.
The result is a*b.
It is the obvious way that we calculate multiply on paper!
This solution is useful for bignumber multiplication too.

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

this is a solution in java and it doesn't involve a loop, the answer is pretty simple:

``````public class Multiply{

public static void main (String[] args){
System.out.println("The result is:" + multiply(5,-13));
}

private static int multiply(int i, int j) {
double k = i;
double l = j;
return (int)(k/(1/l));
}
}``````

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

This solution works if multiplication is among either positive or negative numbers. The ~ operator is used just to make positive number to negative and negative number to positive

``````// multiply 2 no without using mul operat.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<stdio.h>
using namespace std;
void main()
{
int a, b;
int flag1=0,mul=0;
int flag2=0;
printf("enter the two numbers\n");
scanf_s("%d%d",&a,&b);
if(a<0)
{
flag1=1;
a=~(a)+1;
}
if(b<0)
{
flag2=1;
b=~(b)+1;
}
for(int i=0;i<b;i++)
{
mul=mul+a;
printf("the mul inside for loop %d\n",mul);
}
if(flag1==1 || flag2==1)
{
if(flag1==1 && flag2==1)
{
printf("both numbers are negative\n");
}
else
{
mul=~(mul)+1;
}
}
printf("%d",mul);
}``````

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

``````function multiply(a, b)
return exp(ln(a) + ln(b)``````

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

Can any one help me to find the multiplication of two floating point numbers without using * operator or any library fn that uses * internally....
I think we can take the integral & fractional part separately and multiply like above mentioned code for integral part. But m having difficulty with fractional part ...But if any one can help me to identify the bit position of fractional part in float, then it can be done easily....

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

``````int function multiply(int a, int b)
{
int result = 0;
if ( b >= 0 )
{
while( b-- > 0 )
result += a;
}
else
{
while( b++ < 0 )
result -= a;
}

return \$result;
}``````

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

``````public int sum(int a, int b) {
int result = a ^ b;
int carry = a & b;
while (carry != 0) {
carry <<=  1;
int x = result;
result ^= carry;
carry &= x;
}
return result;
}

public int multiply(int a, int b) {
int result = 0;
if (a == 0 || b == 0) {
return result;
}
boolean negative = a > 0 && b > 0 || a < 0 && b < 0 ? false : true;
a = a > 0 ? a : -a;
b = b > 0 ? b : -b;

int k = 0;
while (b != 0) {
if ((b & 1) > 0) {
result = sum(result, a << k);
}
k++;
b = b >>> 1;
}
if (negative)
result = sum(~result, 1);

return result;
}``````

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

method with a helper function

``````def multiply(a,b):
sign = (a<0 and b < 0) or (a>0 and b> 0)
def multiplyHelper(a,b):
if b == 0 or a == 0:
return 0
if b%2 == 0:
return multiplyHelper(a, b/2) + multiplyHelper(a, b/2)
else:
return a + multiplyHelper(a, b-1)
ans = multiplyHelper(abs(a), abs(b))
return ans if sign else ~ans+1

assert 35 == multiply(-7,-5)
assert -35 == multiply(-7, 5)``````

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

``````private static int multiply(int a, int b) {

if(a == 0 || b == 0)
return 0;

int res = 0;
int absA = Math.abs(a);
int absB = Math.abs(b);
if ((a > 0 && b > 0)  || (a < 0 && b < 0)) {
a = absA;
b = absB;
}
if( absA > absB) {
while(absB > 0) {
res+=a;
absB--;
}
} else {
while(absA > 0) {
res+=b;
absA--;
}
}
return res;
}``````

Comment hidden because of low score. Click to expand.
0

@ Simpleone: Your code has a bug, try passing in (-1, 1) or (-1,2) and it will return a +ve integer. Just tweaked your code and verified that it works, changed return type to double to avoid overflow on int.maxvalue. Updated code is in c#. Edited - just for the heck of it added a way to do the same for an array of values.

``````protected internal static double Multiply(int a, int b)
{
if (a == 0 || b == 0) return 0;
double res = 0;
int absA = Math.Abs(a);
int absB = Math.Abs(b);

if (absA > absB)
{
while (absB > 0)
{
res += absA;
absB--;
}
}
else
{
while (absA > 0)
{
res += absB;
absA--;
}
}
if ((a > 0 && b < 0) || (a < 0 && b > 0))
{
res = -res;
}
return res;
}

/// <summary>
/// Method that receives an integer array and returns the product without using mutliply or divide operators.
/// </summary>
protected internal static double MultiplyArray(int[] a)
{
if (a.Length == 0 || a.Contains(0)) return 0;
int iNeg = 0;
int iPos = 0;
int iL = a.Length;
for (int i = 0; i < iL; i++)
{
if (a[i] < 0) iNeg++;
else iPos++;
a[i] = Math.Abs(a[i]);
}
Array.Sort<int>(a);
double res = a;
for (int i = 1; i < iL; i++)
{
res = Multiply((int)res, a[i]);
}

if (iNeg!=iPos)
{
res = -res;
}
return res;
}``````

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

Try something like this:

public int myMethod(int i, int j) {
int x = 0;
if (j >= 0) {
for (int k = 1; k <= j; k++) {
x = x + i;
}
return x;

} else if ((i < 0) && (j < 0)) {
for (int k = 1; k <= -i; k++) {
x = x + j;
}
return (-x);

} else {
for (int k = 1; k <= i; k++) {
x = x + j;
}
return x;

}

}

Comment hidden because of low score. Click to expand.
0

This is the easiest one of all others and work perfectly :)

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

{
int main(){
int a,b;
cout<<" ";
cin>>a>>b;
for(int i=0;i<b;i++){
}

getch();
return 0;
}
}

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

int multiply(int a,int b)
{
while(b!=0)
{ if(b&1)
{ result=result+a;}
a=a<<1;
b=b>>1;
}
return result;
}

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

public static int multiply(int a, int b){
if(a==0||b==0) return 0;
int sign = 0;
if(((a>>31) &0x1) == 1){
sign = 1;
a = ~a + 1;
}if(((b>>31) & 0x1) == 1){
if (sign == 0)sign = 1;
else sign = 0;
b = ~b + 1;
}

int mul = 0;
//System.out.println(b + " "+ a);
while(b>0){
if((b & 0x1) > 0){
mul +=a;
}
b = b>>1;
a = a<<1;
}
if (sign ==1)
return ~mul + 1 ;

return mul;
}

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

def multi(a:Int, b:Int):Int ={ if(b==1) a else multi(a+a,b-1);}

Comment hidden because of low score. Click to expand.
0
of 2 vote

The function should return long for two int.

``````long mulwithoutmul(int a, int b)
{
long res=0;
long la;
int i;
char neg = ((a^b)>>31);
a = abs(a);
b = abs(b);
if(a == 0 || b == 0)
return 0;
la = a;
for(i = 0 ; i < 31 ; i++)
{
if((b>>i)&0x00000001)
res+=la<<i;
}
if(neg)
{
res = 0-res;
}
return res;
}``````

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

``````!python
def multiply(x, y):
if x == 0 or y == 0: return 0

negative = False
if x < 0 and y < 0: x = -x; y = -y;
elif x < 0: x = -x; negative = True
elif y < 0: y = -y; negative = True

# Small optimization
counter_range = y
if y > x: add_value = y; counter_range = x

value = 0
for i in range(counter_range):

return -value if negative else value``````

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

why not a recursive algo like this?

public static int simpleMultiply(int one, int two)
{
if(two==0 || one ==0)
return 0;
if(one>0 && two>0)
{
return one+simpleMultiply(one,two-1);
}
else
if(one<0 && two <0)
{
return simpleMultiply(0-one,0-two);
}
else
if(one<0 && two >0)
{
return simpleMultiply(0-one,0-two);
}
else
if(one>0&&two<0)
{
return (0-one)+simpleMultiply(one,two+1);
}
return 0;
}

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

``````public class convert {

/**
* @param args
*/
public static void main(String[] args) {
System.out.println(multiply(10,300));
}

private static int multiply(int a, int b) {
int result=0;
if(a>b)
{
for(int i=1;i<=b;i++)
{
}
}
else
{
for(int i=1;i<=a;i++)
{
}
}
return result;
}

private static int add(int a, int b) {
int carry=0;
while(b!=0)
{
carry=a&b;
a=a^b;
b=carry<<1;
}
return a;
}
}``````

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

``````def simpleMul(a,b)
i = a
(b-1).times do
a += i
end
a
end
p simpleMul(4,8)``````

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

Very Simple Logic
Input A, B
--> Left Shift the value means multiply by 2
--> Add A the above result once if B is odd number

This solution works irrespective of signs.

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

``````public static int multiply(int a, int b){
int product = 0;
for(int i=0; i<Math.abs(a); i++){
if(a<0){
product = product - b;
}else{
product = product + b;
}
}
return product;``````

}

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

Laziest Solution:-

a=5, b=2
result= a / (1/b) = 5 / (1/ 2) = 10

Note: not using mulitiply operator

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

``````def mult(x, y)
total = 0
y.times do
total += x
end
total
end``````

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.

### 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.