一亩三分地论坛

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

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

Google Kirkland Onsite

[复制链接] |试试Instant~ |关注本帖
kobebyrant 发表于 2016-11-5 12:51:01 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Other在职跳槽

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

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

x
第一轮,Longest Substring with At Most K Distinct Characters变形题,输入是stream而不是string,所以无法知道输入的长度,而且内存不够,无法存入整个stream,所以维持sliding window来更新最大长度的算法无法解决该问题。最后是通过一个map纪录每个字符上次出现的index来实现。提供了函数streamreader.reader()来返回下一个字符。这一轮表现不好,主要是刚听到题目兴奋了一下,好不容易遇到一个做过的,发现并不是那么回事儿,心情有些波动。第二轮,combinations 外加 longest palindrome string from a give string, 比如“atatdc",可以返回”atdta" /"tadat"/"atcta"/"tacat",这个题目需要返回所有可能的结果。
中午吃饭。
第三轮,类似于pacific atlantic water flow,follow up是假如输入不是一个矩阵,或者说小岛的形状是真实的任意形状,如何解决问题,需要自己设计一个类。
第四轮,类似于longest consecutive sequence,输入是collection,有可能是List,也有可能是set,需要自己转换一下。另外一题比较绕,花了十几分钟才搞明白,题目是给一个数组,例如【2,1,3,5,4,6,8】,利用binary search 的思想,但是现在数组不是排好序的,而且pivot是任意的,返回值是总能找到的target的个数。比如我们想找5,pivot不一定是mid=3,有可能是index=4,采用binary search的思想,5>4, 应该搜索右半部分,即6和8,这样是找不到5的。最后的结论是当前的数字大于等于左边所有数字,并且小于等于右边所有数字的情况下,是可以保证找到改值的。上面例子一定可以找到3,6,8,所以返回值是3.. 1point3acres.com/bbs
第五轮,是关于iterator的问题,follow up比较多,但是不是很难。最后还有一些时间,问了一个简单的design的问题,如何处理distribute system里面数据备份保证availability和reliability。

面试可以选择白板或者Chromebook,面完发现全程白板下来,腿还是挺酸的。希望可以有好的结果。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

Soviet 发表于 2016-11-6 02:54:14 | 显示全部楼层
祝楼主好运!如果有offer了记得报一下哈。。感兴趣Google Kirkland,因为离我家就8分钟。。。
回复 支持 反对

使用道具 举报

