一亩三分地论坛

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

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

Google电面面经

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

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

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

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

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

第一题,水题,数组加一操作,for example, 输入[2, 7, 8, 9] 数组,加一后变成 [2, 7, 9, 0]. From 1point 3acres bbs

第二题,给定输入这样的字符串
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
求面试准备清单。。。

***************************************************************
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). visit 1point3acres.com for more.
- 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/. From 1point 3acres bbs
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璁哄潧
“How to Get Hired” by Dan Kegel (Google Engineer)
http://www.kegel.com/academy/getting-hired.html


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:

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
.1point3acres缃
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.鏈枃鍘熷垱鑷1point3acres璁哄潧
Google MapReduce http://research.google.com/archive/mapreduce.html
. 1point 3acres 璁哄潧
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.
. visit 1point3acres.com for more.
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.

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家发的面试准备清单里貌似没有提到“拓扑”。。。俺去复习复习。。

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

使用道具 举报

robinho364 发表于 2014-5-19 12:09:39 | 显示全部楼层
第二题,我的理解是这样的:. 1point 3acres 璁哄潧

fft和aac比较,按照f<a的规则,f在a前面。. Waral 鍗氬鏈夋洿澶氭枃绔,

既然是这样,那和拓扑排序有什么关系呢?. more info on 1point3acres.com

自定义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
.1point3acres缃
- = 你没看懂题. 鍥磋鎴戜滑@1point 3 acres
让建alphabet. 就是说建一个字母的顺序.
例子不是给了么. 比如 f -> a, 的意思是f在a前边.
题目就是让从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

/*拓扑排序*/. Waral 鍗氬鏈夋洿澶氭枃绔,
topologicalsort();

bug_free的topologicalsort其实不难,多练练就成了。

求指教。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
.1point3acres缃
  
回复 支持 反对

使用道具 举报

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

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

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

使用道具 举报

robinho364 发表于 2014-5-19 13:29:15 | 显示全部楼层
readman 发表于 2014-5-19 13:14. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
大概是这意思把..
添加的node是字母, 不是string, 添加前还要先找到位置 避免在字典中重复出现字母.
估 ...

是,添加的是字母。

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

复杂度确实不低,你说的是对的。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. from: 1point3acres.com/bbs
谢谢!

回复 支持 反对

使用道具 举报

robinho364 发表于 2014-5-19 14:04:49 | 显示全部楼层
readman 发表于 2014-5-19 13:14
大概是这意思把..
添加的node是字母, 不是string, 添加前还要先找到位置 避免在字典中重复出现字母.. more info on 1point3acres.com
估 ...
. From 1point 3acres bbs
Hi,根据lz的例子,简单地写了一下,监测结果是:
b
f
a. 1point 3acres 璁哄潧
c
t
d
  1. #define _USE_MATH_DEFINES

  2. #ifdef ONLINE_JUDGE. more info on 1point3acres.com
  3. #define FINPUT(file) 0. 1point 3acres 璁哄潧
  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>
  10. #include <cstdio>
  11. #include <cstring>
  12. #include <cstdlib>
  13. #include <cmath>
    . from: 1point3acres.com/bbs
  14. #include <ctime>
  15. #include <set>. visit 1point3acres.com for more.
  16. #include <stack>
  17. #include <string>-google 1point3acres
  18. #include <map>
  19. #include <vector>
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  20. #include <queue>. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  21. #include <algorithm>
  22. #include <functional>

  23. typedef long long ll;
  24. static const int M = 300;. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.         for (int i = 1; i<n; i++){
  38.                 if (indegree[i] == 0 && alphabet[i].size() != 0){
  39.                         cur.push(i);
  40.                         out.push_back(i);
  41.                 }
  42.         }

  43.         int ncount = 0;
  44.         while (cur.empty() == false){
  45.                 int tmp = cur.front();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  46.                 cur.pop();
  47.                 ncount++;
  48.                 std::map<int, int>::iterator it = alphabet[tmp].begin();
  49.                 for (it = alphabet[tmp].begin(); it != alphabet[tmp].end(); it++) {
  50.                         if (--indegree[it->second] == 0){
  51.                                 cur.push(it->second);
  52.                                 out.push_back(it->second);. From 1point 3acres bbs
  53.                         }
  54.                 }
  55.         }

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


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

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

  83.         topologic_sort(27);

  84.         for (int i = 0; i<n; i++){
  85.                 alphabet[i].clear();
  86.         }. 1point 3acres 璁哄潧

  87. }

  88. int main()
  89. {
  90.         FINPUT("in.txt");
  91.         FOUTPUT("out.txt");

  92.         int n, m;
  93.         while (scanf("%d %d ", &n, &m) != EOF) {
  94.                 solve(n, m);. visit 1point3acres.com for more.
  95.         }
  96.         return 0;
  97. }
复制代码

评分

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
***************************************************************. From 1point 3acres bbs
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手抖打错啦?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
...

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

使用道具 举报

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-4-25 18:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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