一亩三分地论坛

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

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

Google电面求大米

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

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

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

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

x
第一次面试就是Google,亚历山大。。
第一面是口音是个印度中年男人,开始问了一个梦里也不可能不会的概率题,然后上了一道很简单的coding题。给你两个string,表示两个数,比如“132”,“32.5”,比较两个数的大小。要求one pass,不能用库函数。idea两分钟搞定,但因为实力有限,写代码交流费了不少时间,然后跑了跑case,问了问问题就结束了。
-google 1point3acres
第二面应该是个美国白人小哥,上来写个check回文热热身,然后说不能只会python,来用c++写个多线程的程序,我说不会跳过。然后让我写了求根号的程序,LC上有,简单的题费了半天劲。之后又做了个coding题,是给你一个string,求最长的substring,是另一个substring的prefix。比如"abcab", "ab"出现在两个地方,所以是符合条件的。扯来扯去说了一个多小时。最后都扯到美国大选了。

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

. from: 1point3acres.com/bbs

评分

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
. more info on 1point3acres.com请问第一题的思路是什么?

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

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

helloworld00 发表于 2016-11-17 00:58:51 | 显示全部楼层
第一个, 按楼上的方法,先看第一位,然后看小数点位置
. from: 1point3acres.com/bbs
如果第一个数大于或等于返回True,否则返回False

def compareTwostr(str_a, str_b):
        a_flag = False. from: 1point3acres.com/bbs
        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. more info on 1point3acres.com
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                if str_a[index] != str_b[index] and str_b[index] == '.':
                        a_flag = True
                        break

                index += 1

        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;-google 1point3acres
  6.         if(num1[index] == '-' && num2[index] == '-'){
  7.                 minus = true;.1point3acres缃
  8.                 index++;
  9.         }
  10.         else if(num1[index] == '-')
  11.                 return -1;
  12.         else
  13.                 return 1;
    . From 1point 3acres bbs


  14. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  15. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.         while(index < min(num1.length(), num2.length())){
  17.                 if(num1[index] != num2[index] && num1[index] == '.'){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18.                         flag = -1;. 鍥磋鎴戜滑@1point 3 acres
  19.                         point = true;
  20.                         break;.1point3acres缃
  21.                 }
  22.                 else if(num1[index] != num2[index] && num2[index] == '.'){
  23.                         flag =  1;
  24.                         point = true;
  25.                         break;
  26.                 }
  27.                 else if(flag !=0 && num1[index] > num2[index])
  28.                         flag = 1;
  29.                 else if(flag !=0 && num1[index] < num2[index])
  30.                         flag = -1;
  31.                 else;
  32.                 index++;. visit 1point3acres.com for more.
  33.         }
  34.         if(point == false && num1.length() != num2.length())
  35.                 flag = num1.length() > num2.length() ? 1 : -1;
  36.         return minus==true? -flag : flag;

  37. }
    . more info on 1point3acres.com
复制代码
回复 支持 反对

使用道具 举报

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

如果第一个数大于或等于返回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
看起来不错。
“3.0”和“3”呢?
.1point3acres缃
我又改了下, 但是感觉代码有点长, 有没有更好的办法那?
  1. int compare(string num1, string num2){. more info on 1point3acres.com
  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;. visit 1point3acres.com for more.
  8.                 index++;
  9.         }
  10.         else if(num1[index] == '-')-google 1point3acres
  11.                 return -1;
  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;. Waral 鍗氬鏈夋洿澶氭枃绔,
  22.                         point = true;. more info on 1point3acres.com
  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.         }
  32.         if(point == false && num1.length() > num2.length()){
  33.                 if(num1[index++] == '.'){
  34.                         while(index < num1.length()&& num1[index] == '0')
  35.                                 index++;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  36.                         flag = index == num1.length()? 0 : 1;
  37.                 }. 1point 3acres 璁哄潧
  38.                 else
  39.                         flag = 1;
  40.         }. more info on 1point3acres.com
  41.         if(point == false && num1.length() < num2.length()){. visit 1point3acres.com for more.
  42.                 if(num2[index++] == '.'){
  43.                         while(index < num2.length()&& num2[index] == '0'). from: 1point3acres.com/bbs
  44.                                 index++;
  45.                         flag = index == num2.length()? 0 : -1;-google 1point3acres
  46.                 }
  47.                 else
  48.                         flag = -1;. 1point 3acres 璁哄潧
  49.         }

  50.         return minus==true? -flag : flag;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

使用道具 举报

 楼主| asyouknow 发表于 2016-11-17 14:30:08 | 显示全部楼层
zhan1612 发表于 2016-11-17 13:11. 1point3acres.com/bbs
我又改了下, 但是感觉代码有点长, 有没有更好的办法那?
. from: 1point3acres.com/bbs
我不是高手,觉得你写的已经不错了。这题思路很简单,写起来有点烦。
回复 支持 反对

使用道具 举报

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

哇,感谢指出corner case. Waral 鍗氬鏈夋洿澶氭枃绔,
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
确实后面得加个判断

                if not a_flag:. From 1point 3acres bbs
                        index += 1. visit 1point3acres.com for more.
                        while index < len(str_a) and str_a[index] == '0':

                                index += 1
. from: 1point3acres.com/bbs
                        if index == len(str_a):
                                a_flag = True
. 鍥磋鎴戜滑@1point 3 acres

还有正负数的就应该跟前面的一样了
回复 支持 反对

使用道具 举报

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

确实后面得加个判断
. 1point 3acres 璁哄潧
假设同样的数都为True
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| asyouknow 发表于 2016-11-18 14:30:31 | 显示全部楼层
yydcool 发表于 2016-11-17 23:55. more info on 1point3acres.com
楼主最长重复字串是给的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”?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 11:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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