一亩三分地论坛

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

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

Google暑期实习电面

[复制链接] |试试Instant~ |关注本帖
oneselfZhu 发表于 2015-10-24 07:02:35 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Google - 校园招聘会 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
两轮紧靠着的电面,都是直接上来就问问题,简历一句话都没问,现在招实习都那么直接吗
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第一轮是中国小哥,问题是 给定一个9位的键盘,

1 2 3. From 1point 3acres bbs
4 5 6
7 8 9
只有中间没有其他键的两个键才能相连,比如1可以连 2 4 5 6 8 但不能连 3 7 9 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
但是如果中间键被使用了,那就可以连,比如5已经被使用了,那1就可以连9
每个键只能用一次,给定一个长度L,求问有多少unique path with length L

中国小哥人很好,循循善诱,见我卡住了就说先写brute force吧,然后再提示说用回溯法
. 1point3acres.com/bbs
第二轮听口音应该是美国人. Waral 鍗氬鏈夋洿澶氭枃绔,
1. 给定一个函数 boolean isWord(string s),可以判断这个字符串是否是一个合法的英语词汇
然后给一个初始的字符串s,只能对它做删除字母的操作,求问最长的合法的英语词汇
.1point3acres缃
2. 输入一个数组,输出和【0,99】之间的gap,leetcode原题

3. 输入一个二进制int, 两个digit之间交换位置
比如 01010011 交换之后就变成 10100011
0和1交换 0和1交换 0和0交换 1和1交换

总体并不是很难,只是我太菜, 当为接下来其他面试攒经验和rp吧~
. 1point 3acres 璁哄潧

评分

2

查看全部评分

echo33 发表于 2015-12-13 03:14:25 | 显示全部楼层
第一题是分成[1,3,7,9], [2,4,6,8],[5]三种键吗

ls的好像不太对,即使你加上visited

得给每个数字加个obstacle 比如1:[2:3,4:7,5:9] 如果prefix里已经有某个数字e.g.2就可以连对应的那个数字 e.g.3了
回复 支持 1 反对 0

使用道具 举报

wbsnt 发表于 2015-10-24 09:16:50 | 显示全部楼层
为什么说自己菜,有结果了么
回复 支持 反对

使用道具 举报

kyle3782 发表于 2015-10-24 09:57:45 | 显示全部楼层
谢谢楼主分享!
回复 支持 反对

使用道具 举报

xin_gator 发表于 2015-10-27 09:15:12 | 显示全部楼层
谢谢分享~祝你好运呀!!加油!
回复 支持 反对

使用道具 举报

nuanuan1208 发表于 2015-10-27 23:19:13 | 显示全部楼层
请教下楼长第一轮那题是只需要count,还是print out all unique path?除了DFS有什么好方法吗?
回复 支持 反对

使用道具 举报

翔在天空 发表于 2015-10-30 13:14:37 | 显示全部楼层
请问第一题什么意思,不太懂
回复 支持 反对

使用道具 举报

