FB一面面经

一面。。口音很重的国人小哥。

两道题

1. monotonic array。。低频easy。。一开始上来懵了。。没刷过但是现做出来。。有点小Bug。。1，2，2，2

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

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

收到的二面通知。。上周五面得还没消息。。。已经move on 了。。大家加油。积分就不设限了。

2 pass + o(1) space是可行的，但1 pass + o(1) space应该是没法实现的。
正序pass可以过滤掉非法的')',但没法过滤掉非法的'('。因为判定某个'('是否非法，需要用到后面的信息。
同理，逆序pass也只能过滤掉非法的'('。
应该可以严格数学证明，有兴趣的同学可以试试

可以用两个flag left和right，当left遇到左括号加一右括号减一，right相反 小于0时为invalid变成点
好像和刷题网二三吧有点像

1. public static String removeInvalidParentheses(String input) {
   
2.         char[] inputChars = input.toCharArray();
   
3.         int len = inputChars.length;
   
4.         int left = 0;
   
5.         int right = 0;
   
6.         for (int i = 0; i < len; i ++) {
   
7.             if (Character.isLetter(inputChars[i])) {
   
8.                 continue;
   
9.             }
   
10.             if (inputChars[i] == '(') {
    
11.                 left ++;
    
12.             }
    
13.             else if (inputChars[i] == ')') {
    
14.                 left --;
    
15.             }
    
16.             if (left < 0) {
    
17.                 inputChars[i] = '.';
    
18.                 left = 0;
    
19.             }
    
20.             if (inputChars[len - i - 1] == ')') {
    
21.                 right ++;
    
22.             }
    
23.             else if (inputChars[len - i - 1] == '(') {
    
24.                 right --;
    
25.             }
    
26.             if (right < 0) {
    
27.                 inputChars[len - i - 1] = '.';
    
28.                 right = 0;
    
29.             }
    
30.         }
    
31.         return new String(inputChars);
    
32.     }

复制代码

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

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

等等呗 感觉还是有戏的

谢谢楼主分享。写了两题，还好啊。可能面馆没有交review.。等等看。加点米给你。 第一题是最近的高频。"要inplace的将不合法的括号改为一个点"是什么意思啊？

edyyy 发表于 2018-11-7 02:07
谢谢楼主分享。写了两题，还好啊。可能面馆没有交review.。等等看。加点米给你。 第一题是最近的高频。"要i ...

就是比如输入是 )(ab  你要变成..ab。。inplace的改

加米，谢谢lz分享

想了想是不是two pointers可以做。left = 0, right = len-1, 遇到不是括号的往下一个移就好了，如果是括号，必须每次保证left =(, right = ),如果哪个不是，哪个就变成点，然后移动那个不对的指针,直到left > right,left = right的情况也有可能是要变点的。

真的能one pass + constant space么？求大神指点

啊lch 发表于 2018-11-7 04:03
想了想是不是two pointers可以做。left = 0, right = len-1, 遇到不是括号的往下一个移就好了，如果是括号 ...

这个不能保证移除最少啊。。()()()这个例子

用两个变量一个记录左括号 一个记录右括号？扫的过程中可以根据匹配情况改，不过扫一遍后发现左括号或者右括号多还得重新扫一遍改非法括号

zjt610526 发表于 2018-11-7 05:51
这个不能保证移除最少啊。。()()()这个例子

如果给的input一定是invalid的话，这么做是不是是可以的