10/3Facebook电面

2个小时前面完的facebook fulltime电面
刚才找了半天，第一题lc应该没有原题，remove parentheses:
给

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

g>补充内容 (2016-10-4 18:48):
已拿到onsite

tanpf5 发表于 2016-10-4 08:34
原来这样，结果我第一题做了半个小时。。还好第二题我倒背如流。。

第1题， two pass.
用两个变量， int left, int right.
从头扫第1遍的时候， 加进去所有left,如果right不大于left, 就加进去stringbuilder。这样保证“)”都有相对应的"("。
第2遍，从第1次的stringbuilder的末尾扫，加进去所有 )， 如果left 不大于 right, 加进去所有 (。
第2遍pass的时候，解决了第1pass, “（”比 “）“多的情况。

    public String removeInvalidParantheses(String s) {
           
        String firstPass = "";
        int left = 0, right = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                left++;
                firstPass+='(';
            } else if (c == ')' && right<left) {
                right++;
                firstPass+=')';
            } else if (c != ')' && c != '(') {
                firstPass+=c;
            }
        }

        left = 0;
        right = 0;
        StringBuilder sb = new StringBuilder();
        for(int i = firstPass.length()-1;i>=0;i--)
        {
                char c = firstPass.charAt(i);
            if (c == ')') {
                right++;
                sb.append(')');
            } else if (c == '(' && left < right) {
                left++;
                sb.append('(');
            } else if (c != ')' && c != '(') {
                sb.append(c);
            }
        }

        return sb.reverse().toString();
    }

iPhD 发表于 2016-10-4 10:21
问下楼主两题是不是都问了时间空间复杂度？据说这是FB的一贯风格。。。

不是面试官问不问，

写code之前，一定要先说复杂度，
否则你哗啦啦写个O(n^2)的， 结果人家要O(n)的。。。

恭喜拿onsite.
第1题是面经高频原题。

xiaozhuxiaozhu 发表于 2016-10-4 08:33
恭喜拿onsite.
第1题是面经高频原题。

原来这样，结果我第一题做了半个小时。。还好第二题我倒背如流。。

第一题貌似是leetcode题目吧?

k-closest points to origin ?

xiaozhuxiaozhu 发表于 2016-10-4 08:39
第1题， two pass.
用两个变量， int left, int right.
从头扫第1遍的时候， 加进去所有left,如果right ...

这个方法不错，具体在空间复杂度上比我的方法好

第一题是tag 里面的那个的简单版

求楼主把第二题的代码发下好吗？大谢！