传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 6476|回复: 24
收起左侧

Google电面面经

[复制链接] |试试Instant~ |关注本帖
peter668 发表于 2014-5-15 00:30:10 | 显示全部楼层 |阅读模式

2014(4-6月) 码农类 博士 全职@Google - 内推 - 技术电面 |Other

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

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

x
周一google电面,现在还在等消息,发发面经,攒攒RP,也希望得到大家的Bless。。。

第一题,水题,数组加一操作,for example, 输入[2, 7, 8, 9] 数组,加一后变成 [2, 7, 9, 0]

第二题,给定输入这样的字符串
fft, fcp, aac, act, acd, atp, tbk, tdf, …
这些都是按照字母排序好的,但是字母顺序改了,比如 f 在 a之前,t在d之前等等,给定一些这样的rule,问怎么rebuild the alphabet?

评分

1

查看全部评分

本帖被以下淘专辑推荐:

discoveryi 发表于 2014-5-19 11:49:38 | 显示全部楼层
sj1456 发表于 2014-5-19 11:33. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
求面试准备清单。。。
. 1point 3acres 璁哄潧
***************************************************************
GOOGLE PHONE TECHNICAL INTERVIEW TIPS:.鏈枃鍘熷垱鑷1point3acres璁哄潧

Please be prepared for the engineers to ask you questions in the following areas:
- Google products (i.e. what you use). 1point 3acres 璁哄潧
- Coding ability (you will code in a Google Doc).1point3acres缃
- Algorithm Design/Analysis
- System Design

The links below may help you prepare for your interview:      

Interviewing at Google - http://www.youtube.com/watch?v=w887NIa_V9w
Google Products - http://www.google.com/intl/en/options/
Five Essential Phone Screen Questions by Steve Yegge (Google Engineer) - https://sites.google.com/site/st ... ne-screen-questions
Types of algorithm questions Google asks: TopCoder Tutorials - http://www.topcoder.com/tc?modul ... ls&d2=alg_index
The Official Google Blog: “Baby steps to a new job” by Gretta Cook (Google Engineer). 鍥磋鎴戜滑@1point 3 acres
http://googleblog.blogspot.com/2008/01/baby-steps-to-new-job.html
“How to Get Hired” by Dan Kegel (Google Engineer)
http://www.kegel.com/academy/getting-hired.html.1point3acres缃


BOOKS:.1point3acres缃
(#2 was highly recommended by several engineers and quite representative of the types of coding questions asked)

1. Review of Basic Algorithms: Introduction to the Design and Analysis of Algorithms by Anany Levitin
2. Types of coding questions Google asks: Programming Interviews Exposed; Secrets to Landing Your Next Job (Programmer to Programmer) by John Mongan, Noah Suojanen, and Eric Giguere

TIPS DIRECTLY FROM OUR ENGINEERS:
One of our engineers drafted this overview of the main areas software engineers should prepare to have a successful interviews with Google:
. Waral 鍗氬鏈夋洿澶氭枃绔,
1.) Algorithm Complexity: You need to know Big-O. If you struggle with basic big-O complexity analysis, then you are almost guaranteed not to get hired. For more information on Algorithms you can visit:       http://www.topcoder.com/tc?modul ... ls&d2=alg_index

2.) Coding: You should know at least one programming language really well, and it should preferably be C++ or Java. C# is OK too, since it's pretty similar to Java. You will be expected to write some code in at least some of your interviews. You will be expected to know a fair amount of detail about your favorite programming language.
*Strongly recommended* for information on Coding: Programming Interviews Exposed; Secrets to landing your next job by John Monagan and Noah Suojanen (Wiley Computer Publishing)
http://www.wiley.com/WileyCDA/Wi ... tCd-047012167X.html

3.) System Design: http://research.google.com/pubs/ ... allelComputing.html
Google File System http://research.google.com/archive/gfs.html
Google Bigtable http://research.google.com/archive/bigtable.html
Google MapReduce http://research.google.com/archive/mapreduce.html