聚散浮云 发表于 2016-11-6 23:26:32 | 显示全部楼层
请问为什么用stream的话无法维持sliding window?这题内存不是O(charset)的吗?为什么会内存不够呢?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-8 01:57:56 | 显示全部楼层
第一轮,Longest Substring with At Most K Distinct Characters变形题: 假设API streamreader.read()返回'\0' 若stream已读完(具体的要求不影响实现)。因为内存有限制,那么这个题还有一个细节就是所给的k大小能不能认为是有界的,一般若假设是26或256个字符的话那么用一个unordered_map<char, int> lastInx记录当前最后k个distinct char出现的最后index 就可以了。但是这样实际会造成O(Nk)时间复杂度,因为在前进substring front的时候还会涉及判断front index是不是某个char的最后index。我是再定义一个reverse mapping: unordered_map<int, char> chars来记录每个最后index所对应的char. 这样用O(2k)的空间就可以实现O(N)的时间。.1point3acres缃
当然假设内存虽然有限制,但至少是O(k)的 (即使不是O(N)的)。
  1. int maxLength(StreamReader& streamreader, int k) {
  2.   unordered_map<char, int> lastInx; // last index of distinct char, space O(k). From 1point 3acres bbs
  3.   unordered_map<int, char> chars;   // distinct char of last index, space O(k)
  4.   char c = '\0'; // current char
  5.   int front = 0; // first char's index of valid substring
  6.   int cur = -1;  // current char's index of valid substring
  7.   int maxLen = 0; // max length of valid substring
  8.   while ((c = streamreader.read()) != '\0') { // time: O(N)
  9.     // update maps of last index and char
  10.     if (lastInx.count(c)) chars.erase(lastInx[c]);
  11.     lastInx[c] = ++cur; chars[cur] = c;
  12.     // advance front index of substring if invalid
  13.     while (chars.size() > k) {-google 1point3acres
  14.       if (chars.count(front)) { lastInx.erase(chars[front]); chars.erase(front); }
  15.       ++front;
  16.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  17.     // update max length
  18.     maxLen = max(maxLen, cur - front + 1);
  19.   }
  20.   return maxLen;
  21. }
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-8 02:06:36 | 显示全部楼层
聚散浮云 发表于 2016-11-6 23:26
请问为什么用stream的话无法维持sliding window?这题内存不是O(charset)的吗?为什么会内存不够呢?

关键看你的sliding window在advance front index的时候需要记录什么。
在无内存限制的时候,advance front index需要判断删除char s[front_index]后是否减少了某种字符的出现,若是这样实现必然要存储substring从front_index一直到cur_index的字符,这需要O(N)空间,也就是这道题不允许的。所以按照Leetcode原题只记录char frequency是不行的。.1point3acres缃
实际上每次front_index++时并不需要知道s[front_index]本身是什么,只需要知道该字符是否是最后出现的instance。这个改进应该就是这个题的考点吧。
当然,前提是内存虽然没有O(N),但至少有O(k). 注意O(k)可以远远小于O(charset).

补充内容 (2016-11-8 02:12):
这个题其实就是在时间O(N)最优的基础上,让你把空间从O(N)优化到O(k).
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-8 02:12:05 | 显示全部楼层
zzgzzm 发表于 2016-11-8 02:06-google 1point3acres
关键看你的sliding window在advance front index的时候需要记录什么。
在无内存限制的时候,advance fro ...
. more info on 1point3acres.com
这个题其实就是在时间O(N)最优的基础上,让你把空间从O(N)优化到O(k).
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-8 03:05:30 | 显示全部楼层
第二轮: longest palindrome string from a give string: 若假设已经有了从一个char frequency map算所有不同string的算法“vector<string> getDistinctStrings(const unordered_map<char, int>)”,那么是不是就是暴力直接把半个frequency的所有组合再加上一个有可能的中心char的所有组合呢?不确定有没有更快的算法。
  1. vector<string> getAllLongestPalindrome(string& s) {
  2.   unordered_map<char, int> freq, halfFreq;. 鍥磋鎴戜滑@1point 3 acres
  3.   string odds;
  4.   for (char c : s) freq[c]++, halfFreq[c] = freq[c] / 2;
  5.   for (auto& p : freq) {
  6.     if (p.second > 1) halfFreq[p.first] = p.second / 2;
  7.     if (p.second % 2) odds += p.first;-google 1point3acres
  8.   }
  9.   vector<string> half = getDistinctStrings(halfFreq), res;
  10.   for (auto& x : half) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  11.     string rx(x); reverse(rx.begin(), rx.end());
  12.     if (odds.empty()) res.push_back(x + rx);
  13.     else for (char c : odds) res.push_back(x + c + rx);
  14.   }
  15.   return res;
  16. }
复制代码
回复 支持 反对

使用道具 举报

cuiyi 发表于 2016-11-8 07:43:16 | 显示全部楼层
zzgzzm 发表于 2016-11-8 03:05
第二轮: longest palindrome string from a give string: 若假设已经有了从一个char frequency map算所有不 ...
-google 1point3acres
是这样做的,这个是leetcode原题。对于有重复的字符如何产生所有permutation参见Leetcode Permutations II
回复 支持 反对

使用道具 举报

cuiyi 发表于 2016-11-8 07:56:03 | 显示全部楼层
楼主最后一问distributed system是怎么答的?
回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-11-8 12:53:49 | 显示全部楼层
祝愿lz顺利拿到offer!请问第二轮最后一题是不是类似lc267
回复 支持 反对

