传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 3980|回复: 26
收起左侧

Google电面求大米

[复制链接] |试试Instant~ |关注本帖
asyouknow 发表于 2016-11-15 13:33:54 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
第一次面试就是Google,亚历山大。。. 1point3acres.com/bbs
第一面是口音是个印度中年男人,开始问了一个梦里也不可能不会的概率题,然后上了一道很简单的coding题。给你两个string,表示两个数,比如“132”,“32.5”,比较两个数的大小。要求one pass,不能用库函数。idea两分钟搞定,但因为实力有限,写代码交流费了不少时间,然后跑了跑case,问了问问题就结束了。

第二面应该是个美国白人小哥,上来写个check回文热热身,然后说不能只会python,来用c++写个多线程的程序,我说不会跳过。然后让我写了求根号的程序,LC上有,简单的题费了半天劲。之后又做了个coding题,是给你一个string,求最长的substring,是另一个substring的prefix。比如"abcab", "ab"出现在两个地方,所以是符合条件的。扯来扯去说了一个多小时。最后都扯到美国大选了。

两个人都很nice。第二个人还挺喜欢我,但题太简单还完成得很慢,估计跪了。提高实力,来年再战!


评分

3

查看全部评分

本帖被以下淘专辑推荐:

如果我是金牛座 发表于 2016-11-16 10:54:17 | 显示全部楼层
请问第一题的思路是什么?
回复 支持 反对

使用道具 举报

hwu2498 发表于 2016-11-16 11:34:28 | 显示全部楼层
不一定会跪!你跟面试官聊得很开心说不定加印象分哈哈

楼主加油
回复 支持 反对

使用道具 举报

 楼主| asyouknow 发表于 2016-11-16 12:57:15 | 显示全部楼层
如果我是金牛座 发表于 2016-11-16 10:54
请问第一题的思路是什么?

你当然可以把数恢复出来做。比如一个一个读,每次先把旧的×10,遇到小数点就改一下策略。
但我觉得更简单的思路是直接比较首位,谁大就暂时认为谁大,同时记录数的位数。然后结合位数可以决定大小。负数的case我都没考虑。
想法简单,写得清楚简单要点时间
回复 支持 反对

使用道具 举报

 楼主| asyouknow 发表于 2016-11-16 12:58:50 | 显示全部楼层
hwu2498 发表于 2016-11-16 11:34
不一定会跪!你跟面试官聊得很开心说不定加印象分哈哈

楼主加油

第二个人肯定给我过了,主要是第一个做得太慢。实力确实不够,地里好多厉害人。
回复 支持 反对

使用道具 举报

hwu2498 发表于 2016-11-16 15:58:27 | 显示全部楼层
asyouknow 发表于 2016-11-16 12:58
第二个人肯定给我过了,主要是第一个做得太慢。实力确实不够,地里好多厉害人。

第一题其实很好做吧。。记录一下小数点的位置,之前的数*10 + 新的digit然后变成float型的然后加上小数点后面的
回复 支持 反对

使用道具 举报

helloworld00 发表于 2016-11-17 00:58:51 | 显示全部楼层
第一个, 按楼上的方法,先看第一位,然后看小数点位置

如果第一个数大于或等于返回True,否则返回False
.1point3acres缃
def compareTwostr(str_a, str_b):
        a_flag = False
        index = 0

        if str_a[0] > str_b[0]:
                a_flag = True
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        while index < min(len(str_a), len(str_b)):
                if str_a[index] != str_b[index] and str_a[index] == '.':
                        a_flag = False                               
                        break.鐣欏璁哄潧-涓浜-涓夊垎鍦

                if str_a[index] != str_b[index] and str_b[index] == '.':
                        a_flag = True
                        break

                index += 1
. Waral 鍗氬鏈夋洿澶氭枃绔,
        return a_flag
回复 支持 反对

使用道具 举报

jizhoutong 发表于 2016-11-17 02:11:58 | 显示全部楼层
toCharArray这个函数 让用吗
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-17 12:37:29 | 显示全部楼层
我写了下第一题, 大家看下还有没有什么Corner case没有考虑到。
  1. int compare(string num1, string num2){
  2.         int flag = 0;
  3.         int index = 0;
  4.         bool point = false;
  5.         bool minus = false;
  6.         if(num1[index] == '-' && num2[index] == '-'){
  7.                 minus = true;
  8.                 index++;
  9.         }
  10.         else if(num1[index] == '-')
  11.                 return -1;. 1point3acres.com/bbs
  12.         else
  13.                 return 1;




  14.         while(index < min(num1.length(), num2.length())){
  15.                 if(num1[index] != num2[index] && num1[index] == '.'){
  16.                         flag = -1;
  17.                         point = true;
  18.                         break;
  19.                 }
  20.                 else if(num1[index] != num2[index] && num2[index] == '.'){
  21.                         flag =  1;
  22.                         point = true;
  23.                         break;
  24.                 }
  25.                 else if(flag !=0 && num1[index] > num2[index])
  26.                         flag = 1;
  27.                 else if(flag !=0 && num1[index] < num2[index])
  28.                         flag = -1;
  29.                 else;
  30.                 index++;
  31.         }-google 1point3acres
  32.         if(point == false && num1.length() != num2.length())
  33.                 flag = num1.length() > num2.length() ? 1 : -1;
  34.         return minus==true? -flag : flag;

  35. }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
