Youtube 11/17 Onsite 面经

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

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

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

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

第二轮就是1维曼哈顿距离咯，求出最小值，然后任何大于它的值都能找到对应的位置

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

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

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

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

xiaoniuona 发表于 2015-12-9 05:11
at most two的话，不用hash table，也不用min heap，直接2个指针维护window的start和end就好了，扫描的时 ...

如果是char string就不行吧，得维护一个deque/queue

AnthonyNeu 发表于 2015-12-9 03:08
因为这个地方是at most two distinct,所以我觉得这个heap其实优化的程度并不大

面试官只是对于我用一 ...

为什么不用queue或者deque呢？minheap poll 或者 offer都是O(lgn)啊

写了下CSV Parser, corner case真的很多

1. public class CSVParser {
   
2. 
   
3.         public static List<String> csvParser(String s) {
   
4.                 List<String> result = new ArrayList<>();
   
5.                 if (s == null || s.length() == 0) {
   
6.                         return result;
   
7.                 }
   
8.                 s = s.replaceAll(" ", "");
   
9.                 boolean inQuote = false;
   
10.                 StringBuffer sb = new StringBuffer();
    
11.                 for (int i = 0; i < s.length(); i++) {
    
12.                         if (inQuote) {
    
13.                                 if (s.charAt(i) == '\'') {
    
14.                                         if (i == s.length() - 1) {
    
15.                                                 sb.append(s.charAt(i));
    
16.                                                 result.add(sb.toString());
    
17.                                                 return result;
    
18.                                         } else if (s.charAt(i + 1) == '\'') {
    
19.                                                 sb.append('\'');
    
20.                                                 i++;
    
21.                                         } else {
    
22.                                                 sb.append(s.charAt(i));
    
23.                                                 inQuote = false;
    
24.                                         }
    
25.                                 } else {
    
26.                                         sb.append(s.charAt(i));
    
27.                                 }
    
28.                         } else {
    
29.                                 if (s.charAt(i) == '\'') {
    
30.                                         if (i + 1 < s.length() && s.charAt(i + 1) == '\'') {
    
31.                                                 inQuote = false;
    
32.                                                 i++;
    
33.                                         } else {
    
34.                                                 inQuote = true;
    
35.                                         }
    
36.                                         sb.append('\'');
    
37.                                 } else if (s.charAt(i) == ',') {
    
38.                                         result.add(sb.toString());
    
39.                                         sb.setLength(0);
    
40.                                 } else {
    
41.                                         sb.append(s.charAt(i));
    
42.                                 }
    
43.                         }
    
44.                 }
    
45.        
    
46.                 if (sb.length() > 0) {
    
47.                         result.add(sb.toString());
    
48.                 }
    
49.                
    
50.                 return result;
    
51.         }
    
52.        
    
53.         public static void main(String[] args) {
    
54.                 String str = "a, a'b, c',d ''c,b''d,ba";
    
55.                 List<String> result = csvParser(str);
    
56.                 for (String s : result) {
    
57.                         System.out.println(s);
    
58.                 }
    
59.                 System.out.println();
    
60.                 String str2 = "a, a'b, c, d'c, b";
    
61.                 List<String> res = csvParser(str2);
    
62.                 for (String s : res) {
    
63.                         System.out.println(s);
    
64.                 }
    
65.                
    
66.         }
    
67. }

复制代码

xiaoniuona 发表于 2015-12-14 06:55
我在StackOverflow上找到个DP解法：
http://stackoverflow.com/questions/22424885/find-subset-of-size ...

有点没看懂，可以分享下code吗？