《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2353|回复: 18
收起左侧

集中讨论一下RoundRobin的问题

[复制链接] |试试Instant~ |关注本帖
wxr.dal 发表于 2015-11-21 10:08:48 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Amazon - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
开个帖子集中讨论一下Round Robin可能出现的follow up,corner case. 还有请video后的小伙伴过来说说,面试官都会问什么问题~谢谢啦

补充内容 (2015-11-24 14:23):
补充一下吧,最近挖帖子,有同学提到过的follow up。怎么求最大最小wait time。

本帖被以下淘专辑推荐:

fagyjames 发表于 2015-11-21 10:17:21 | 显示全部楼层
我准备时候分析了container的选择,比如queue list vector stack array等等 他们之间的区别以及什么情况下RR可以考虑queue以外的 比如list。。。当时想的头都炸了。。。
回复 支持 反对

使用道具 举报

 楼主| wxr.dal 发表于 2015-11-21 10:17:54 | 显示全部楼层
fagyjames 发表于 2015-11-21 10:17
我准备时候分析了container的选择,比如queue list vector stack array等等 他们之间的区别以及什么情况下R ...

有道理有道理~
回复 支持 反对

使用道具 举报

fagyjames 发表于 2015-11-21 10:19:56 | 显示全部楼层
. From 1point 3acres bbs
学姐加油!!!!~
回复 支持 反对

使用道具 举报

ay-pythonista 发表于 2015-11-26 12:12:18 | 显示全部楼层
这最小wait time 不就是0 吗第一个任务直接就执行了 还是说重新加到queue之后这个任务的等待时间还要加进去?
回复 支持 反对

使用道具 举报

 楼主| wxr.dal 发表于 2015-11-26 12:13:51 | 显示全部楼层
ay-pythonista 发表于 2015-11-26 12:12
这最小wait time 不就是0 吗第一个任务直接就执行了 还是说重新加到queue之后这个任务的等待时间还要加进去 ...
. From 1point 3acres bbs
那第一个任务的run time要是大于q不就得等。
回复 支持 反对

使用道具 举报

ay-pythonista 发表于 2015-11-26 12:17:31 | 显示全部楼层
wxr.dal 发表于 2015-11-26 12:13
那第一个任务的run time要是大于q不就得等。

我的意思是如果一个任务重新加到queue里面不算是新的任务 那如果这样的话大于q还得累计每个任务分别的总共等待时间就好了
回复 支持 反对

使用道具 举报

 楼主| wxr.dal 发表于 2015-11-26 12:21:02 | 显示全部楼层
ay-pythonista 发表于 2015-11-26 12:17
我的意思是如果一个任务重新加到queue里面不算是新的任务 那如果这样的话大于q还得累计每个任务分别的总 ...

.鏈枃鍘熷垱鑷1point3acres璁哄潧 我觉得,是until finish, 中间所有的wait time都要加在一起。
回复 支持 反对

使用道具 举报

ay-pythonista 发表于 2015-11-26 12:26:20 | 显示全部楼层
wxr.dal 发表于 2015-11-26 12:21
我觉得,是until finish, 中间所有的wait time都要加在一起。

那我觉得很简单啊 用一个list记录所有执行时间大于q的任务的等待时间 然后一个variable 记录所有执行时间小于q的最大和最小时间 然后跟list里面最大最小时间比较一下就可以了吧
回复 支持 反对

使用道具 举报

 楼主| wxr.dal 发表于 2015-11-26 12:30:06 | 显示全部楼层
ay-pythonista 发表于 2015-11-26 12:26
那我觉得很简单啊 用一个list记录所有执行时间大于q的任务的等待时间 然后一个variable 记录所有执行时间 ...

小于q的任务也有可能排在队尾等很久,并不知道哪个是最小时间。
回复 支持 反对

使用道具 举报

ay-pythonista 发表于 2015-11-26 12:40:06 | 显示全部楼层
wxr.dal 发表于 2015-11-26 12:30. Waral 鍗氬鏈夋洿澶氭枃绔,
小于q的任务也有可能排在队尾等很久,并不知道哪个是最小时间。
. Waral 鍗氬鏈夋洿澶氭枃绔,
每次累加等待时间的时候和当前最小时间比较一下就好了啊
回复 支持 反对

