一亩三分地论坛

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

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

Linkedin Intern OA

[复制链接] |试试Instant~ |关注本帖
zhaodaogongzuo 发表于 2016-11-10 09:50:34 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 硕士 实习@Linkedin - 内推 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
刚刚做完OA,题目是给你一个string, 然后长度范围,以及一个m值(表示你的substring里面不同的字母数),然后返回substring的最大频率,比如 ababab, 长度2  - 3, m = 4, 那么最大值3(ab 或者ba)
-google 1point3acres
做得很不好,最后一个case一直超时,把comment删掉了就过了……感觉做得不好,不知道会不会有电面,跪求

评分

1

查看全部评分

Jasonyuan 发表于 2016-11-12 11:21:40 | 显示全部楼层
我能想到的优化就是一次遍历算出2个长度的结果,比如一开始是2,由于你要加一个char,又要减一个char,在你加了一个char以后,你就得到长度为3的了,之后再减掉1个char。这样就可以一次遍历算出2个长度的,不过复杂度还是O(n*length)
回复 支持 1 反对 0

使用道具 举报

 楼主| zhaodaogongzuo 发表于 2016-11-12 02:39:26 | 显示全部楼层
garycheck 发表于 2016-11-11 17:36
还有m是啥呀,如果是不同字母数的话那么ab的m不应该是2嘛
. From 1point 3acres bbs
m是不同字母的上限,如果m是3,那么a, ab, abc都可以

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

say543 发表于 2016-11-10 14:21:39 | 显示全部楼层
这题感觉slicing window 不能做....楼主怎做的? 只想到brute force...
回复 支持 反对

使用道具 举报

 楼主| zhaodaogongzuo 发表于 2016-11-10 14:26:29 | 显示全部楼层
say543 发表于 2016-11-10 14:21
这题感觉slicing window 不能做....楼主怎做的? 只想到brute force...

我用的就是sliding window的brute force,不知道有什么牛逼的解法,但是最后一个case始终过不去,改了又改,最后过了,加了一点comment又过不去了……
回复 支持 反对

使用道具 举报

say543 发表于 2016-11-10 14:34:01 | 显示全部楼层
zhaodaogongzuo 发表于 2016-11-10 14:26
我用的就是sliding window的brute force,不知道有什么牛逼的解法,但是最后一个case始终过不去,改了又 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
slidin window 感覺會少掉一些解....能說說你shrink i 的嗎?  因為長度長的  未必frequency 高?
回复 支持 反对

使用道具 举报

 楼主| zhaodaogongzuo 发表于 2016-11-10 14:37:51 | 显示全部楼层
say543 发表于 2016-11-10 14:34
slidin window 感覺會少掉一些解....能說說你shrink i 的嗎?  因為長度長的  未必frequency 高?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我是在长度一定的情况下用sliding window,然后遍历长度范围
回复 支持 反对

使用道具 举报

say543 发表于 2016-11-10 15:37:49 | 显示全部楼层
zhaodaogongzuo 发表于 2016-11-10 14:37
我是在长度一定的情况下用sliding window,然后遍历长度范围
. visit 1point3acres.com for more.
所以假设string length is 2 to 3. 每一个length都做一次sliding window吗? 2做一次 3做一次 求讨论...
回复 支持 反对

使用道具 举报

 楼主| zhaodaogongzuo 发表于 2016-11-11 01:36:59 | 显示全部楼层
say543 发表于 2016-11-10 15:37
所以假设string length is 2 to 3. 每一个length都做一次sliding window吗? 2做一次 3做一次 求讨论...

我是这样的,这样感觉效率不高,最开始想着从0开始,然后长度变化2-3,也就是
for(int i = 0; i < s.length(); i++) {
     for(int len = 2; len <= 3 ; len++) {
..........
}
}
. Waral 鍗氬鏈夋洿澶氭枃绔,感觉写起来有点麻烦,就没这样写了
回复 支持 反对

使用道具 举报

