一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 4940|回复: 24
收起左侧

Google电面面经

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

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

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

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

x
周一google电面,现在还在等消息,发发面经,攒攒RP,也希望得到大家的Bless。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
第一题,水题,数组加一操作,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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
sj1456 发表于 2014-5-19 11:33
求面试准备清单。。。
.1point3acres缃
***************************************************************. more info on 1point3acres.com
GOOGLE PHONE TECHNICAL INTERVIEW TIPS:

Please be prepared for the engineers to ask you questions in the following areas:. more info on 1point3acres.com
- Google products (i.e. what you use)
- Coding ability (you will code in a Google Doc). 鍥磋鎴戜滑@1point 3 acres
- Algorithm Design/Analysis
- System Design

The links below may help you prepare for your interview:      
. from: 1point3acres.com/bbs
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. 1point3acres.com/bbs
“How to Get Hired” by Dan Kegel (Google Engineer).鐣欏璁哄潧-涓浜-涓夊垎鍦
http://www.kegel.com/academy/getting-hired.html
. 1point 3acres 璁哄潧. more info on 1point3acres.com

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
. 1point3acres.com/bbs
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:

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. more info on 1point3acres.com
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 3 acres

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.
. 1point 3acres 璁哄潧
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.

For information on System Design:
http://research.google.com/pubs/ ... allelComputing.html

11.) Also, you can review some of our research publications: http://research.google.com/pubs/papers.html
回复 支持 1 反对 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家发的面试准备清单里貌似没有提到“拓扑”。。。俺去复习复习。。

. more info on 1point3acres.com求面试准备清单。。。
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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

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

既然是这样,那和拓扑排序有什么关系呢?

自定义std::sort规则,直接暴力排序,复杂度为O(nlog(n)*m),其中m为字符串长度,n为字符串个数。

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

使用道具 举报

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

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

使用道具 举报

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

- = 你没看懂题. 鍥磋鎴戜滑@1point 3 acres
让建alphabet. 就是说建一个字母的顺序.
例子不是给了么. 比如 f -> a, 的意思是f在a前边.. visit 1point3acres.com for more.
题目就是让从input中, 找出更多这样的顺序. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
非常明显的拓扑排序, 非常直接.

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

使用道具 举报

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

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

我原先看到:“给定一些这样的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
. visit 1point3acres.com for more.
/*拓扑排序*/
topologicalsort();

bug_free的topologicalsort其实不难,多练练就成了。. From 1point 3acres bbs

求指教。

  
回复 支持 反对

使用道具 举报

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

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

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

使用道具 举报

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

是,添加的是字母。

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

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

谢谢!

回复 支持 反对

使用道具 举报

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

Hi,根据lz的例子,简单地写了一下,监测结果是:
b
f. From 1point 3acres bbs
a
c
t
d
  1. #define _USE_MATH_DEFINES

  2. #ifdef ONLINE_JUDGE
  3. #define FINPUT(file) 0
  4. #define FOUTPUT(file) 0
  5. #else
  6. #define FINPUT(file) freopen(file,"r",stdin)
  7. #define FOUTPUT(file) freopen(file,"w",stdout)
  8. #endif
  9. -google 1point3acres
  10. #include <iostream>
  11. #include <cstdio>
  12. #include <cstring>
  13. #include <cstdlib>. 1point 3acres 璁哄潧
  14. #include <cmath>
  15. #include <ctime>
  16. #include <set>
  17. #include <stack>
  18. #include <string>
  19. #include <map>
  20. #include <vector>
  21. #include <queue>
  22. #include <algorithm>
  23. #include <functional>

  24. typedef long long ll;
  25. static const int M = 300;. visit 1point3acres.com for more.
  26. static const int N = 10;.1point3acres缃
  27. static const int LEN = 1000010;
  28. static const int MAX = 0x7fffffff;
  29. static const int MIN = ~MAX;
  30. static const double EPS = 1e-7;.1point3acres缃
  31. char arr[N][M];
  32. int indegree[N];. 1point 3acres 璁哄潧
  33. std::vector< std::map<int, int> > alphabet(27);

  34. void topologic_sort(int n). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  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);.1point3acres缃
  41.                         out.push_back(i);
  42.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  43.         }
  44. . visit 1point3acres.com for more.
  45.         int ncount = 0;
  46.         while (cur.empty() == false){
  47.                 int tmp = cur.front();
  48.                 cur.pop();
  49.                 ncount++;
  50.                 std::map<int, int>::iterator it = alphabet[tmp].begin();
  51.                 for (it = alphabet[tmp].begin(); it != alphabet[tmp].end(); it++) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  52.                         if (--indegree[it->second] == 0){
  53.                                 cur.push(it->second);
  54.                                 out.push_back(it->second);
  55.                         }
  56.                 }
  57.         }

  58.         for (int i = 0; i < out.size(); i++) {
  59.                 printf("%c\n", out[i] + 'a' - 1);
  60.         }
  61. }
  62. .1point3acres缃

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

  68.         char *prev_str = arr[0];
  69.         size_t prev_len = strlen(prev_str);
  70.         for (int i = 1; i < m; i++) {
  71.                 size_t len = std::min(prev_len, strlen(arr[i]));
  72.                 for (int j = 0; j < len; j++) {
  73.                         if (prev_str[j] != arr[i][j]) {
  74.                                 int prev = prev_str[j] - 'a' + 1;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  75.                                 int cur = arr[i][j] - 'a' + 1;
  76.                                 if (alphabet[prev][cur] == 0) {
  77.                                         alphabet[prev][cur] = cur;. 鍥磋鎴戜滑@1point 3 acres
  78.                                         indegree[cur]++;
  79.                                 }
  80.                                 break;
  81.                         }
  82.                 }
  83.                 prev_str = arr[i];
  84.                 prev_len = len;
  85.         }

  86.         topologic_sort(27);

  87.         for (int i = 0; i<n; i++){
  88.                 alphabet[i].clear();
  89.         }
  90. . 鍥磋鎴戜滑@1point 3 acres
  91. }

  92. int main()
  93. {
  94.         FINPUT("in.txt");
  95.         FOUTPUT("out.txt");. From 1point 3acres bbs
  96. -google 1point3acres
  97.         int n, m;
  98.         while (scanf("%d %d ", &n, &m) != EOF) {
  99.                 solve(n, m);
  100.         }
  101.         return 0;
  102. }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sj1456 发表于 2014-5-20 05:26:04 | 显示全部楼层
discoveryi 发表于 2014-5-19 11:49
***************************************************************. more info on 1point3acres.com
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 1point3acres
***************************************************************
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. 鍥磋鎴戜滑@1point 3 acres
想问一下第二题  数组最后一个数据 tdf 感觉会造成图里有环呀 这样还能拓扑排序么? 还是lz手抖打错啦?
. Waral 鍗氬鏈夋洿澶氭枃绔,
...

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

使用道具 举报

chwcrazy 发表于 2015-6-19 02:02:18 | 显示全部楼层
如果没有tdf  这条路径(排除环)的话,应该是 afctbpk(在没给全所有node的条件下算的)当然 Topological Sorting答案不唯一
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2015-6-18 13:20):
应该是['a', 'f', 'c', 't', 'p', 'b', 'd', 'k'], 如果没有tdf的话
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-20 14:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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