一亩三分地论坛

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

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

9月4号google电面【已挂】

[复制链接] |试试Instant~ |关注本帖
discoveryi 发表于 2015-9-11 11:38:58 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 本科 全职@Google - 内推 - 技术电面 |Fail在职跳槽

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

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

x
楼主我连续2年倒在google电面上了,希望明年能拿到onsite。哎!. from: 1point3acres.com/bbs

题目要求如下:输入: List<String>,int minDistance
要求:输出任意permutation使得List中的相同element的间距要小于minDistance。
. more info on 1point3acres.com

例1:
输入:[B, E, A, C, D, F, F],2  
输出:[B, F, A, C, D, E, F]


例2:
输入:[A, B, B],1
输出:[A, B, B]


例3:
输入:[A, B, B],2  
输出:[B, A, B]


. 1point3acres.com/bbs

补充内容 (2015-9-11 12:31):
it's ok if 两个相同element的index间距 >= minDistance

补充内容 (2015-9-11 12:37):
不好意思之前题目敲错了,以下的是正确的: 输出任意permutation使得List中的相同element的间距要大于minDistance。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

mint0715 发表于 2015-9-15 06:23:12 | 显示全部楼层
夜行码农耗子 发表于 2015-9-15 06:15
确定吗?AAABBBCDE MinDis=3
-google 1point3acres
补充内容 (2015-9-15 06:16):

一开始A3 B3 C1 D1 E1
找最大的三个:ABC
之后A2 B2 D1 E1. from: 1point3acres.com/bbs
最大的三个加入:ABCABD
之后A1 B1 E1
ABCABDABE

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

