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;  
      }  

Simple Best Time Stock

Question: Given an array, find the maximum difference between two array elements given the second element comes after the first.

Idea: Use a variable to remember the minimum showed up before.

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

Code:

 public class maxSub {  
      public maxSub()  
      {  
           int[] input1={1,2,3,4};  
           int[] input2={-5,1,6,17};  
           int[] input3={90,12,4,-11};  
           System.out.println(maxSubInArray(input1));  
           System.out.println(maxSubInArray(input2));  
           System.out.println(maxSubInArray(input3));  
      }  
      public int maxSubInArray(int[] A)  
      {  
           if(A.length<=1)  
                return 0;  
           int minNow=A[0];  
           int maxSubNow=Integer.MIN_VALUE;  
           for(int i=1;i<A.length;i++)  
           {  
                maxSubNow=Math.max(A[i]-minNow, maxSubNow);  
                minNow=Math.min(minNow,A[i]);  
           }  
           return maxSubNow;  
      }  
 }  

UTF-8 Validation (Array)

Question: A string is encoded in UTF-8 as a sequence of bytes, where each character is composed of one or more bytes in the encoding.  To figure out how many bytes are in a character, look at the leading number of ones in the binary representation of the character’s first byte:
0xxxxxxx - 1-byte character (i.e., 0xxxxxxx)
10xxxxxx - continuation byte (not valid as a leading byte)
110xxxxx - starts a 2-byte character (i.e., 110xxxxx 10xxxxxx)
1110xxxx - starts a 3-byte character (i.e., 1110xxxx 10xxxxxx 10xxxxxx)
11110xxx - starts a 4-byte character
…
11111111 - starts a 8-byte character
For example:
[11001101, 10000111, 00110000, 11101111, 10010011, 10000110] is a valid three-character string.
First character is 11001101, 10000111.
Second character is 00110000.
Third character is 11101111, 10010011, 10000110.
[01001110, 11000011, 11010101] is an invalid string.
3rd byte should be continuation byte.
[10111000, 00010010] is an invalid string.
1st byte is should be a non-continuation byte.
Write a function that determines whether a given byte array is a valid UTF-8-encoded string.

Idea: Brute force. For each input string array, scan from left to right. If it is a start character, check the next x strings whether it is 10xxxxxx format.

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

Code:

 public class UTF8 {  
      public UTF8()  
      {  
           String[] input1={"11001101", "10000111", "00110000", "11101111", "10010011", "10000110"};  
           String[] input2={"01001110", "11000011", "11010101"};  
           String[] input3={"10111000", "00010010"};  
           String[] input4={"11001101", "10000111", "00110000", "11101111", "10010011", "10000110","10010011"};  
           System.out.println(checkUTF8(input1));  
           System.out.println(checkUTF8(input2));  
           System.out.println(checkUTF8(input3));  
           System.out.println(checkUTF8(input4));  
      }  
      public boolean checkUTF8(String[] input)  
      {  
           if(input==null||input.length==0)  
                return true;  
           int index=0;  
           while(index<input.length)  
           {  
                int type=getType(input[index]);  
                if(type==0)  
                     return false;  
                int end=index+type-1;  
                if(end>=input.length)  
                     return false;  
                while(end>index)  
                {  
                     if(getType(input[end])!=0)  
                          return false;  
                     end--;  
                }  
                index=index+type;  
           }  
           return true;  
      }  
      public int getType(String s)  
      {  
           int i=0;  
           for(;i<s.length();i++)  
           {  
                if(s.charAt(i)!='1')  
                     break;  
           }  
           if(i==0)  
                return 1;  
           else if(i==1)  
                return 0;  
           else  
                return i;  
      }  
 }  

Print All Ascii

Question: Write a function that prints all ASCII characters. You are not allowed to use for/while loop.

Idea: Recursion. Start from 0, print, add 1 then recursively next until 255

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

Code: 

 public class printAllASIC {  
      public printAllASIC()  
      {  
           printASIC(0);  
      }  
      public void printASIC(int charNum)  
      {  
           if(charNum<255)  
           {  
                char toPrint=(char)charNum;  
                System.out.println(toPrint);  
                printASIC(charNum+1);  
           }  
      }  
 }  

Closest Number Below (Binary Search)

Question: 
Given: array/list/whatever arr of integers, sorted (“people’s guesses”) target integer x (“actual price”)
Find the largest arr[i] <= x.

Idea: Binary Search.

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

Code:

 public class ClosestNumber {  
      public ClosestNumber()  
      {  
           int[] input1={1};  
           int target1=6;  
           int[] input2={1,4};  
           int target2=2;  
           int[] input3={1,4,12};  
           int target3=8;  
           int[] input4={1, 13, 101,Integer.MAX_VALUE};  
           int target4=100;  
           System.out.println(binarySearch(input1,target1));  
           System.out.println(binarySearch(input2,target2));  
           System.out.println(binarySearch(input3,target3));  
           System.out.println(binarySearch(input4,target4));       
      }  
      //assume A!=empty  
      public int binarySearch(int[] A, int target)  
      {  
           int left=0;  
           int right=A.length-1;  
           while(left<=right)  
           {  
                int mid=(left+right)/2;  
                if(A[mid]==target)  
                     return target;  
                if(A[mid]<target)  
                     left=mid+1;  
                else  
                     right=mid-1;  
           }  
           return A[right];  
      }  
 }  

