ksjeyabarani
BAN USER// for simplicity assume all characters are in lower case
public class FormWordsFromChemistryPeriodicTable {
public static List<String> findWords (String[] dictionary, HashSet<String> periodicTableElements) {
List<String> words = new LinkedList<String>();
if(dictionary == null || periodicTableElements == null
|| periodicTableElements.isEmpty() || dictionary.length ==0)
return words;
for (int i = 0; i < dictionary.length; i++) {
boolean flag = true;
for (int j = 0; j < dictionary[i].length(); j++) {
// if current letter is an element symbol, continue loop; else check its neighbhours
if (! periodicTableElements.contains("" + dictionary[i].charAt(j))) {
// if current letter is not an element symbol
// check if the prev letter + this letter is a symbol,
// else; check if this letter + next letter is a symbol
if ( ! (
(j != 0) &&
periodicTableElements.contains("" + dictionary[i].charAt(j-1) + dictionary[i].charAt(j)))) {
if ((j == dictionary[i].length()-1) ||
! periodicTableElements.contains("" + dictionary[i].charAt(j) + dictionary[i].charAt(j+1))) {
flag = false;
break;
}
j=j+1;
}
}
}
if(flag == true) {
words.add(dictionary[i]);
}
}
return words;
}
public static void main(String[] args) {
String[] dictionary = {"ark","sick", "arc", "arch", "arche"};
HashSet<String> periodicTableElements = new HashSet<String>();
periodicTableElements.add("ar");
periodicTableElements.add("k");
periodicTableElements.add("si");
periodicTableElements.add("c");
periodicTableElements.add("ch");
System.out.println(findWords (dictionary, periodicTableElements));
}
}
public static int[] adjust(int[] ar) {
if(ar == null || ar.length < 2)
return ar;
int read;
int write;
for(read = 1, write = 0; read < ar.length; ) {
if (ar[read] == ar[write]) {
read++;
continue;
} else {
write++;
int temp = ar[write];
ar[write] = ar[read];
ar[read] = temp;
read++;
}
}
return ar;
}
The below code is a variation to Kadane's algorithm.
maxSumSubArrayDivisibleByNumber(int[], int) - finds the maximum sum in the sub sequence of the array that is divisible by the given number
longestSubArrayWhoseSumDivisibleByNumber(int[], int) - finds the longest subsequence whose sum is divisible by the given number
public class MaximumSubArray {
public static void main(String[] s) {
int a[] = new int[] {-2,-4,-3,5,-2,2,2,-5,4,2,2,3,1,-7,-1, 11};
maxSumSubArrayDivisibleByNumber(a, 7);
longestSubArrayWhoseSumDivisibleByNumber(a, 7);
}
// returns the maximum sub sequence sum that is that is divisible by the given number
public static void maxSumSubArrayDivisibleByNumber(int[] a, int k) {
int max_so_far = a[0];
int max_ending_here = a[0];
int begin = 0;
int end = 0;
int begintemp = 0;
int kbegin = 0;
int kend = 0;
int ksum = 0;
for(int i=0; i<a.length; i++) {
if(max_ending_here < 0) {
max_ending_here = a[i];
begintemp = i;
} else {
max_ending_here = max_ending_here + a[i];
}
if(max_ending_here >= max_so_far) {
max_so_far = max_ending_here;
begin = begintemp;
end = i;
if((max_so_far % k)==0) {
if((end-begin) > (kend-kbegin)) {
kbegin = begin;
kend = end;
}
ksum = max_so_far;
}
}
}
System.out.println("Max sum in subsequence divisible by " + k + " is " + ksum + "\tfrom:" + kbegin + " to:" + kend);
}
public static void longestSubArrayWhoseSumDivisibleByNumber(int[] a, int k) {
int max_so_far = a[0];
int max_ending_here = a[0];
int begin = 0;
int end = 0;
int begintemp = 0;
int kbegin = 0;
int kend = 0;
int ksum = 0;
for(int i=0; i<a.length; i++) {
if(max_ending_here < 0) {
max_ending_here = a[i];
begintemp = i;
} else {
max_ending_here = max_ending_here + a[i];
}
if(max_ending_here >= max_so_far) {
max_so_far = max_ending_here;
begin = begintemp;
end = i;
}
if((max_ending_here % k)==0) {
kbegin = begintemp;
kend = i;
ksum = max_ending_here;
}
}
System.out.println("Longest subsequence sum divisible by " + k + " is " + ksum + "\tfrom:" + kbegin + " to:" + kend);
}
}
The program result:
Max sum in subsequence divisible by 7 is 14 from:3 to:12
Longest subsequence sum divisible by 7 is 7 from:3 to:13
public static boolean isPalindromeIgnoreSpace(String s) {
if(s==null) {
return false;
} else if(s.isEmpty()) {
return true;
} else {
int p1=0;
int p2=s.length()-1;
while(p1<p2) {
while(s.charAt(p1) == ' ') {
p1++;
}
while(s.charAt(p2) == ' ') {
p2--;
}
if(s.charAt(p1) != s.charAt(p2)) {
return false;
}
p1++;
p2--;
}
return true;
}
}
/**
* algorithm to reverse a singly linked list using one pointer
* without any additional datastructures
* @author ksjeyabarani
*
*/
public class ReverseSingleLinkedList {
public static void main(String[] args) {
ReverseSingleLinkedList r = new ReverseSingleLinkedList();
LList<Integer> l = new LList<Integer>();
l.add(1);
l.add(2);
l.add(3);
l.add(4);
System.out.println("List is " + l);
l.reverse();
System.out.println("List after 2 pointer reverse " + l);
l.reverse();
System.out.println("List reversed back to original " + l);
l.reverseWithOnePointerAndNoExtraDS();
System.out.println("List WithOnePointerAndNoExtraDS " + l);
}
private static class LList<T> {
Node<T> head;
private int size;
public void add(T data) {
Node<T> n = new Node<T>(data);
if(null == head) {
head = n;
} else {
Node<T> x = head;
while(x.next != null) {
x = x.next;
}
x.next = n;
}
size++;
}
// uses three pointers - can be improved to use two pointers by accessing third node using two.next
public void reverse() {
if((null == head) || (head.next == null)) {
return;
}
Node<T> one = head;
Node<T> two = one.next;
Node<T> three = two.next;
head.next = null;
while(two != null) {
two.next = one;
one = two;
two = three;
if( null != two) {
three = two.next;
}
}
head = one;
}
public void reverseWithOnePointerAndNoExtraDS() {
if((null == head) || (head.next == null)) {
return;
}
int mid = size/2;
int x = 0;
while (x < mid) {
T temp;
temp = get(x).data;
get(x).data = get((size-1)-x).data;
get((size-1)-x).data = temp;
x++;
}
}
public Node<T> get(int index) {
if((index >= size) || (index < 0)) {
return null;
}
Node<T> n = head;
for(int x = 0; x<index; x++) {
n = n.next;
}
return n;
}
public String toString() {
if(null == head)
return null;
StringBuilder sb = new StringBuilder();
Node<T> x = head;
while(x != null) {
sb.append(x.data + " ");
x = x.next;
}
return sb.toString();
}
private static class Node<T> {
T data;
Node<T> next;
public Node(T data) {
this.data = data;
}
@Override
public String toString() {
return data + " ";
}
}
}
}
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);
}
}
- ksjeyabarani November 19, 2014