聊聊在私立文理读cs的两年感受

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 4365|回复: 24
收起左侧

Bloomberg电面

[复制链接] |试试Instant~ |关注本帖
hison7463 发表于 2016-3-4 04:58:17 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类General 硕士 全职@Bloomberg - 网上海投 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
半个小时就一题,估计跪了,题目:有一个list,里面有n个学生,有一个值d,从index 0开始取第d个学生,把他放到新的list上面,在从新的index开始取第d个学生,放入新的list。。。。
假如有5个学生,分别是1,2,3,4,5,d是4
              old             new
第一次 1 2 3 5             4
第二次 1 2 5              4 3
第三次 1 2                4 3 5
第四次 1                4 3 5 2
第五次                  4 3 5 2 1
面试的时候有点紧张,脑子没转过来,只想到了n * n的解法,最后他告诉我其实用linked list可以有n * d的解法
这个面试跪了就真的没面试了。。。人品不好,没面到leet code原题

评分

2

查看全部评分

本帖被以下淘专辑推荐:

meikylrs123 发表于 2016-3-14 09:06:55 | 显示全部楼层
LinkedList应该是指循环链表,比如1->2->3->4->5->1,这样每次就删除一个点,从新的位置往后数d次。停止条件就是cur->next = cur。
感觉这样做比较简单
回复 支持 1 反对 0

使用道具 举报

Ulu2005 发表于 2016-3-5 00:44:03 | 显示全部楼层
这题目看的不是很懂,“再从新的index取第d个”,这个新的index是怎么算?
回复 支持 反对

使用道具 举报

 楼主| hison7463 发表于 2016-3-5 02:28:43 | 显示全部楼层
Ulu2005 发表于 2016-3-5 00:44.留学论坛-一亩-三分地
这题目看的不是很懂,“再从新的index取第d个”,这个新的index是怎么算?

按我给的例子走,d是4,最开始从index 0开始数4个(1 -> 2 -> 3 -> 4),那么index = 3的数要被拿出来,然后再从index = 3的地方开始往下数4个(5 -> 1 -> 2 -> 3),就得到index = 2,那么就把3拿出来,然后再从index = 2开始数,一直循环没有学生可以取。
回复 支持 反对

使用道具 举报

Ulu2005 发表于 2016-3-5 02:48:09 | 显示全部楼层
hison7463 发表于 2016-3-5 02:28-google 1point3acres
按我给的例子走,d是4,最开始从index 0开始数4个(1 -> 2 -> 3 -> 4),那么index = 3的数要被拿出来,然 ...

原来如此,所以第三次的时候上一轮“5”在最后一个位置,就从头开始,变成"1->2->1->2",取“2”。感谢解释。
回复 支持 反对

使用道具 举报

donnice 发表于 2016-3-13 16:16:30 | 显示全部楼层
linkedlist虽然make sense,但这要怎么写啊?
回复 支持 反对

使用道具 举报

donnice 发表于 2016-3-14 06:22:19 | 显示全部楼层
最后想了种参考linkedlist的解法的解法,用arraylist即可
  1. public static List<Integer> getStudent(List<Integer> student, int index){
  2.                 List<Integer> res = new ArrayList<>();. 围观我们@1point 3 acres
  3.                 int count = -1;
  4.                 while(!student.isEmpty()){.留学论坛-一亩-三分地
  5.                         for(int i = 0; i < index; i++){
  6.                                 count++;
    . 一亩-三分-地,独家发布
  7.                                 if(count >= student.size())
  8.                                         count = 0;
  9.                         }
  10.                         res.add(student.get(count));
  11.                         if(student.get(count) == 4)
  12.                                 System.out.println("index:"+count+"size:"+student.size());
  13.                         student.remove(count);
  14.                         count--;
  15.                 }.1point3acres网
  16.                 return res;
  17.         }
复制代码
回复 支持 反对

使用道具 举报

