一亩三分地论坛

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

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

Coursera 两道题版本的OA

[复制链接] |试试Instant~ |关注本帖
忆梦前尘 发表于 2016-9-2 07:08:44 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Coursera - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
本来5天前收到的链接,准备了好久的题库,顺便也恢复一下状态,结果刚点开就发现Coursera新发来个OA,之前的链接作废了。

于是从5道题的版本变成了两道题。而之前卡住许久的题目就是lovely number,这次查了一下新面经,发现题目基本一样。就是最大substring和滑动窗口最小值中找最大值的题目。
稍作准备,打开链接就上了。

然后第二道就是那道滑动窗口的题目,第一道撞上了lovely number。没办法,只能暴力解掉,其实两道题都挺暴力的,只不过第二题加了个判断,遇到窗口最小值比当前结果小的话,那直接跳一个窗口的距离。
上图。
Screen Shot 2016-09-01 at 15.45.28.png
Screen Shot 2016-09-01 at 15.45.17.png
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
题目介绍就是这里,如果不熟悉hackerrank的话,可以做做它家的sample test,就当是熟练一下手感。
祝各位都好运~
. 1point3acres.com/bbs
by the way,这家是海投就给OA,希望能有下文吧。

评分

3

查看全部评分

Sorrow雨 发表于 2016-9-23 01:06:21 | 显示全部楼层
恕我直言,暴力枚举复杂度太高了吧?顶我上去,分享简单做法
回复 支持 1 反对 0

使用道具 举报

Sorrow雨 发表于 2016-9-23 02:30:47 | 显示全部楼层
mymax2009 发表于 2016-9-23 02:03
然后其实我想问的是  Ashley 这题, 121算不算是repeated digit number,还是要连续的?

121 应该是算repeated number的
我的思路是先计算1到m不重复的个数减去1到n-1的不重复个数
举个例子吧 比如说要算1-223中不重复的个数,先存1-9,10-99的不重复个数90个,当算到最高位2时,我们开始算100-199的个数,百位有1众取法“1”,十位9种,个位8种,就是72,接下来算200-219的个数,这时候用个vector保存已经用过的数字,十位有“0,1”两种取法,个位有8种,总共16种,220-223,有0个。关键就在于每次计算当前位数字取整减一不重复数字的个数。最后累加起来。每次计算一个数字的复杂度就是O(1),因为m,n digit最多为5位。这是我的想法。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

Sorrow雨 发表于 2016-9-23 01:43:46 | 显示全部楼层
mymax2009 发表于 2016-9-23 01:39
segment这题应该可以O(N)解决,遍历number,用deque存升序number的index(当前number
. 1point 3acres 璁哄潧
嗯嗯 用queue做O(N)复杂度 , 不过我的做法是pq里面存pair<nums,i> 然后做法和你一样啦
回复 支持 1 反对 0

使用道具 举报

chensheng 发表于 2016-9-4 03:19:06 | 显示全部楼层
1. Segment

  1. public int segment(int x, int[] arr) {
  2. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.         if (x == 0 || x > arr.length) {. from: 1point3acres.com/bbs
  4.             return 0;
  5.         }
  6. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.         List<List<Integer>> list = new ArrayList<List<Integer>>();

  8.         for (int i = 0; i < arr.length; i++) {-google 1point3acres
  9.             ArrayList<Integer> nums = new ArrayList();

  10.             for (int j = i; j < x + i && i != arr.length - 1; j++) {
  11.                 nums.add(arr[j]);
  12.             }
  13.             list.add(nums);-google 1point3acres
  14.         }
  15. . more info on 1point3acres.com
  16.         List<Integer> minValues = new ArrayList<>();

  17.         for (int i = 0; i < list.size(); i++) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  18. . Waral 鍗氬鏈夋洿澶氭枃绔,
  19.             List<Integer> nums = list.get(i);
  20.             if (nums == null || nums.size() == 0) {
  21.                 continue; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.             }

  23.             int min = Integer.MAX_VALUE;
  24.             for (int j = 0; j < nums.size(); j++) {
  25.                 min = Math.min(nums.get(j), min);
  26.             }
  27.             minValues.add(min);
  28.         }

  29.         int max = Integer.MIN_VALUE;
  30.         for (int i = 0; i < minValues.size(); i++) {.1point3acres缃
  31.             max = Math.max(max, minValues.get(i));
  32.         }

  33.         return max;
  34.     }
复制代码