4.) Sorting: Know how to sort. Don't do bubble-sort. You should know the details of at least one n*log(n) sorting algorithm, preferably two (say, quicksort and merge sort). Merge sort can be highly useful in situations where quicksort is impractical, so take a look at it.
. 1point 3acres 璁哄潧
5.) Hashtables: Arguably the single most important data structure known to mankind. You absolutely should know how they work. Be able to implement one using only arrays in your favorite language, in about the space of one interview.
. From 1point 3acres bbs
6.) Trees: Know about trees; basic tree construction, traversal and manipulation algorithms. Familiarize yourself with binary trees, n-ary trees, and trie-trees. Be familiar with at least one type of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree, and know how it's implemented. Understand tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder.. 1point3acres.com/bbs
.鐣欏璁哄潧-涓浜-涓夊垎鍦
7.) Graphs: Graphs are really important at Google. There are 3 basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list); familiarize yourself with each representation and its pros & cons. You should know the basic graph traversal algorithms: breadth-first search and depth-first search. Know their computational complexity, their tradeoffs, and how to implement them in real code. If you get a chance, try to study up on fancier algorithms, such as Dijkstra and A*.

8.) Other data structures: You should study up on as many other data structures and algorithms as possible. You should especially know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise. Find out what NP-complete means.
. 1point 3acres 璁哄潧
9.) Mathematics: Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other companies because we are surrounded by counting problems, probability problems, and other Discrete Math 101 situations. Spend some time before the interview refreshing your memory on (or teaching yourself) the essentials of combinatorics and probability. You should be familiar with n-choose-k problems and their ilk – the more the better.

10.) Operating Systems: Know about processes, threads and concurrency issues. Know about locks and mutexes and semaphores and monitors and how they work. Know about deadlock and livelock and how to avoid them. Know what resources a processes needs, and a thread needs, and how context switching works, and how it's initiated by the operating system and underlying hardware. Know a little about scheduling. The world is rapidly moving towards multi-core, so know the fundamentals of "modern" concurrency constructs.. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 鍥磋鎴戜滑@1point 3 acres
For information on System Design:
http://research.google.com/pubs/ ... allelComputing.html.鏈枃鍘熷垱鑷1point3acres璁哄潧

11.) Also, you can review some of our research publications: http://research.google.com/pubs/papers.html
回复 支持 3 反对 0

使用道具 举报

 楼主| peter668 发表于 2014-5-15 00:42:59 | 显示全部楼层
其实第二题本质是拓扑排序

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

discoveryi 发表于 2014-5-15 01:39:47 | 显示全部楼层
谢谢楼主面经。。
G家发的面试准备清单里貌似没有提到“拓扑”。。。俺去复习复习。。
回复 支持 反对

使用道具 举报

sj1456 发表于 2014-5-19 11:33:21 | 显示全部楼层
discoveryi 发表于 2014-5-15 01:39
谢谢楼主面经。。. 1point 3acres 璁哄潧
G家发的面试准备清单里貌似没有提到“拓扑”。。。俺去复习复习。。

求面试准备清单。。。
回复 支持 反对

使用道具 举报

robinho364 发表于 2014-5-19 12:09:39 | 显示全部楼层
第二题,我的理解是这样的:

fft和aac比较,按照f<a的规则,f在a前面。

既然是这样,那和拓扑排序有什么关系呢?
. 1point3acres.com/bbs
自定义std::sort规则,直接暴力排序,复杂度为O(nlog(n)*m),其中m为字符串长度,n为字符串个数。

这样不能解决问题吗?
回复 支持 反对

使用道具 举报

robinho364 发表于 2014-5-19 12:12:15 | 显示全部楼层
discoveryi 发表于 2014-5-15 01:39
谢谢楼主面经。。. more info on 1point3acres.com
G家发的面试准备清单里貌似没有提到“拓扑”。。。俺去复习复习。。

拓扑排序可以用depth-first,也可以用breadth-first
回复 支持 反对

使用道具 举报

readman 发表于 2014-5-19 12:45:09 | 显示全部楼层
robinho364 发表于 2014-5-19 12:12
拓扑排序可以用depth-first,也可以用breadth-first

- = 你没看懂题.鏈枃鍘熷垱鑷1point3acres璁哄潧
让建alphabet. 就是说建一个字母的顺序.
例子不是给了么. 比如 f -> a, 的意思是f在a前边.
题目就是让从input中, 找出更多这样的顺序.
非常明显的拓扑排序, 非常直接.

不过写不写的出来 bug free 的tsort...这个...我反正写不出来
回复 支持 反对

使用道具 举报

robinho364 发表于 2014-5-19 13:10:10 | 显示全部楼层
readman 发表于 2014-5-19 12:45
. visit 1point3acres.com for more.- = 你没看懂题
让建alphabet. 就是说建一个字母的顺序.
例子不是给了么. 比如 f -> a, 的意思是f在a ...