Sendoh2015 发表于 2016-3-14 08:07:18 | 显示全部楼层
donnice 发表于 2016-3-14 06:22
最后想了种参考linkedlist的解法的解法,用arraylist即可

没看明白你的解法,感觉好像有点不对啊。。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

Sendoh2015 发表于 2016-3-14 08:19:09 | 显示全部楼层
楼主list讲了是sorted的吗?
回复 支持 反对

使用道具 举报

Sendoh2015 发表于 2016-3-14 09:46:03 | 显示全部楼层
meikylrs123 发表于 2016-3-14 09:06
LinkedList应该是指循环链表,比如1->2->3->4->5->1,这样每次就删除一个点,从新的位置往后数d次。停止条 ...

能给贴个代码吗?谢谢
回复 支持 反对

使用道具 举报

donnice 发表于 2016-3-14 10:26:21 | 显示全部楼层
Sendoh2015 发表于 2016-3-14 08:07
没看明白你的解法,感觉好像有点不对啊。。

你拿到eclipse里跑跑看就知道了,把那个system.out.print的部分去掉

补充内容 (2016-3-14 10:28):
原理很简单的,就是index += d这样不断往上加,一旦超出list长度了就换到0从头开始,就是linkedlist的原理。只是我不知道怎么在java里具体调用linkedlist里的next这种,感觉要自己写个数据结构
回复 支持 反对

使用道具 举报

池大侠 发表于 2016-3-14 11:29:27 | 显示全部楼层
  1. arr = [1,2,3,4,5]
  2. i = 0
  3. while arr:. 围观我们@1point 3 acres
  4.     i = (i + 4 - 1) % len(arr). 留学申请论坛-一亩三分地
  5.     print arr.pop(i)
复制代码
回复 支持 反对

使用道具 举报

池大侠 发表于 2016-3-14 11:55:46 | 显示全部楼层
本帖最后由 nunuh89 于 2016-4-22 14:00 编辑
  1. def buildLink(arr, d):
  2.     if not arr:
  3.         return None
  4.     dummy = Node(None)
  5.     dummy.next = head = Node(arr[0])
  6.     for i in range(1, len(arr)):
  7.         head.next = Node(arr[i]). 一亩-三分-地,独家发布
  8.         head = head.next
  9.     head.next = dummy.next
  10.     cur = dummy.next
  11.     #print cur.val
  12.     pre = None
  13.     while cur.next != cur:
  14.         k = d - 1
  15.         if pre:
  16.             cur = pre.next
  17.         while k:
  18.           #  print k, cur.val
  19.             pre = cur
  20.             cur = cur.next
  21.             k -= 1
  22.         
  23.         print cur.val
  24.         pre.next = cur.next
  25. . more info on 1point3acres
  26. arr = [1,2,3,4,5]
  27. buildLink(arr, 4)
复制代码
回复 支持 反对

使用道具 举报

 楼主| hison7463 发表于 2016-3-15 03:54:44 | 显示全部楼层
donnice 发表于 2016-3-14 06:22
最后想了种参考linkedlist的解法的解法,用arraylist即可
来源一亩.三分地论坛.
arraylist就是我听完题目就报给他的解法,但是arraylist删除操作要O(n),所以整体操作就是O(n * n),而link list的删除操作只要O(1),每次找到要O(d),结果就是O(d * n)
回复 支持 反对

使用道具 举报

 楼主| hison7463 发表于 2016-3-15 03:55:36 | 显示全部楼层
meikylrs123 发表于 2016-3-14 09:06 来源一亩.三分地论坛.
LinkedList应该是指循环链表,比如1->2->3->4->5->1,这样每次就删除一个点,从新的位置往后数d次。停止条 ...

正解,最后面试官也说的是这样做
回复 支持 反对

使用道具 举报

