📣 独立日限时特惠: VIP通行证立减$68
楼主: discoveryi
跳转到指定楼层
上一主题 下一主题
收起左侧

9月4号google电面【已挂】

🔗
gp89757 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 | 只看该作者
全局:
gp89757 发表于 2015-9-12 00:21
感觉应该先把最高频的每个MinDist个就填一个 剩下的慢慢填就行了 我想下code怎么写

感觉还是要用heap
回复

使用道具 举报

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

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

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

无论如何,电面问这个,有点变态啊。

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

使用道具 举报

🔗
mint0715 2015-9-13 06:37:28 | 只看该作者
回复

使用道具 举报

🔗
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 ...

对这个到处都能碰到原题的世界无奈了,这以后面试就是比谁看的多么,通刷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
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
总的来说,认为你的思路是正确的,不过有两个问题。

一问:为什么(除了最后一个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?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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