Labels

Wednesday, March 25, 2015

Regular Expression Matching (Advanced)

def Match(string, pattern):
        '*' star matches zero or more preceding characters
       '.' each dot matches exactly one character
       '^' prefix match, meaning that input string must start with exactly the same string following '^', e.g., '^abc' will match 'abcdefg', but 'cdefg' doesn't.
        '$' suffix match, meaning that input string must end with exactly the same string following '$', e.g., '$abc' will match 'cdefgabc', but 'abcdefg' doesn't
        without any special character: return True if pattern is in string (contains, not exactly same), and False otherwise
    # Your code here


Naive Way: This question is really hard in that it requires to match exactly part of the string. And it doesn't need to start from beginning of the string. I am assuming that ^ and $ will always appear as the first character of pattern and either of them will appear or nor of them appear.

My brute force way to match from every possible position. Use a recursive matching.

 public class Solution{  
   
      public static void main(String args[]){  
           Solution s = new Solution();  
           System.out.println(s.match("aabab",".*bab"));  
      }  
   
      public boolean match(String string, String pattern){  
           // edge case  
           if(pattern==null || pattern.length()==0) return string==null || string.length()==0;  
           if(string==null || string.length()==0) return pattern==null || pattern.length()==0;  
   
           // get suffix and prefix  
           boolean isPrefixed = false, isSuffixed = false;  
           if(pattern.charAt(0)=='^') isPrefixed = true;  
           if(pattern.charAt(0)=='$') isSuffixed = true;  
   
           // main process  
           char[] s = string.toCharArray();  
           char[] p = pattern.toCharArray();  
           if(isPrefixed) return match(s, 0, p, 1, -1);  
           else if(isSuffixed){  
                for(int i = 1;i < s.length;i++)  
                     if(match(s,i,p,1,1)) return true;  
           }else{  
                for(int i = 0;i < s.length;i++){  
                     if(i==0 && match(s,i,p,0,-1)) return true;  
                     else if(i!=0 && match(s,i,p,0,0)) return true;  
                }  
           }  
           return false;  
      }  
   
      private boolean match(char[] string, int index1, char[] pattern, int index2, int matchEnd){  
           // ending case  
           if(index2 == pattern.length){  
                if(matchEnd==1) return index1==string.length;  
                else if(matchEnd==-1) return index1 < string.length;  
                else return true;  
           }  
           if(index1 < 0 || index1 >= string.length || index2 >= pattern.length) return false;  
             
   
           int i = index1, j = index2;  
           if(string[i] == pattern[j] || pattern[j] == '.') return match(string, i+1, pattern, j+1, matchEnd);  
           else if(j+1 < pattern.length && pattern[j+1] == '*') return match(string, i, pattern, j+2, matchEnd);  
           else if(pattern[j] == '*'){  
                int u = i-2;  
                while(u < string.length && (u==i-2 || string[u] == pattern[j-1] || pattern[j-1] == '.'))  
                     if(match(string, u++, pattern, j+1, matchEnd)) return true;  
           }  
           return false;  
      }  
 }  

Tuesday, March 24, 2015

Conway's Game of Life

From wiki
The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:
  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overcrowding.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.

The class interface is as follows.

class GameOfLife:
def __init__(self, board_width):
""" Your code here """

def set_alive(self, row, column):
""" Your code here """

def set_dead(self, row, column):
        """ Your code here """.


def step(self):
  """ Your code here """.
# more stuffs if you want to add.

Naive Thinking: Follow the rule to accomplish these functions. To update the board, I need a temporary board to store next state information.
 
 public class GameOfLife{  
      private int board[][];  
      GameOfLife(){init(10,10);}  
      GameOfLife(int row, int column){init(row, column);}  
      public void init(int L, int W){  
           assert L > 0;  
           assert W > 0;  
           board = new int[L][W];  
      }  
      public void set_alive(int row, int column){  
           if(!isInitialized()) return;  
           if(row > board.length && column > board[0].length) return;  
           board[row][column] = 1;  
      }  
      public void set_dead(int row, int column){  
           if(!isInitialized()) return;  
           if(row > board.length && column > board[0].length) return;  
           board[row][column] = 0;  
      }  
      public void step(){  
           if(!isInitialized()) return;  
           int temp[][] = new int[board.length][board[0].length];  
           // make a temporary board to store next state  
           for(int i = 0; i < board.length;i++)  
                for(int j = 0;j < board[0].length;j++)  
                     if(board[i][j]==1){  
                          if(getAliveNeighbor(i,j) < 2 || getAliveNeighbor(i,j) > 3)  
                               temp[i][j] = 0;  
                          else  
                               temp[i][j] = 1;  
                     }else if(getAliveNeighbor(i,j) == 3)  
                          temp[i][j] = 1;  
           // copy the temp board to main board  
           for(int i = 0;i < board.length;i++)  
                for(int j = 0;j < board[0].length;j++)  
                     board[i][j] = temp[i][j];  
      }  
      private int getAliveNeighbor(int x, int y){  
           int sum = 0;  
           for(int i = -1;i <= 1;i++)  
                for(int j = -1;j <= 1;j++)  
                     if(x+i >= 0 && x+i < board.length && y+j >= 0 && y+j < board[0].length && !(i==0 && j==0))  
                          sum += board[x+i][y+j]==1?1:0;  
           return sum;  
      }  
      private boolean isInitialized(){return !(board == null || board.length == 0);}  
      public void print(){  
           if(!isInitialized()) return;  
           for(int i = 0;i < board.length;i++){  
                for(int j = 0;j < board[0].length;j++)  
                     System.out.print(board[i][j]+" ");  
                System.out.println();  
           }  
           System.out.println();  
      }  
 }  

