《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 6707|回复: 24
收起左侧

Google电面面经

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

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

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

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

x
周一google电面,现在还在等消息,发发面经,攒攒RP,也希望得到大家的Bless。。。. 1point 3acres 璁哄潧

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

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

***************************************************************
GOOGLE PHONE TECHNICAL INTERVIEW TIPS:. visit 1point3acres.com for more.

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 1point3acres
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. Waral 鍗氬鏈夋洿澶氭枃绔,
“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)
. From 1point 3acres bbs
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:.鐣欏璁哄潧-涓浜-涓夊垎鍦
-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). 1point 3acres 璁哄潧
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.

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*.. 鍥磋鎴戜滑@1point 3 acres

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.
.鏈枃鍘熷垱鑷1point3acres璁哄潧
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:.鏈枃鍘熷垱鑷1point3acres璁哄潧
http://research.google.com/pubs/ ... allelComputing.html

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

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

使用道具 举报

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

fft和aac比较,按照f<a的规则,f在a前面。.鐣欏璁哄潧-涓浜-涓夊垎鍦
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
既然是这样,那和拓扑排序有什么关系呢?

自定义std::sort规则,直接暴力排序,复杂度为O(nlog(n)*m),其中m为字符串长度,n为字符串个数。
. from: 1point3acres.com/bbs
这样不能解决问题吗?
回复 支持 反对

使用道具 举报

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
. from: 1point3acres.com/bbs
- = 你没看懂题
让建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 ...

就是说意思是从给定的字符串中重建字母表?
.1point3acres缃
我原先看到:“给定一些这样的rule”,以为这些rule是给你的,让我们重排字符串。

抱歉。

那这个思路就是这样了:

/*首先建图*/
prev_str = arr[0];
for i = 1 to num of strings. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  cur_str = arr[1];. 1point3acres.com/bbs
  compare cur_str with prev_str, add an edge to the graph;
  prev_str = cur_str;
end

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

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

求指教。

  
回复 支持 反对

使用道具 举报

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. 鍥磋鎴戜滑@1point 3 acres
大概是这意思把..
添加的node是字母, 不是string, 添加前还要先找到位置 避免在字典中重复出现字母.
估 ...

是,添加的是字母。

我的意思是,添加字母的时候本质上是比较string,比如ffd和fdd,需要比较的是第二位的f和d。
. 鍥磋鎴戜滑@1point 3 acres
复杂度确实不低,你说的是对的。
. 1point3acres.com/bbs
谢谢!. 1point3acres.com/bbs

回复 支持 反对

使用道具 举报

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

Hi,根据lz的例子,简单地写了一下,监测结果是:. 1point 3acres 璁哄潧
b
f
a. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
c
t
d
  1. #define _USE_MATH_DEFINES. 1point3acres.com/bbs

  2. #ifdef ONLINE_JUDGE
  3. #define FINPUT(file) 0. more info on 1point3acres.com
  4. #define FOUTPUT(file) 0. 1point 3acres 璁哄潧
  5. #else
  6. #define FINPUT(file) freopen(file,"r",stdin)
  7. #define FOUTPUT(file) freopen(file,"w",stdout)
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8. #endif

  9. #include <iostream>. from: 1point3acres.com/bbs
  10. #include <cstdio>
  11. #include <cstring>. 1point3acres.com/bbs
  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>
  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. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  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++;
  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.         }

  57.         for (int i = 0; i < out.size(); i++) {
  58.                 printf("%c\n", out[i] + 'a' - 1);
  59.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  60. }

  61. . from: 1point3acres.com/bbs
  62. void solve(int n, int m)
  63. {
  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];
  83.                 prev_len = len;
  84.         }

  85.         topologic_sort(27);
  86. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  87.         for (int i = 0; i<n; i++){
  88.                 alphabet[i].clear();
  89.         }

  90. }

  91. int main()
  92. {
  93.         FINPUT("in.txt");
  94.         FOUTPUT("out.txt"); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

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

...

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

使用道具 举报

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的话
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-23 08:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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