一亩三分地论坛

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

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

Bloomberg电面

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

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

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

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

x
半个小时就一题,估计跪了,题目:有一个list,里面有n个学生,有一个值d,从index 0开始取第d个学生,把他放到新的list上面,在从新的index开始取第d个学生,放入新的list。。。。
假如有5个学生,分别是1,2,3,4,5,d是4. From 1point 3acres bbs
              old             new
第一次 1 2 3 5             4. more info on 1point3acres.com
第二次 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

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

 楼主| hison7463 发表于 2016-3-5 02:28:43 | 显示全部楼层
Ulu2005 发表于 2016-3-5 00:44.1point3acres缃
这题目看的不是很懂,“再从新的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
按我给的例子走,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<>();
  3.                 int count = -1;
  4.                 while(!student.isEmpty()){
  5.                         for(int i = 0; i < index; i++){
  6.                                 count++;
  7.                                 if(count >= student.size()). 1point3acres.com/bbs
  8.                                         count = 0;
  9.                         }
  10.                         res.add(student.get(count));. from: 1point3acres.com/bbs
  11.                         if(student.get(count) == 4)
  12.                                 System.out.println("index:"+count+"size:"+student.size());
  13.                         student.remove(count);
  14.                         count--;
  15.                 }
  16.                 return res;
  17.         }
复制代码
回复 支持 反对

使用道具 举报

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

没看明白你的解法,感觉好像有点不对啊。。
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

Sendoh2015 发表于 2016-3-14 09:46:03 | 显示全部楼层
meikylrs123 发表于 2016-3-14 09:06-google 1point3acres
LinkedList应该是指循环链表,比如1->2->3->4->5->1,这样每次就删除一个点,从新的位置往后数d次。停止条 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
能给贴个代码吗?谢谢
回复 支持 反对

使用道具 举报

donnice 发表于 2016-3-14 10:26:21 | 显示全部楼层
Sendoh2015 发表于 2016-3-14 08:07
没看明白你的解法,感觉好像有点不对啊。。
. from: 1point3acres.com/bbs
你拿到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:
  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)-google 1point3acres
  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:
    . 鍥磋鎴戜滑@1point 3 acres
  16.             cur = pre.next. From 1point 3acres bbs
  17.         while k:
  18.           #  print k, cur.val
  19.             pre = cur-google 1point3acres
  20.             cur = cur.next
  21.             k -= 1
  22.         
  23.         print cur.val
  24.         pre.next = cur.next

  25. arr = [1,2,3,4,5]
  26. buildLink(arr, 4)
复制代码
回复 支持 反对

使用道具 举报

 楼主| hison7463 发表于 2016-3-15 03:54:44 | 显示全部楼层
donnice 发表于 2016-3-14 06:22
最后想了种参考linkedlist的解法的解法,用arraylist即可
. from: 1point3acres.com/bbs
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应该就行了?
-google 1point3acres
补充内容 (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写了一下
  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){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8.                 ArrayList<Integer> result = new ArrayList<Integer>();
  9.                
  10.                 if(nums == null || nums.length == 0 || d < 1){
  11.                         return result;
  12.                 }. 1point3acres.com/bbs
  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.                 }
  40.                
  41.                 result.add(curr.val);
  42.                 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  43.                 return result;
  44.         }
  45.         . 1point 3acres 璁哄潧
  46.         public static void main(String[] args){
  47.                 int[] nums = {1,2,3,4,5};
  48.                 int d = 4;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  49.                 TestListStudentD test = new TestListStudentD();.1point3acres缃
  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结构,不需要太深究它具体是怎么实现的,只要了解它的一些操作的时间复杂度就行了.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2016-3-16 02:32):
当然这道题要自己写一个linkedlist比较好做
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 10:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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