一亩三分地论坛

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

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

发一个迟到的g家面经,offer

[复制链接] |试试Instant~ |关注本帖
jyzzxcvb 发表于 2016-10-12 10:07:51 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - Onsite |Passfresh grad应届毕业生

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

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

x
欠地里的Google面经。Timeline在报offer的帖子里。想了一下(其实都写好了)还是不post完整的面经了。签了nda,怕。毕竟fb拒了这个是唯一的offer了。其他三轮包括加面2轮都是lc或者地里面经有过的,觉得都是medium,下面这个算我面的比较难的了。我的面试官都是美国小哥或者国人小哥,没有过烙印, 题都答上来了。下面这道题面经里我没见过
有一些string 比如 “ata”,“tat”,“ata”他们仨可以组成一个square. from: 1point3acres.com/bbs

ata
tat
ata

让第1,2,3行和第1,2,3列分别相等。. from: 1point3acres.com/bbs
上面的例子是长度为3的,这样的square可以由n个长度为n的string组成。
Input是很多string,长度不等(要自己问出来)。然后返回所有的square. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Output形式比如vector<vector<string>>


评分

2

查看全部评分

本帖被以下淘专辑推荐:

weihu816 发表于 2016-10-14 15:31:15 | 显示全部楼层
  1. public List<List<String>> getSquares(List<Integer> strs, int len) {
  2.         List<List<String>> result = new ArrayList<>();
  3.         List<String> cur = new ArrayList<>();
  4.         for (int i = 0; i < len; i++) cur.add("");
  5.         dfs(result, cur);
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  6.         return result;
  7.     }
  8. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.     public void dfs(List<List<String>> result, List<String> cur) {. from: 1point3acres.com/bbs
  10.         int m = cur.size(), n = cur.get(m-1).length();
  11.         if (m == n) {
  12.             result.add(new ArrayList<>(cur));
  13.             return;
  14.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  15.         String pre = cur.get(n);
  16.         List<String> list = getStrsByPrefix(cur.get(n), m); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  17.         for (String next : list) {
  18.             cur.set(n, pre + next);
  19.             for (int i = n + 1; i < m; i++) {
  20.                 cur.set(i, cur.get(i).substring(0, n) + next.charAt(i - n));
  21.             }
  22.             dfs(result, cur);
  23.         }. 鍥磋鎴戜滑@1point 3 acres
  24.     }
  25.     public List<String> getStrsByPrefix(String prefix, int len) {...}
  26.     public static void main(String[] args) {
  27.         System.out.println((new SquareTrie().getSquares(null, 3)));
  28.     }
复制代码
回复 支持 1 反对 0

使用道具 举报

william_gong 发表于 2016-10-12 10:12:36 | 显示全部楼层
dfs加剪枝?还是要用trie?
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-12 10:39:02 | 显示全部楼层
啊 这个在电面面经里见过 Word square 是dfs按行找下一个单词吗?
回复 支持 反对

使用道具 举报

 楼主| jyzzxcvb 发表于 2016-10-12 11:22:27 | 显示全部楼层
william_gong 发表于 2016-10-12 10:12
dfs加剪枝?还是要用trie?

都要吧 我想了没到30秒面试官就不耐烦的提示 trie了 虽然他没说这个词 需要一个function返回某prefix某长度的所有string
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-10-12 11:24:06 | 显示全部楼层
用trie写起来好麻烦啊。。。楼主一轮能写完这么多代码,真强
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2016-10-13 02:20:42 | 显示全部楼层
jyzzxcvb 发表于 2016-10-11 22:22.鐣欏璁哄潧-涓浜-涓夊垎鍦
都要吧 我想了没到30秒面试官就不耐烦的提示 trie了 虽然他没说这个词 需要一个function返回某prefix某长 ...

如果所求正方形条件是让第1,2,3行和第1,2,3列分别相等。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
那么:
abcd
bche
chef
defg
应该也符合对吧. from: 1point3acres.com/bbs
换句话说,也就是要求矩阵沿着左上到右下的对角线完全对称。
然后沿着矩形DFS看最大能找到多大的符合条件的矩形。
我还没想通怎么用trie。请指教.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2016-10-12 13:24):
(⊙o⊙)哦,不好意思我没理解透,原来是要返回所有的square
回复 支持 反对

