一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1569|回复: 13
收起左侧

11.23 Bloomberg和Google FULL TIME 电面

[复制链接] |试试Instant~ |关注本帖
xxqqxiao 发表于 2015-11-24 04:46:05 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Google - 内推 - 技术电面 |Other其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
今天上午和下午分别电面的bloomberg和google。Full time。
Bloomberg:
欧美小哥,电面问了两部分,第一部分关于coding language的,第二部分算法。因为用python,第一部分全部是python的。
第一部分:
1) list, tuple, dict的区别
A: tuple是immutable的,如果作为dict的key的时候,只能用tuple, 不能用list。list和dict查找complexity分别是O(n)和O(1). more info on 1point3acres.com
2) string concatenation for a list of strings, 除了用“+”,有没有更快的python写法
A: "".join(A)
3) python的exception的处理
第二部分:
1) 2 sum
2) reverse a sentence, word和space的个数保持原来的,e.g. “hello   world”--》“world   hello”, 我说了用python split的function,遇到empty string “”则恢复成space。follow up,实现split function
. Waral 鍗氬鏈夋洿澶氭枃绔,
总体上bloomberg的题目答的还行,有些写的时候有点bug,听上去小哥基本满意。

Google:
欧美人
warm up:给两个list of string, A, B,判断A和B中的string是否是彼此的permutation。e.g., A=["a", "b"], B=["b", "a"], A是B中words的permutation
A: 先给了sort,然后比较的办法。说完反应过来,直接用hash table记录频率,然后比较两个hash table是否相同即可。
interviewer听了solution,问了time complexity,然后让写code. more info on 1point3acres.com

question 2, 现在同样给两个string, A和B,但是B特别大,可以想象成一个doc,判断B中是否有sub-list 是A的permutation,要求是consecutive sub list,-google 1point3acres
e.g. A= ["a", "b"], B=["c", "b", "a"], return yes
["a", "b"], B=["c", "b", "d", "a"], return no
A:同样用hash table,construct A的frequency hash table T, deepcopy T-->D, 从B的头开始scan, 同时maintain一个window,每当遇到string不在hash table的key时候,重新deepcopy T重置D, 遇到的在D中的string的时候,decrement D[key], 如果D是empty则return True
大致的思路是这样的,写完interviewer指出这个不能handle 有A和B中duplicate的一些case,脑袋瞬间打结,interviewer花费了好多口舌并举了个例子我才明白过来。。。。。顿时更紧张了。最后明白了,需要maintain window的起始位置,有duplicate的时候得记录该string第一次出现的index,然后回去处理window起始位置到这个位置的string。大致写了一下。不过各种messy,脑袋已经想不清楚了。最后interviewer说其实不用这么麻烦,说了一下代码里一些不必要的condition check。然后就结束了。。。. from: 1point3acres.com/bbs

面完发现确实自己的方法太麻烦了,只要maintain一个window,并记录size,window一超过A的size的时候,就drop第一个,当该string频率降为0时去掉这个key, 然后每移动一步都比较这个window对应的hashtable是否和A一样就行。

anyway, 最后写的代码很乱,没有complete,被指出问题后就变得紧张,没法仔细思考了。希望interviewer放我一马,还能onsite。

评分

2

查看全部评分

zzgzzm 发表于 2016-10-24 06:42:25 | 显示全部楼层
Google Question 2: 按照LZ最终的意思,用frequency hash table比较就可以了。注意在B的sub-list向前前进时更新新增string和删除string的频率。
时间O((Nb-Na)*Na), 空间O(Na)  (assuming Na < Nb). Note that operator "unordered_map<string,int>::==" has O(N) time complexity -google 1point3acres
  1. typedef vector<string> StrVec;
  2. typedef unordered_map<string,int> StrFreq;

  3. StrFreq getStrFreq(const StrVec& strs) {
  4.     StrFreq freq;. 鍥磋鎴戜滑@1point 3 acres
  5.     for (const auto& s:strs) freq[s]++;
  6.     return freq;
  7. }

  8. bool findPermutationSublist(const StrVec& a, const StrVec& b) {
  9.     int na = a.size(), nb = b.size();
  10.     if (nb < na) return false;
  11.     StrFreq afreq = getStrFreq(a);
  12.     StrVec bsub(b.begin(), b.begin()+na);
  13.     StrFreq bfreq = getStrFreq(bsub);
  14.     if (afreq == bfreq) return true;
  15.     for (int i = na; i < nb; ++i) {
  16.         bfreq[b[i]]++; bfreq[b[i-na]]--;
  17.         if (bfreq[b[i-na]] == 0) bfreq.erase(b[i-na]);
  18.         if (afreq == bfreq) return true;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  19.     }
  20.     return false;
  21. }
复制代码
回复 支持 1 反对 0

使用道具 举报

tomato347 发表于 2015-11-24 08:17:46 | 显示全部楼层
可以不用hashtable, 用character array的特性来做int count[] = new int[256]. 比如count['a']++
回复 支持 反对

使用道具 举报

 楼主| xxqqxiao 发表于 2015-11-24 09:44:30 | 显示全部楼层
tomato347 发表于 2015-11-24 08:17. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
可以不用hashtable, 用character array的特性来做int count[] = new int[256]. 比如count['a']++

原题的意思array里面的element是任意string, 这里用character只是作为例子比较简单。
回复 支持 反对

使用道具 举报

brucezu 发表于 2015-11-25 02:12:22 | 显示全部楼层
大体思路没问题,9成会onsite的  good luck!. 鍥磋鎴戜滑@1point 3 acres
回复 支持 反对

使用道具 举报