kelvinzhong 发表于 2015-9-16 11:27:30 | 显示全部楼层
第一题我写了个C++ code, 亲测可用

  1. string Mindist(string s, int min_dist) {
  2.         map<char, int> table;
  3.         for (int i = 0; i < s.length(); i ++) {
  4.                 if (table.find(s[i]) == table.end()) {
  5.                         table[s[i]] = 1;
  6.                 } else {
  7.                         table[s[i]] ++;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8.                 }
  9.         }

  10.         auto it = table.rbegin();
  11.         if (it->second > s.length() / min_dist + 1)
  12.                 return "No Solution";. from: 1point3acres.com/bbs

  13.         string ret = s;
  14.         for (int j = 0; j < min_dist; j ++) {
  15.                 for (int i = 0; i <= s.length() / min_dist; i ++) {
  16.                         if (j + i * min_dist >= s.length()) {
  17.                                 break;
  18.                         }
  19.                         if (it->second == 0) {
  20.                                 it ++;
  21.                         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  22.                         ret[j + i * min_dist] = it->first;-google 1point3acres
  23.                         it->second --;
  24.                 }       
  25.         }
  26.         return ret;
  27. }

  28. void test() {
  29.         string s = "BEACDFF";. Waral 鍗氬鏈夋洿澶氭枃绔,
  30.         cout << Mindist(s, 2) << endl;
  31.         s = "ABB";. from: 1point3acres.com/bbs
  32.         cout << Mindist(s, 1) << endl;
  33.         cout << Mindist(s, 2) << endl;. from: 1point3acres.com/bbs
  34. }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
复制代码
回复 支持 2 反对 0

使用道具 举报

zxy_snow 发表于 2015-9-13 14:36:05 | 显示全部楼层
mint0715 发表于 2015-9-13 14:25
对你发现问题了,直接贪心从高频隔d挨个放进去是错的
所以请看里面下面的评论。

http://articles.leetcode.com/201 ... hone-interview.html
. from: 1point3acres.com/bbs
这里的解法貌似是对的。
我按照这个解法写了一遍,生成了几万个样例验证了下,没出错。。
回复 支持 1 反对 0

使用道具 举报

wenqiang88 发表于 2015-9-11 21:39:32 | 显示全部楼层
可以先统计每个String出现的频率,然后存到一个max heap里。然后用一个map纪录每个string上一次出现的时间。
每次pop最大的,看满不满足距离上一次大于minDis。如果满足就加进去,否则就继续pop,直到找到一个满足的或者heap为空。记得把这些pop的元素存到一个list里然后add回去。
回复 支持 1 反对 0

使用道具 举报

mint0715 发表于 2015-9-13 06:37:28 | 显示全部楼层
回复 支持 1 反对 0

使用道具 举报

hulahu 发表于 2015-9-11 12:04:35 | 显示全部楼层
楼主, 是大于, 还是小于? 如果是小的话,. from: 1point3acres.com/bbs
例3:
输入:[A, B, B],2 ==》[A, B, B]这也valid吧?
回复 支持 反对

使用道具 举报

 楼主| discoveryi 发表于 2015-9-11 12:30:56 | 显示全部楼层
hulahu 发表于 2015-9-11 12:04
楼主, 是大于, 还是小于? 如果是小的话,.1point3acres缃
例3:
.鐣欏璁哄潧-涓浜-涓夊垎鍦输入:[A, B, B],2 ==》[A, B, B]这也valid吧?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
it's ok if 两个相同element的index间距 >= minDistance
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-11 12:35:11 | 显示全部楼层
hulahu 发表于 2015-9-11 12:04
楼主, 是大于, 还是小于? 如果是小的话,
例3:
输入:[A, B, B],2 ==》[A, B, B]这也valid吧?

觉得是大于...
回复 支持 反对

使用道具 举报

 楼主| discoveryi 发表于 2015-9-11 12:37:05 | 显示全部楼层
输出任意permutation使得List中的相同element的间距要大于minDistance。
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-11 13:13:23 | 显示全部楼层
discoveryi 发表于 2015-9-11 12:37. Waral 鍗氬鏈夋洿澶氭枃绔,
输出任意permutation使得List中的相同element的间距要大于minDistance。

LZ 我的解法式先统计character 的出现次数出现次数最高的代表我至少要有几个parts 然后再根据次数从高到小填. 最后check 是不是每个row(除了最后一个row) 满足条件如果满足答案get 如果不满足表示没有解
这样能解吗? 欢迎讨论. 1point 3acres 璁哄潧
ex: aaa, bb cc
m = 3. more info on 1point3acres.com
a b c
a b
a c
(X) fail

m= 2
a b c
a b
a c
(O)
回复 支持 反对

使用道具 举报

 楼主| discoveryi 发表于 2015-9-11 13:46:31 | 显示全部楼层
say543 发表于 2015-9-11 13:13. 1point3acres.com/bbs
LZ 我的解法式先统计character 的出现次数出现次数最高的代表我至少要有几个parts 然后再根据次数从高到 ...

总的来说,认为你的思路是正确的,不过有两个问题。

一问:为什么(除了最后一个row)不check?
二问:那你怎么写check function保证每个相同element的index间距都大于minDistance?


.1point3acres缃补充内容 (2015-9-11 14:42):
想了想,你是不是离题了,但是LZ判断的char而不是String,所以要统计每个String出现的次数。
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-12 00:03:26 | 显示全部楼层
应该是只要最高频的可以满足 就有解 否则无解 最高频的是否满足取决于 (k-1)*minDistance < size of list
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-12 00:16:08 | 显示全部楼层
flexwang 发表于 2015-9-12 00:03
应该是只要最高频的可以满足 就有解 否则无解 最高频的是否满足取决于 (k-1)*minDistance < size of list

有道理。如果满足的话,怎么样返回这个permutation比较快呢?
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-12 00:21:09 | 显示全部楼层
wenqiang88 发表于 2015-9-12 00:16
有道理。如果满足的话,怎么样返回这个permutation比较快呢?

感觉应该先把最高频的每个MinDist个就填一个 剩下的慢慢填就行了 我想下code怎么写
回复 支持 反对

使用道具 举报

huanghe0828 发表于 2015-9-12 01:45:06 | 显示全部楼层
这题类似的以前没遇到过的话 面试当场要想通确实挺难的
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-12 02:09:58 | 显示全部楼层
flexwang 发表于 2015-9-12 00:21. visit 1point3acres.com for more.
感觉应该先把最高频的每个MinDist个就填一个 剩下的慢慢填就行了 我想下code怎么写
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
感觉还是要用heap
回复 支持 反对

使用道具 举报

edna 发表于 2015-9-13 01:37:58 | 显示全部楼层
首先判断有没有合法输出,只要比较最高频出现的次数t,要求的间隔k,和总长度n之间是否满足n > (t-1)*k就可以了。

打印结果的话,可以先申请一个长度为n的,然后按照高频往低频打印,如果当前位置已经被占,就往后挪一位。

感觉这种方式打印效率略低,有没有更高的方法?

无论如何,电面问这个,有点变态啊。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

补充内容 (2015-9-13 01:40):
这个打印方式有点趋向于greedy,暂时没想到更好的。
回复 支持 反对

使用道具 举报

edna 发表于 2015-9-13 06:44:43 | 显示全部楼层
mint0715 发表于 2015-9-13 06:37
http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-become-at-least-d-distan ...
. 1point3acres.com/bbs
对这个到处都能碰到原题的世界无奈了,这以后面试就是比谁看的多么,通刷CC150, geeksforgeeks,leetcode,lintcode...
回复 支持 反对

使用道具 举报

mint0715 发表于 2015-9-13 07:01:00 | 显示全部楼层
edna 发表于 2015-9-13 06:44
对这个到处都能碰到原题的世界无奈了,这以后面试就是比谁看的多么,通刷CC150, geeksforgeeks,leetcod ...

我挂过这道题,所以挂完查了一下。
回复 支持 反对

使用道具 举报

 楼主| discoveryi 发表于 2015-9-13 07:23:33 | 显示全部楼层
mint0715 发表于 2015-9-13 06:37. Waral 鍗氬鏈夋洿澶氭枃绔,
http://www.geeksforgeeks.org/rearrange-a-string-so-that-all-same-characters-become-at-least-d-distan ...

我的天啊,居然是原题。谢谢你挖出来!
这么看来面试官看来还是对我很厚道的了?
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-13 10:31:11 | 显示全部楼层
discoveryi 发表于 2015-9-11 13:46. from: 1point3acres.com/bbs
总的来说,认为你的思路是正确的,不过有两个问题。

一问:为什么(除了最后一个row)不check?

回答
1. 因为第i row 只要check 和i+1 row 的关西所以最后一个row 不用check 这样就可以保证条件都成立
2. 我这边是assume都会有解然后这个算法保证找到的解是valid的
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
恩 是该想想怎么写checking function...

这边是string or char我觉得没有差别
回复 支持 反对

使用道具 举报

edna 发表于 2015-9-13 11:03:36 | 显示全部楼层
say543 发表于 2015-9-11 13:13
LZ 我的解法式先统计character 的出现次数出现次数最高的代表我至少要有几个parts 然后再根据次数从高到 ...

第一个例子是错的啊,如果是aaa, bb, cc然后间距是3,那么abcabca是合法的,但是你这个返回了个fail?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 01:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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