CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

VMWare Inc Interview Question for Staff Engineers


Team: High Availability
Country: United States



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

class StringMultiplier {

  public static void main(String[] args) {
    String s1 = args[0];
    String s2 = args[1];

    String ans = multiplyStringsAsIntegers(s1, s2);

    System.out.println(ans);
  }

  public static String multiplyStringsAsIntegers(String s1, String s2) {
    int[] results = new int[s1.length() + s2.length() + 1];

    // Bytes because each digit will never exceed 0-9, so ints will be a waste
    byte[] a1 = toByteArray(s1);
    byte[] a2 = toByteArray(s2);

    for (int i = 0; i < a1.length; i++) {
      for (int j = 0; j < a2.length; j++) {
        results[i + j] += a1[i] * a2[j];
      }
    }

    processCarryOvers(results);

    return toString(results);
  }

  public static void processCarryOvers(int[] results) {
    int carry = 0;

    for (int i = 0; i < results.length; i++) {
      results[i] += carry;
      carry = results[i] / 10;
      results[i] = results[i] % 10;
    }
  }

  public static byte[] toByteArray(String s) {
    byte[] bArr = new byte[s.length()];

    for (int i = 0; i < s.length(); i++) {
      // Convert each character into its corresponding integer representation
      bArr[i] = (byte)(s.charAt(s.length() - i - 1) - '0');
    }

    return bArr;
  }

  public static String toString(int[] arr) {
    // This appends the values in arr in reverse order,
    // Since we multiply right to left, so the result in arr is reversed
    StringBuilder s  = new StringBuilder();

    for (int i = arr.length - 1; i >= 0; i--) {
      s.append(arr[i]);
    }

    return s.toString();
  }
}

- havanagrawal November 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java implementation O(n^2):

package com.cracking.vmware;

import java.util.ArrayList;

public class ProductOfTwoStrings {

	public static void main(String[] args) {
		int sumInt = Multiple_RetInt("123456789", "987654321");
		System.out.println("Int calculation: " + sumInt);
		
		String sumStr = Multiple_RetStr("123456789", "987654321");
		System.out.println("Str calculation: " + sumStr);
	}
	
	public static String Multiple_RetStr(String str1, String str2) {
		char[] arr1 = str1.toCharArray();
		char[] arr2 = str2.toCharArray();
		
		if(str1.length() > str2.length()) {
			return Multiple_RetStr(arr2,arr1);
		}

		return Multiple_RetStr(arr1,arr2);
	}
	
	public static String Multiple_RetStr(char[] arr1, char[] arr2) {
		
		int startPos = 0;
		ArrayList<ArrayList<Character>> calculations = new ArrayList<ArrayList<Character>>();
		for(int i=arr1.length-1; i>=0; i--) {
			
			char a = arr1[i];
			int carry = 0;
			
			ArrayList<Character> calculation = new ArrayList<Character>();
			AddToArray('0', startPos++, calculation);
			
			for(int j=arr2.length-1; j>=0; j--) {
				char b = arr2[j];
				int res = Multiple(a,b);
				res+= carry;
				
				int value = res%10;
				carry = res/10;
				calculation.add( (char)(value+'0') );
			}
			calculation.add( (char)(carry+'0') );
			calculations.add(calculation);
		}
		
		return Sum(calculations);
	}
	
	public static String Sum(ArrayList<ArrayList<Character>> calculations) {
		ArrayList<Character> sum = new ArrayList<Character>();
		for(int i=0;i<calculations.size();i++) {
			sum = Sum(sum,calculations.get(i));
		}
		return GetReverseStr(sum);
	}
	
	public static String GetReverseStr(ArrayList<Character> arr) {
		StringBuilder builder = new StringBuilder();
		for(int i=arr.size()-1; i>=0; i--) {
			builder.append(arr.get(i));
		}
		return builder.toString();
	}
	
	public static ArrayList<Character> Sum(ArrayList<Character> arr1, ArrayList<Character> arr2) {
		if(arr1.isEmpty()) return arr2;
		if(arr2.isEmpty()) return arr1;
		
		ArrayList<Character> sum = new ArrayList<Character>();
		int carry = 0;
		int i = 0;
		while( i<arr1.size() && i<arr2.size() ) {
			char a = arr1.get(i);
			char b = arr2.get(i);
			int res = Sum(a,b) + carry;
			int val = res%10;
			carry = res/10;
			sum.add( (char)(val+'0') );
			i++;
		}
		
		while(i<arr1.size()) {
			char ch = arr1.get(i++);
			int res = (ch-'0') + carry;
			int val = res%10;
			carry = res/10;
			sum.add( (char)(val+'0') );
			i++;
		}
		
		while(i<arr2.size()) {
			char ch = arr2.get(i++);
			int res = (ch-'0') + carry;
			int val = res%10;
			carry = res/10;
			sum.add( (char)(val+'0') );
			i++;
		}
		
		return sum;
	}
	
	public static int Multiple(char a,char b) {
		return (a-'0')*(b-'0');
	}
	
	public static int Sum(char a, char b) {
		return (a-'0') + (b-'0');
	}
	
	public static boolean AddToArray(char ch,int count,ArrayList<Character> arr) {
		while(count-- > 0) {
			arr.add(ch);
		}
		return true;
	}
	
	public static int Multiple_RetInt(String str1, String str2) {
		char[] arr1 = str1.toCharArray();
		char[] arr2 = str2.toCharArray();
		
		if(str1.length() > str2.length()) {
			return Multiple_RetInt(arr2,arr1);
		}

		return Multiple_RetInt(arr1,arr2);
	}
	
