AlgoAlgae
BAN USER- 3of 3 votes
AnswersCode for computing a^b and optimize it.
- AlgoAlgae in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer
This by no means is optimal solution. I dont think there can ever be optimal solutions to such problems. However, this is a start.
Logic :
Since we expect each word to be jumbled in itself, we better pre-process the dictionary and build another dictionary that maps the word to sorted chars in that word. Instead of matching each permutation of word to original dictionary, we can just sort the jumbled up word and look it up in new dictionary. Note: all permutations of a string when sorted are same.
Now we take the deformed string and find words, as we go along.
Dictionary pre-processing : O(n m log m) where n is number of words and m length of a word.
Lookup : O(m log m)
package com.google.practice;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class SentenceResolver {
public static Set<String> dictionary = new HashSet<String>();
public static Map<Integer,Set<String>> possibleWords = new HashMap<Integer,Set<String>>();
public static Map<String,String> dictionaryPreProcessed = new HashMap<String,String>();
public static void main(String[] arg){
dictionary.add("what");dictionary.add("the");dictionary.add("hell");dictionary.add("happened");
String sentence = "ahwtethlehlepnepdha";
preProcessDictionary();
List<String> foundWords = new ArrayList<String>();
sentenceCorrector(sentence,foundWords,1);
printSentence();
}
public static void printSentence(){
for(int i=1;i<=possibleWords.keySet().size();i++){
Set<String> s = possibleWords.get(i);
for(String str : s)
System.out.print(str+" ");
}
}
public static void preProcessDictionary(){
for(String s : dictionary){
char[] s1 = s.toCharArray();
Arrays.sort(s1);
dictionaryPreProcessed.put(String.valueOf(s1),s);
}
}
public static void sentenceCorrector(String sentence,List<String> foundWords,int index){
Set<String> w = new HashSet<String>();
for(int i=1;i<=sentence.length();i++){
possibleWords.put(index, w);
String word = sentence.substring(0,i);
if(checkWord(word,possibleWords,index,possibleWords.get(index).size())){
sentenceCorrector(sentence.substring(i,sentence.length()),foundWords,index+1);
}
}
}
public static boolean checkWord(String word,Map<Integer,Set<String>> possibleWords,int index,int prevSize){
char[] c = word.toCharArray();
Arrays.sort(c);
if(dictionaryPreProcessed.containsKey(String.valueOf(c))){
Set<String> tmp = possibleWords.get(index);
tmp.add(dictionaryPreProcessed.get(String.valueOf(c)));
possibleWords.put(index,tmp);
}
return possibleWords.get(index).size()>prevSize;
}
package com.google.practice;
public class Compress2 {
public static void main(String[] arg){
String s = "9___6aab ";//"daaad";//"5eeeecd";//"1aa4aggg3hagst5";
if(s.length()==0)
System.out.println("Provide Input");
else
System.out.println(compress(s));
}
public static String compress(String s){
char p; StringBuilder sb = new StringBuilder();
int i=1,j=0;
for(;i<s.length();i++){
if(s.charAt(i)==s.charAt(j)){
if(j-1<0)
p = 'a';
else
p = s.charAt(j-1);i++;
while(i<s.length() && s.charAt(i)==s.charAt(j))
i++;
if(isDigit(p)){
sb = sb.append("*1"+(i-j)+"*"+s.charAt(j));
}else{
sb = sb.append((i-j)+"*"+s.charAt(j));
}
j = i;
}else{
sb.append(s.charAt(j));
j++;
}
}
if(j<s.length() && j==i-1)
sb.append(s.charAt(j));
return sb.toString();
}
public static boolean isDigit(char p){
try{
int n = Integer.parseInt(""+p);
if(n>=0 && n<=9)
return true;
}catch(Exception e){
return false;
}
return false;
}
}
Consider this as a tree with only root having two children. Given a node, if I do inorder traversal, I would get the cluster in order. How would I know when to stop forming cluster? I keep going left right and stop looking in a direction if the node is not listed in array or is pointing to null.
package com.google.practice;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
class Server implements Comparable<Server>{
public Server left;
public Server right;
public String name;
public Server(String name){
this.name = name;
}
@Override
public int compareTo(Server s) {
// TODO Auto-generated method stub
if(this.name.equals(s.name))
return 0;
else
return ((int) Math.random())%2==0?-1:1;
}
public String toString(){
return this.name;
}
}
public class Cluster {
public static void main(String[] arg){
Server n1 = new Server("n1");
Server n2 = new Server("n2");
Server n3 = new Server("n3");
Server n4 = new Server("n4");
Server n5 = new Server("n5");
Server n6 = new Server("n6");
n1.left = null; n1.right = n2;
n2.left = n1; n2.right = n3;
n3.left = n2; n3.right = n4;
n4.left = n3; n4.right = n5;
n5.left = n4; n5.right = n6;
n6.left = n5; n6.right = null;
Server[] network = {n1,n4,n5};
Set<Server> netSet = new TreeSet<Server>();
for(int i=0;i<network.length;i++){
netSet.add(network[i]);
}
List<List<Server>> clusters = new ArrayList<List<Server>>();
findClusters(netSet,clusters);
System.out.println(clusters.toString());
}
public static void findClusters(Set<Server> netSet,List<List<Server>> clusters){
Iterator<Server> it = netSet.iterator();
while(it.hasNext()){
Server s = it.next();
List<Server> cluster = new ArrayList<Server>();
netSet.remove(s);
findConnected(s,netSet,cluster);
clusters.add(cluster);
it = netSet.iterator();
}
}
public static void findConnected(Server s, Set<Server> netSet, List<Server> cluster){
if(s.left!=null && netSet.contains(s.left)){
netSet.remove(s.left);
findConnected(s.left,netSet,cluster);
}
cluster.add(s);
if(s.right!=null && netSet.contains(s.right)){
netSet.remove(s.right);
findConnected(s.right,netSet,cluster);
}
}
}
BFS - for accessing all vertex and edges and handling cycles with love.
for every vertex you take out from queue, clone it. store in hashmap <orinigal,clone>.
if adjacent is found for first time,
clone vertex store in hashmap <orinigal,clone> and add edge in clone adjacency.
else
take out the visited node for hashmap, add edge, put it back.
vertex and edges need to be objects. you can have 2 vertex with same value.
How are you going to do this parallely for each pass. even if you divide and conquer, you would endup with O(n log n). You have to merge each search string with the subsequent one. Why dont do it in linear time O(n)
StringBuilder sb = new StringBuilder ();
for(String s : searchList)
sb.append(s);
"or am I missing something."
1. Have a TreeSet to store each line parsed.
2. Divide file in chunks.
3. Create another file handler for new file for output.
4. Split input file in chunks.
5. For each chunk and start parsing it line by line.
if(you find the line is existing in set) - skip the line
else output the line to output file.
6. Once done, delete the input file and rename output file to that of input file.
I would still go with unix command as mentioned by nilkn.
Lets take example of Google page - auto suggestion. This is what I believe should be happening.
1. When user enters into search box, the view module (ex jsp) makes a call the google webapp servlet with user inputs as parameter string using ofcourse AJAX.
2. Based on the inputs / paramter string the server looks up the possible suggestion by looking up the data structure that stores all the previous searched strings. Data structure here would best be Trie. search is a DFS
3. after completing all strings search, the servlet sends back the collection to view module.
4. view on reciept of response, sets the respective DOM object to display the suggestion.
This happens as you type :).
This is N-Queen problem. Applying greedy approach to find all possible values for each char. Best guess - D can only have have value 0/1. We can set that in advance and find others.
package com.google.practice;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
public class StringAdd {
public static Set<String> result = new TreeSet<String>();
public static void main(String[] arg){
char[] x = {'R','E','V','E'};//{'E','V','E','R'};
char[] y = {'E','C','N','I','S'};//{'S','I','N','C','E'};
char[] sum = {'N','I','W','R','A','D'};//{'D','A','R','W','I','N'};
char[] chars = {'A','C','D','E','I','N','R','S','V','W'};
Map<Character,Integer> m = new HashMap<Character,Integer>();
for(char c : chars)
m.put(c, 0);
int[] position = new int[10];
solve(x,y,sum,position,m,chars);
Iterator<String> it = result.iterator();
while(it.hasNext())
System.out.println(it.next());
}
public static void solve(char[] x, char[] y,char[] sum, int[] q,Map<Character,Integer> m,char[] chars){
if(max(x.length,y.length)<sum.length){
for(int i=0;i<2;i++){
q[2] = i;
m.put(chars[2], i);
findOther(x,y,sum,q,i,0,m,chars);
}
}
}
public static void findOther(char[] x, char[] y,char[] sum, int[] q, int d,int n,Map<Character,Integer> m,char[] chars){
int N = q.length;
if(N==n){
if(checkResult(x,y,sum,q,m,chars)){
String s="[";
int result_sum = m.get('D')+m.get('A')+m.get('R')+m.get('W')+m.get('I')+m.get('N');
for(int i=0;i<10;i++){
s = s+chars[i]+"="+m.get(chars[i])+",";
}
result.add(s.substring(0, s.length()-1)+"]"+" [D+A+R+W+I+N = "+result_sum+"]");
return;
}
else{
return;
}
}
for(int i=0;i<N;i++){
if(i!=d){
if(n!=2){
q[n] = i;
m.put(chars[n], i);
}
if(noClash(q,n))
findOther(x,y,sum,q,d,n+1,m,chars);
}
}
}
public static boolean noClash(int[] q, int n){
for(int i=0;i<n;i++){
if(q[i]==q[n])
return false;
}
return true;
}
public static boolean checkResult(char[] x, char[] y,char[] sum, int[] q,Map<Character,Integer> m,char[] chars){
int carry = 0;
int limit = max(x.length,y.length);
int i=0;
for(;i<limit;i++){
if(((i>=x.length?0:m.get(x[i]))+(i>=y.length?0:m.get(y[i]))+carry)%10!=m.get(sum[i]))
return false;
carry = ((i>=x.length?0:m.get(x[i]))+(i>=y.length?0:m.get(y[i])))/10;
}
if(m.get(sum[i])!=carry)
return false;
return true;
}
public static int max(int x, int y){
if(x==y || x>y)
return x;
return y;
}
}
Result :
[A=2,C=3,D=0,E=5,I=8,N=9,R=4,S=1,V=7,W=6] [D+A+R+W+I+N = 29]
[A=4,C=2,D=0,E=6,I=9,N=1,R=5,S=3,V=7,W=8] [D+A+R+W+I+N = 27]
[A=7,C=3,D=0,E=5,I=8,N=9,R=4,S=6,V=2,W=1] [D+A+R+W+I+N = 29]
[A=8,C=2,D=0,E=6,I=9,N=1,R=5,S=7,V=3,W=4] [D+A+R+W+I+N = 27]
[A=9,C=3,D=0,E=4,I=7,N=6,R=2,S=8,V=5,W=1] [D+A+R+W+I+N = 25]
package com.google.practice;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
class CrazyIterator implements Iterator<String>{
public CrazyObject c;
public CrazyIterator(CrazyObject c){
this.c = c;
}
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
if(!this.c.myCharacter.get(this.c.cposition).equals("#")){
if(this.c.myCharacter.get(this.c.cposition).equals("@")){
this.c.cposition++;
this.c = this.c.mySperm.get(this.c.sposition++);
this.hasNext();
}
return true;
}else{
if(this.c.myParent!=null){
this.c = this.c.myParent;
return this.hasNext();
}
}
return false;
}
@Override
public String next() {
// TODO Auto-generated method stub
return this.c.myCharacter.get(this.c.cposition++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
}
class CrazyObject implements Iterable{
public List<String> myCharacter;
public List<CrazyObject> mySperm;
public CrazyObject myParent=null;
public int cposition = 0,sposition=0;
public CrazyObject(){
myCharacter = new ArrayList<String>();
mySperm = new ArrayList<CrazyObject>();
}
public void test(){}
@Override
public Iterator iterator() {
// TODO Auto-generated method stub
return new CrazyIterator(this);
}
public String toString(){
String s = "[",s1;
CrazyIterator ct = (CrazyIterator) this.iterator();
while(ct.hasNext()){
s1 = ct.next();
if(s1.length()>0)
s = s +(s1+",");
}
return s.substring(0,s.length()-1)+"]";
}
}
public class Iter {
public static void main(String[] arg){
String s = "[[0,1,2],[3,4,5],[6,7,8],[9,10,11],[]]";//"[1,2,[3,[4,5]],6]";
CrazyObject crazyFamily = buildCrazyObject(s);
System.out.println(crazyFamily);
}
public static CrazyObject buildCrazyObject(String s){
String n = "";
CrazyObject crazy = null,previous = null;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='['){
CrazyObject c = new CrazyObject();
if(crazy!=null){
crazy.myCharacter.add("@");
crazy.mySperm.add(c);
}
c.myParent = crazy;
crazy = c;
}else if(s.charAt(i)==']'){
crazy.myCharacter.add(n);
n="";
crazy.myCharacter.add("#");
previous = crazy;
crazy = crazy.myParent;
}else if(s.charAt(i)!=','){
n = n+s.charAt(i);
}else{
crazy.myCharacter.add(n);
n="";
}
}
return previous;
}
}
package com.google.practice;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
class Pos{
public int x;
public int y;
public int level;
public Pos(int x,int y,int level){
this.x = x;
this.y = y;
this.level = level;
}
}
public class DiagonalPrint {
public static void main(String[] arg){
int[][] mat = {{1,2},{5,6},{9,10}};
int n=mat.length;
int m=mat[0].length;
//printDiagonally(mat,n,m);
printDiagonallyBFS(mat,0,0,n,m);
}
public static void printDiagonally(int[][] mat,int n,int m){
for(int i=0,j=0;i<n;){
for(int k=j-i,inc=0;k>=0;k--,inc++){
System.out.print(mat[i+inc][j-inc]);
}
System.out.println();
if(j==m-1)
i++;
else
j++;
}
}
public static void printDiagonallyBFS(int[][] mat,int i,int j,int n,int m){
int level = 1;
Map<Integer,String> matVal = new HashMap<Integer,String>();
Queue<Pos> q = new LinkedList<Pos>();
matVal.put(level, mat[i][j]+" ");
q.add(new Pos(i,j,1));
while(!q.isEmpty()){
Pos u = q.poll();
i = u.x;
j = u.y;
int l = u.level;
//right
if(i==0 && j<m-1){
Pos p = new Pos(i,j+1,l+1);
putInHash(i,j+1,l+1,matVal,mat);
q.add(p);
}
//down
if(i<n-1){
Pos p = new Pos(i+1,j,l+1);
putInHash(i+1,j,l+1,matVal,mat);
q.add(p);
}
}
printDiagonal(matVal);
}
public static void putInHash(int i,int j,int l,Map<Integer,String> matVal,int[][] mat){
if(matVal.containsKey(l)){
String s = matVal.get(l);
matVal.put(l, s+mat[i][j]+" ");
}else{
matVal.put(l, mat[i][j]+" ");
}
}
public static void printDiagonal(Map<Integer,String> matVal){
Set<Integer> levels = matVal.keySet();
for(int i : levels)
System.out.println(matVal.get(i));
}
}
BFS approach. Storing diagonals level wise. time O(nm)
- AlgoAlgae April 23, 2014package com.google.practice;
public class SortItOut {
public static void main(String[] arg){
char[] mix = {'a','1','b','2','c','3','d','4'};
sortItOut(mix);
System.out.println(String.copyValueOf(mix).toString());
}
//since every alphabet is at odd position, making sure j points to odd location
// for every swap will ensure the alphabets to be placed before digits.
public static void sortItOut(char[] mix){
int skip = 0;
for(int i=1;i<mix.length;i++){
int j = i+skip+1;
if(j>=mix.length)
skip = 0;
else{
char tmp = mix[i];
mix[i] = mix[j];
mix[j] = tmp;
skip++;
}
}
}
}
Need a little help here. I am able to place all alphabets before digits, before the skip is reset. When I apply the same logic again for the numeric part, it isn't working for all inputs. Trying to figure that out, but I think I am almost there.
- AlgoAlgae April 23, 2014package com.google.practice;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Pointe implements Comparable<Pointe>{
int x;
int y;
int pointSpot;
public Pointe(int x,int y,int pointSpot){
this.x = x;
this.y = y;
this.pointSpot = pointSpot;
}
@Override
public int compareTo(Pointe o) {
// TODO Auto-generated method stub
return Double.compare(this.pointSpot, o.pointSpot);
}
}
public class BlacknWhite {
public static void main(String[] arg){
int n=5,m=5;
int[][] board = {{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,1}};
findMinRec(board,n,m);
}
public static void findMinRec(int[][] board,int n,int m){
List<Pointe> corner = findTopCorner(board,n);
Collections.sort(corner);
if(corner.size()==0)
System.out.println("No Black found");
else if(corner.size()==1)
printResult(corner.get(0).x, corner.get(0).y, corner.get(0).x, corner.get(0).y);
else if(corner.size()==4 || (corner.get(0).pointSpot==1 && corner.get(1).pointSpot==2)){
int x1 = corner.get(0).x,y1= corner.get(0).y,x2 = corner.get(1).x,y2 = corner.get(1).y;
if(corner.size()==4 || corner.size()==3){
if( corner.size()==3){
if(corner.get(2).pointSpot==3){
corner.add(new Pointe(corner.get(0).x,corner.get(0).y,4));
}else
corner.add(new Pointe(corner.get(1).x,corner.get(1).y,3));
Collections.sort(corner);
}
if(corner.get(3).y < corner.get(0).y)
y1 = corner.get(3).y;
if(corner.get(2).x<corner.get(0).x)
x1 = corner.get(2).x;
if(corner.get(2).y>corner.get(1).y)
y2 = corner.get(2).y;
if(corner.get(3).x>corner.get(1).x)
x2 = corner.get(3).x;
}
printResult(x1, y1, x2, y2);
}else{
if(corner.size()==3){
if(corner.get(0).pointSpot==1){
printResult(corner.get(0).x, corner.get(0).y, corner.get(1).y, corner.get(2).x);
}else{
printResult(corner.get(1).x, corner.get(2).y, corner.get(0).x, corner.get(0).y);
}
}else {
if(corner.get(0).pointSpot==2)
printResult(corner.get(1).x, corner.get(1).y, corner.get(0).x, corner.get(0).y);
else
printResult(corner.get(0).x, corner.get(0).y, corner.get(1).x, corner.get(1).y);
}
}
}
public static List<Pointe> findTopCorner(int[][] board,int n){
List<Pointe> points = new ArrayList<Pointe>();
boolean topLeft=false;Pointe tLeft = new Pointe(-1,-1,1);
boolean topRight=false;Pointe tRight = new Pointe(-1,-1,3);
boolean bottomLeft=false;Pointe bLeft = new Pointe(-1,-1,4);
boolean bottomRight=false;Pointe bRight = new Pointe(-1,-1,2);
for(int i1=0,i2=n-1;i1<=n/2;i1++,i2--){
for(int j1=0,j2=n-1;j1<=n/2;j1++,j2--){
if(points.size()==4)
return points;
if(!topLeft){
if(board[i1][j1]==1 || board[j1][i1]==1){
topLeft = true;
if(board[i1][j1]==1){
tLeft.x = i1;
tLeft.y = j1;
}
else{
tLeft.x = j1;
tLeft.y = i1;
}
points.add(tLeft);
}
}
if(!topRight){
if(board[i1][j2]==1 || board[j1][i2] == 1){
topRight = true;
if(board[i1][j2]==1){
tRight.x = i1;
tRight.y = j2;
}
else{
tRight.x = j1;
tRight.y = i2;
}
points.add(tRight);
}
}
if(!bottomLeft){
if(board[i2][j1]==1 || board[j2][i1]==1){
bottomLeft = true;
if(board[i2][j1]==1){
bLeft.x = i2;
bLeft.y = j1;
}
else{
bLeft.x = j2;
bLeft.y = i1;
}
points.add(bLeft);
}
}
if(!bottomRight){
if(board[i2][j2]==1 || board[j2][i2]==1){
bottomRight = true;
if(board[i2][j2]==1){
bRight.x = i2;
bRight.y = j2;
}
else{
bRight.x = j2;
bRight.y = i2;
}
points.add(bRight);
}
}
}
}
return points;
}
public static void printResult(int x1,int y1,int x2,int y2){
System.out.println("("+x1+","+y1+")-("+x2+","+y2+")");
}
}
Good or bad, this also works for 1's that are not connected. Finds the enclosing minimum rectangle. O(n^2) but pruned to 1/4th of total time.
- AlgoAlgae April 22, 2014package com.google.practice;
public class SortOnPerm {
public static void main(String[] arg){
int[] x = {0,3,7,15,2,8};//{0,17,5,1,9};
int[] a = {0,4,2,3,1,5};//{0,3,2,4,1};
mergeSort(a,x,1,a.length-1);
for(int i=1;i<x.length;i++)
System.out.print(x[i]+" ");
}
public static void mergeSort(int[] a,int[] x,int low,int high){
if(low>=high)
return;
int mid = (low+high)/2;
mergeSort(a,x,low,mid);
mergeSort(a,x,mid+1,high);
merge(a,x,low,mid,high);
}
public static void merge(int[] a,int[] x,int low,int mid ,int high){
for(int i=low,j=mid+1;i<=high&&j<=high;j++){
if(i<=high && j<=high){
if(a[j]<a[i]){
int tmp = x[i];
x[i] = x[j];
x[j] = tmp;
tmp = a[i];
a[i] =a[j];
a[j] = tmp;
i++;j--;
}
}
}
}
}
Merge Sort, without helper array for merge. O(n log n)
- AlgoAlgae April 22, 2014package com.google.practice;
public class Subseqsum {
public static void main(String[] arg){
int[] a = { 1, 2, 3, 4, -10, -2 };
int sum = 8;
findMinSeq(a,sum);
}
public static void findMinSeq(int[] a, int sum){
int minSoFar = Integer.MAX_VALUE;
int start=0,end=0;
int pStart=0,pEnd=0;
int seqSum = 0;
while(true){
if(end<a.length)
seqSum = seqSum + a[end];
if(seqSum<=sum){
//no need check anymore
if(end==a.length-1)
break;
end++;
}
else{
//if sequence length is shorter than previously found
if(end-start < minSoFar){
minSoFar = end - start;
pStart = start;
pEnd = end;
}
seqSum = seqSum - a[start] - a[end];
start++;
}
//another term condition when all sequence is checked
if(end==a.length-1 && start == a.length){
break;
}
}
if(minSoFar>a.length)
System.out.println("no subsequence");
else{
System.out.print("{");
for(int i=pStart;i<=pEnd;i++){
System.out.print(" "+a[i]);
}
System.out.print(" }");
}
}
}
start and end move n positions each. O(n+n) = O(n)
- AlgoAlgae April 21, 2014Here is java solution. you can try expression starting with -/+ sign, expression with braces (only '()') or normal expression as in problem definition. I haven't put any validation so please don't try with invalid expression.
package com.amazon.general;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Pattern;
class Stack<T>{
private List<T> stack = new ArrayList<T>();
private int top = -1;
private boolean stackEmpty= true;
public void push(T t){
stack.add(t);
top++;
stackEmpty = false;
}
public T pop(){
T t = null;
if(!stackEmpty){
t = (T) stack.get(top);
stack.remove(top--);
if(top==-1){
stackEmpty = true;
}
}
return t;
}
public T peak(){
T t = null;
if(!stackEmpty){
t = (T) stack.get(top);
}
return t;
}
}
public class ExpressionCalc {
static Pattern p = Pattern.compile("[()*/+-]");
static Stack<String> stack = new Stack<String>();
static Stack<Float> numeric = new Stack<Float>();
static Stack<String> operator = new Stack<String>();
public static void main(String[] arg){
String exp = "12+5*4/7";//"(((12)+5)*4)/7";
stackIt(exp,p);
if(p.matcher(""+exp.charAt(0)).find())
System.out.println(calc(0.0f));
else
System.out.println(calc(numeric.pop()));
}
public static void stackIt(String exp, Pattern p){
String n = "";
for(int i=exp.length()-1;i>=0;i--){
if(!p.matcher(""+exp.charAt(i)).find()){
n = exp.charAt(i) + n;
}else{
if(n.length()!=0){
numeric.push(Float.valueOf(n));
n="";
}
if((exp.charAt(i)=='*' || exp.charAt(i)=='/') && exp.charAt(i-1)==')'){
operator.push(""+exp.charAt(i));
operator.push(")");
i--;
}else{
switch(exp.charAt(i)){
case '*' : for(int j=i-1;j>=0 && !p.matcher(""+exp.charAt(j)).find();j--){
n = exp.charAt(j)+n;i=j;
}
numeric.push((numeric.pop())*(Integer.parseInt(n)));n="";
break;
case '/' : for(int j=i-1;j>=0 && !p.matcher(""+exp.charAt(j)).find();j--){
n = exp.charAt(j)+n;i=j;
}
numeric.push((Integer.parseInt(n))/(numeric.pop()));n="";
break;
default : operator.push(""+exp.charAt(i));
//if(i==0)
// numeric.push(0.0f);
break;
}
}
}
}
if(n.length()>0)
numeric.push(Float.valueOf(n));
}
public static float calc(float result){
while(operator.peak()!=null){
switch(operator.pop()){
case "+" : if((operator.peak()!=null && !operator.peak().equals("(")) || operator.peak()==null)
result = result + numeric.pop();
else{operator.pop();
if(operator.peak()!=null && operator.peak().equals("("))
result = result + calc(0.0f);
else
result = result + calc(numeric.pop());
}
break;
case "-" : if((operator.peak()!=null && !operator.peak().equals("(")) || operator.peak()==null)
result = result - numeric.pop();
else{operator.pop();
if(operator.peak()!=null && operator.peak().equals("("))
result = result - calc(0.0f);
else
result = result - calc(numeric.pop());
}
break;
case "*" : if((operator.peak()!=null && !operator.peak().equals("(")) || operator.peak()==null)
result = result * numeric.pop();
else{operator.pop();
if(operator.peak()!=null && operator.peak().equals("("))
result = result * calc(0.0f);
else
result = result * calc(numeric.pop());
}
break;
case "/" : if((operator.peak()!=null && !operator.peak().equals("(")) || operator.peak()==null)
result = result / numeric.pop();
else{operator.pop();
if(operator.peak()!=null && operator.peak().equals("("))
result = result / calc(0.0f);
else
result = result / calc(numeric.pop());
}
break;
case "(" : if(operator.peak()!=null && !operator.peak().equals("("))
result = calc(numeric.pop());
else
result = calc(result);
break;
case ")" : return result;
}
}
return result;
}
}
public class CircularQueue<E> {
private E[] queue;
private int size;
private int head,tail;
public CircularQueue(int size){
this.head = 0;
this.tail = 0;
this.size = size;
this.initialize(size);
}
@SuppressWarnings("unchecked")
public void initialize(int size){
this.setQueue((E[]) new Object[size]);
this.head = 0;
this.tail = 0;
this.size = size;
}
public E[] getQueue() {
return queue;
}
public void setQueue(E[] queue) {
this.queue = queue;
}
public synchronized void enqueue(E e){
if(checkOverflow()){
System.out.println("Queue overflow");
return;
}
this.queue[this.tail] = e;
this.tail = (this.tail+1)%this.size;
}
public synchronized void dequeue(){
if(checkUnderflow()){
System.out.println("Queue underflow");
return;
}
this.queue[this.head] = null;
this.head = (this.head+1)%this.size;
}
private boolean checkOverflow(){
if(this.tail==this.head && this.queue[this.head]!=null){
return true;
}
return false;
}
private boolean checkUnderflow(){
if(this.tail==this.head && this.queue[this.head]==null){
return true;
}
return false;
}
}
public static void checkExistense(int z, int k){
int d = checkPrime(z);
if(d==0){
System.out.println(z+" is present in Arr-"+k);
return;
}
if(k>d){
System.out.println(z+" is not present in Arr-"+k);
}else{
if(z%2==0 || z%3==0 || z%5==0){
System.out.println(z+" is not present in Arr-"+k);
}else{
System.out.println(z+" is present in Arr-"+k);
}
}
}
public static int checkPrime(int z){
for(int i=(int) Math.sqrt(z);i>1;i--){
if(z%i==0)
return i;
}
return 0;
}
Here you go. This handles unequal sized lists too.
int[] carriage = new int[Math.max(num1.size(), num2.size())+1];
int[] result = new int[carriage.length];
boolean carr = false;
Iterator<Node> itMax = num1.size()<num2.size()?num2.iterator():num1.iterator();
Iterator<Node> itMin = num1.size()<num2.size()?num1.iterator():num2.iterator();
int n,n1,n2;
int multiplier = (Math.max(num1.size(), num2.size()) - Math.min(num1.size(), num2.size()));
int minSize = Math.min(num1.size(), num2.size());
int maxSize = Math.max(num1.size(), num2.size());
int y=0,x=0;
// Initial sum from left to right. Also maintaining carriages for normalization.
// Parsing the linked list only once.
for(int i=0;itMax.hasNext();i++){
n1 = itMax.hasNext()?(itMax.next()).val:0;
n2 = itMin.hasNext()?(itMin.next()).val:0;
y = (int) (y + n2 * (Math.pow(10,(minSize-1-i))));
n = (n1 + n2);
if(n/10 > 0 || n==10){
carriage[i] = 1;
carr = true;
}
result[i+1] = n%10;
}
//Normalizing
while(carr){
x = 0;
carr = false;
for(int i=1;i<result.length;i++){
if((result[i]+carriage[i])/10>0 || (result[i]+carriage[i])==10){
carriage[i-1] = 1;
carr = true;
}
result[i] = (result[i]+carriage[i])%10;
x = (int) (x + (result[i] * (Math.pow(10,(maxSize-i)))));
carriage[i] = 0;
}
}
//Result Sum
System.out.println("SUM = "+(x-(int)(((Math.pow(10,multiplier))-1)*y)));
O(n^2)
- AlgoAlgae May 06, 2014