## Microsoft Interview Question for Applications Developers

Country: India
Interview Type: In-Person

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

``````#include <iostream>

void multipy(char* a, char* b, char* res)
{
int lenA = strlen(a);
int lenB = strlen(b);

int i, j;

int* c = new int[lenA + lenB];
memset(c, 0, sizeof(int) * (strlen(a) + strlen(b)));

for (i = lenA - 1; i >= 0; i--)
for (j = lenB - 1; j >= 0; j--)
c[i + j + 1] += (b[j] - '0') * (a[i] - '0');

for (i = lenA + lenB - 1; i >= 0; i--)
{
if (c[i] >= 10)
{
c[i - 1] += c[i] / 10;
c[i] %= 10;
}
}

i = 0;
while (c[i] == 0)
i++;

j = 0;
while (i < lenA + lenB)
{
res[j] = c[i] + '0';
i++; j++;
}

res[j] = 0;
delete[] c;
};

int main()
{
char* a = "999";
char* b = "9999";
char* res = new char[strlen(a) + strlen(b)];

multipy(a, b, res);
return 0;
}``````

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

Bcoz of this, got selected in Companey! thnx a ton dear!!!

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

The solution has the complexity of O(nm) while n is the digit number of the first number and m is the second one.

``````#define toAscii(A,len)   for(int i=0; i<len; A[i++]+='0');
#define fromAscii(A,len) for(int i=0; i<len; A[i++]-='0');
char * multiply(char *A, char*B)
{
int n= strlen(A);
int m = strlen(B);
char * res = (char*) malloc (sizeof(char)*n+m+1);
memset(res, 0, sizeof(char)*n+m+1);
fromAscii(A,n);
fromAscii(B,m);
for(int i=n-1; i>=0; i--)
for(int j=m-1; j>=0; j--)
{
res[i+j+1]+=(A[i] * B[j]);
res[i+j]+=res[i+j+1]/10;
res[i+j+1] = res[i+j+1]%10;
}
toAscii(res, n+m+1);
res[n+m]='\0';
return res;
}``````

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

There are also faster algorithms. There's a simple to understand one that runs in n ^ (log base 2 of 3) when n is the size of m, and then the fast Fourier transform, which runs in n*log(n).

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

great code. but you forget to take off the additional zeros.
101 * 101 = 10201

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

Need more information. Is each char an ascii number, or does the whole char array represent a big binary number?

Is the output an integer or also a char array of the right size?

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

In the worst case you can implement the same mechanism you have learned to do multiplications at school: multiply and add in multiple levels.

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

``````#include<iostream>
#include<string.h>

using namespace std;

void add(char *a, char *b, char *c)
{
int i, cc=0,m=strlen(a)>strlen(b)?strlen(a):strlen(b),k,s;
k=s=strlen(a)<strlen(b)?strlen(a):strlen(b);
k-=1;m--;s--;
if(strlen(a)>strlen(b)?1:0)
{
for(i=m;i>=m-s;--i,k--)
{
c[i]=((int)(a[i])+(int)(b[k])-48*2+cc)%10+48;
cc=((int)(a[i])+(int)(b[k])-48*2)>9?1:0;
}
for(;i>=0;--i)
{
c[i]=((int)a[i]+cc-48)%10+48;
cc=((int)(a[i])+cc-48)>9?1:0;
}
}
else
{
for(i=m;i>=m-s;--i,k--)
{
c[i]=((int)(a[k])+(int)(b[i])-48*2+cc)%10+48;
cc=((int)(a[k])+(int)(b[i])-48*2)>9?1:0;
}
for(;i>=0;--i)
{
c[i]=((int)b[i]+cc-48)%10+48;
cc=((int)(b[i])+cc-48)>9?1:0;
}
}
}

main()
{
char a[]="111000",b[]="110001",*c;
c= new char[strlen(a)>strlen(b)?strlen(a):strlen(b)];
cout<<c<<endl;
}``````

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

``````public static int[] multiplyBigNumbers(int[] num1, int[] num2) {

int[] result = new int[num1.length + num2.length];
int carry = 0;
int offset = 0;

for (int i = num1.length - 1; i >= 0; i--) {
int tail = result.length - 1 - offset;
for (int j = num2.length - 1; j >= 0; j--) {
int sum = result[tail] + (num1[i] * num2[j]) + carry;
result[tail] = sum % 10;
carry = sum / 10;
tail--;
}
if (carry > 0) {
carry = 0;
}
offset++;
}

return result;
}

private static void addCarry(int[] result, int tail, int carry) {
result[tail] += carry;
while (result[tail] >= 10) {
carry = result[tail] / 10; // add carry
result[tail] = result[tail] % 10;
result[--tail] += carry;
}
}

public static void main(String[] args) {
int[] num1 = {9, 9, 9, 9, 9};
int[] num2 = {9, 9, 9, 9, 9};
int[] result = multiplyBigNumbers(num1, num2);

System.out.println("Result: ");
for (int i : result) {
System.out.print(i + " ");
}
}``````

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

``````int *multiply(char *a,char *b)
{
int* c = (int *)malloc(strlen(a)+ strlen(b));
memset(c, 0, sizeof(int) * (strlen(a) + strlen(b)));
int carry,bi,ai;
for(bi = strlen(b)-1; bi>=0; bi--){
carry = 0;
for(ai = strlen(a)-1; ai >=0; ai--){
c[ai + bi + 1] += carry + (a[ai]-'0')*(b[bi]-'0');
carry = c[ai + bi  + 1]/10;
c[ai + bi + 1] = c[ai + bi + 1] % 10;
}
c[bi]= carry;
}
return c;
}

