一亩三分地论坛

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

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

[找工就业] coursera OA面经 8.31

[复制链接] |试试Instant~ |关注本帖
wszk1992 发表于 2016-9-1 04:33:22 | 显示全部楼层 |阅读模式

2017(10-12月)-[]CE硕士+fresh grad 无实习/全职 - 网上海投| 码农类全职@Courserafresh grad应届毕业生

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

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

x
一共两道题:1. 返回一个string的所有substring按字典顺序排序后的最后一个substring.
例子:"acb"的substring排序{"a", "ac", "acb", "b", "c", "cb"}, 返回"cb" 。   EASY难度

2.  Leetcode 239 . Sliding Window Maximum  
改为从所有Sliding window的minimum中找Maximum。
例子: {1,4,6,8,3,5} k = 3  
minimum最大的窗口是{4,6,8}, 返回4.

感觉别人的oa都好简单,我这直接来HARD了。。。
第二题leetcode没做过, 只想出来暴力解。 已崩。

评分

1

查看全部评分

WTYJack 发表于 2016-9-2 10:13:55 | 显示全部楼层
Crystal_yy 发表于 2016-9-2 09:18
觉得应该是找到最大的字母之后,把所有那个字母开头的substring重新比较吧

我觉得不需要,只要遍历一次,不停更新最大子串的头和长度就行了,比如遇到字母比head小的就加个长度,比字母大的就更新head,重置len为1,如果相当在比较两个长度为len的子串,然后根据结果更新head和len,这样下来O(N)就能解决
回复 支持 1 反对 0

使用道具 举报

Crystal_yy 发表于 2016-9-2 10:49:58 | 显示全部楼层
WTYJack 发表于 2016-9-2 10:13
我觉得不需要,只要遍历一次,不停更新最大子串的头和长度就行了,比如遇到字母比head小的就加个长度,比 ...

或许只要确认head的位置就可以了,因为排在最后的应该永远是以最优head开头最长的substring吧
回复 支持 1 反对 0

使用道具 举报

syjohnson 发表于 2016-9-1 23:10:00 | 显示全部楼层
请问lz是海投的吗
回复 支持 反对

使用道具 举报

 楼主| wszk1992 发表于 2016-9-2 03:35:49 | 显示全部楼层
syjohnson 发表于 2016-9-1 23:10.鏈枃鍘熷垱鑷1point3acres璁哄潧
请问lz是海投的吗

是的,直接去官网投就行了
回复 支持 反对

使用道具 举报

WTYJack 发表于 2016-9-2 04:36:16 | 显示全部楼层
请问第一题有什么思路么?感觉貌似可以用O(N)解但还想不太清楚。。。
回复 支持 反对

使用道具 举报

 楼主| wszk1992 发表于 2016-9-2 05:21:52 | 显示全部楼层
WTYJack 发表于 2016-9-2 04:36.鐣欏璁哄潧-涓浜-涓夊垎鍦
请问第一题有什么思路么?感觉貌似可以用O(N)解但还想不太清楚。。。

