Facebook intern phone interview一面

1.two sum2.Longest Valid Parentheses  
但是输出string


follow up:
因为我用的是StringBuilder输出的结果，然后他说  那你这样要copy原来的string 能不能不用出来extra space
我说直接在string上删除其实是产生新的string，也是要extra space
面试官说python和c++可以浓缩啊  那我们假设java也可以吧= =   我说str

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

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

16-2-28 05:02):
第二题不是原题  说错了
()()))()  -> ()()()
)(( ->
(())(() -> (())()

补充内容 (2016-2-29 09:57):
一面过了 准备onsite

frank11118 发表于 2016-3-1 03:46
請問有空間複雜度為 O(1) 的版本嗎？ 謝謝 :-)

对于java来说是不可能的 因为要重新创建一个string作为结果

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

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

第二题，空间1，时间n

1. public class Solution {
   
2.   public int valid(char[] arr, int len) {
   
3.     int count = 0;
   
4.     for (int i = 0; i < len; i++) {
   
5.       if (arr[i] == '(') {
   
6.         count++;
   
7.       } else if (arr[i] == ')') {
   
8.         count--;
   
9.         if (count < 0) {
   
10.           arr[i] = '#';
    
11.           count = 0;
    
12.         }
    
13.       }
    
14.     }
    
15.     count = 0;
    
16.     for (int i = len - 1; i >= 0; i--) {
    
17.       if (arr[i] == ')') {
    
18.         count++;
    
19.       } else if (arr[i] == '(') {
    
20.         count--;
    
21.         if (count < 0) {
    
22.           arr[i] = '#';
    
23.           count = 0;
    
24.         }
    
25.       }
    
26.     }
    
27.     int writer = 0;
    
28.     for (int i = 0; i < len; i++) {
    
29.       if (arr[i] != '#') {
    
30.         arr[writer++] = arr[i];
    
31.       }
    
32.     }
    
33.     return writer;
    
34.   }
    
35. 
    
36.   public static void main(String[] args) {
    
37.     Solution s = new Solution();
    
38.     char[] arr = "()()))()".toCharArray();
    
39.     int len = s.valid(arr, arr.length);
    
40.     for (int i = 0; i < len; i++) {
    
41.       System.out.print(arr[i]);
    
42.     }
    
43.     System.out.println();
    
44. 
    
45.     arr = ")((".toCharArray();
    
46.     len = s.valid(arr, arr.length);
    
47.     for (int i = 0; i < len; i++) {
    
48.       System.out.print(arr[i]);
    
49.     }
    
50.     System.out.println();
    
51. 
    
52.     arr = "(())(()".toCharArray();
    
53.     len = s.valid(arr, arr.length);
    
54.     for (int i = 0; i < len; i++) {
    
55.       System.out.print(arr[i]);
    
56.     }
    
57.     System.out.println();
    
58.   }
    
59. }
    

复制代码

同求人品。。。

求人品！

lz第二题是什么思路？

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

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

你填写完问卷以后，多久收到的面试通知

xiaozhuxiaozhu 发表于 2016-2-27 07:54
你填写完问卷以后，多久收到的面试通知

on campus转为电面的  没有填问卷

马上要面facebook 看面经都是考hard... 感觉很虚

设两个指针 i,j，指向当前最长valid括号的开头和结尾

当有一个新的更长的括号匹配出现时，更新一下i和j

最后输出 str.substring(i,j+1)即可


整个过程需要一个O(n)的for loop, DP

补充内容 (2016-2-27 08:25):
时间复杂度O(n),空间O(1)吧

aangel 发表于 2016-2-27 08:22
设两个指针 i,j，指向当前最长valid括号的开头和结尾

当有一个新的更长的括号匹配出现时，更新一下i和j
...

不对吧..
如果是())()()()
删掉的是中间的‘)’