[职场感言] 工作一年了,聊聊三件事

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3482|回复: 13
收起左侧

11.23 Bloomberg和Google FULL TIME 电面

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

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

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

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

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)
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. 1point 3acres 论坛

总体上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

question 2, 现在同样给两个string, A和B,但是B特别大,可以想象成一个doc,判断B中是否有sub-list 是A的permutation,要求是consecutive sub list,
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。然后就结束了。。。

面完发现确实自己的方法太麻烦了,只要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
  1. typedef vector<string> StrVec;
  2. typedef unordered_map<string,int> StrFreq;. 一亩-三分-地,独家发布
  3. .留学论坛-一亩-三分地
  4. StrFreq getStrFreq(const StrVec& strs) {. 1point3acres
  5.     StrFreq freq;. From 1point 3acres bbs
  6.     for (const auto& s:strs) freq[s]++;
  7.     return freq;
  8. }

  9. bool findPermutationSublist(const StrVec& a, const StrVec& b) {
  10.     int na = a.size(), nb = b.size();
  11.     if (nb < na) return false;
  12.     StrFreq afreq = getStrFreq(a);
  13.     StrVec bsub(b.begin(), b.begin()+na);
  14.     StrFreq bfreq = getStrFreq(bsub);
  15.     if (afreq == bfreq) return true;
  16.     for (int i = na; i < nb; ++i) {
  17.         bfreq[b[i]]++; bfreq[b[i-na]]--;
  18.         if (bfreq[b[i-na]] == 0) bfreq.erase(b[i-na]);
  19.         if (afreq == bfreq) return true;
  20.     }
  21.     return false;
  22. }
复制代码
回复 支持 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!
回复 支持 反对

使用道具 举报

北岸三叶草 发表于 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
请问这个能举个例子吗? 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了
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

神行客 发表于 2015-12-5 20:32:50 | 显示全部楼层
北岸三叶草 发表于 2015-11-25 10:36
请问这个能举个例子吗? A = {"a", "b", "b"}, B = {"c", "b", "b", "b", "a"}算吗?
. 一亩-三分-地,独家发布
应该算。
. Waral 博客有更多文章,
B的后3位  b b a 是 A 的组合
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-10 02:31:49 | 显示全部楼层
写了下第2题,起始就是strstr + minimum window , 欢迎指教
  1. public class StrStrIII {
  2.         . 留学申请论坛-一亩三分地
  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.         . Waral 博客有更多文章,
  11.         public static boolean findNeedle(String[] needle, String[] haystack) {. more info on 1point3acres
  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)) {. visit 1point3acres for more.
  16.                                 map.put(c, map.get(c) + 1);
  17.                         } else {
  18.                                 map.put(c, 1);
  19.                         }
  20.                 }
  21.                 int m = haystack.length;. 1point 3acres 论坛
  22.                 int n = needle.length;
  23.                 int start = 0;. 1point3acres
  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;
  30.                         }
  31.                         if (found.containsKey(ch)) {
  32.                                 found.put(ch, found.get(ch) + 1);
  33.                         } else {
  34.                                 found.put(ch, 1);.留学论坛-一亩-三分地
  35.                         }
  36.                         if (found.get(ch) > map.get(ch)) {
  37.                                 while (start < i && haystack[start] != ch) {. 留学申请论坛-一亩三分地
  38.                                         found.put(haystack[start],. 1point3acres
  39.                                                         found.get(haystack[start]) - 1);
  40.                                         if (found.get(ch) == 0) {
  41.                                                 found.remove(ch);
  42.                                         }
  43.                                         start++;
  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] ...

是的,应该改成这个样子
回复 支持 反对

使用道具 举报

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. visit 1point3acres for more.
bloomberg竟然允许你用Python面试?? 难道因为你是PhD所以不太在乎你的语言么 我同学们回来反馈的第一条都 ...

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-24 07:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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