## Microsoft Interview Question for SDE-2s

Country: United States
Interview Type: Phone Interview

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

change the numbers representation say first number =(a+b+c+d) second number =(e+f+g+h) and then the product will be a polynomial expression

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

I think they was interested in Karatsuba multiplication, that give us O(n^(1,6)) rather that O(n^2) for classical approach.

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

A possible solution could be to use an alternate representation of the number say in a exponent form say m^n.

Once the representation is done then you can multiply arbitrary number of such numbers by doing exponent addition with common base for ex:

(2^a)*(2^b)*(2^c)*....*(2^z) = 2^(a+b+c+...+z)

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

Store them in lists and multiply number by number, like grade school multiplication

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

Store digits and multiply them one at a time, like grade school math, though order goes to n^2.

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

change the numbers representation say first number =(a+b+c+d) second number =(e+f+g+h) and then the product will be a polynomial expression

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

On a very serious note, this is what people tend to do, for real.
codeproject.com/Articles/36323/BigInt

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

Is this ok ?
Bit manipulation.

until Num2 becomes 0
- Shift Num2 to right. Shift Num1 to left.

Complexity Log(N2)

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

using System;

public class Program
{
public static void Main()
{
Console.WriteLine( GetProduct("18888888888888888888888888","19999999999999999999999999999999999999999999999999999999999"));
}
public static string GetProduct(string s1,string s2)
{
int digit1=0;
int digit2=0;

char[] str1=s1.ToCharArray();
char[] str2=s2.ToCharArray();
int carry;
string[] result=new string[str1.Length];
string finalproduct=string.Empty;

for(int i=str1.Length-1;i>=0;i--)
{
digit1=str1[i]-'0';
string resval=string.Empty;
carry=0;
int j;
for(j=str2.Length-1;j>=0;j--)
{
digit2=str2[j]-'0';

int product=digit1*digit2+carry;
carry=product/10;
resval=resval+(product%10);

}
if(carry>0)
{
resval=resval+carry;
}
{
resval="0"+resval;
}
result[i]=resval;
}

int max=findMax(result);
int count=0;
int car=0;

while(count<max)
{
int sum=0;

for(int x=0;x<result.Length;x++)
{

if(count<result[x].Length)
{

sum+=result[x][count]-'0';
}

}
sum+=car;
car=sum/10;
int p=sum%10;
finalproduct=p+finalproduct;
count++;
}

finalproduct=car+finalproduct;

return finalproduct.TrimStart('0');

}

public static int findMax(string[] s)
{
int max=0;
for(int i=0;i<s.Length;i++)
{
int len=s[i].Length;
max=Math.Max(max,len);
}
return max;
}
}

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

``````using System;

public class Program
{
public static void Main()
{
Console.WriteLine( GetProduct("18888888888888888888888888","19999999999999999999999999999999999999999999999999999999999"));
}
public static string GetProduct(string s1,string s2)
{
int digit1=0;
int digit2=0;

char[] str1=s1.ToCharArray();
char[] str2=s2.ToCharArray();
int carry;
string[] result=new string[str1.Length];
string finalproduct=string.Empty;

for(int i=str1.Length-1;i>=0;i--)
{
digit1=str1[i]-'0';
string resval=string.Empty;
carry=0;
int j;
for(j=str2.Length-1;j>=0;j--)
{
digit2=str2[j]-'0';

int product=digit1*digit2+carry;
carry=product/10;
resval=resval+(product%10);

}
if(carry>0)
{
resval=resval+carry;
}
{
resval="0"+resval;
}
result[i]=resval;
}

int max=findMax(result);
int count=0;
int car=0;

while(count<max)
{
int sum=0;

for(int x=0;x<result.Length;x++)
{

if(count<result[x].Length)
{

sum+=result[x][count]-'0';
}

}
sum+=car;
car=sum/10;
int p=sum%10;
finalproduct=p+finalproduct;
count++;
}

finalproduct=car+finalproduct;

return finalproduct.TrimStart('0');

}

public static int findMax(string[] s)
{
int max=0;
for(int i=0;i<s.Length;i++)
{
int len=s[i].Length;
max=Math.Max(max,len);
}
return max;
}
}``````

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

Good luck coding this optimal solution with Fast Fourier transform within 30 minutes of phone interview:

"
The basic FFT algorithm itself runs in O(n log n) time; using FFTs for integer
and Joris van der Hoeven in 2018, runs in O(n * (log n) * (4^log\$n))) time.
Here, log\$n denotes the slowly growing iterated logarithm of n, which is the number of times
one must take the logarithm of n before the value is less than 1.
"

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.