Yahoo Interview Question
Country: India
Interview Type: In-Person
The first step is to normalize the chemical equation. Such as: Equation->{compound+}*compound={compound+}*compound, compound->{element}*element.
Element->Uppercase{lowercase}. Then you use a grammatical analysis to analysis this to build a symbol table(a hash table maybe). At last, make sure the element in the left equals to that in the right.
Data structure for this question is not given...
Lets say equation is given in string format...
-Tokanize the formulas like (H2O) by checking below point
---in case first occurrence is numeric (5H2O) then save this multipliable number 5 in a variable coefficient array . (coefficient [token_index]=5)
-Initialize a HashMap and start inserting elements as key and next numeric as its value... in case no next numeric value assume it 1... also multiply the value with 'coefficient [token_index]'.... take care of Capital/Small letter as HS are two element but Hs is a single
-Now start fetching resultant formula and compare with hashmap
----in case element from right side not present in HashMap return -1
----in case coefficient is there in right side multiply it with elements coefficient value the compare in HashMap.
package yahoo;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
/**
* Write a function to check if the given chemical equation is balanced or not?
Ex: Cu + S = CuS
2H2 + 02 = 2H2O
* @author ksjeyabarani
*
*/
public class ChemicalEquation {
private String LHS;
private String RHS;
private String equation;
private String[] equationSides;
private List<ChemicalFormula> lhsParts;
private List<ChemicalFormula> rhsParts;
private Map<String, Integer> lhsTotalChemicalCountmap;
private Map<String, Integer> rhsTotalChemicalCountmap;
private boolean isBalanced;
public ChemicalEquation(String equation) throws Exception {
super();
this.equation = equation;
if((null != equation) && (!equation.equals(""))) {
equationSides = equation.split("=");
if(equationSides.length != 2)
throw new Exception("This is not a valid equation");
LHS = equationSides[0];
RHS = equationSides[1];
lhsParts = getParts(LHS);
rhsParts = getParts(RHS);
}
this.equationSides = this.getEquationSides();
List<ChemicalFormula> lhsParts = this.getParts(this.equationSides[0]);
List<ChemicalFormula> rhsParts = this.getParts(this.equationSides[1]);
this.lhsTotalChemicalCountmap = totalChemicalCountForTheGivenSide(lhsParts);
this.rhsTotalChemicalCountmap = totalChemicalCountForTheGivenSide(rhsParts);
System.out.println(lhsTotalChemicalCountmap);
System.out.println(rhsTotalChemicalCountmap);
this.isBalanced = true;
if(lhsTotalChemicalCountmap.size() != rhsTotalChemicalCountmap.size())
this.isBalanced = false;
Iterator<Entry<String, Integer>> iterator = this.lhsTotalChemicalCountmap.entrySet().iterator();
while(iterator.hasNext()) {
Map.Entry<String, Integer> pairs = (Map.Entry<String, Integer>)iterator.next();
//System.out.println(pairs.getKey() + " = " + pairs.getValue());
if(this.lhsTotalChemicalCountmap.get(pairs.getKey()) != this.rhsTotalChemicalCountmap.get(pairs.getKey())) {
this.isBalanced = false;
}
}
}
public List<ChemicalFormula> getParts(String equationSide) throws Exception {
String[] parts;
if((null != equationSide) && (!equationSide.equals(""))) {
parts = equationSide.split("-");
List<ChemicalFormula> list = new LinkedList<ChemicalFormula>();
for(int i=0; i < parts.length; i++) {
list.add(new ChemicalFormula(parts[i]));
}
return list;
}
return null;
}
public Map<String, Integer> totalChemicalCountForTheGivenSide(List<ChemicalFormula> parts) {
Map<String, Integer> givenSideChemicalCount = new HashMap<String, Integer>();
if((null != parts) && (!parts.isEmpty())) {
for(int i=0; i<parts.size(); i++) {
ChemicalFormula formula = parts.get(i);
int count = formula.getCount();
Map<String, Integer> map = formula.elementCountMap;
Iterator<Entry<String, Integer>> iterator = map.entrySet().iterator();
while(iterator.hasNext()) {
Map.Entry<String, Integer> pairs = (Map.Entry<String, Integer>)iterator.next();
//System.out.println(pairs.getKey() + " = " + pairs.getValue());
if(null == givenSideChemicalCount.get(pairs.getKey())) {
String ch = (String) pairs.getKey();
int totalCount = count * (Integer) pairs.getValue();
givenSideChemicalCount.put(ch, totalCount);
} else {
String ch = (String) pairs.getKey();
int totalCount = (count * (Integer) pairs.getValue()) + givenSideChemicalCount.get(pairs.getKey());
givenSideChemicalCount.put(ch, totalCount);
}
}
}
} else {
givenSideChemicalCount = null;
}
return givenSideChemicalCount;
}
public Map<String, Integer> getLhsTotalChemicalCountmap() {
return lhsTotalChemicalCountmap;
}
public void setLhsTotalChemicalCountmap(
Map<String, Integer> lhsTotalChemicalCountmap) {
this.lhsTotalChemicalCountmap = lhsTotalChemicalCountmap;
}
public Map<String, Integer> getRhsTotalChemicalCountmap() {
return rhsTotalChemicalCountmap;
}
public void setRhsTotalChemicalCountmap(
Map<String, Integer> rhsTotalChemicalCountmap) {
this.rhsTotalChemicalCountmap = rhsTotalChemicalCountmap;
}
public boolean isBalanced() throws Exception {
return this.isBalanced;
}
public String getLHS() {
return LHS;
}
public void setLHS(String lHS) {
LHS = lHS;
}
public String getRHS() {
return RHS;
}
public void setRHS(String rHS) {
RHS = rHS;
}
public String[] getEquationSides() {
return equationSides;
}
public void setEquationSides(String[] equationSides) {
this.equationSides = equationSides;
}
public String getEquation() {
return equation;
}
public void setEquation(String equation) {
this.equation = equation;
}
@Override
public String toString() {
return "ChemicalEquation [equation=" + equation + ", equationSides="
+ Arrays.toString(equationSides) + ", lhsParts=" + lhsParts
+ ", rhsParts=" + rhsParts + ", lhsTotalChemicalCountmap="
+ lhsTotalChemicalCountmap + ", rhsTotalChemicalCountmap="
+ rhsTotalChemicalCountmap + ", isBalanced=" + isBalanced + "]";
}
private static class ChemicalFormula {
String formula;
int count;
Map<String, Integer> elementCountMap = new HashMap<String, Integer>();
public String getFormula() {
return formula;
}
public void setFormula(String formula) {
this.formula = formula;
}
public Map<String, Integer> getElementCountMap() {
return elementCountMap;
}
public void setElementCountMap(Map<String, Integer> elementCount) {
this.elementCountMap = elementCount;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public ChemicalFormula(String formula) throws Exception {
if((null != formula) && (!formula.equals(""))) {
this.formula = formula;
formula = formula.trim();
int formulaSize = formula.length();
//System.out.println("formula " + formula);
boolean notADigit = false;
int x = 0;
// get count
if (Character.isDigit(Character.valueOf(formula.charAt(0)))) {
x = 1;
StringBuilder countStringBuilder = new StringBuilder(""+Character.valueOf(formula.charAt(0)));
while(true) {
if(notADigit || (x >=formulaSize)) {
break;
}
if(Character.isDigit(Character.valueOf(formula.charAt(x)))) {
countStringBuilder.append(""+Character.valueOf(formula.charAt(x)));
x++;
} else {
notADigit = true;
}
}
count = Integer.parseInt(countStringBuilder.toString());
}
String key = "";
Integer value = null;
boolean previousWasASymbol = false;
while(x < formulaSize) {
value = null;
if (Character.isDigit(Character.valueOf(formula.charAt(x)))) {
//System.out.println(" x is a Digit " + formula.charAt(x) + " at x: " + x);
StringBuilder countStringBuilder = new StringBuilder("");
while((x<formulaSize) && (Character.isDigit(Character.valueOf(formula.charAt(x))))) {
countStringBuilder.append(""+Character.valueOf(formula.charAt(x)));
x++;
}
value = Integer.parseInt(countStringBuilder.toString());
elementCountMap.put(key, value);
//System.out.println("key " + key + "-value--" + value);
} else {
key = "";
//System.out.println(" x is a NOT Digit " + formula.charAt(x) + " at x: " + x);
StringBuilder elementStringBuilder = null;
elementStringBuilder = new StringBuilder("");
if (Character.isUpperCase(Character.valueOf(formula.charAt(x)))) {
elementStringBuilder.append(""+Character.valueOf(formula.charAt(x)));
x++;
while((x<formulaSize) && (Character.isLowerCase(Character.valueOf(formula.charAt(x))))) {
//System.out.println(" x is a LOWER Case " + formula.charAt(x) + " at x: " + x);
elementStringBuilder.append(Character.valueOf(formula.charAt(x)));
x++;
}
}
//System.out.println("-- x --- " + x);
key = elementStringBuilder.toString();
//System.out.println(" key " + key);
previousWasASymbol = true;
}
if(!(key.equals("") || (null == key)) && (null != value)) {
elementCountMap.put(key, value);
}
if(previousWasASymbol && (null == value)) {
elementCountMap.put(key, new Integer(1));
}
}
}
if(count == 0) {
count = 1;
}
}
@Override
public String toString() {
return "ChemicalFormula [formula=" + formula + ", count=" + count
+ ", elementCountMap=" + elementCountMap + "]";
}
}
public static void main(String[] args) throws Exception {
//System.out.println("this+Jeya".split("+"));
//ChemicalEquation.ChemicalFormula formula = new ChemicalEquation.ChemicalFormula("H2O");
ChemicalEquation equation = new ChemicalEquation("NaOH-H2SO4=NaSHO4-H2O");
System.out.println(equation.isBalanced());
System.out.println(equation);
}
}
Basically its the creation of 2 Arrays.
- hprem991 October 01, 20131> One Array to the left of the equation where we read each element and then multiply by the number of occurrences.
2> Array two does the same but on the left hand side of the equation.
We can use the hash to decrease the time complexity by taking the hash bucket as 26 (max number of alphabet.)
For First array we populate the hash table by the number of occurrences and the next array can be use to remove the entry from the table by the number of occurrences.
Now , we can get the final value from the hash table along with the corresponding alphabet and occurences to be match
if Hash table is empty mean balances.
if value of an alphabet is negative means need to put values on left side of the equation.
if value is positive means same to be done on right hand side.
Time :- O(n)