Calculator (Math)

Question:  design and implement a calculate that can calculate expressions like:
+ 2 4
* 8 ( + 7 12)
( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 )

(PS:all items are space deli-metered.)

Example answers
+ 2 4 => 2 + 4 = 6
* 8 ( + 7 12) => 8 * ( 7 + 12 ) = 152
"( + + + 7 ( * 8 12 ) ( * * 2 ( + 9 4 ) 7 ) 3 )" => 7+8*12+2*(9+4)*7+3 = 288

Idea: Polish notation (prefix notation). Use a stack. Scan from right to left,
1) if the character is "(" or ")": ignore
2) if the character is an operator, pop two operands for the operator and push back the results
3) if the character is an integer, push to the stack.

Time: O(n) Space: O(n)

Code:

 public class Calculator {  
      public Calculator()  
      {  
           String input1="+ 2 4";  
           String input2="* 8 ( + 7 12 )";  
           String input3="( + + + 7 ( * 8 12 ) ( * * 2 ( + 9 4 ) 7 ) 3 )";  
           System.out.println(calculate(input1));  
           System.out.println(calculate(input2));  
           System.out.println(calculate(input3));  
      }  
      public int calculate(String s)  
      {  
           if(s==null||s.length()==0)  
                return 0;  
           String[] symbols=s.split(" ");  
           Stack<Integer> stack=new Stack<Integer>();  
           for(int i=symbols.length-1;i>=0;i--)  
           {  
                int type=isOperator(symbols[i]);  
                if(type==0)  
                     continue;  
                if(type==5)  
                     stack.push(Integer.parseInt(symbols[i]));  
                else  
                {  
                     int second=stack.pop();  
                     int first=stack.pop();  
                     switch(type)  
                     {  
                     case 1:  
                          stack.push(first+second);  
                          break;  
                     case 2:  
                          stack.push(first-second);  
                          break;  
                     case 3:   
                          stack.push(first*second);  
                          break;  
                     case 4:  
                          stack.push(first/second);  
                          break;  
                     default:  
                          break;  
                     }  
                }  
           }  
           return stack.pop();  
      }  
      public int isOperator(String s)  
      {  
           if(s.equals("(")||s.equals(")"))  
                return 0;  
           if(s.equals("+"))  
                return 1;  
           else if(s.equals("-"))  
                return 2;  
           else if (s.equals("*"))  
                return 3;  
           else if(s.equals("/"))  
                return 4;  
           else  
                return 5;  
      }  
 }  

ThreeAndFive (Math)

Question: write an algorithm to find sum of numbers which are smaller than N and divisible by 3 or 5

Example:
N = 9 => 3 + 5 + 6 = 14
N = 10 => 3 + 5 + 6 + 9 = 23

Idea: Arithmetic progression and inclusion-exclusion principle.
The sum of 3's and 5's = The sum of 3's+ The sum of 5's - The sum of 15's. Take care the question asks for smaller than, so 9 does not count if the input is 9.

Time: O(1) Space: O(1)

Code:

 public class ThreeAndFive {  
      public ThreeAndFive()  
      {  
           int input1=9;  
           int input2=10;  
           int input3=16;  
           int input4=100;  
           System.out.println(threeAndFive(input1));  
           System.out.println(threeAndFive(input2));  
           System.out.println(threeAndFive(input3));  
           System.out.println(threeAndFive(input4));  
      }  
      public int threeAndFive(int n)  
      {  
           n--;  
           int numOf3=n/3;  
           int numOf5=n/5;  
           int numOf15=n/15;  
           return getSum(0,numOf3*3,3)+getSum(0,numOf5*5,5)-getSum(0,numOf15*15,15);  
      }  
      public int getSum(int first,int last,int step)  
      {  
           int howMany=(last-first)/step+1;  
           int sum=(first+last)*howMany/2;  
           return sum;  
      }  
 }  

String Character Count (String)

Question: a#3bd#5 -》 aaabddddd..

Idea: Since the number after # may be zero or numbers larger than 9, we need to take care of the corner cases a little bit.
Use a stringbuilder to cache the result and use a pointer to scan from left to right. If it is a letter, append to the stringbuilder; if it is a '#', temporally store the last character in the stringbuilder, pop the last character, count the number to append, append them and move the pointer forward.

Time: O(n) Space: O(1)

