Doordash 上门过经

Doordash onsite, 一共5轮

  1. connect 4 game, 要求implement winning condition 判断的function, follow up 是加 robot player

  2. 纯聊之前工作中的项目,问得很细,主要是考经验

  3. BQ,纯BQ面,专门有一道问题问你对diversity的看法。。。

  4. 拓扑排序,package dependency 问题, 给定一个package x,需要以怎样的顺序安装 x 需要的dependency libs,需要注意的是,这个问题需要先正向 dfs/bfs 找到dependecy graph 中的 connected component,再reverse graph 用 topological sort 找顺序,这里要注意有环的情况要单独判断

  5. system design, Design 一个公司内部用的网页,用来做charity donation

面完第二天告诉有offer,但是自己实在是不想去sf,并且seattle这边有更高的offer,就拒掉了

我实现了connect 4 game,请大家看看对不对?public class Connect

{

    private int [][] board;
    private int col;
    private int row;
    public Connect(int row,int col) {
        board = new int[row][col];
        this.col = col;
        this.row = row;
    }

    public void move(int player, int r,int c) {
        board[r][c] = player;
    }

    public int checkWin(int player,int r,int c) {

        //checkout vertically;
        int count = 1;
        for(int i=r+1;i<row;i++) {
            if(board[i][c]!=player) break;
            if(++count==4) return player;
        }
        //check horizontally
        count = 1;
        //check right side
        for(int i= c+1;i<col;i++) {
            if(board[r][i]!=player) break;
            if(++count==4) return player;
        }
        //check left side
        for(int i= c-1;i>=0;i--) {
            if(board[r][i]!=player) break;
            if(++count==4) return player;
        }

        count=1;
        int i = r-1;
        int j = c-1;
        while(i>=0 && j>=0) {
            if(board[i][j]!=player) break;
            i--;
            j--;
            if(++count==4) return player;
        }
        i = r+1;
        j = c+1;
        while(i<row && j<col) {
            if(board[i][j]!=player) break;
            i++;
            j++;
            if(++count==4) return player;
        }
        count=1;
        i = r-1;
        j = c+1;
        while(i>=0 && j<col) {
            if(board[i][j]!=player) break;
            i--;
            j++;
            if(++count==4) return player;
        }
        i = r+1;
        j = c-1;
        while(i<row && j>=0) {
            if(board[i][j]!=player) break;
            i++;
            j--;
            if(++count==4) return player;
        }

        return 0;
    }


}

思路没啥问题,写的有点繁琐,用python,可以简化到10行以内

楼主 请问robot player这个你怎么实现呢

其实就是根据当前棋盘去找一个valid position,然后可以用多个robot class实现一个统一的接口去实现多种不同strategy的robot

请问4为什么要找到connected component啊?topological sorting够了吧?

topological sort 输出的packages顺序里,有可能有target package不需要的dependency,需要把这些不在target package里面的package去掉

请问可以用java去做吗?给的class源码可以选择语言种类嘛

Any language should be fine.

cool

请问楼主是海投的还是找的内推呀