使用道具 举报

 楼主| wxr.dal 发表于 2015-11-26 12:42:39 | 显示全部楼层
ay-pythonista 发表于 2015-11-26 12:40
每次累加等待时间的时候和当前最小时间比较一下就好了啊

"然后一个variable 记录所有执行时间小于q的最大和最小时间" 我没看懂,你这个是要怎么记录
回复 支持 反对

使用道具 举报

ay-pythonista 发表于 2015-11-26 12:42:40 | 显示全部楼层
wxr.dal 发表于 2015-11-26 12:30
小于q的任务也有可能排在队尾等很久,并不知道哪个是最小时间。

还有请问你能把看到这个问题的帖子链接发一下吗 谢啦
回复 支持 反对

使用道具 举报

 楼主| wxr.dal 发表于 2015-11-26 12:43:58 | 显示全部楼层
ay-pythonista 发表于 2015-11-26 12:42
还有请问你能把看到这个问题的帖子链接发一下吗 谢啦

这个要去翻帖子了,慢慢翻吧…… 我一时半会儿也找不到
回复 支持 反对

使用道具 举报

chuxidemeng 发表于 2015-11-28 03:59:36 | 显示全部楼层
对求最大最小时间没什么好的思路,求大神们指点!!
回复 支持 反对

使用道具 举报

ay-pythonista 发表于 2015-11-28 04:25:27 | 显示全部楼层
chuxidemeng 发表于 2015-11-28 03:59
对求最大最小时间没什么好的思路,求大神们指点!!

一个hash table 应该就解决了吧 用index记录process ID, value是积累的等待时间
回复 支持 反对

使用道具 举报

returning 发表于 2015-11-28 15:58:53 | 显示全部楼层
ay-pythonista 发表于 2015-11-26 12:42. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
还有请问你能把看到这个问题的帖子链接发一下吗 谢啦

同问,云里雾里,看不懂啊。。。
回复 支持 反对

使用道具 举报

leonidas1573 发表于 2015-12-4 14:27:30 | 显示全部楼层
http://www.1point3acres.com/bbs/thread-142143-1-1.html 我的C++解法. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;.鏈枃鍘熷垱鑷1point3acres璁哄潧

  4. float roundRobin(int* Atime, int len, int* Etime, int q) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.         if (len < 2) return 0;
  6.         queue< pair<int, int> > qq;        // execution time, insert time.
  7.         int currenttime = 0, stackhead = 0, currenttask = 0, totalwaittime = 0;. From 1point 3acres bbs
  8.         bool killcurrenttask = 0;
  9.         while (qq.size() || stackhead != len || killcurrenttask) {
  10.                 while (stackhead < len && Atime[stackhead] <= currenttime) {
  11.                         qq.push(make_pair(Etime[stackhead], Atime[stackhead]));
  12.                         stackhead++;
  13.                 }
  14.                 if (killcurrenttask) {
  15.                         qq.push(make_pair(currenttask - q, currenttime)); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  16.                 }
  17.                 if (!qq.size())
  18.                         currenttime = Atime[stackhead];
  19.                 else {
  20.                         currenttask = qq.front().first;
  21.                         totalwaittime += currenttime - qq.front().second;
  22.                         qq.pop();
  23.                         killcurrenttask = currenttask > q;. 鍥磋鎴戜滑@1point 3 acres
  24.                         currenttime += ((q < currenttask) ? q : currenttask);
  25.                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  26.         }
  27.        
  28.         return totalwaittime / (double)(len);
  29. }

  30. int main() {
  31.         // int Atime[] = { 0, 1, 3, 9 };
  32.         // int Etime[] = { 2, 1, 7, 5 };
  33.         // int q = 2;

  34.         // int Atime[] = { 0, 1, 4 };
  35.         // int Etime[] = { 5, 2, 3 };
  36.         // int q = 3;

  37.         int Atime[] = { 0, 4, 8 };
  38.         int Etime[] = { 1, 1, 1 };.鐣欏璁哄潧-涓浜-涓夊垎鍦
  39.         int q = 3;
  40. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  41.         cout << roundRobin(Atime, sizeof(Atime) / sizeof(int), Etime, q);

  42.         // your code goes here
  43.         return 0;
  44. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-23 23:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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