就是说意思是从给定的字符串中重建字母表?. From 1point 3acres bbs

我原先看到:“给定一些这样的rule”,以为这些rule是给你的,让我们重排字符串。

抱歉。

那这个思路就是这样了:

/*首先建图*/
prev_str = arr[0];
for i = 1 to num of strings
  cur_str = arr[1];
  compare cur_str with prev_str, add an edge to the graph;
  prev_str = cur_str;
end

/*拓扑排序*/
topologicalsort();
.鏈枃鍘熷垱鑷1point3acres璁哄潧
bug_free的topologicalsort其实不难,多练练就成了。

求指教。

  
回复 支持 反对

使用道具 举报

readman 发表于 2014-5-19 13:14:59 | 显示全部楼层
robinho364 发表于 2014-5-19 13:10
就是说意思是从给定的字符串中重建字母表?

我原先看到:“给定一些这样的rule”,以为这些rule是给你 ...

大概是这意思把..
添加的node是字母, 不是string, 添加前还要先找到位置 避免在字典中重复出现字母.. 鍥磋鎴戜滑@1point 3 acres
估计复杂度也不低, 我怎么觉得起码也有n2logn....
回复 支持 反对

使用道具 举报

robinho364 发表于 2014-5-19 13:29:15 | 显示全部楼层
readman 发表于 2014-5-19 13:14
大概是这意思把..
添加的node是字母, 不是string, 添加前还要先找到位置 避免在字典中重复出现字母.
估 ...

是,添加的是字母。

我的意思是,添加字母的时候本质上是比较string,比如ffd和fdd,需要比较的是第二位的f和d。

复杂度确实不低,你说的是对的。. 1point 3acres 璁哄潧

谢谢!

回复 支持 反对

使用道具 举报

robinho364 发表于 2014-5-19 14:04:49 | 显示全部楼层
readman 发表于 2014-5-19 13:14
大概是这意思把..
添加的node是字母, 不是string, 添加前还要先找到位置 避免在字典中重复出现字母.
估 ...