Code:

      public StringConvert()  
      {  
           String input1="a#3bd#5e#33";  
           System.out.println(stringExpand(input1));  
      }  
      public String stringExpand(String s)  
      {  
           if(s==null||s.length()==0)  
                return s;  
           StringBuilder builder=new StringBuilder();  
           for(int i=0;i<s.length();)  
           {  
                char c=s.charAt(i);  
                if(getType(c)==3)  
                {  
                     builder.append(c);  
                     i++;  
                }  
                else  
                {  
                     int num=0;  
                     char lastC=builder.charAt(builder.length()-1);  
                     int j=i;  
                     for(j=i+1;j<s.length()&&getType(s.charAt(j))==2;j++)  
                     {  
                          num=num*10+(int)(s.charAt(j)-'0');  
                     }  
                     builder.deleteCharAt(builder.length()-1);  
                     for(int k=0;k<num;k++)  
                          builder.append(lastC);  
                     i=j;  
                }  
           }  
           return builder.toString();  
      }  
      public int getType(char c)  
      {  
           if(c=='#')  
                return 1;  
           if(c>='0'&&c<='9')  
                return 2;  
           else  
                return 3;  
      }  

Cube Sum (HashMap)

Question: Please write a function that would print all positive numbers smaller than n that can be expressed as the sum of two cubes in two different ways. Bonus: calculate the complexity of that function.
For example, 1729 is one such number because 1729 = 1^3 + 12^3 = 9^3 + 10^3.

Idea: Binary search to find the ceiling(power(n,1/3)), then from 0 to the ceiling, we find calculate i^3+j^3, where j is from i+1 to the ceiling and store all the sum in a hashmap<sum, times appeared>. If any sum value shows up more than once, append to the result.
I would suggest not to use math.power(n, 1.0/3), since math.pow(64,1.0/3)=3.99999996.
"Output" is a class I wrote for printing my own tests, the function is just to print a list of integers if the input is not null. If the List<Integer> is null, print an "\n".

Time: O(n^2/3) Space: O(n^2/3)

Code:

 public class CubeSum {  
      public CubeSum()  
      {  
           int n1=1;  
           int n2=7;  
           int n3=8;  
           int n4=26;  
           int n5=27;  
           int n6=29;  
           int n7=1729;  
           int n8=30000;  
           Output.printList(getCubeNumbers(n1));  
           Output.printList(getCubeNumbers(n2));  
           Output.printList(getCubeNumbers(n3));  
           Output.printList(getCubeNumbers(n4));  
           Output.printList(getCubeNumbers(n5));  
           Output.printList(getCubeNumbers(n6));  
           Output.printList(getCubeNumbers(n7));  
           Output.printList(getCubeNumbers(n8));  
      }  
      public List<Integer> getCubeNumbers(int n)  
      {  
           List<Integer> result=new ArrayList<Integer>();  
           int start=0;  
           int end=cubeRootUp(n);  
           HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();  
           for(int i=start;i<end;i++)  
           {  
                for(int j=i+1;j<=end;j++)  
                {  
                     int cube=i*i*i+j*j*j;  
                     if(cube<=n&&map.containsKey(cube))  
                          map.put(cube, map.get(cube)+1);  
                     else  
                          map.put(cube, 1);  
                }  
           }  
           for(int key:map.keySet())  
           {  
                if(map.get(key)>1)  
                     result.add(key);  
           }  
           return result;  
      }  
      public int cubeRootUp(int x)  
      {  
           long y=(long)x;  
           long left=0;  
           long right=x/3;  
           while(left<=right)  
           {  
                long mid=(left+right)/2;  
                long cube=mid*mid*mid;  
                if(cube==y)  
                     return (int)mid;  
                if(cube<x)  
                     left=mid+1;  
                else  
                     right=mid-1;  
           }  
           return (int)left;  
      }  
 }  

Repeated DNA Sequences (LeetCode Bit Manipulation)

Question: All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
For example,
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Idea: Create a HashMap<bit representation of substring, appeared times>. For each 10 letter window, calculate its bit representation as the key. Then slide the window from left to right, if the key shows up exactly twice, append the substring to the result.

Time: O(n) Space: O(n)

Code:

 public class Solution {  
   public List<String> findRepeatedDnaSequences(String s) {  
     List<String> result=new ArrayList<String>();  
     HashMap<Integer,Integer> computed=new HashMap<Integer,Integer>();  
     for(int i=0;i<=s.length()-10;i++)  
     {  
       String sub=s.substring(i,i+10);  
       int key=getKey(sub);  
       if(computed.containsKey(key))  
       {  
         computed.put(key,computed.get(key)+1);  
         if(computed.get(key)==2)  
           result.add(sub);  
       }  
       else  
         computed.put(key,1);  
     }  
     return result;  
   }  
   public int getKey(String s)  
   {  
     int result=0;  
     for(int i=s.length()-1;i>=0;i--)  
     {  
       int b=0;  
       switch(s.charAt(i))  
       {  
         case 'A':  
           b|=0;  
           break;  
         case 'T':  
           b|=1;  
           break;  
         case 'G':  
           b|=2;  
           break;  
         case 'C':  
           b|=3;  
           break;  
       }  
       result=b|result;  
       result=result<<2;  
     }  
     return result;  
   }  
 }