今日头条算法实习生面试

Posted on | In | |

I took an interview with TouTiao.com today. This article records the process and content of the interview.

今天参加了今日头条的算法实习生面试，本文记录了面试的内容。

今天做了一个今日头条的算法实习生面试，是在牛客网上视频面试的。

上来就自我介绍了一下我的经历，讲了讲学校做的项目和实体链接SRTP项目。

然后就是限时编程测试，题目是：删除给定字符串中的合法括号对，void remove_bracket(string &str)，时间 O(n) 空间O(1)，e.g.:ab(c()( —> ab(c(

由于本人愚钝，一时没有想到 O(1) 空间的做法，感觉可能空间做不到 O(1)，因为不知道括号匹配合不合法，所以得把读到的左括号位置存储一下。

用栈的操作来解决这题很容易，遇到左括号压栈，遇到右括号判断栈是否为空，如果非空，说明之前读到了左括号，此时则将这一对括号从字符串中删除；如果空，那么说明之前字符串中没有出现与之对应的左括号，当前的右括号匹配失败。这种做法是 O(n)时间 O(n)空间的。

[C++ Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <stack>
#include <string>
using namespace std;

void remove_bracket(string &str) {
    int length = str.length();
    stack<int> left;
    
    if (length == 0)    return;
    
    for (int i=0; i<length; i++) {
        if (str[i] == '(') {
            left.push(i);
        }
        else {
            if (str[i] == ')') {
                if (!left.empty()) {
                    str.erase(i, 1);
                    i--;
                    int left_pos = left.top();
                    left.pop();
                    str.erase(left_pos, 1);
                    i--;
                    length-=2;
                }
            }
        }
    }
}

int main() {
    string str = "ab(c()(";
    remove_bracket(str);
    cout<<str<<endl;
    return 0;
}

后来问了下面试官，说确实有 O(1)空间的做法。

暂时还没想到。

资磁一下？