推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 6249|回复: 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]
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二题,给定输入这样的字符串. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
fft, fcp, aac, act, acd, atp, tbk, tdf, …
这些都是按照字母排序好的,但是字母顺序改了,比如 f 在 a之前,t在d之前等等,给定一些这样的rule,问怎么rebuild the alphabet?
-google 1point3acres

评分

1

查看全部评分

本帖被以下淘专辑推荐:

discoveryi 发表于 2014-5-19 11:49:38 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
sj1456 发表于 2014-5-19 11:33
求面试准备清单。。。

***************************************************************
GOOGLE PHONE TECHNICAL INTERVIEW TIPS:

Please be prepared for the engineers to ask you questions in the following areas:
- Google products (i.e. what you use)
- Coding ability (you will code in a Google Doc)
- 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)
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. from: 1point3acres.com/bbs
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

BOOKS:
(#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:
.鏈枃鍘熷垱鑷1point3acres璁哄潧
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. from: 1point3acres.com/bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,
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.

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.

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.

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.

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 3acres 璁哄潧
For information on System Design:. 1point 3acres 璁哄潧
http://research.google.com/pubs/ ... allelComputing.html
. 1point3acres.com/bbs
11.) Also, you can review some of our research publications: http://research.google.com/pubs/papers.html
回复 支持 2 反对 0

使用道具 举报

 楼主| peter668 发表于 2014-5-15 00:42:59 | 显示全部楼层
关注一亩三分地微博:
Warald
其实第二题本质是拓扑排序

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

robinho364 发表于 2014-5-19 12:09:39 | 显示全部楼层
第二题,我的理解是这样的:
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
fft和aac比较,按照f<a的规则,f在a前面。

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

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

使用道具 举报

robinho364 发表于 2014-5-19 12:12:15 | 显示全部楼层
discoveryi 发表于 2014-5-15 01:39. Waral 鍗氬鏈夋洿澶氭枃绔,
谢谢楼主面经。。
G家发的面试准备清单里貌似没有提到“拓扑”。。。俺去复习复习。。

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

使用道具 举报

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

- = 你没看懂题
让建alphabet. 就是说建一个字母的顺序.
例子不是给了么. 比如 f -> a, 的意思是f在a前边.
题目就是让从input中, 找出更多这样的顺序.
非常明显的拓扑排序, 非常直接.
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
不过写不写的出来 bug free 的tsort...这个...我反正写不出来
回复 支持 反对

使用道具 举报

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

就是说意思是从给定的字符串中重建字母表?

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

抱歉。

那这个思路就是这样了:

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

/*拓扑排序*/
topologicalsort();

bug_free的topologicalsort其实不难,多练练就成了。. 鍥磋鎴戜滑@1point 3 acres

求指教。

  
回复 支持 反对

使用道具 举报

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

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

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

使用道具 举报

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

是,添加的是字母。
. Waral 鍗氬鏈夋洿澶氭枃绔,
我的意思是,添加字母的时候本质上是比较string,比如ffd和fdd,需要比较的是第二位的f和d。.鐣欏璁哄潧-涓浜-涓夊垎鍦

复杂度确实不低,你说的是对的。

谢谢!. more info on 1point3acres.com
. From 1point 3acres bbs
回复 支持 反对

使用道具 举报

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

Hi,根据lz的例子,简单地写了一下,监测结果是:
b 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
f
a
c. from: 1point3acres.com/bbs
t
d
  1. #define _USE_MATH_DEFINES

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

  9. #include <iostream>
  10. #include <cstdio>
  11. #include <cstring>
  12. #include <cstdlib>
  13. #include <cmath>
  14. #include <ctime>
  15. #include <set>. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  16. #include <stack>
  17. #include <string>
  18. #include <map>
  19. #include <vector>
  20. #include <queue>. From 1point 3acres bbs
  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);

  33. void topologic_sort(int n)
  34. {
  35.         std::queue<int> cur;
  36.         std::vector<int> out;
  37. . 1point 3acres 璁哄潧
  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);
    . 1point 3acres 璁哄潧
  42.                 }
  43.         }

  44.         int ncount = 0;
  45.         while (cur.empty() == false){. Waral 鍗氬鏈夋洿澶氭枃绔,
  46.                 int tmp = cur.front();. from: 1point3acres.com/bbs
  47.                 cur.pop();
  48.                 ncount++;. more info on 1point3acres.com
  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.                         }
  55.                 }
  56.         }. 1point 3acres 璁哄潧

  57.         for (int i = 0; i < out.size(); i++) {-google 1point3acres
  58.                 printf("%c\n", out[i] + 'a' - 1); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  59.         }
  60. }


  61. void solve(int n, int m)
  62. {-google 1point3acres
  63.         for (int i = 0; i < m; i++) {.1point3acres缃
  64.                 scanf("%s", arr[i]);
  65.         }

  66.         char *prev_str = arr[0];
  67.         size_t prev_len = strlen(prev_str);
  68.         for (int i = 1; i < m; i++) {. 1point3acres.com/bbs
  69.                 size_t len = std::min(prev_len, strlen(arr[i]));.鐣欏璁哄潧-涓浜-涓夊垎鍦
  70.                 for (int j = 0; j < len; j++) {
  71.                         if (prev_str[j] != arr[i][j]) {
  72.                                 int prev = prev_str[j] - 'a' + 1;
  73.                                 int cur = arr[i][j] - 'a' + 1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  74.                                 if (alphabet[prev][cur] == 0) {
  75.                                         alphabet[prev][cur] = cur;. more info on 1point3acres.com
  76.                                         indegree[cur]++;
  77.                                 }
  78.                                 break;
  79.                         }
  80.                 }
  81.                 prev_str = arr[i];
    .1point3acres缃
  82.                 prev_len = len;
  83.         }

  84.         topologic_sort(27);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  85. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  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. . 1point3acres.com/bbs
  95.         int n, m;
  96.         while (scanf("%d %d ", &n, &m) != EOF) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  97.                 solve(n, m);
  98.         }
  99.         return 0;
  100. }
复制代码

评分

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手抖打错啦?

下周可能要电面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
-google 1point3acres想问一下第二题  数组最后一个数据 tdf 感觉会造成图里有环呀 这样还能拓扑排序么? 还是lz手抖打错啦?

...
. 1point 3acres 璁哄潧
我也觉得楼主打错了, 这里面有环
回复 支持 反对

使用道具 举报

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

补充内容 (2015-6-18 13:20):.鏈枃鍘熷垱鑷1point3acres璁哄潧
应该是['a', 'f', 'c', 't', 'p', 'b', 'd', 'k'], 如果没有tdf的话
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-25 10:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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