新鲜狗狗店面

Job Hunting Interview
, , , , , ,
1

非常简单的面试，但是我个人学艺不精，希望不会挂
背靠背两轮，第一轮的面试官自我介绍完之后没来得及说题，就跟我讲地震了，要reschedule，随后挂断了电话。

一小时后第二轮正常进行。面试开始后我跟面试官寒暄，问地震有没有影响，结果面试官说他办公室不在地震区，而且明显感觉不方便讲自己的位置。第二轮的面试官整体给我感觉就是心不在焉，我在整个编程过程中没有给我回应，只在我每次编完又验证完程序之后说了句OK，而且由于最后结束时间超过45分钟，就没有给我提问的机会。

一共考了两道题

第一题 是给定一个文档，文档的每一行包含一字符串，有些行的字符串可能完全相同，也就是说有些行是重复的，把文档逐行复制到一个新文档中，要求重复的行只保留一行。我的做法是把字符串储存到dictionary中，复制新的一行之前要检查是否出现过在我答完第二题后大哥又回头问了第一题的follow up: 考虑有限内存，并且可能出现的字符串个数要大于内存，应该如何处理？ 我的做法是每次内存满的时候记录当前位置，分批去除重复的行

follow up: 如果不考虑保持原文档中字符串的顺序，应该如何优化？这题没有回答上，我觉得应该是需要先排序，然后线性时间去除重复的行。但是，我不知道有限内存如何对文档存储的内容进行排序，跟过分的是我完全没有把我的想法跟面试官讲！我就是想了一下觉得可能不对，而忽略了与面试官的交流！

第二题 ，帕斯卡三角形，求给定位置的值直接用了dynamic programming

2

报个我的

You’re given a matrix, and all the elements in it is either 0 or 1.
What is considered as a submatrix is a matrix whose elements are all 0s.
For example, for given matrix
[ 0 0 1
0 0 0
1 0 1]
only one
|0| itself,

| 0 0 |,

| 0 |
| 0 |,

and

| 0 0 |
| 0 0 |

are both submatrixes, however something like
| 0 1 |
| 0 0 |
isn’t a legal one.
How to find the total number of submatrixes?

1 Like
3

这个题应该是hard难度了．思路就是先用一个矩阵算每一个cell(i,j) 右边的连续为０的长度，然后根据列进行计算以cell(i,j)开头的submatrix的个数，用stack来表示深度（思路类似leetcode 1063，不过此处包含了一个pair和一个ｃ来表示深度).

解法如下：

public int numOfSubMatrix(int[][] matrix){
    int n = matrix.length;
    int m = matrix[0].length;
    //create p_matrix
    int[][] p_matrix = new int[n][m];
    for(int i=0;i<n;i++){
        for(int j=m-1;j>=0;j--){
            if(matrix[i][j]==1) {
                p_matrix[i][j] = 0;
            }else if(matrix[i][j]==0){
                if(j==m-1) {
                    p_matrix[i][j] = 1;
                }
                else {
                    p_matrix[i][j]  = p_matrix[i][j+1]+1;
                }
            }
        }
    }

   int ret =0;
    for(int j=0;j<m;j++){
        int i = n-1;
        Stack<int[]> stack = new Stack<int[]>();
        int to_sum =0;
        while(i>=0){
            int c =0;
            while(!stack.isEmpty() && stack.peek()[0]> p_matrix[i][j]){
                to_sum -=(stack.peek()[1]+1)*(stack.peek()[0]-p_matrix[i][j]);
                c+= stack.peek()[1]+1;
                stack.pop();
            }
            to_sum +=p_matrix[i][j];
            ret += to_sum;
            stack.push(new int[]{p_matrix[i][j], c});
            i--;
        }
    }
    return ret;