复制代码
回复 支持 反对

使用道具 举报

 楼主| asyouknow 发表于 2016-11-17 12:49:53 | 显示全部楼层
helloworld00 发表于 2016-11-17 00:58.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一个, 按楼上的方法,先看第一位,然后看小数点位置.1point3acres缃

如果第一个数大于或等于返回True,否则返回False ...

如果是“3.0”和“3”有些问题吧
回复 支持 反对

使用道具 举报

 楼主| asyouknow 发表于 2016-11-17 12:50:32 | 显示全部楼层
jizhoutong 发表于 2016-11-17 02:11
toCharArray这个函数 让用吗

是个linked list,用现成函数就没意思了
回复 支持 反对

使用道具 举报

 楼主| asyouknow 发表于 2016-11-17 12:52:20 | 显示全部楼层
zhan1612 发表于 2016-11-17 12:37
我写了下第一题, 大家看下还有没有什么Corner case没有考虑到。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
看起来不错。
“3.0”和“3”呢?
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-17 13:11:56 | 显示全部楼层
asyouknow 发表于 2016-11-17 12:52
看起来不错。-google 1point3acres
“3.0”和“3”呢?
.1point3acres缃
我又改了下, 但是感觉代码有点长, 有没有更好的办法那?
  1. int compare(string num1, string num2){
  2.         int flag = 0;
  3.         int index = 0;
  4.         bool point = false;
  5.         bool minus = false;
  6.         if(num1[index] == '-' && num2[index] == '-'){
  7.                 minus = true;
  8.                 index++;. visit 1point3acres.com for more.
  9.         }
  10.         else if(num1[index] == '-')
  11.                 return -1;
  12.         else.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.                 return 1;

  14.         while(index < min(num1.length(), num2.length())){
  15.                 if(num1[index] != num2[index] && num1[index] == '.'){
  16.                         flag = -1;
  17.                         point = true;
  18.                         break;
  19.                 }. 鍥磋鎴戜滑@1point 3 acres
  20.                 else if(num1[index] != num2[index] && num2[index] == '.'){
  21.                         flag =  1;
  22.                         point = true;
  23.                         break;. visit 1point3acres.com for more.
  24.                 }
  25.                 else if(flag !=0 && num1[index] > num2[index])
  26.                         flag = 1;
  27.                 else if(flag !=0 && num1[index] < num2[index])
  28.                         flag = -1;
  29.                 else;
  30.                 index++;
  31.         }
  32.         if(point == false && num1.length() > num2.length()){
  33.                 if(num1[index++] == '.'){
  34.                         while(index < num1.length()&& num1[index] == '0')
  35.                                 index++;. 鍥磋鎴戜滑@1point 3 acres
  36.                         flag = index == num1.length()? 0 : 1;
  37.                 }
  38.                 else
  39.                         flag = 1;
  40.         }
  41.         if(point == false && num1.length() < num2.length()){
  42.                 if(num2[index++] == '.'){
  43.                         while(index < num2.length()&& num2[index] == '0')
  44.                                 index++;-google 1point3acres
  45.                         flag = index == num2.length()? 0 : -1;
  46.                 }
  47.                 else
  48.                         flag = -1;
  49.         }

  50.         return minus==true? -flag : flag;

  51. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| asyouknow 发表于 2016-11-17 14:30:08 | 显示全部楼层
zhan1612 发表于 2016-11-17 13:11
我又改了下, 但是感觉代码有点长, 有没有更好的办法那?

我不是高手,觉得你写的已经不错了。这题思路很简单,写起来有点烦。
回复 支持 反对

使用道具 举报

helloworld00 发表于 2016-11-17 19:46:25 | 显示全部楼层
asyouknow 发表于 2016-11-17 12:49. visit 1point3acres.com for more.
如果是“3.0”和“3”有些问题吧

哇,感谢指出corner case

确实后面得加个判断
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                if not a_flag:
                        index += 1
                        while index < len(str_a) and str_a[index] == '0':

                                index += 1

                        if index == len(str_a):
                                a_flag = True

. more info on 1point3acres.com
还有正负数的就应该跟前面的一样了
回复 支持 反对

使用道具 举报

helloworld00 发表于 2016-11-17 19:48:12 | 显示全部楼层
helloworld00 发表于 2016-11-17 19:46
哇,感谢指出corner case

确实后面得加个判断

假设同样的数都为True
回复 支持 反对

使用道具 举报

yydcool 发表于 2016-11-17 23:55:20 | 显示全部楼层
楼主最长重复字串是给的O(n)算法吗
回复 支持 反对

使用道具 举报

 楼主| asyouknow 发表于 2016-11-18 14:30:31 | 显示全部楼层
yydcool 发表于 2016-11-17 23:55
楼主最长重复字串是给的O(n)算法吗

没有,n^2。怎么做O(n)啊?求教!
回复 支持 反对

使用道具 举报

yydcool 发表于 2016-11-19 11:42:48 | 显示全部楼层
后缀树,搜longest repeated substring
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-19 12:36:47 | 显示全部楼层
麻烦问一下楼主第二题, 第一题是不是就是找longest suffix, 是剩下的prefix?
如果不是的话那像"abcabd"这种应该返回什么?还是返回“ab”?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-22 16:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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