一个月刷完cc150

从6.1开始，这个六月
这个夏天！……

楼主加油！⛽️

I finished CC189 in last winter break. But when I received some interviews and prepare for it I find the question tags in the CC189 couldn't handle all the topic in the real interview, and the most of the questions in the book is easy or medium. Just a kindly suggestion. Summer break has 3 months, so you can spend one month on it and other two months on the leetcode, otherwise you may struggle in the real code base interview.

16.4
Problem:
Design an algorithm to figure out if someone has won a game of tic-tac-toe.

Analysis:
This problem could be 4 scenarios: 1)we use this method multiple times: we can store all possible boards and winner as int value using base-3 and boolean key-value set in hash table to look up. 2)we use this method one time: we can either check all 8 lines of winning scenario which is not scalable, or 3) look up all rows/columns/diagonals. 4)we use this method on N*N board: we can expand 3*3 board second method with iterator or directions passed to check.

Code:
enum Piece {Empty,Red,Blue};
1)multiple times:
public int boardToInt(Piece[][] board){
    int res=0;
    for(int row=0;row<board.length;row++){
        for(int col=0;col<board[0].length;col++){
            int p=board[row][col]==Piece.Empty?0:(board[row][col]==Piece.Red?1:2);
            res=res*3+p;
        }
    }
    return res;
}

2)one time with last move:
public Piece isWinner(Piece[][] board,int row,int col){
    Piece p=board[row][col];
    if(p==Piece.Empty){return Piece.Empty;}
    //if column/row is wining
    if(colWin(col,board)||rowWin(row,board)){return p;}

    //if diagonal is winning
    if(col==row&&diaWin(p,board,1)){return p;}
    if(col==board[0].length-1&&diaWin(p,board,-1)){return p;}

    return Piece.Empty;
}

public boolean diaWin(Piece p,Piece[][] board,int direction){
    int row=0,col=direction==1?0:board[0].length-1;
    while(row<board.length){
        if(board[row][col]!=board[p.row][p.col]){return false;}
        col+=direction;         
        row++;     
    }
    return true;
}

public boolean colWin(int col,Piece[][] board){
    for(int row=1;row<board.length;row++){
        if(board[row][col]!=board[0][col]){return false;}
    }
    return true;
}

public boolean rowWin(int row,Piece[][] board){
    for(int col=1;col<board[0].length;col++){
        if(board[row][col]!=board[row][0]){return false;}
    }
    return true;
}

3)one time without last move look up all rows/columns/diagonals
4)for N*N board
public Piece isWinner(Piece[][] board){
    int len=board.length;
    List<Direction> directions=new ArrayList<>();

    setUpDirections(len,directions);
    for(Direction direction:directions){
        Piece winner=check(board,direction);
        if(winner!=Piece.Empty){return winner;}
    }
}

public Piece check(Piece[][] board,Direction direction){
    Piece p=board[0][0];
    for(int row=direction.row,col=direction.col;row<board.length&&col<board[0].length&&row>=0&&col>=0;row+=direction.rowInc,col+=direction.colInc){
        if(board[row][col]!=p){return Piece.Empty;}
    }
    return p;
}

public void setUpDirections(int len,List<Direction> directions){
    //set up checker for rows and columns
    for(int i=0;i<len;i++){
        directions.add(new Direction(i,0,0,1));
        directions.add(new Direction(0,i,1,0));
    }
    //set up checker for diagonals
    directions.add(new Direction(0,0,1,1));
    directions.add(new Direction(0,len-1,1,-1));
}

public class Direction{
    int row,col,rowInc,colInc;

    public Direction(int row,int col,int rowInc,int colInc){
        this.row=row;
        this.col=col;
        this.rowInc=rowInc;
        this.colInc=colInc;
    }
}
   

cc150是啥

iona 发表于 2019/06/03 08:20:59
cc150是啥

Cracking the code interview 150 questions

这个夏天，加油！

WarriorZ 发表于 2019-6-4 01:46
I finished CC189 in last winter break. But when I received some interviews and prepare for it I fin ...

How hard is real code base interview?

WarriorZ 发表于 2019-6-4 01:46
I finished CC189 in last winter break. But when I received some interviews and prepare for it I fin ...

How hard is real code base interview?

googlewaterloo 发表于 2019-6-4 05:47
How hard is real code base interview?

Based on the company you are looking for. You can practice the code through the company tag and each time when you are accepted a solution, ask yourself can you explain your idea to the interviewer clearly and write your code without bugs in 20 minutes. Some of the hardest problems I read from other people's mianjin are Word ladder2, the skyline problem, regular expression. By the way, the problem in the interview may have some slightly different.

cc150 1.1 Is Unique
Problem:
Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Analysis:
If the string is an ascii string, we can use a fixed size(256) array to represent unique characters. Then iterate through the string.

Code:
public boolean isUnique(String s) {
  if (s.length()>256){
    return false;
  }
  boolean[] set = new boolean[256];
  for(int i = 0; i < s.length(); i++){
    char c = s.charAt(i);
    if(set[c]) return false;
    set[c]=true;
  }
  return true;
}

Follow up: fewer space if string only uses lower letters a-z
Analysis:
We can manipulate bit to use an integer to store as a set, because max int max length in base 2 is 32 (Max int is 2^32-1). Each bit suggests a character in a-z.

Code:
public boolean isUnique(String s){
  if (s.length()>26) return false;
  int bits = 0;
  for (int i = 0; i < s.length(); i++){
    int c = s.charAt(i) - 'a’;
    //The Character at c in bits is 1
    if (bits & (1<<c) != 0) return false;
    bits = bits | (1<<c);
  }
  return true;
}

1.2 Check Permutation
Problem:
Given two strings, write a method to decide if one is a permutation of the other.

Analysis:
If whitespaces are significant, we can use length to filter some non-permutations. When the strings are the same length, if not permutations, the count of specific character must be larger than the other. We can use character array as set for a-z.

Code:
public boolean isPermutation(String s1, String s2) {
  if (s1.length() != s2.length()) return false;
  int[] set = new int[256];
  for (char c : s1.toCharArray()) {
    set[c]++;
  }
  for (char c : s2.toCharArray()) {
    if (--set[c] < 0) return false;
  }
  return true;
}