	public static int Multiple_RetInt(char[] arr1, char[] arr2) {
		int totalSum=0;
		
		for(int topWeight=1, i=arr1.length-1; i>=0; i--) {
			int sum = 0;
			int value,carry = 0;
			int weight=topWeight;
			for(int j=arr2.length-1; j>=0; j--) {
				int res = (arr1[i] - '0' )*(arr2[j] - '0' ) + carry;
				value = res%10;
				int calc = value*weight;
				sum += calc;
				carry = res/10;
				weight *= 10;
			}
			sum += carry*weight;
			totalSum += sum;
			topWeight*=10;
		}
		return totalSum;
	}

}

Output:
Int calculation: -67153019
Str calculation: 121932631112635269

- ProTechMulti November 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>

using namespace std;

string Add(string s1, string s2, int place)
{
	if (s2 != "0") {
		while (place-- > 0) {
			s2 += '0';
		}
	}

	string out;
	int i = s1.size() - 1;
	int j = s2.size() - 1;
	int carry = 0;
	while (i >= 0 ||
			j >= 0 ||
			carry != 0)
	{
		int summand1 = (i >= 0) ? s1[i--] - '0' : 0;
		int summand2 = (j >= 0) ? s2[j--] - '0' : 0;
		int sum = summand1 + summand2 + carry;
		out += (sum % 10) + '0';
		carry = sum >= 10 ? 1 : 0;
	}

	reverse(out.begin(), out.end());
	return out;
}

string MultiplyByDigit(string s, char digit)
{
	string out;
	int digit_val = digit - '0';
	for (int i = s.size() - 1; i >= 0; --i) {
		out = Add(out, to_string((s[i] - '0') * digit_val), s.size() - 1 - i);
	}
	return out;
}

string Multiply(string const &s1, string const &s2)
{
	string out;
	for (int i = s2.size() - 1; i >= 0; --i) {
		out = Add(out, MultiplyByDigit(s1, s2[i]), s2.size() - 1 - i);
	}
	return out;
}

int main()
{
	cout << Multiply("240834975028740983740298740325723952835357021759874592475924875290475293573295", "7047851704578497502349857405927430957340597320457329045873") << "\n";
}

- Alex November 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@havanagrawal. A nice approach!
I can see one drawback though. E.g. if the two strings, containing only '9's, are 1000 long. results[500] element will be added 81 about 500 times, i.e. size / 2 times. So, at a particular size, any integer type will overflow.

- Alex November 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static string Multiply(string num1, string num2) {
int[] result = new int[num1.Length + num2.Length];

for(int i=num1.Length-1; i>=0; i--){
for(int j=num2.Length-1; j>=0; j--){
var sum = (num1[i] -'0') * (num2[j] - '0') + result[i+j+1];

result[i+j+1] = sum % 10;
result[i+j] = sum/10;

}

}

var final = new StringBuilder();
for(int i=0; i<result.Length; i++){
if(result[i] !=0 && final.Length == 0)
final.Append(result[i]);
}


return final.Length > 0 ? final.ToString() : "0";
}

- Rohit June 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
    public String multiply(String num1, String num2) {
        
        if(num1==null || num1.isEmpty() || num2==null || num2.isEmpty() || num1.equals("0") || num2.equals("0"))    return "0";
        
        int len1 = num1.length();
        int len2 = num2.length();
        
        int index = len2-1;
        int numOfZeroes = 0;
        
        String sum = "";
        
        while(index>=0) {
            StringBuilder val = multiply(num1, len1, num2.charAt(index));
            
            for (int i=0;i<numOfZeroes;i++) {
                val.append("0");
            }
            
            sum = add(sum, val.toString()); 
            
            numOfZeroes++;
            index--;
        }
        
        return sum;
    }
    
    private static StringBuilder multiply(String num, int len, char multiplier) {
        
        StringBuilder result = new StringBuilder();
        int index = len-1;
        
        int carry = 0;
        int multi = multiplier - '0';
        
        while(index>=0) {
            
            char c = num.charAt(index);
            
            int val = (c-'0')*multi + carry;
            result.append(val%10);
            carry = val/10;
            
            index--;
        }
        
        if(carry!=0)    result.append(carry);
        
        return result.reverse();
    }
    
    private static String add(String num1, String num2) {
        
        int len1 = num1.length()-1;
        int len2 = num2.length()-1;
        int carry = 0;
        
        StringBuilder result = new StringBuilder();
        
        while(len1>=0 && len2>=0) {
            
            int val1 = num1.charAt(len1)-'0';
            int val2 = num2.charAt(len2)-'0';
            
            int sum = val1+val2+carry;
            
            result.append(sum%10);
            carry = sum/10;
            
            len1--;
            len2--;
        }
        
        while(len1>=0) {
            
            int val1 = num1.charAt(len1)-'0';
            
            int sum = val1+carry;
            result.append(sum%10);
            carry = sum/10;
            
            len1--;
        }
        
        while(len2>=0) {
            int val2 = num2.charAt(len2)-'0';
            
            int sum = val2+carry;
            
            result.append(sum%10);
            carry = sum/10;
            
            len2--;
        }
        
        if(carry!=0)    result.append(carry);
        
        return result.reverse().toString();
    }

}

- sawantshubham027 February 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

s1_i = 0
s2_i = 0

for index, element in enumerate(s1[::-1]):
        s1_i += int(element) * 10 ** index

for index, element in enumerate(s2[::-1]):
        s2_i += int(element) * 10 ** index


print(s1_i * s2_i)

- kususe November 04, 2017 | 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