北岸三叶草 发表于 2015-11-25 10:36:03 | 显示全部楼层
请问
写完interviewer指出这个不能handle 有A和B中duplicate的一些case
这个能举个例子吗? A = {"a", "b", "b"}, B = {"c", "b", "b", "b", "a"}算吗?
回复 支持 反对

使用道具 举报

 楼主| xxqqxiao 发表于 2015-12-5 02:27:19 | 显示全部楼层
北岸三叶草 发表于 2015-11-25 10:36. 鍥磋鎴戜滑@1point 3 acres
请问这个能举个例子吗? A = {"a", "b", "b"}, B = {"c", "b", "b", "b", "a"}算吗?

这道题类似leetcode 76, Minimum Window Substring, 区别就是这道题要求是连续的substring,window中间出现A中没有的元素就不算,因此也就可以简化很多,因为window的size是fix的,就是A的长度。不过A中还是可以有很多重复的element。希望这样解释清楚些。
回复 支持 反对

使用道具 举报

 楼主| xxqqxiao 发表于 2015-12-5 02:30:52 | 显示全部楼层
Update:google来消息已挂,具体为啥也不太清楚,因为不给feedback。看来没写出perfect的answer还是不行。另外,给我分配的这个interviewer其实不大懂python,写的代码居然问我list的index function的是干什么的。。。anyway, move on了
回复 支持 反对

使用道具 举报

神行客 发表于 2015-12-5 20:32:50 | 显示全部楼层
北岸三叶草 发表于 2015-11-25 10:36
请问这个能举个例子吗? A = {"a", "b", "b"}, B = {"c", "b", "b", "b", "a"}算吗?

应该算。

B的后3位  b b a 是 A 的组合
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-10 02:31:49 | 显示全部楼层
写了下第2题,起始就是strstr + minimum window , 欢迎指教.鏈枃鍘熷垱鑷1point3acres璁哄潧
  1. public class StrStrIII {
  2.         . from: 1point3acres.com/bbs
  3.         public static void main(String[] args) {
  4.                 String[] needle = {"a", "b"};
  5.                 String[] haystack = {"c", "b", "a"};
  6.                 System.out.println(findNeedle(needle, haystack));
  7.                 String[] haystack1 = {"c", "b", "d", "a"};
  8.                 System.out.println(findNeedle(needle, haystack1));
  9.         }
  10.        
  11.         public static boolean findNeedle(String[] needle, String[] haystack) {
  12.                 HashMap<String, Integer> map = new HashMap<String, Integer>();
  13.                 HashMap<String, Integer> found = new HashMap<String, Integer>();
  14.                 for (String c : needle) {
  15.                         if (map.containsKey(c)) {. From 1point 3acres bbs
  16.                                 map.put(c, map.get(c) + 1);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  17.                         } else {
  18.                                 map.put(c, 1);
  19.                         }
  20.                 }
  21.                 int m = haystack.length;
  22.                 int n = needle.length;
  23.                 int start = 0;
  24.                 for (int i = 0; i < m; i++) {
  25.                         String ch = haystack[i];
  26.                         if (!map.containsKey(ch)) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  27.                                 start = i + 1;
  28.                                 found.clear();
  29.                                 continue;-google 1point3acres
  30.                         }
  31.                         if (found.containsKey(ch)) {
  32.                                 found.put(ch, found.get(ch) + 1);
  33.                         } else {
  34.                                 found.put(ch, 1);. 1point 3acres 璁哄潧
  35.                         }. 1point3acres.com/bbs
  36.                         if (found.get(ch) > map.get(ch)) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  37.                                 while (start < i && haystack[start] != ch) {
  38.                                         found.put(haystack[start],
  39.                                                         found.get(haystack[start]) - 1);
  40.                                         if (found.get(ch) == 0) {
  41.                                                 found.remove(ch);
  42.                                         }
  43.                                         start++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  44.                                 }
  45.                                 start++;
  46.                         }
  47.                         if (i - start + 1 == n) {
  48.                                 return true;
  49.                         }
  50.                 }

  51.                 return false;
  52.         }
  53. }
复制代码
回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2015-12-31 06:33:22 | 显示全部楼层
bobzhang2004 发表于 2015-12-10 02:31
写了下第2题,起始就是strstr + minimum window , 欢迎指教

这个40行是不是应该改成
if (found.get(haystack[start]) == 0)  {
    found.remove(haystack[start]);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
}
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-28 08:44:04 | 显示全部楼层
javaprogrammer 发表于 2015-12-31 06:33
这个40行是不是应该改成
if (found.get(haystack[start]) == 0)  {
    found.remove(haystack[start] ...
. 1point 3acres 璁哄潧
是的,应该改成这个样子
回复 支持 反对

使用道具 举报

haveto 发表于 2016-10-24 02:32:29 | 显示全部楼层
bloomberg竟然允许你用Python面试?? 难道因为你是PhD所以不太在乎你的语言么 我同学们回来反馈的第一条都是bb喜欢C++ Java也可以 Python面试除非对Python特别熟悉否则都跪了 因为BB热爱C++
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-24 06:07:12 | 显示全部楼层
haveto 发表于 2016-10-24 02:32
bloomberg竟然允许你用Python面试?? 难道因为你是PhD所以不太在乎你的语言么 我同学们回来反馈的第一条都 ...

BB的确是很热爱C++, 尤其对C++的inheritance, polymorphism以及memory management.. 鍥磋鎴戜滑@1point 3 acres
我不会用Python,但我知道Python有很多自带的函数,所以写出的程序往往比其它语言的短,但难免有"cheating"的嫌疑,所以听说有的interviewer不让用呢。C++是比较实打实的performance language, 对基本功要求比较高。但感觉现在好像Java更popular, 很多Algorithm & Data Structure的书都是用Java为例的。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 03:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表