To test the game:

 public class Test{  
      public static void main(String args[]){  
           GameOfLife g = new GameOfLife();  
           for(int i = 0;i < 10;i++)  
                for(int j = 0;j < 10;j++)  
                     if(j%2==0 && i%2==0 || i%3==0) g.set_alive(i,j);  
           int loop = 5;  
           for(int i = 0;i < loop;i++){  
                g.print();  
                g.step();  
           }  
      }  
 }  

Output:

 1 1 1 1 1 1 1 1 1 1   
 0 0 0 0 0 0 0 0 0 0   
 1 0 1 0 1 0 1 0 1 0   
 1 1 1 1 1 1 1 1 1 1   
 1 0 1 0 1 0 1 0 1 0   
 0 0 0 0 0 0 0 0 0 0   
 1 1 1 1 1 1 1 1 1 1   
 0 0 0 0 0 0 0 0 0 0   
 1 0 1 0 1 0 1 0 1 0   
 1 1 1 1 1 1 1 1 1 1   
   
 0 1 1 1 1 1 1 1 1 0   
 1 0 0 0 0 0 0 0 0 1   
 1 0 1 0 1 0 1 0 1 1   
 1 0 0 0 0 0 0 0 0 1   
 1 0 1 0 1 0 1 0 1 1   
 1 0 0 0 0 0 0 0 0 1   
 0 1 1 1 1 1 1 1 1 0   
 1 0 0 0 0 0 0 0 0 1   
 1 0 1 0 1 0 1 0 1 1   
 1 0 1 0 1 0 1 0 1 1   
   
 0 1 1 1 1 1 1 1 1 0   
 1 0 0 0 0 0 0 0 0 1   
 1 0 0 0 0 0 0 0 1 1   
 1 0 0 0 0 0 0 0 0 0   
 1 0 0 0 0 0 0 0 1 1   
 1 0 0 0 0 0 0 0 0 1   
 1 1 1 1 1 1 1 1 1 1   
 1 0 0 0 0 0 0 0 0 1   
 1 0 0 0 0 0 0 0 0 0   
 0 0 0 0 0 0 0 0 1 1   
   
 0 1 1 1 1 1 1 1 1 0   
 1 0 1 1 1 1 1 0 0 1   
 1 1 0 0 0 0 0 0 1 1   
 1 1 0 0 0 0 0 0 0 0   
 1 1 0 0 0 0 0 0 1 1   
 1 0 1 1 1 1 1 0 0 0   
 1 0 1 1 1 1 1 1 0 1   
 1 0 1 1 1 1 1 1 0 1   
 0 0 0 0 0 0 0 0 1 1   
 0 0 0 0 0 0 0 0 0 0   
   
 0 1 0 0 0 0 0 1 1 0   
 1 0 0 0 0 0 0 0 0 1   
 0 0 0 1 1 1 0 0 1 1   
 0 0 1 0 0 0 0 0 0 0   
 0 0 0 1 1 1 0 0 0 0   
 1 0 0 0 0 0 0 0 0 1   
 1 0 0 0 0 0 0 0 0 0   
 0 0 1 0 0 0 0 0 0 1   
 0 0 0 1 1 1 1 1 1 1   
 0 0 0 0 0 0 0 0 0 0   

Minesweeper