Hi,根据lz的例子,简单地写了一下,监测结果是:
b. from: 1point3acres.com/bbs
f
a.鐣欏璁哄潧-涓浜-涓夊垎鍦
c.1point3acres缃
t
d
  1. #define _USE_MATH_DEFINES

  2. #ifdef ONLINE_JUDGE
  3. #define FINPUT(file) 0
  4. #define FOUTPUT(file) 0. From 1point 3acres bbs
  5. #else
  6. #define FINPUT(file) freopen(file,"r",stdin)
  7. #define FOUTPUT(file) freopen(file,"w",stdout)
  8. #endif

  9. #include <iostream>. 1point3acres.com/bbs
  10. #include <cstdio>.1point3acres缃
  11. #include <cstring>
    . 1point 3acres 璁哄潧
  12. #include <cstdlib>. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13. #include <cmath> 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  14. #include <ctime>. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  15. #include <set>. more info on 1point3acres.com
  16. #include <stack>. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  17. #include <string>. 鍥磋鎴戜滑@1point 3 acres
  18. #include <map>
  19. #include <vector>-google 1point3acres
  20. #include <queue>
  21. #include <algorithm>
  22. #include <functional>

  23. typedef long long ll;
  24. static const int M = 300;
  25. static const int N = 10;
  26. static const int LEN = 1000010;
  27. static const int MAX = 0x7fffffff;
  28. static const int MIN = ~MAX;
  29. static const double EPS = 1e-7;
  30. char arr[N][M];
  31. int indegree[N];
  32. std::vector< std::map<int, int> > alphabet(27);. 1point 3acres 璁哄潧
  33. . Waral 鍗氬鏈夋洿澶氭枃绔,
  34. void topologic_sort(int n). Waral 鍗氬鏈夋洿澶氭枃绔,
  35. {
  36.         std::queue<int> cur;
  37.         std::vector<int> out;

  38.         for (int i = 1; i<n; i++){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  39.                 if (indegree[i] == 0 && alphabet[i].size() != 0){
  40.                         cur.push(i);
  41.                         out.push_back(i);
  42.                 }
  43.         }

  44.         int ncount = 0;
  45.         while (cur.empty() == false){
  46.                 int tmp = cur.front();
  47.                 cur.pop();
  48.                 ncount++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  49.                 std::map<int, int>::iterator it = alphabet[tmp].begin();
  50.                 for (it = alphabet[tmp].begin(); it != alphabet[tmp].end(); it++) {
  51.                         if (--indegree[it->second] == 0){
  52.                                 cur.push(it->second);
  53.                                 out.push_back(it->second);
  54.                         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  55.                 }
  56.         }
  57. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  58.         for (int i = 0; i < out.size(); i++) {
  59.                 printf("%c\n", out[i] + 'a' - 1);
  60.         }
  61. }


  62. void solve(int n, int m)
  63. {. 鍥磋鎴戜滑@1point 3 acres
  64.         for (int i = 0; i < m; i++) {
  65.                 scanf("%s", arr[i]);
  66.         }

  67.         char *prev_str = arr[0];
  68.         size_t prev_len = strlen(prev_str);
  69.         for (int i = 1; i < m; i++) {
  70.                 size_t len = std::min(prev_len, strlen(arr[i]));
  71.                 for (int j = 0; j < len; j++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  72.                         if (prev_str[j] != arr[i][j]) {
  73.                                 int prev = prev_str[j] - 'a' + 1;
  74.                                 int cur = arr[i][j] - 'a' + 1;
  75.                                 if (alphabet[prev][cur] == 0) {
  76.                                         alphabet[prev][cur] = cur;
  77.                                         indegree[cur]++;
  78.                                 }
  79.                                 break;
  80.                         }
  81.                 }
  82.                 prev_str = arr[i];-google 1point3acres
  83.                 prev_len = len;
  84.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  85.         topologic_sort(27);

  86.         for (int i = 0; i<n; i++){
  87.                 alphabet[i].clear();
  88.         }

  89. }

  90. int main().鐣欏璁哄潧-涓浜-涓夊垎鍦
  91. {
  92.         FINPUT("in.txt");
  93.         FOUTPUT("out.txt");

  94.         int n, m;
  95.         while (scanf("%d %d ", &n, &m) != EOF) {
  96.                 solve(n, m);
  97.         }
  98.         return 0;
  99. }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sj1456 发表于 2014-5-20 05:26:04 | 显示全部楼层
discoveryi 发表于 2014-5-19 11:49
***************************************************************
GOOGLE PHONE TECHNICAL INTERVIEW  ...

碉堡,谢拉兄台!
回复 支持 反对

使用道具 举报

littlecoolblaxk 发表于 2014-9-21 02:57:44 | 显示全部楼层
想问一下第二题  数组最后一个数据 tdf 感觉会造成图里有环呀 这样还能拓扑排序么? 还是lz手抖打错啦?
-google 1point3acres
下周可能要电面G 图相关的还有点弱。。好好准备了。。
回复 支持 反对

使用道具 举报

shinichish 发表于 2014-9-22 08:25:12 | 显示全部楼层
discoveryi 发表于 2014-5-19 11:49.鐣欏璁哄潧-涓浜-涓夊垎鍦
***************************************************************
GOOGLE PHONE TECHNICAL INTERVIEW  ...

请问,Familiarize yourself with binary trees, n-ary trees, and trie-trees. Be familiar with at least one type of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree。真的是这样吗?Google 有在考这些吗?
回复 支持 反对

使用道具 举报

tbian 发表于 2014-10-15 03:12:46 | 显示全部楼层
可以简单解释一下怎么做吗
回复 支持 反对

使用道具 举报

xdrealmadrid 发表于 2014-10-31 03:41:30 | 显示全部楼层
topological sort正解
回复 支持 反对

使用道具 举报

volcano 发表于 2015-6-5 17:15:56 | 显示全部楼层
littlecoolblaxk 发表于 2014-9-21 02:57
想问一下第二题  数组最后一个数据 tdf 感觉会造成图里有环呀 这样还能拓扑排序么? 还是lz手抖打错啦?

...

我也觉得楼主打错了, 这里面有环
回复 支持 反对

使用道具 举报

chwcrazy 发表于 2015-6-19 02:02:18 | 显示全部楼层
如果没有tdf  这条路径(排除环)的话,应该是 afctbpk(在没给全所有node的条件下算的)当然 Topological Sorting答案不唯一. more info on 1point3acres.com

补充内容 (2015-6-18 13:20):
应该是['a', 'f', 'c', 't', 'p', 'b', 'd', 'k'], 如果没有tdf的话
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-24 13:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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