Google Interview Question
Software EngineersCountry: India
Interview Type: Phone Interview
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
public class GoogleFunctionSolving {
public static Map<String, Integer> variables = new HashMap<String, Integer>();
public static int fountValues = 0;
public static void initVariables (ArrayList<String> eq) {
for (String line: eq) {
String[] tempSplit = line.split("=");
String LHS = tempSplit[0].trim();
String RHS = tempSplit[1].trim();
String[] subStringLHS = LHS.split("\\+");
String[] subStringRHS = RHS.split("\\+");
for (String c : subStringLHS) {
c = c.trim();
if ((Character.isLetter(c.charAt(0)) == true)) {
variables.put(c, Integer.MIN_VALUE);
}
}
for (String c : subStringRHS) {
c = c.trim();
if ((Character.isLetter(c.charAt(0)) == true)) {
variables.put(c, Integer.MIN_VALUE);
}
}
}
}
public static int countChars(String line) {
String[] elements = line.split(" ");
int count = 0;
for (String element : elements) {
element = element.trim();
if (Character.isLetter(element.charAt(0))) {
if(variables.get(element) == Integer.MIN_VALUE) {
count++;
}
}
}
return count;
}
public static void loopPart(String line) {
int charCount = countChars(line);
if(charCount == 1) {
solve(line);
}
}
public static void solve (String line) {
String[] elements = line.replace("+", "").split(" ");
int LHValue = 0;
int RHValue = 0;
String variable = null;
boolean isVariableLeft = true;
boolean isRHS = false;
for(String element : elements) {
element = element.trim();
if (!element.isEmpty()) {
if (!isRHS) {
if (!element.equals("=")) {
if (!Character.isLetter(element.charAt(0))) {
LHValue += Integer.parseInt(element);
} else {
if (variables.get(element) != Integer.MIN_VALUE) {
LHValue += variables.get(element);
} else {
isVariableLeft = true;
variable = element;
}
}
} else {
isRHS = true;
}
} else {
if (!Character.isLetter(element.charAt(0))) {
RHValue += Integer.parseInt(element);
} else {
if (variables.get(element) != Integer.MIN_VALUE) {
RHValue += variables.get(element);
} else {
isVariableLeft = false;
variable = element;
}
}
}
}
}
if (isVariableLeft) {
variables.put(variable, (RHValue - LHValue));
} else {
variables.put(variable, (LHValue - RHValue));
}
}
public static void main(String[] args) {
ArrayList<String> eq = new ArrayList<>();
eq.add("y = x + 1");
eq.add("5 = x + 3");
eq.add("10 = z + y + 2");
eq.add("a = b + 1");
eq.add("5 = b + 3");
eq.add("10 = d + z + y + a + b");
initVariables(eq);
int end = variables.size();
// O(numberOfLines*numberOfVariables)
for(int i = 0; i < end; i++) {
for (String arr : eq) {
loopPart(arr);
}
}
boolean isSolved = true;
for (String key : variables.keySet()) {
if(variables.get(key) == Integer.MIN_VALUE) {
System.out.println("Cannot be solved");
isSolved = false;
break;
}
}
if(isSolved) {
for (String key : variables.keySet()) {
System.out.println(key + ": " + variables.get(key));
}
}
}
}
public class T2 {
private static final int COUNT = 10;
private static final int MIN = -1000000;
private static final String input = "y = x + 1\n5 = x + 3\n10 = z + y + 2";
private static Map<String, Integer> inputVariables = new HashMap<>();
private static Stack<String> lineStack = new Stack<>();
public static void main(String[] args) {
String[] lines = input.split("\n");
String[] sides = new String[100];
String line = new String();
for (int i = 0; i < lines.length; i++) {
line = lines[i];
lineStack.add(line);
}
int i = 0;
while (i < lineStack.size()) {
line = lineStack.get(i);
sides = line.split("=");
if (checkLines(sides) == false) {
i = i + 1;
continue;
} else {
lineStack.remove(i);
i = 0;
continue;
}
} // end i
if (lineStack.isEmpty()) {
System.out.println("success to solve");
} else {
System.out.println("Fail to solve");
}
System.out.println("unsolved statement : " + lineStack);
System.out.println("final values : " + inputVariables);
}
private static Boolean checkLines(String[] sides) {
Boolean retVal = false;
String[] variables = new String[COUNT];
Integer[] getNumber = new Integer[COUNT];
String[] getVariables = new String[COUNT];
int intCount = 0;
int varCount = 0;
for (int j = 0; j < sides.length; j++) {
if (j == 0)
continue;
String temp = sides[j].toString().trim();
for (int k = 0, count = 0; k < temp.length(); k++) {
switch (temp.charAt(k)) {
case '+':
break;
case ' ':
break;
default:
variables[count] = String.valueOf(temp.charAt(k));
count++;
break;
}
} // end for k
for (int i = 0; i < variables.length; i++) {
if (variables[i] == null)
continue;
String tempChar = variables[i].toString().trim();
if (checkDigit(tempChar)) {
// number
getNumber[intCount] = Integer.valueOf(tempChar);
intCount++;
} else {
// variable
if (checkVariables(tempChar) != MIN) {
getNumber[intCount] = checkVariables(tempChar);
intCount++;
} else {
getVariables[varCount] = tempChar;
varCount++;
}
}
}
} // end for j
String tempChar = sides[0].toString().trim();
char getLeftVariable = tempChar.charAt(0);
if (Character.isDigit(getLeftVariable)) {
// number
if (varCount > 1) {
retVal = false;
return retVal;
} else {
calculate(tempChar, getNumber, getVariables);
retVal = true;
return retVal;
}
} else {
if (varCount > 0) {
retVal = false;
return retVal;
} else {
calculate(tempChar, getNumber, getVariables);
retVal = true;
return retVal;
}
}
}
private static void calculate(String left, Integer[] getNumber, String[] getVariables) {
int countedVariable = 0;
if (checkDigit(left)) {
countedVariable = Integer.valueOf(left);
for (int i = 0; i < getNumber.length; i++) {
if (getNumber[i] == null)
continue;
countedVariable = countedVariable - getNumber[i];
}
inputVariables.put(getVariables[0], countedVariable);
} else {
for (int i = 0; i < getNumber.length; i++) {
if (getNumber[i] == null)
continue;
countedVariable += getNumber[i];
}
inputVariables.put(left, countedVariable);
}
}
private static Boolean checkDigit(String getStr) {
Boolean retVal = false;
String temp = getStr.trim();
char getCh = temp.charAt(0);
if (Character.isDigit(getCh))
retVal = true;
return retVal;
}
private static int checkVariables(String variable) {
int retVal = MIN;
if (!inputVariables.isEmpty()) {
if (inputVariables.containsKey(variable)) {
retVal = inputVariables.get(variable);
}
}
return retVal;
}
}
If we simplify the question it turns to a classical problem of solving a system of linear equation. So the simplified version of this question is -
- Tanmoy Datta June 08, 2020"You are given a system of linear equation and you need to find the roots".
This can be done using Gaussian Elimination.