Use a 2D board to represent the board. Given length (L) and width (W) and the number of mines (M). Randomly put mines into the L-by-W cells and mark the cell by number of surrounding mines. Must be absolutely random and no collision.
Naive Way: What does collision mean? I never met collision when I was playing minesweeper. I assume collision means no two mines are in the same position.
 
 public class Solution{  
      public static void main(String args[]){  
           Solution s = new Solution();  
           int b[][];  
           b = s.generateBoard(10, 10, 20);  
           printArray(b);  
      }  
      /**  
      * 9 means there is a mine in that particular cell  
      */  
      public int[][] generateBoard(int L, int W, int M){  
           // edge case  
           if( M > L*W) return null;  
           int[][] board = new int[L][W];  
           int row, col;  
           // generate mines in random position  
           for(int i = 0;i < M;i++){  
                // generate row index  
                do{  
                     row = (int)Math.floor(Math.random()*L);  
                     col = (int)Math.floor(Math.random()*W);  
                }while(board[row][col] == 9);  
                board[row][col] = 9;  
           }  
           // scan the board, put numbers on safe cells  
           for(int i = 0;i < L;i++){  
                for(int j = 0;j < W;j++){  
                     if(board[i][j]!=9){  
                          int sum = 0;  
                          // surronding area  
                          for(int x = -1; x <= 1; x++)  
                               for(int y = -1;y <= 1;y++)  
                                    if(i+x >= 0 && i+x < L && j+y >= 0 && j+y < W)  
                                         sum += board[i+x][j+y]==9?1:0;  
                          board[i][j] = sum;  
                     }  
                }  
           }  
           return board;  
      }  
      public static void printArray(int[][] b){  
           if(b == null || b.length==0) return;  
           for(int i = 0;i < b.length;i++){  
                for(int j = 0;j < b[0].length;j++)  
                     System.out.print(b[i][j] + " ");  
                System.out.println();  
           }  
      }  
 }  

Saturday, March 21, 2015

Shuffle to Wavy Array

Given an unordered array A[]={1,2,3,7,1,2,5}, shuffle the array matching the condition A[0]<=A[1]>=A[2]<=A[3]...A possible result would be A[]={1,7,3,5,2,2,1}

Naive Thinking:Sorting the array helps to know the put integers in order. And put the second half one by one in between of the first half. This would take O(nlogn) run time. And Sorting definitely has redundancy. It doesn't need to be all in order.

Then I came to greedy. As greedy should do it in O(n). I try to match the condition as far as I traversal. If condition fails, pick up another one afterwards. This approach is not guaranteed to be O(n) and may fail at certain point.

Then I came up with swapping, as I swapping at each position will only cost O(n) run time. I try to keep the condition as far as I traversal. If no satisfied, like A[i] < A[i+1], where the condition is A[i] >= A[i+1], swap A[i] with A[i+1]. This approach works on several examples I randomly pick up. Then I found this approach is theoretically correct.

Proof by induction:
(1) when there is only 1 number, it satisfies.
(2) when there are two numbers, at most one swap with fulfill.
(3) 1.suppose A[i-1] <= A[i],
      if A[i] >= A[i+1]
          satisfies
      else A[i] < A[i+1]
          since A[i-1] <= A[i], A[i] < A[i+1], A[i+1] is the peek of three
          swap A[i] and A[i+1]
      2. suppose A[i-1] >= A[i],
      if A[i] <= A[i+1]
          satisfies
      else A[i] > A[i+1]
          since A[i-1] >= A[i], A[i] > A[i+1], A[i+1] is the valley of three
          swap A[i] and A[i+1].
Proved.

 public class Solution{  
      public static void main(String args[]){  
           Solution s = new Solution();  
           int A[] = {1,2,2,7,3,1,5};  
           s.suffle(A);  
           for(int i = 0;i < A.length;i++)  
                System.out.println(A[i]);  
      }  
      public void suffle(int[] A){  
           for(int i = 0;i < A.length-1;i++){  
                if(i%2==0)  
                     if(A[i] > A[i+1]) swap(A, i, i+1);  
                else  
                     if(A[i] < A[i+1]) swap(A, i, i+1);  
           }  
           return;  
      }  
      private void swap(int A[], int a, int b){  
           int temp = A[a];  
           A[a] = A[b];  
           A[b] = temp;  
      }  
 }  

Friday, March 6, 2015

Common String in Lists

Given a List of List of String, find the common String in all Lists, output them in sorted order. (could contain duplicates)