.鏈枃鍘熷垱鑷1point3acres璁哄潧
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
2. Lovely numbers
  1. public void countNumbers(int[][] arr) {

  2.         if (arr == null || arr.length == 0 || arr[0].length == 0) {
  3.             return;
  4.         }

  5.         int m = arr.length;
  6.         int count;
  7.         ArrayList<Integer> list = new ArrayList<>();

  8.         for (int i = 0; i < m; i++) {
  9.             count = 0;
  10.             for (int j = arr[i][0]; j <= arr[i][1]; j++) {
  11.                 if (!checkRepeating(j)) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  12.                      count++;
  13.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  14.             }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.             list.add(count);
  16.         }. visit 1point3acres.com for more.

  17.         for (int i = 0; i < list.size(); i++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18.             System.out.println(list.get(i));
  19.         }
  20.     }

  21. . 鍥磋鎴戜滑@1point 3 acres
  22.     private boolean checkRepeating(int num) {
  23. .1point3acres缃
  24.         Set<Integer> set = new HashSet<>();
  25. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  26.         while (num > 0) {
  27.             if (set.contains(num % 10)) {
  28.                 return true;
  29.             }
  30.             set.add(num % 10);
  31.             num /= 10;
  32.         }

  33.         return false;
  34.     }
复制代码
回复 支持 1 反对 0

使用道具 举报

y111d 发表于 2016-9-6 08:30:54 | 显示全部楼层
chensheng 发表于 2016-9-3 14:19. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1. Segment

层主这种方法的时间复杂度应该是 O(n*maxLen) 吧?
回复 支持 反对

使用道具 举报

chensheng 发表于 2016-9-7 04:56:28 | 显示全部楼层
y111d 发表于 2016-9-6 08:30. visit 1point3acres.com for more.
层主这种方法的时间复杂度应该是 O(n*maxLen) 吧?

没错啊,正确
回复 支持 反对

使用道具 举报

laahaa 发表于 2016-9-19 12:08:58 | 显示全部楼层
我也是MSE转的CS。。USC37学分的。。一口气看了你写的那些课程的经验介绍,感觉。。。。更虚了。。。。。。。。。。。。LZ名字是LTM吗?
回复 支持 反对

使用道具 举报

 楼主| 忆梦前尘 发表于 2016-9-19 13:11:17 | 显示全部楼层
laahaa 发表于 2016-9-18 20:08
我也是MSE转的CS。。USC37学分的。。一口气看了你写的那些课程的经验介绍,感觉。。。。更虚了。。。。。。 ...

我去。。。这是抓到我真人了?
回复 支持 反对

使用道具 举报

mymax2009 发表于 2016-9-22 02:43:23 | 显示全部楼层
求问下楼主他家能用C++做吗? 我看input全是stdin,是要先从std::cin预处理input再写算法对吗
回复 支持 反对

使用道具 举报

mymax2009 发表于 2016-9-23 01:39:55 | 显示全部楼层
segment这题应该可以O(N)解决,遍历number,用deque存升序number的index(当前number <=deque.back()的时候就pop_back()),同时要从deque的front开始deque中所存index的值小于  i - x (当前index- window size)的都pop掉, 保证deque中只有当前window。 deque的front存的就是segment中最小值。  当然这题只需要求最小值中的最大值, 可能还会有更简洁高效的办法。


补充内容 (2016-9-23 02:00):. 1point3acres.com/bbs
JAVA的话只要任何一个可以进行头尾操作的container都可以
回复 支持 反对

使用道具 举报

Sorrow雨 发表于 2016-9-23 01:47:19 | 显示全部楼层
lovely number我想的算法复杂度是O(q) 每个区间是O(1).
回复 支持 反对

使用道具 举报

mymax2009 发表于 2016-9-23 01:58:38 | 显示全部楼层
Sorrow雨 发表于 2016-9-23 01:47
lovely number我想的算法复杂度是O(q) 每个区间是O(1).
. From 1point 3acres bbs
可以share一下你的idea吗~同学
回复 支持 反对

使用道具 举报

 楼主| 忆梦前尘 发表于 2016-9-23 02:02:36 | 显示全部楼层
mymax2009 发表于 2016-9-22 09:58
可以share一下你的idea吗~同学

同求share,就是现在手上没有大米了。。
回复 支持 反对

使用道具 举报

mymax2009 发表于 2016-9-23 02:03:03 | 显示全部楼层
然后其实我想问的是  Ashley 这题, 121算不算是repeated digit number,还是要连续的?
回复 支持 反对

使用道具 举报

Sorrow雨 发表于 2016-9-23 02:31:15 | 显示全部楼层
忆梦前尘 发表于 2016-9-23 02:02
同求share,就是现在手上没有大米了。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
我写了思路,可以讨论一下
回复 支持 反对

使用道具 举报

mymax2009 发表于 2016-9-23 02:44:25 | 显示全部楼层
Sorrow雨 发表于 2016-9-23 02:31. visit 1point3acres.com for more.
我写了思路,可以讨论一下
. more info on 1point3acres.com
nice, 我开始想的有点复杂了,应该是这个排列组合的思路
回复 支持 反对

使用道具 举报

TerenceFeng 发表于 2016-10-5 08:34:02 | 显示全部楼层
lovely number 很像leetcode357.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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