donnice 发表于 2016-3-15 11:53:46 | 显示全部楼层
hison7463 发表于 2016-3-15 03:54
arraylist就是我听完题目就报给他的解法,但是arraylist删除操作要O(n),所以整体操作就是O(n * n),而li ...

原来如此,那其实我直接把arraylist换成linkedlist应该就行了?

补充内容 (2016-3-15 11:56):
关键是我实在不太了解怎么用Java的linkedlist做具体的事情,没有->next这种syntax……

补充内容 (2016-3-15 11:56):
还是说自己写一个linkedlist就行了?我觉得会不会太麻烦了?
回复 支持 反对

使用道具 举报

Sendoh2015 发表于 2016-3-15 12:22:49 | 显示全部楼层
谁能贴个Java版的?多谢啊
回复 支持 反对

使用道具 举报

gimook 发表于 2016-3-15 22:16:05 | 显示全部楼层
meikylrs123 发表于 2016-3-14 09:06. 留学申请论坛-一亩三分地
LinkedList应该是指循环链表,比如1->2->3->4->5->1,这样每次就删除一个点,从新的位置往后数d次。停止条 ...
来源一亩.三分地论坛.
好机智!!
回复 支持 反对

使用道具 举报

gimook 发表于 2016-3-15 22:53:04 | 显示全部楼层
我用java写了一下. 1point3acres
  1. class ListNode{
  2.                 int val;
  3.                 ListNode next;
  4.                 ListNode(int x){this.val = x;}
  5.         }
  6.        
  7.         public ArrayList<Integer> getStudentList(int[] nums, int d){. Waral 博客有更多文章,
  8.                 ArrayList<Integer> result = new ArrayList<Integer>();
  9.                
  10.                 if(nums == null || nums.length == 0 || d < 1){
  11.                         return result;
  12.                 }
  13.                
  14.                 ListNode head = new ListNode(nums[0]);
  15.                 ListNode prev = head;
  16.                
  17.                 for(int i = 1; i < nums.length; i++){
  18.                         ListNode nextNode = new ListNode(nums[i]);
  19.                         prev.next = nextNode;
  20.                         prev = nextNode;. 牛人云集,一亩三分地
  21.                 }
  22.                
  23.                 prev.next = head;
  24.                
  25.                 ListNode curr = head;
  26.                
  27.                 while(curr.next != curr){
  28.                         int i = 1;
  29.                         while(i < d){
  30.                                 prev = curr;
  31.                                 curr = curr.next;
  32.                                 i++;. 留学申请论坛-一亩三分地
  33.                         }
  34.                        
  35.                         result.add(curr.val);
  36.                        
  37.                         prev.next = curr.next;
  38.                         curr = curr.next;
  39.                 }. Waral 博客有更多文章,
  40.                
  41.                 result.add(curr.val);
  42.                
  43.                 return result;. visit 1point3acres for more.
  44.         }. more info on 1point3acres
  45.        
  46.         public static void main(String[] args){
  47.                 int[] nums = {1,2,3,4,5};
  48.                 int d = 4;
  49.                 TestListStudentD test = new TestListStudentD();
  50.                 ArrayList<Integer> result = test.getStudentList(nums, d);
  51.                
  52.                 for(Integer num : result){
  53.                         System.out.println(num);
  54.                 } 来源一亩.三分地论坛.
  55.         }
复制代码
回复 支持 反对

使用道具 举报

 楼主| hison7463 发表于 2016-3-16 02:32:15 | 显示全部楼层
donnice 发表于 2016-3-15 11:53
原来如此,那其实我直接把arraylist换成linkedlist应该就行了?

补充内容 (2016-3-15 11:56):

java内部的linkedlist就是我们熟知的list结构,不需要太深究它具体是怎么实现的,只要了解它的一些操作的时间复杂度就行了

补充内容 (2016-3-16 02:32):. 围观我们@1point 3 acres
当然这道题要自己写一个linkedlist比较好做
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-21 17:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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