Naive Way:Need to consider case [[a,a,a],[a,a],[a,a,b]] outputs [a,a]. Use a HashMap as pattern, go through the lists, for each list, match it with the pattern, update the pattern, what left in the pattern is common string.

 public List<String> commonString(List<List<String>> lists){  
           List<String> rslt = new ArrayList<String>();  
           // edge case  
           if(lists.size()==0) return rslt;  
           // initialize pattern   
           Map<String, Integer> pattern = new HashMap<String, Integer>();  
           List<String> temp = lists.get(0);  
           setMap(pattern, temp);  
           // match pattern with other lists  
           for(int i = 1;i < lists.size();i++){  
                Map<String, Integer> map = new HashMap<String, Integer>();  
                setMap(map, lists.get(i));  
                Iterator it = pattern.entrySet().iterator();  
                List<String> toBeRemove = new ArrayList<String>();  
                while(it.hasNext()){  
                     Map.Entry pair = (Map.Entry)it.next();  
                     if(map.containsKey(pair.getKey()))  
                          pattern.put((String)pair.getKey(), Math.min(map.get(pair.getKey()),(int)pair.getValue()));  
                     else  
                          toBeRemove.add((String)pair.getKey());  
                }  
                for(int j = 0;j < toBeRemove.size();j++)  
                     pattern.remove(toBeRemove.get(j));  
           }  
           // collect results  
           Iterator it = pattern.entrySet().iterator();  
           while(it.hasNext()){  
                Map.Entry pair = (Map.Entry)it.next();  
                for(int i = 0;i < (int)pair.getValue();i++)  
                     rslt.add((String)pair.getKey());  
           }  
           // sort the result  
           Collections.sort(rslt);  
           return rslt;  
      }  
      private void setMap(Map<String, Integer> map, List<String> list){  
           for(int i = 0;i < list.size();i++){  
                if(!map.containsKey(list.get(i)))  
                     map.put(list.get(i), 1);  
                else  
                     map.put(list.get(i), map.get(list.get(i))+1);  
           }  
      }  

Iterator over HashMap

How to use iterator to go through a HashMap?

 public static void printMap(Map mp) {  
   Iterator it = mp.entrySet().iterator();  
   while (it.hasNext()) {  
     Map.Entry pair = (Map.Entry)it.next();  
     System.out.println(pair.getKey() + " = " + pair.getValue());  
     it.remove(); // avoids a ConcurrentModificationException  
   }  
 }  

Friday, February 27, 2015

Find the row with Max 1s

From http://www.careercup.com/question?id=5700588635422720

 A 2-D array of 1's and 0's is given. Find the row with max 1's. The array is sorted row wise (all 0's in a row are followed by all 1's).





Naive Thinking: A first I just came up with all kinds of O(nm) solutions. For example scan column by column to find the first 1, or scan row by row and note down the earliest 1. Pretty bad, though, because O(n+m) solution did exists and there exists solution better than that.

An O(m+n) algorithm is kinda greedy. Keep two pointers, one for row(i), one for column(j). Start from the very end of first row, each time encounter a 1, step forward(j--), each time encounter a 0, it means current row will have no chance have more 1 than m-j, thus go to next row, starting from j. That saves us the time from repeatedly scanning rows that are denied.




 public class Solution{   
   public static void main(String args[]){   
    Solution s = new Solution();   
    int[][] matrix = {{0,0,0,1,1},   
        {0,0,1,1,1},   
        {0,0,0,0,1},   
        {0,0,0,1,1}};   
    System.out.println(s.findRowWithMaxOnes(matrix));   
   }   
   public int findRowWithMaxOnes(int[][] array){   
    int n = array.length;   
    int m = n==0?0:array[0].length;   
    int i = 0, j = m-1;   
    int row = 0;   
    while(i < n && j >= 0){   
     if(array[i][j]==1){   
      row = i;   
      j--;   
     }else{   
      i++;   
     }   
    }   
    return row;   
   }   
  }    


Improved Way: As you see, since the question gives the condition each row is sorted. That leads to binary search thinking. We can do a binary search to find the first 1 of current row instead of stepping forward once. That brings the run time to O(m+log n)


 public int findRowWithMaxOnes(int[][] array){  
           int n = array.length;  
           int m = n==0?0:array[0].length;  
           int i = 0, j = m-1;  
           int row = 0;  
           while(i < n && j >= 0){  
                j = binarySearch(array[i], 0, j);  
                row = i;  
                i++;  
                while(i < n && array[i][j]==0) i++;  
           }  
           return row;  
      }  
      private int binarySearch(int[] arr, int begin, int end){  
           while(begin < end){  
                int middle = (begin+end)/2;  
                if(arr[middle] == 0 && arr[middle+1] == 1) return middle+1;  
                if(arr[middle] == 0) begin = middle+1;  
                else end = middle;  
           }  
           return begin;  
      }