一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2057|回复: 11
收起左侧

Google电面 被虐

[复制链接] |试试Instant~ |关注本帖
那可是你B爹 发表于 2015-4-24 06:09:42 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Fail其他

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

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

x
整体来说 这次电面就是个悲剧 :一来是我能力不济,有些问题实在忘了。

二来沟通问题,电话信号差,欧洲口音,我没法完全理解他的意思。

题目:
第一题: 二维数组作为函数参数和返回值时的问题:
  1. char **string_transpose(char **str) {
  2.        char new_string[3][3];
  3.        for (int i = 0; i <= 3; ++i)
  4.              for (int j = 0; j <= 3; ++j)
  5.                     new_string[i][j] = str[j][i];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6.        return new_string;
  7. }

  8. int main() {
  9.       char old_string[3][3];
  10.       string_transpose(old_string);
  11. }
复制代码
找出并改正以上代码中的错误,注意:不能修改函数签名
这么基础的知识,我忘了,非常非常汗颜. visit 1point3acres.com for more.

第二题:
  1. Given a list of strings L(S) of arbitrary length and arbitrary characters. How would you save this list into a single file? Describe Writer and Reader procedures!
复制代码
bool Writer(const std::vector<string> &list)


}. 1point 3acres 璁哄潧
-google 1point3acres
Efficient:
bool Writer(const std::vector<string> &list) {


}. from: 1point3acres.com/bbs

不让写代码,只用伪代码描述就可以我犯得错误:. 1point3acres.com/bbs
   我:在文本中一行打印一个字符串
   他:如果字符串是 “\n\n\n\n\n”, 你怎么区分.1point3acres缃
   我:那就写的时候编码一下\\n\\n\\n\\n\\n,读得时候解码
   他:字符串是cons 你不可以修改,你的reader和writer不具有这种功能
   我:那用 每个字符串的长度+字符串 的形式输入
   他:好,那我有百万个字符串,我要不遍历文本,直接找到最后一个怎么办

以上对话是我理解转述他的话,真实对话特别扯淡。可能是我英文太差,我不能完全理解他的话,他描述问题,怎么说 给人的感觉特别玄乎,特别假大空的感觉。
事后想想,这问题不难,关键他描述的特别玄乎,我完全蒙了。而且他态度很不好,也不给我提示,开了免提信号特差,自己在干活,说,你写好了叫我。。。

题目三
  1. What is a priority queue? How would you implement it efficiently? How can you improve the complexity of the queue for a restricted interval of priorities, e.g. [0, 1]?
  2. . From 1point 3acres bbs
  3. struct Item {
  4.   …. more info on 1point3acres.com
  5.   
  6.   double priority() const;
  7. };

  8. class Queue {
  9.   void Push(const Item &);
  10.   void Pop();
    -google 1point3acres
  11.   Item &Top();
  12.   ….鐣欏璁哄潧-涓浜-涓夊垎鍦
  13. };
复制代码

补充内容 (2015-4-25 01:23):
第三题口面写了一长串怎么木有了。。。我补充在第十楼了。。。

评分

5

查看全部评分

rengokantai 发表于 2015-4-24 06:48:22 | 显示全部楼层
感谢分享,第一题楼主现在会了吗,我看不出错误
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-4-24 07:19:35 | 显示全部楼层
rengokantai 发表于 2015-4-24 06:48
感谢分享,第一题楼主现在会了吗,我看不出错误
  1. char **string_transpose(char **str) {
  2.     char **new_string = new char*[3];
  3.     for(int i = 0; i < 3; i++)
  4.         new_string[i] = new char[3];
  5.     for (int i = 0; i <= 3; ++i)
  6.         for (int j = 0; j <= 3; ++j)
  7.             new_string[i][j] = str[j][i];
  8.     return new_string;. more info on 1point3acres.com
  9. }

  10. int main() {
  11.     //char old_string[3][3];.1point3acres缃
  12.     char **old_string = new char*[3];
  13.     for(int i = 0; i < 3; i++)
  14.         old_string[i] = new char[3];
  15.     string_transpose(old_string);
  16. }
复制代码
回复 支持 反对

使用道具 举报

kevinking813 发表于 2015-4-24 08:08:44 | 显示全部楼层

楼主第5 第6行应该都是 i < 3  j <3 吧 越界了~
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-4-24 08:20:22 | 显示全部楼层

how can u get the new string?
回复 支持 反对

使用道具 举报

mmliu 发表于 2015-4-24 11:06:16 | 显示全部楼层
谢谢楼主分享