Page Number

Question: A book contains with pages numbered from 1 - N. Imagine now that you concatenate all page numbers in the book such that you obtain a sequence of numbers which can be represented as a string. You can compute number of occurrences 'k' of certain digit 'd' in this string.
For example, let N=12, d=1, hence
s = '123456789101112' => k=5
since digit '1' occurs five times in that string.

Problem: Write a method that, given a digit 'd' and number of its occurrences 'k', returns a number of pages N. More precisely, return a lower and upper bound of this number N.
Example:
input: d=4, k=1;
output {4, 13} - the book has 4-14 pages
input d=4 k=0;
output {1, 3} - the book has 1-3 pages

Idea: Brute force. Start from 1, accumulate the number of d's appearance. At the first accumulated appearance==k, update the lower bound; at the last appearance==k, update the upper bound.

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

Code:

 public class PageNumber {  
      public PageNumber()  
      {  
           int[] test1=pageNumber(4,1);  
           printArray(test1);  
           int[] test2=pageNumber(4,0);  
           printArray(test2);  
      }  
      public void printArray(int[] array)  
      {  
           for(int i:array)  
           {  
                System.out.print(i);  
                System.out.print(' ');  
           }  
           System.out.println("\n");  
      }  
      public int[] pageNumber(int d,int k)  
      {  
           int[] result={Integer.MIN_VALUE,Integer.MIN_VALUE};  
           int i=1;  
           char target=(char)(d+'0');  
           int counter=0;  
           while(counter<=k)  
           {  
                String s=Integer.toString(i);  
                for(char c:s.toCharArray())  
                {  
                     if(c==target)  
                          counter+=1;  
                }  
                if(result[0]==Integer.MIN_VALUE&&counter==k)  
                     result[0]=i;  
                if(counter==k)  
                     result[1]=i;  
                i++;  
           }  
           return result;  
      }  
 }  

Number of Countries

Question: 2D matrix with 0s and 1s. Try to find out how many countries in this matrix?
For example:
[[1,1,1,0]
[1,1,0,0]
[0,0,0,1]]
return 3, because one for 1s, one for 0s, and one for the last one.
another example:
[[1,1,1,1]
[0,0,0,0]
[1,0,0,1]]
return 4

Idea: Breadth-first search. For each untagged block, start breadth-first-search and marked the visited block with a specific TAG. When all the board has been marked, return the result.

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

Code: 

 public class CountryNumber {  
      public CountryNumber()  
      {  
           int[][] input1={{1,1,1,0},{1,1,0,0},{0,0,0,1}};  
           int[][] input2={{1,1,1,1},{0,0,0,0},{1,0,0,1}};  
           printMatrix(input2);  
           System.out.println(solution(input2));  
      }  
      public void printMatrix(int[][] matrix)  
      {  
           for(int i=0;i<matrix.length;i++)  
           {  
                for(int j=0;j<matrix[0].length;j++)  
                {  
                     System.out.print(matrix[i][j]);  
                     System.out.print(' ');  
                }  
                System.out.print("\n");  
           }  
      }  
      public class Block{  
           int x;  
           int y;  
           public Block(int x,int y)  
           {  
                this.x=x;  
                this.y=y;  
           }  
      }  
      public int solution(int[][] board)  
      {  
           int TAG=Integer.MIN_VALUE;  
           int counter=0;  
           for(int i=0;i<board.length;i++)  
           {  
                for(int j=0;j<board[0].length;j++)  
                {  
                     if(board[i][j]!=TAG)  
                     {  
                          bfs(board,i,j);  
                          counter+=1;  
                     }  
                }  
           }  
           return counter;  
      }  
      public void bfs(int[][] board,int startX,int startY)  
      {  
           int TAG1=Integer.MIN_VALUE;  
           int TAG2=board[startX][startY];  
           int m=board.length;  
           int n=board[0].length;  
           Queue<Block> queue=new LinkedList<Block>();  
           queue.offer(new Block(startX,startY));  
           while(queue.isEmpty()==false)  
           {  
                int queueSize=queue.size();  
                for(int i=0;i<queue.size();i++)  
                {  
                     Block cur=queue.poll();  
                     board[cur.x][cur.y]=TAG1;  
                     if(cur.x+1<m&&board[cur.x+1][cur.y]==TAG2)  
                          queue.offer(new Block(cur.x+1,cur.y));  
                     if(cur.y+1<n&&board[cur.x][cur.y+1]==TAG2)  
                          queue.offer(new Block(cur.x,cur.y+1));  
                     if(cur.x-1>=0&&board[cur.x-1][cur.y]==TAG2)  
                          queue.offer(new Block(cur.x-1,cur.y));  
                     if(cur.y-1>=0&&board[cur.x][cur.y-1]==TAG2)  
                          queue.offer(new Block(cur.x,cur.y-1));  
                }  
           }  
      }  
 }