一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 3215|回复: 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,问了问问题就结束了。

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

两个人都很nice。第二个人还挺喜欢我,但题太简单还完成得很慢,估计跪了。提高实力,来年再战!. 鍥磋鎴戜滑@1point 3 acres
. from: 1point3acres.com/bbs
. From 1point 3acres bbs

评分

3

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

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

楼主加油
回复 支持 反对

使用道具 举报

 楼主| 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 | 显示全部楼层
第一个, 按楼上的方法,先看第一位,然后看小数点位置. Waral 鍗氬鏈夋洿澶氭枃绔,
.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果第一个数大于或等于返回True,否则返回False

def compareTwostr(str_a, str_b):
        a_flag = False.1point3acres缃
        index = 0
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        if str_a[0] > str_b[0]:
                a_flag = True
. Waral 鍗氬鏈夋洿澶氭枃绔,
        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. Waral 鍗氬鏈夋洿澶氭枃绔,
                        break

                index += 1.鏈枃鍘熷垱鑷1point3acres璁哄潧

        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;. from: 1point3acres.com/bbs
  12.         else. 1point3acres.com/bbs
  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]).鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.                 flag = num1.length() > num2.length() ? 1 : -1;
  34.         return minus==true? -flag : flag;-google 1point3acres

  35. } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
复制代码
回复 支持 反对

使用道具 举报

 楼主| asyouknow 发表于 2016-11-17 12:49:53 | 显示全部楼层
helloworld00 发表于 2016-11-17 00:58.鐣欏璁哄潧-涓浜-涓夊垎鍦
第一个, 按楼上的方法,先看第一位,然后看小数点位置

如果第一个数大于或等于返回True,否则返回False ...
. visit 1point3acres.com for more.
如果是“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”呢?
. 1point 3acres 璁哄潧
我又改了下, 但是感觉代码有点长, 有没有更好的办法那?
  1. int compare(string num1, string num2){
  2.         int flag = 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.         int index = 0;. Waral 鍗氬鏈夋洿澶氭枃绔,
  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;
  12.         else
  13.                 return 1;. Waral 鍗氬鏈夋洿澶氭枃绔,
  14. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  15.         while(index < min(num1.length(), num2.length())){
  16.                 if(num1[index] != num2[index] && num1[index] == '.'){
  17.                         flag = -1;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18.                         point = true;
  19.                         break;
  20.                 }
  21.                 else if(num1[index] != num2[index] && num2[index] == '.'){
  22.                         flag =  1;
  23.                         point = true;
  24.                         break;
  25.                 }
  26.                 else if(flag !=0 && num1[index] > num2[index])
  27.                         flag = 1;
  28.                 else if(flag !=0 && num1[index] < num2[index])
  29.                         flag = -1;
  30.                 else;
  31.                 index++;
  32.         }
  33.         if(point == false && num1.length() > num2.length()){. 鍥磋鎴戜滑@1point 3 acres
  34.                 if(num1[index++] == '.'){
  35.                         while(index < num1.length()&& num1[index] == '0'). from: 1point3acres.com/bbs
  36.                                 index++;
  37.                         flag = index == num1.length()? 0 : 1;
  38.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  39.                 else
  40.                         flag = 1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  41.         }
  42.         if(point == false && num1.length() < num2.length()){
  43.                 if(num2[index++] == '.'){
  44.                         while(index < num2.length()&& num2[index] == '0')
  45.                                 index++;
  46.                         flag = index == num2.length()? 0 : -1;
  47.                 }
  48.                 else. From 1point 3acres bbs
  49.                         flag = -1;
  50.         }

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

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

使用道具 举报

 楼主| 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
如果是“3.0”和“3”有些问题吧
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
哇,感谢指出corner case

确实后面得加个判断
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                if not a_flag:
                        index += 1. 鍥磋鎴戜滑@1point 3 acres
                        while index < len(str_a) and str_a[index] == '0':

                                index += 1

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


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

使用道具 举报

helloworld00 发表于 2016-11-17 19:48:12 | 显示全部楼层
helloworld00 发表于 2016-11-17 19:46. visit 1point3acres.com for more.
哇,感谢指出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 下一条

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

custom counter

GMT+8, 2017-5-1 11:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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