say543 发表于 2016-11-11 15:34:26 | 显示全部楼层
zhaodaogongzuo 发表于 2016-11-11 01:36-google 1point3acres
我是这样的,这样感觉效率不高,最开始想着从0开始,然后长度变化2-3,也就是
for(int i = 0; i < s.len ...

. From 1point 3acres bbs
这就是我的想法 那楼主不是这样写的吗? 能给个伪代码?  thanks
回复 支持 反对

使用道具 举报

 楼主| zhaodaogongzuo 发表于 2016-11-11 16:02:55 | 显示全部楼层
say543 发表于 2016-11-11 15:34
这就是我的想法 那楼主不是这样写的吗? 能给个伪代码?  thanks

. Waral 鍗氬鏈夋洿澶氭枃绔,我不是哈,我是反过来了,先遍历len,在遍历string, 这个比较慢
回复 支持 反对

使用道具 举报

garycheck 发表于 2016-11-11 17:23:51 | 显示全部楼层
求问是不是可以重复提交多次,只要限时内每个case都过了就好了呀
回复 支持 反对

使用道具 举报

garycheck 发表于 2016-11-11 17:29:33 | 显示全部楼层
以及为啥是ba呢,ba不是只出现了2次吗
回复 支持 反对

使用道具 举报

garycheck 发表于 2016-11-11 17:36:23 | 显示全部楼层
还有m是啥呀,如果是不同字母数的话那么ab的m不应该是2嘛
回复 支持 反对

使用道具 举报

garycheck 发表于 2016-11-12 05:11:15 | 显示全部楼层
zhaodaogongzuo 发表于 2016-11-12 02:39
m是不同字母的上限,如果m是3,那么a, ab, abc都可以
.鐣欏璁哄潧-涓浜-涓夊垎鍦
谢谢!LZ sliding window 的时候是怎么数不同字母个数的呀. 1point3acres.com/bbs
我的想法是对于一个特定的len,sliding window 循环n-len次, 然后建一个map,每次slide的时候加入一个新字母,减掉一个老字母,然后map的size就是不同字母个数,这样总时间是O(n*len) 这样的复杂度还是超时的嘛
回复 支持 反对

使用道具 举报

 楼主| zhaodaogongzuo 发表于 2016-11-12 05:15:08 | 显示全部楼层
garycheck 发表于 2016-11-12 05:11
谢谢!LZ sliding window 的时候是怎么数不同字母个数的呀
我的想法是对于一个特定的len,sliding window ...

我就是这样做的……最开始写了一个函数专门去算制定长度,结果最后一个case超时,然后把这个函数直接全部写在一起,没有超时了,打算加一写comment,结果又超时了……我就直接把comment删掉交了……想不出什么办法优化了
回复 支持 反对

使用道具 举报

 楼主| zhaodaogongzuo 发表于 2016-11-12 14:12:31 | 显示全部楼层
Jasonyuan 发表于 2016-11-12 11:21
我能想到的优化就是一次遍历算出2个长度的结果,比如一开始是2,由于你要加一个char,又要减一个char,在你 ...
. From 1point 3acres bbs
我也这么想过,但是当时不想改了,看case都过了,就提交了
回复 支持 反对

使用道具 举报

格格笑 发表于 2016-11-13 14:10:17 | 显示全部楼层
感觉目前看到的方法(包括我所想的)  根本就是以不同长度  为一轮来穷举.....  2—4 长度  10 个字母的strig  就是  (4-2+1)* 10  然后除此之外还要遍历不同长度的 字符串段 看他们满足不满足  distinct char < M
的要求,满足就全加到hashmap里...    有没有好一点的解法
回复 支持 反对

使用道具 举报

say543 发表于 2016-11-13 14:55:19 | 显示全部楼层
Jasonyuan 发表于 2016-11-12 11:21
我能想到的优化就是一次遍历算出2个长度的结果,比如一开始是2,由于你要加一个char,又要减一个char,在你 ...

. 1point3acres.com/bbs
我照这想法coding 了一下但是有些不懂我猜你是assume length is [2,4] maintain一个winodw if window length 在2-4 间check distinct character 然后用hashMap<String, Fr​​equency> 纪录一旦window > 4 shrink window 直到window length 2-1 这些过程中每走一步either window length 增加or window length 减少都要check是否distinct和length 都要符合如果符合就要纪录这样思考对吗 ?
回复 支持 反对

使用道具 举报

Jasonyuan 发表于 2016-11-13 23:14:27 | 显示全部楼层
我昨天做oa刚好又遇到这题。。我是每次循环计算出2个长度的,比如一开始2,因为sliding window是要加一个char再减一个char的,加了一个char后,先判断长度是不是小于上限并且满足要求,是的话就加入到hash map里。因为你第一次算得是2,3长度,第二次会算4,5长度,而5是不满足的,一个循环里长的那个要判断长度。实测不会超时。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 12:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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