发一下之前FB onsite

每一轮都很简单

第一轮: 三哥，输入一个array，元素都不是负数 和一个 int: target   输出是否存在有没有subarray sum = target, follow up 有负数怎么办
第二轮: 亚裔小哥，常见题， 给一个string，删掉不正确的括号，  

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

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

Houboy/57.gif" smilieid="190" border="0" alt="" />   不过冷冻期不是一年， 叫我过3-6个月联系他们

第一题

1. public class Solution {
   
2.   public boolean subarraySum(int[] arr, int target) {
   
3.     int last = 0;
   
4.     int sum = 0;
   
5.     for (int i = 0; i < arr.length; i++) {
   
6.       sum += arr[i];
   
7.       while (sum > target) {
   
8.         sum -= arr[last++];
   
9.       }
   
10.       if (sum == target) {
    
11.         return true;
    
12.       }
    
13.     }
    
14.     return false;
    
15.   }
    
16. 
    
17.   public boolean subarraySumNegtive(int[] arr, int target) {
    
18.     for (int i = 1; i < arr.length; i++) {
    
19.       arr[i] += arr[i - 1];
    
20.     }
    
21.     Set<Integer> s = new HashSet<>();
    
22.     for (int i = 0; i < arr.length; i++) {
    
23.       if (s.contains(arr[i] - target)) {
    
24.         return true;
    
25.       }
    
26.       s.add(arr[i]);
    
27.     }
    
28.     return false;
    
29.   }
    
30. 
    
31.   public static void main(String[] args) {
    
32.     Solution ss = new Solution();
    
33.     System.out.println(ss.subarraySum(new int[] {1, 2, 3, 4, 5, 6}, 14));
    
34.     System.out.println(ss.subarraySum(new int[] {1, 2, 3, 4, 5, 6}, 10));
    
35.     System.out.println(ss.subarraySum(new int[] {1, 2, 3, 4, 5, 6}, 18));
    
36.     System.out.println(ss.subarraySum(new int[] {1, 2, 3, 4, 5, 6}, 17));
    
37.     System.out.println(ss.subarraySumNegtive(new int[] {1, -2, 3, -4, 5, -6}, 4));
    
38.     System.out.println(ss.subarraySumNegtive(new int[] {1, -2, 3, -4, 5, -6}, -5));
    
39.     System.out.println(ss.subarraySumNegtive(new int[] {1, -2, 3, -4, 5, -6}, 0));
    
40.     return;
    
41.   }
    
42. }
    

复制代码

锦木千束 发表于 2016-3-31 13:35
不啊，修改原来的string， 不用额外的空间嘛

懂了，写了下代码

1. public class RemoveInvalidParenthesesII {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 System.out.println(removeInvalidParenthesesII("()()(()"));
   
5.                 System.out.println(removeInvalidParenthesesII("()())(()"));
   
6.                 System.out.println(removeInvalidParenthesesII("())"));
   
7.         }
   
8.         public static String removeInvalidParenthesesII(String str) {
   
9.                 if (str == null || str.length() == 0) {
   
10.                         return "";
    
11.                 }
    
12.                 StringBuilder sb = new StringBuilder();
    
13.                 int left = 0;
    
14.                 int right = 0;
    
15.                 for (int i = 0; i < str.length(); i++) {
    
16.                         char c = str.charAt(i);
    
17.                         if (c == '(') {
    
18.                                 sb.append(c);
    
19.                                 left++;
    
20.                         } else if (c == ')') {
    
21.                                 if (left > 0) {
    
22.                                         left--;
    
23.                                         sb.append(c);
    
24.                                 }
    
25.                         }
    
26.                 }
    
27.                 str = sb.toString();
    
28.                 sb = new StringBuilder();
    
29.                 left = 0;
    
30.                 right = 0;
    
31.                 for (int i = str.length() - 1; i >= 0; i--) {
    
32.                         char c = str.charAt(i);
    
33.                         if (c == ')') {
    
34.                                 right++;
    
35.                                 sb.insert(0, c);
    
36.                         } else if (c == '(') {
    
37.                                 if (right > 0) {
    
38.                                         right--;
    
39.                                         sb.insert(0, c);
    
40.                                 }
    
41.                         }
    
42.                 }
    
43.                
    
44.                 return sb.toString();
    
45.         }
    
46. }
    

复制代码

有问问feedback么，全做出来都没给过？

mingzhou1987 发表于 2016-3-30 15:00
有问问feedback么，全做出来都没给过？

问了 不说。。 只叫我保持联系， 和给他update找工作的情况。。。。

你是本科还是研究生啊

请问楼主第二轮是用的 "Remove Invalid Parentheses"的backtracking的方法写的吗？

mdzzxswl 发表于 2016-3-30 15:13
你是本科还是研究生啊

master   

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

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

请问下楼主，不是说fb不招研究生的new grad了吗今年？ 难道现在又开放了？

yueliu2366 发表于 2016-3-31 00:28
请问下楼主，不是说fb不招研究生的new grad了吗今年？ 难道现在又开放了？

肯定在招的， 只是不多而已

我觉得我面得还没有楼主好HR要了reference check，说今天就可以告诉我要不要move forward，因为我三月底有一个offer deadline。

感觉拒信已经在路上了……