使用道具 举报

 楼主| kobebyrant 发表于 2016-11-8 13:34:39 | 显示全部楼层
zzgzzm 发表于 2016-11-8 01:57
第一轮,Longest Substring with At Most K Distinct Characters变形题: 假设API streamreader.read()返回' ...

能否测试一下这个test case, stream 是"abcabc***" 无限循环,整个steam的最终长度是1m,内存只有1k。
回复 支持 反对

使用道具 举报

 楼主| kobebyrant 发表于 2016-11-8 13:35:28 | 显示全部楼层
syjohnson 发表于 2016-11-8 12:53
祝愿lz顺利拿到offer!请问第二轮最后一题是不是类似lc267

是的,只需要返回最长的那些palindrome字符串。
回复 支持 反对

使用道具 举报

 楼主| kobebyrant 发表于 2016-11-8 13:41:44 | 显示全部楼层
cuiyi 发表于 2016-11-8 07:56
楼主最后一问distributed system是怎么答的?

看过几片distributed systems的paper,基本上的思路是master-slave的server-mode,replication在不同地域,不同dag保证reliability,同时需要有transaction log来保证recovery failover,同时还比较了一下strict consistency和relaxed consistency的优劣。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-8 14:05:20 | 显示全部楼层
kobebyrant 发表于 2016-11-8 13:34
能否测试一下这个test case, stream 是&quot;abcabc***&quot; 无限循环,整个steam的最终长度是1m,内存只有1k。

这样charset 就是3,那么无论k是多少,所需的空间就是来存两个大小至多是3的map和几个local index. 长度只是通过index 相减得到的。这个和stream 的长度无关。只是和O(min(k,charset size))有关。
回复 支持 反对

使用道具 举报

spwahaha 发表于 2016-11-9 02:48:36 | 显示全部楼层
zzgzzm 发表于 2016-11-8 14:05
这样charset 就是3,那么无论k是多少,所需的空间就是来存两个大小至多是3的map和几个local index. 长度 ...

这样和双指针+统计出现character的频率应该是一样的吧, 用双指针+词频应该也是O(K)的空间复杂度吧,因为我们只统计在双指针间出现哪些character
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-9 03:09:17 | 显示全部楼层
spwahaha 发表于 2016-11-9 02:48
这样和双指针+统计出现character的频率应该是一样的吧, 用双指针+词频应该也是O(K)的空间复杂度吧,因为 ...

词频map本身的空间是O(k)没错,但沒有记录任何和index有关的信息,所以依赖于原始string s的随机access s[j]. 这是内存限制不允许的。
回复 支持 反对

使用道具 举报

spwahaha 发表于 2016-11-9 03:22:19 | 显示全部楼层
zzgzzm 发表于 2016-11-9 03:09
词频map本身的空间是O(k)没错,但沒有记录任何和index有关的信息,所以依赖于原始string s的随机access s ...

有道理,所以要用map记录那些character对应的index哈,如果left对应字母的index是这个字母出现的最后一个index, 那么就能remove 掉了,不行的话说明left 到 right之间还有这个字母, 有道理。 是这个意思吧?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-9 04:17:25 | 显示全部楼层
spwahaha 发表于 2016-11-9 03:22 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
有道理,所以要用map记录那些character对应的index哈,如果left对应字母的index是这个字母出现的最后一个 ...

没错,用map记录字母出现的最后的index
回复 支持 反对

使用道具 举报

spwahaha 发表于 2016-11-9 09:11:09 | 显示全部楼层
zzgzzm 发表于 2016-11-9 04:17
没错,用map记录字母出现的最后的index

谢谢~~
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-9 12:09:27 | 显示全部楼层
祝楼主拿到offer, 麻烦问一下楼主第三轮第二题是什么意思? 给一个数组然后求什么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 11:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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