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);

}

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

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>();

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

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;
i++;
}

while(i<arr1.size()) {
char ch = arr1.get(i++);
int res = (ch-'0') + carry;
int val = res%10;
carry = res/10;
i++;
}

while(i<arr2.size()) {
char ch = arr2.get(i++);
int res = (ch-'0') + carry;
int val = res%10;
carry = res/10;
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) {
}
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;
}
}

}``````

Output:
Int calculation: -67153019
Str calculation: 121932631112635269

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

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.

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

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");
}

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

}

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)``````

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.