main()
{
char* a = "55555555";
char* b = "3333333333";

int* c1 = (int *)malloc(strlen(a) + strlen(b));

c1 = multiply(a,b);

for(int i=0;i < strlen(a) + strlen(b); i++)
printf("%d", c1[i]);
}``````

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

can we have O(n) or better than O(n^2) algorithm for this problem or

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

``````public class BigMultiplication {

public static void main(String[] args) {
String s1 = "99";
String s2 = "999";
int result = Integer.valueOf(new BigMultiplication().multiply(s1, s2));
System.out.println(s1 + "*" + s2 + "=" + result);

}

private String multiply(String s1, String s2) {
char[] n1 = s1.toCharArray();
char[] n2 = s2.toCharArray();
int size1 = s1.length();
int size2 = s2.length();
int[][] out = new int[size2][size1+1]; // extra size for one remainder
StringBuilder mainResult = new StringBuilder();

int previousRemainder = 0;

// make a 2D array of multiplication where each row denote n1*(a digit
// of n2 starting from the unit place digit)
for (int j = size2 - 1; j >= 0; j--) { //for each character of  of 2nd number
previousRemainder=0;
for (int i = size1 - 1; i >= 0; i--) { // multiply with each  character of first array
int data = (Character.getNumericValue(n2[j]) * Character.getNumericValue(n1[i])) + previousRemainder;
previousRemainder = data / 10; // if the multiplication gives result >= 10 fin the remainder and preserve it to be added to the next multiplication
int actualData = data % 10; // get the actual data at unit place of the multiplication
if(i==0){
out[size2 - 1 - j][size1 - 1 - i] = actualData;
out[size2 - 1 - j][size1  - i] = previousRemainder; // for last multiplication put the remainder also in the matrix
}else{
out[size2 - 1 - j][size1 - 1 - i] = actualData; // set the actual data in a 2D matrix starting from index (0,0)
}
}

}
// the 2D array so formed is:
for (int i = 0; i < out.length; i++) {
for (int j = 0; j < out[i].length; j++) {
System.out.print(out[i][j] + "\t");
}
System.out.println();
}

/**
* this array will contain the sum of diagoinal elements. the logic
* behind is that in a 2D array, on any diagonal the sum of indices
* (i+j) is always constant & (i+j) varies fro 0 to (row +column)
*
*/
int[] rawResult = new int[size1 + size2 + 1];
for (int i = 0; i < out.length; i++) {
for (int j = 0; j < out[i].length; j++) {
rawResult[i + j] += out[i][j];
}
}

previousRemainder = 0;
for (int i = 0; i < rawResult.length; i++) {
int data = rawResult[i] + previousRemainder;
mainResult.append(String.valueOf((data % 10)));
previousRemainder = data / 10;
}
return mainResult.reverse().toString();
}

}``````

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

``````package demo;

public class BigMultiplication {

public static void main(String[] args) {
String s1 = "99";
String s2 = "999";
int result = Integer.valueOf(new BigMultiplication().multiply(s1, s2));
System.out.println(s1 + "*" + s2 + "=" + result);

}

private String multiply(String s1, String s2) {
char[] n1 = s1.toCharArray();
char[] n2 = s2.toCharArray();
int size1 = s1.length();
int size2 = s2.length();
int[][] out = new int[size2][size1+1]; // extra size for one remainder
StringBuilder mainResult = new StringBuilder();

int previousRemainder = 0;

// make a 2D array of multiplication where each row denote n1*(a digit
// of n2 starting from the unit place digit)
for (int j = size2 - 1; j >= 0; j--) { //for each character of  of 2nd number
previousRemainder=0;
for (int i = size1 - 1; i >= 0; i--) { // multiply with each  character of first array
int data = (Character.getNumericValue(n2[j]) * Character.getNumericValue(n1[i])) + previousRemainder;
previousRemainder = data / 10; // if the multiplication gives result >= 10 fin the remainder and preserve it to be added to the next multiplication
int actualData = data % 10; // get the actual data at unit place of the multiplication
if(i==0){
out[size2 - 1 - j][size1 - 1 - i] = actualData;
out[size2 - 1 - j][size1  - i] = previousRemainder; // for last multiplication put the remainder also in the matrix
}else{
out[size2 - 1 - j][size1 - 1 - i] = actualData; // set the actual data in a 2D matrix starting from index (0,0)
}
}

}
// the 2D array so formed is:
for (int i = 0; i < out.length; i++) {
for (int j = 0; j < out[i].length; j++) {
System.out.print(out[i][j] + "\t");
}
System.out.println();
}

/**
* this array will contain the sum of diagoinal elements. the logic
* behind is that in a 2D array, on any diagonal the sum of indices
* (i+j) is always constant & (i+j) varies fro 0 to (row +column)
*
*/
int[] rawResult = new int[size1 + size2 + 1];
for (int i = 0; i < out.length; i++) {
for (int j = 0; j < out[i].length; j++) {
rawResult[i + j] += out[i][j];
}
}

previousRemainder = 0;
for (int i = 0; i < rawResult.length; i++) {
int data = rawResult[i] + previousRemainder;
mainResult.append(String.valueOf((data % 10)));
previousRemainder = data / 10;
}
return mainResult.reverse().toString();
}

}``````

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;
}
}``````

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.