使用道具 举报

 楼主| jyzzxcvb 发表于 2016-10-13 10:00:06 | 显示全部楼层
alucardzhou 发表于 2016-10-13 02:20
. from: 1point3acres.com/bbs 如果所求正方形条件是让第1,2,3行和第1,2,3列分别相等。
那么:
abcd

是啊 是啊 input都是string 代表一行
回复 支持 反对

使用道具 举报

 楼主| jyzzxcvb 发表于 2016-10-13 10:01:07 | 显示全部楼层
william_gong 发表于 2016-10-12 11:24. from: 1point3acres.com/bbs
用trie写起来好麻烦啊。。。楼主一轮能写完这么多代码,真强
.1point3acres缃
哦哈哈 忘了说trie我刚要提笔写他让我定义每个function头就行了
回复 支持 反对

使用道具 举报

hjx447297354 发表于 2016-10-13 13:16:41 | 显示全部楼层
请问楼主是在哪里面的?谢谢~
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2016-10-13 23:47:30 | 显示全部楼层
jyzzxcvb 发表于 2016-10-12 21:01
哦哈哈 忘了说trie我刚要提笔写他让我定义每个function头就行了


好贴心
回复 支持 反对

使用道具 举报

 楼主| jyzzxcvb 发表于 2016-10-13 23:54:32 | 显示全部楼层
hjx447297354 发表于 2016-10-13 13:16
请问楼主是在哪里面的?谢谢~
.鐣欏璁哄潧-涓浜-涓夊垎鍦
mtv,忘了说了
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-15 00:20:33 | 显示全部楼层
用不用考虑string长度不一样的情况?比如
“abcd,
bnr,
cr,
d”. more info on 1point3acres.com
回复 支持 反对

使用道具 举报

 楼主| jyzzxcvb 发表于 2016-10-15 03:24:38 | 显示全部楼层
chestnut9919 发表于 2016-10-15 00:20
用不用考虑string长度不一样的情况?比如. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
“abcd,
bnr,

不用 那样不能组成square吧 相等长度的之间
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-15 05:07:09 | 显示全部楼层
jyzzxcvb 发表于 2016-10-15 03:24
不用 那样不能组成square吧 相等长度的之间

那这个还简单一点 之前看电面有人考这个是要考虑不等长string的 不过我只想到dfs 每次找正确的prefix的string trie是怎么做啊?
回复 支持 反对

使用道具 举报

 楼主| jyzzxcvb 发表于 2016-10-15 05:09:39 | 显示全部楼层
chestnut9919 发表于 2016-10-15 05:07. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
那这个还简单一点 之前看电面有人考这个是要考虑不等长string的 不过我只想到dfs 每次找正确的prefix的st ...

诶 我不太确定你的意思,就是比如说第一个string是四个char,那下三个都是4个的,不用一行又两个string来凑  input是各种不同长度的string
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-15 05:29:59 | 显示全部楼层
jyzzxcvb 发表于 2016-10-15 05:09
诶 我不太确定你的意思,就是比如说第一个string是四个char,那下三个都是4个的,不用一行又两个string来 ...

就是每行长度可以不一样,不是两个string凑得,就比如 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
abcd. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
bnr
cr. Waral 鍗氬鏈夋洿澶氭枃绔,
d
这样也算有效的。只要第一行和第一列一样,第二行和第二列一样等等 就可以
回复 支持 反对

使用道具 举报

 楼主| jyzzxcvb 发表于 2016-10-15 05:31:15 | 显示全部楼层
chestnut9919 发表于 2016-10-15 05:29. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
就是每行长度可以不一样,不是两个string凑得,就比如
abcd. 鍥磋鎴戜滑@1point 3 acres
bnr

好可怕 不是这样 或者就是我答得慢他没来得及问
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-10-16 08:06:10 | 显示全部楼层
感谢分享,关注下。。
回复 支持 反对

使用道具 举报

steveguang 发表于 2016-10-16 09:09:06 | 显示全部楼层
楼主能否讲下dfs+trie的思路?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 16:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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