找到最大字符的首个index。. visit 1point3acres.com for more.
例如 “abczczba”  中 ‘z’最大,第一个出现的index是3, 返回的就是“zczba”, 也就是s.substr(3);
部分代码:

  1. char maxChar = s[0];
  2. int maxCharIndex = 0;
  3. for(int i = 0; i < s.size(); i++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  4. if(s[i] > maxChar) {
  5.   maxChar = s[i];
  6.   maxCharIndex = i;
复制代码
回复 支持 反对

使用道具 举报

WTYJack 发表于 2016-9-2 06:19:38 | 显示全部楼层
wszk1992 发表于 2016-9-2 05:21
找到最大字符的首个index。
例如 “abczczba”  中 ‘z’最大,第一个出现的index是3, 返回的就是“zcz ...

谢回答!不过这样的话,"abczbzca"不就不对了么?要是我没理解错的话,应该返回"zca"吧?
话说这OA应该可以编译提交的吧?
回复 支持 反对

使用道具 举报

AierEden 发表于 2016-9-2 07:53:50 | 显示全部楼层
请问LZ这是第几个oa?我之前做了一个oa 今天又收到一个两小时的oa
回复 支持 反对

使用道具 举报

Crystal_yy 发表于 2016-9-2 09:18:43 | 显示全部楼层
WTYJack 发表于 2016-9-2 06:19. 1point3acres.com/bbs
谢回答!不过这样的话,"abczbzca"不就不对了么?要是我没理解错的话,应该返回"zca"吧?
话说这OA应该 ...

觉得应该是找到最大的字母之后,把所有那个字母开头的substring重新比较吧
回复 支持 反对

使用道具 举报

WTYJack 发表于 2016-9-2 10:14:27 | 显示全部楼层
AierEden 发表于 2016-9-2 07:53
请问LZ这是第几个oa?我之前做了一个oa 今天又收到一个两小时的oa
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
应该是第一个,60min两道题
回复 支持 反对

使用道具 举报

Crystal_yy 发表于 2016-9-2 10:31:08 | 显示全部楼层
WTYJack 发表于 2016-9-2 10:13
我觉得不需要,只要遍历一次,不停更新最大子串的头和长度就行了,比如遇到字母比head小的就加个长度,比 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
好像这样是更优化了!谢谢提醒!
回复 支持 反对

使用道具 举报

WTYJack 发表于 2016-9-2 11:54:49 | 显示全部楼层
Crystal_yy 发表于 2016-9-2 10:49. From 1point 3acres bbs
或许只要确认head的位置就可以了,因为排在最后的应该永远是以最优head开头最长的substring吧

赞!这样代码简单好多,谢谢指教!
回复 支持 反对

使用道具 举报

robotwish 发表于 2016-9-2 21:18:19 | 显示全部楼层
abczabczcbazbaczcab,这样的话应该答案从zcba……(到底),要记录之前最优head(z)的位置,如果遇到同是最优head,two pointer比较z后面的值来更新最优head,字典顺序不是比长度吧
回复 支持 反对

使用道具 举报

liuqi627 发表于 2016-9-4 07:05:22 | 显示全部楼层
WTYJack 发表于 2016-9-2 10:13
. more info on 1point3acres.com我觉得不需要,只要遍历一次,不停更新最大子串的头和长度就行了,比如遇到字母比head小的就加个长度,比 ...

这是个O(n^2)的做法吧
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2016-9-4 07:06):
我的做法和你一样,这是O(n^2)时间O(1)空间的,应该还有O(n)时间的做法
回复 支持 反对

使用道具 举报

WTYJack 发表于 2016-9-4 09:02:45 | 显示全部楼层
liuqi627 发表于 2016-9-4 07:05
这是个O(n^2)的做法吧

补充内容 (2016-9-4 07:06):

是O(N)呀,每个元素只遍历一次,比较完substring就可以根据结果直接把指针往后推了
回复 支持 反对

使用道具 举报

liuqi627 发表于 2016-9-4 10:15:30 | 显示全部楼层
WTYJack 发表于 2016-9-4 09:02
是O(N)呀,每个元素只遍历一次,比较完substring就可以根据结果直接把指针往后推了

这个比较substring也是O(n)的呀
回复 支持 反对

使用道具 举报

WTYJack 发表于 2016-9-5 06:56:28 | 显示全部楼层
liuqi627 发表于 2016-9-4 10:15. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这个比较substring也是O(n)的呀
. from: 1point3acres.com/bbs
就是可以根据比较的结果,比方说在第k位上区分出大小后,把i直接移动到k,因为i到k和之间的子串已经判断过是和最大的子串的k-i位相等了,有点儿two pointers的感觉
回复 支持 反对

使用道具 举报

menghuanboluomi 发表于 2016-9-29 23:12:29 | 显示全部楼层
WTYJack 发表于 2016-9-4 09:02
是O(N)呀,每个元素只遍历一次,比较完substring就可以根据结果直接把指针往后推了

你们有没有考虑出现multiple的z的情况呢  zfkzfkzkfzkfzfkzz 比如这种循环的 就会有很多candidate子串..
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 08:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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