Augustus 发表于 2015-11-16 08:30:31 | 显示全部楼层
第一题啥意思?能具体讲下马,看不懂。。。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-7 08:41:02 | 显示全部楼层
写了下第一题,不太确定是不是正解,欢迎指教
  1. public class KeyboardUniquePath {

  2.         private int count = 0;
  3.         public int getNumberOfKeyboardUniquePath(int n) {
  4.                 if (n <= 0) {
  5.                         return 0;.1point3acres缃
  6.                 }
  7.                 String[] map = {"24568", "1345679", "24567", "1235789", "12346789", "12356789", "24568", "1345679", "24568"};
  8.                 helper(map, new StringBuilder(), n, "123456789");
  9.                 return count;
  10.         }
  11.         private void helper(String[] map, StringBuilder sb, int n, String choices) {
  12.                 if (sb.length() == n) {
  13.                         count++;. Waral 鍗氬鏈夋洿澶氭枃绔,
  14.                         return;
  15.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  16.                 for (int i = 0; i < choices.length(); i++) {
  17.                         char c = choices.charAt(i);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  18.                         sb.append(c);
  19.                         helper(map, sb, n, map[(int)(c - '1')]);
  20.                         sb.deleteCharAt(sb.length() - 1);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  21.                 }
  22.         }
  23.        
  24.         public static void main(String[] args) {
  25.                 KeyboardUniquePath su = new KeyboardUniquePath();
  26.                 System.out.println(su.getNumberOfKeyboardUniquePath(1));.鐣欏璁哄潧-涓浜-涓夊垎鍦
  27.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  28. }
复制代码

补充内容 (2015-12-7 23:16):
如果不能有重复数字的话,加一个if (sb.toString().contains(String.valueOf(c))) continue;就行了,因为最多9个数字,所以这儿也是contant的时间
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-7 08:42:29 | 显示全部楼层
请问楼主这个求问最长的合法的英语词汇是怎么做的?
回复 支持 反对

使用道具 举报

jefferyy 发表于 2015-12-7 12:56:29 | 显示全部楼层
bobzhang2004 发表于 2015-12-7 08:41
写了下第一题,不太确定是不是正解,欢迎指教

这个貌似没有处理一个键只能用一次
应该加一个 visited hashset, 如果已经出现 跳过
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-7 23:16:34 | 显示全部楼层
jefferyy 发表于 2015-12-7 12:56
这个貌似没有处理一个键只能用一次. more info on 1point3acres.com
应该加一个 visited hashset, 如果已经出现 跳过

如果不能有重复数字的话,加一个if (sb.toString().contains(String.valueOf(c))) continue;就行了,因为最多9个数字,所以这儿也是contant的时间
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-10 09:11:01 | 显示全部楼层
求问楼主 第二轮最后一题怎么做的呢? 考Bit嘛?
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-12-11 11:21:18 | 显示全部楼层
bobzhang2004 发表于 2015-12-7 08:41.鐣欏璁哄潧-涓浜-涓夊垎鍦
写了下第一题,不太确定是不是正解,欢迎指教

求出来是多少,比10**4大吗
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-11 12:48:10 | 显示全部楼层
aiweiwei 发表于 2015-12-11 11:21
求出来是多少,比10**4大吗
. 1point 3acres 璁哄潧
这个不是跟len有关吗?得看输入的长度是多少吧?

补充内容 (2015-12-11 12:48):
如果是9的话,就是35928
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-12-12 00:14:27 | 显示全部楼层
第一题感觉要处理特殊情况,基本每个数字都要处理一下,类似如下的感觉
if pre == '1':. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                if 2 in visited and curr == 3:
                    continue. From 1point 3acres bbs
                if 4 in visited and curr == 7:
                    continue
                if 5 in visited and curr == 9:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                    continue. 鍥磋鎴戜滑@1point 3 acres
            if pre == '2':. Waral 鍗氬鏈夋洿澶氭枃绔,
                if 5 in visited and curr == 8:
                    continue                    
            if pre == '3':
                if 2 in visited and curr == 1:-google 1point3acres
                    continue
                if 5 in visited and curr == 7:
                    continue
                if 6 in visited and curr == 9:. 1point 3acres 璁哄潧
                    continue                    
            if pre == '4':
                if 5 in visited and curr == 6:
                    continue              
            if pre == '6':. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                if 5 in visited and curr == 4:
                    continue                 
            if pre == '7':
                if 8 in visited and curr == 9:-google 1point3acres
                    continue
                if 4 in visited and curr == 1:
                    continue
                if 5 in visited and curr == 3:
                    continue               
            if pre == '8':
                if 8 in visited and curr == 2:
                    continue               
            if pre == '9':
                if 8 in visited and curr == 7:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                    continue.鐣欏璁哄潧-涓浜-涓夊垎鍦
                if 6 in visited and curr == 3: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                    continue
                if 5 in visited and curr == 1:-google 1point3acres
                    continue           

第一题写了60行了,感觉挺麻烦的
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-12-12 00:27:45 | 显示全部楼层
输出和【0,99】之间的gap 这题是是哪题啊,求问能给个link或者题目名字不~~~  :)
回复 支持 反对

使用道具 举报

ohyline 发表于 2015-12-12 18:05:27 | 显示全部楼层
aiweiwei 发表于 2015-12-12 00:27. more info on 1point3acres.com
输出和【0,99】之间的gap 这题是是哪题啊,求问能给个link或者题目名字不~~~  :)

Missing Ranges
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-12-12 22:26:24 | 显示全部楼层

看到,多谢!
回复 支持 反对

使用道具 举报

snooze 发表于 2015-12-27 17:25:59 | 显示全部楼层
哈哈 第一题其实就是安卓系统的画图解锁
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 03:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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