优先队列这题,对于给定了 restricted interval 的情况,咋个提高复杂度呀?
回复 支持 反对

使用道具 举报

泡妞被妞泡 发表于 2015-4-24 13:53:39 | 显示全部楼层
第一题可以直接做个Trie吗?. from: 1point3acres.com/bbs

补充内容 (2015-4-24 13:54):
错了,我指第二题
回复 支持 反对

使用道具 举报

 楼主| 那可是你B爹 发表于 2015-4-25 00:58:42 | 显示全部楼层
rengokantai 发表于 2015-4-24 06:48
感谢分享,第一题楼主现在会了吗,我看不出错误
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我面完就去看谭浩强了 哭
二维数组作为参数传递需要规定第二位的值,如果不想规定死,就要用指针的指针
我大概写了一下 你试试 望指正
  1. char **transpose(char **matrix, int m , int n){
  2.     //build a [n][m] matrix
  3.     char **t = new char* [n];
  4.     for(int i = 0; i < n; ++i)
  5.         t[i] = new char [m];
  6.     //transpose
  7.     for(int i = 0; i < m; ++i){
  8.         for(int j = 0; j < n; ++j)
  9.             t[j][i] = *((char*)matrix + i * n + j);   
  10.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.     //print matrix
  12.     for(int i = 0; i < m; ++i){
  13.         for(int j = 0; j < n; ++j)
  14.             cout << *((char*)matrix + i * n + j) << " ";
  15.         cout << endl;   
  16.     }
  17.     cout << endl;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  18.     //print transpose matrix. 1point 3acres 璁哄潧
  19.     for(int i = 0; i < n; ++i){
  20.         for(int j = 0; j < m; ++j)
  21.             cout << t[i][j] << " ";   
  22.         cout << endl; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  23.     }
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.     cout << endl;-google 1point3acres
  25.     return t;
  26.         
  27. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| 那可是你B爹 发表于 2015-4-25 01:00:25 | 显示全部楼层
kevinking813 发表于 2015-4-24 08:08
楼主第5 第6行应该都是 i < 3  j

我当时也就改了这个 说 我实在看不出来了 那个小哥 深深的叹了口气。。。。
回复 支持 反对

使用道具 举报

 楼主| 那可是你B爹 发表于 2015-4-25 01:21:04 | 显示全部楼层
mmliu 发表于 2015-4-24 11:06
谢谢楼主分享

优先队列这题,对于给定了 restricted interval 的情况,咋个提高复杂度呀?

第三题后面打了一长串 怎么没了
他只是用优先级队列作为引子,开始问heap,问的非常细致。然后问了插入删除的时间复杂度。我说logn。他说好,你能优化这个时间复杂度吗。我说用hash map。然后就开始写unordered_map....他说nonono,你不能用STL,你给我写一个hash map和hash function。我当时蒙了啊,就跟他扯什么是哈希表 哈希函数 怎么找prime。他看我实在不会,就写了这个函数签名int MAP(Item &t),说那你就写这个哈希函数就行了。天天说哈希,哈希来哈希去,真让我写一个[0,1]上double的哈希函数,我!蒙!b!了!
其实后来想想也不是很那么没头绪,比如如果我问了这些double在[0,1]上怎么分布,或者需要关注优先值为多少的Item,可能还是可以解的。问题的关键在于。。。我面试前看了好多面经,觉得都不难,再怎么变换也无非是leetcode上升级版。出这些题目,我是真没想到,完全被虎了。
后来聊天,问道他是在google earth的,一下子明白过来他为什么考我这些,这都是他在工作中最常用的啊。然后他说自己要处理多大数量级的数怎么怎么怎么之类的。
祝福我的同学,非常感谢。我写这么多,一来是自己记录一下,查缺补漏;二来,是给大家分享下,扩展大家准备的广度。面试真是看运气。
回复 支持 反对

使用道具 举报

 楼主| 那可是你B爹 发表于 2015-4-25 01:22:42 | 显示全部楼层
泡妞被妞泡 发表于 2015-4-24 13:53.1point3acres缃
第一题可以直接做个Trie吗?

补充内容 (2015-4-24 13:54):

他要求,把这些字符串写到文本中,不能修改字符串的结构,不能有太大的overhead。我不太明吧你用trie做什么。怎么做。
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-5-8 09:02:06 | 显示全部楼层
那可是你B爹 发表于 2015-4-25 01:21
第三题后面打了一长串 怎么没了
他只是用优先级队列作为引子,开始问heap,问的非常细致。然后问了插入 ...

heap的作用是求动态维持最大值和最小值,用hashmap怎么替代?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 20:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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