Google Interview Question
Software EngineersCountry: UK
Interview Type: Phone Interview
Continue to the answer above.
Tested with the UT:
assertEquals("0", codeBase.bigSum("909876545678909876878765546789765490987654567890987687876554678976546789909876545678909876878765546789765467890876545678908765457890087654567890876545789067899098765456789098768787655467897654678908765456789087654578900876545678908765457890", "909876545678909876878765546789765490987654567890987687876554678976546789909876545678909876878765546789765467890876545678908765457890087654567890876545789067899098765456789098768787655445678908765457890"));
Here is the multiplication. The method "bigSum" is described above.
The function works only with an equal Strings by length.
unit test:
bigMultipl("123456781234567812345678123456781231234567812345678123456781234567812345678123456781234567812345678123456781234567812345678123456781234567812345678123456781234567812345678123456781234567812345678456781234567812345678123456781234567812345678",
"123456781234567812345678123456781231234567812345678123456781234567812345678123456781234567812345678123456781234567812345678123456781234567812345678123456781234567812345678123456781234567812345678456781234567812345678123456781234567812345678"));
result =
15241566832799835131840019356816873129412161060136908261522059216750369293320360971620290100369704845365086870331252870116370369202120372405370527895373317370413557870939420377432620454710371351027673886100984519252301774947583571499390156842912823863303992974797473165550166654279282375988982091851404238129875577457087736154196977375165932083620904155824874754407079505654114672374342882186495595263426186618964206036665458836888572988923249505065691208988873673208352565279684
public String bigMultipl(String s1, String s2) {
LinkedList<String> list = new LinkedList<>();
int lengthS1 = s1.length();
int lengthS2 = s2.length();
int diff = Math.abs(lengthS1 - lengthS2);
StringBuilder prefix = new StringBuilder();
for (int i = 0; i < diff; i++) {
prefix.append("0");
}
if (lengthS1 < lengthS2) {
s1 = prefix + s1;
} else if (lengthS2 < lengthS1) {
s2 = prefix + s2;
}
for (int i = s1.length() - 1; i >= 0; i --) {
int buf = 0;
String tempSum = "";
for (int j = s2.length() - 1; j >= 0; j --) {
int n1 = Integer.parseInt(String.valueOf(s1.charAt(i)));
int n2 = Integer.parseInt(String.valueOf(s2.charAt(j)));
int sum = buf + n1 * n2;
buf = 0;
if (sum >= 10) {
buf += sum / 10;
sum = sum % 10;
} else {
buf = 0;
}
tempSum = String.valueOf(sum) + tempSum;
}
if (buf > 0) {
list.add(buf + tempSum);
} else {
list.add(tempSum);
}
}
String sum = "";
for (int i = 0; i < list.size(); i ++) {
sum = bigSum(sum, list.get(i) + repeatString("0", i));
}
if (sum.startsWith("0")) {
sum = "1" + sum;
}
return sum;
}
public static String mul(String l, String r) {
if (l == null || l.equals("0") || r == null || r.equals("0")) {
return "0";
}
boolean isNegative = false;
if (l.startsWith("-")) {
isNegative = true;
l = l.substring(1);
}
if (r.startsWith("-")) {
isNegative ^= true;
r = r.substring(1);
}
int[] result = new int[l.length() + r.length()];
int resultEnd = result.length - 1;
int resultIdx = 0;
for (int rightIdx = r.length() - 1; rightIdx >= 0; rightIdx--) {
int carry = 0;
resultIdx = resultEnd;
for (int leftIdx = l.length() - 1; leftIdx >= 0; leftIdx--) {
int curr = (l.charAt(leftIdx) - '0') * (r.charAt(rightIdx) - '0')
+ carry + result[resultIdx];
result[resultIdx--] = curr % 10;
carry = curr / 10;
}
if (carry > 0) {
result[resultIdx] = carry;
}
resultEnd--;
}
StringBuilder sb = new StringBuilder();
if (isNegative) sb.append("-");
if (result[resultIdx] == 0) resultIdx++;
for (int i = resultIdx; i < result.length; i++) {
sb.append(result[i]);
}
return sb.toString();
}
+ (NSString *)mulS1:(NSString *)s1 withS2:(NSString *)s2
{
NSString *result = [NSString new];
NSMutableString *tempResult;
NSInteger temp = 0;
NSInteger carry = 0;
for (NSInteger i = [s1 length] - 1; i >= 0; i--) {
tempResult = [NSMutableString new];
for (NSInteger j = [s2 length] - 1; j >= 0; j--) {
temp = ([s1 characterAtIndex:i] - '0') * ([s2 characterAtIndex:j] - '0') + carry;
carry = temp / 10;
[tempResult insertString:[@(temp % 10) stringValue] atIndex:0];
}
[tempResult insertString:[@(carry) stringValue] atIndex:0];
carry = 0;
if ([s1 length] - i - 1 > 0) {
[tempResult appendString:[[@(pow(10, [s1 length] - 1 - i)) stringValue] substringFromIndex:1]];
}
result = [self sumS1:result withS2:[tempResult copy]] ;
}
return result;
}
+ (NSString *)sumS1:(NSString *)s1 withS2:(NSString *)s2
{
NSInteger temp = 0;
NSInteger carry = 0;
NSMutableString *result = [NSMutableString new];
for (NSInteger i = 0; i <= MAX([s1 length], [s2 length]); i++) {
temp = (i < [s1 length] ? [s1 characterAtIndex:[s1 length] - i - 1] - '0' : 0) + (i < [s2 length] ? [s2 characterAtIndex:[s2 length] - i - 1] - '0' : 0) + carry;
carry = temp / 10;
[result insertString:[@(temp % 10) stringValue] atIndex:0];
}
return [result copy];
}
String function(String s1, String s2) {
if (s1 == null || s1?.isEmpty() || s2 == null || s2?.isEmpty())
throw new Exception("Please input the valid strings. Current input strings are \"$s1\" and \"$s2\"")
ArrayList<Objects> analyzedNumbers = analyzeNumbers(s1, s2)
boolean negativeSign = analyzedNumbers.get(2)
int sizeNum1 = s1.size()
int sizeNum2 = s2.size()
Stack<Character> num1 = sizeNum1 <= sizeNum2 ? analyzedNumbers.get(0).split('') : analyzedNumbers.get(1).split('')
Stack<Character> num2 = sizeNum1 <= sizeNum2 ? analyzedNumbers.get(1).split('') : analyzedNumbers.get(0).split('')
int mulRemainder = 0, i = 0
int[][] matrix = (sizeNum1 > sizeNum2) ? new int[sizeNum1 + sizeNum2][sizeNum2] : new int[sizeNum1 + sizeNum2][sizeNum1]
for (i; num1.size() > 0; i++) {
Stack<String> cloneNum2 = (Stack<String>) num2.clone()
String multiplier1 = num1.pop()
int j = i
for (j; cloneNum2.size() > 0; j++) {
String multiplier2 = cloneNum2.pop()
if (multiplier1 == '0' || multiplier2 == '0') {
matrix[j][i] = mulRemainder
mulRemainder = 0
} else {
try {
mulRemainder += multiplier1.toInteger() * multiplier2.toInteger()
} catch (NumberFormatException ex) {
throw new Exception("Please input the valid strings. Current input strings are \"$s1\" and \"$s2\"")
}
if (mulRemainder > 9) {
matrix[j][i] = mulRemainder % 10
mulRemainder = mulRemainder / 10
} else {
matrix[j][i] = mulRemainder
mulRemainder = 0
}
if (cloneNum2.size() == 0) {
matrix[++j][i] = mulRemainder
mulRemainder = 0
}
}
}
}
StringBuilder res = calculateResult(matrix)
while (res.substring(res.length() - 1) == '0')
res.deleteCharAt(--res.length())
negativeSign ? res.append('-').toString() : res.toString()
res.reverse()
}
private static StringBuilder calculateResult(int[][] inputMatrix) {
StringBuilder res = new StringBuilder()
int sumRemainder = 0
for (int n = 0; n < inputMatrix.length; n++) {
int sum = sumRemainder
for (int m = 0; m < inputMatrix[n].length; m++) {
sum += inputMatrix[n][m]
}
if (sum > 9) {
sumRemainder = sum / 10
sum = sum % 10
} else {
sumRemainder = 0
}
res.append(sum)
}
res
}
private static ArrayList<Objects> analyzeNumbers(String str1, String str2) {
ArrayList<Objects> result = new ArrayList<>()
boolean negativeFirstVar = str1.startsWith('-')
boolean negativeSecondVar = str2.startsWith('-')
result.add(negativeFirstVar ? str1.substring(1) : str1)
result.add(negativeSecondVar ? str2.substring(1) : str2)
result.add(negativeFirstVar ^ negativeSecondVar)
result
}
function('247', '384') == '94848'
function('-247655', '-44') == '10896820'
function('10265893', '-3658156') == '-37554238073308'
function('894761335465132123543696666635453102658931546541536555555555554654145341343', '-952000000000000133214564352154352456432156453143658156') == '-851812791362805900808840729776363087775056644562160840739403170545129605964203662825133780128500820674736147406436873872325943508'
function('','') throw java.lang.Exception: Please input the valid strings.
function(null,'') throw java.lang.Exception: Please input the valid strings.
function(null,null) throw java.lang.Exception: Please input the valid strings.
function('','1sdf56') throw java.lang.Exception: Please input the valid strings.
function('',null) throw java.lang.Exception: Please input the valid strings.
public class AnalyzeNumbers {
public static void main(String[] args) {
java.util.Scanner input = new java.util.Scanner(System.in);
System.out.print("Enter the number of items: ");
int n = input.nextInt();
double[] numbers = new double[n];
double sum = 0;
System.out.print("Enter the numbers: ");
for (int i = 0; i < n; i++) {
numbers[i] = input.nextDouble();
sum += numbers[i];
}
double average = sum / n;
int count = 0; // The numbers of elements above average
for (int i = 0; i < n; i++)
if (numbers[i] > average)
count++;
System.out.println("Average is " + average);
System.out.println("Number of elements above the average is "
+ count);
}
}
public class AnalyzeNumbers {
public static void main(String[] args) {
java.util.Scanner input = new java.util.Scanner(System.in);
System.out.print("Enter the number of items: ");
int n = input.nextInt();
double[] numbers = new double[n];
double sum = 0;
System.out.print("Enter the numbers: ");
for (int i = 0; i < n; i++) {
numbers[i] = input.nextDouble();
sum += numbers[i];
}
double average = sum / n;
int count = 0; // The numbers of elements above average
for (int i = 0; i < n; i++)
if (numbers[i] > average)
count++;
System.out.println("Average is " + average);
System.out.println("Number of elements above the average is "
+ count);
}
}
- Denys February 12, 2018