一亩三分地论坛

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

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

Amazon 电面

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

2016(7-9月) 码农类 硕士 实习@Amazon - 校园招聘会 - 技术电面 |Passfresh grad应届毕业生

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

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

x
一个白人,说话语速比较快,但好在没什么口音,反正自我介绍我是没听懂。没问简历,直接让我介绍linkedlist和相关操作,又问了和array的区别,最后问了hashmap的实现和处理collision的方法
coding 就一道(可能我做的太慢了……)把一个sorted linkedlist 按照最大->最小->第二大->第二小->...的顺序输出来,我写了个O(n)的算法,追问是要求space O(1)
就这样吧……

本帖被以下淘专辑推荐:

sjh00700 发表于 2016-1-22 06:22:02 | 显示全部楼层
大概是先反转后半部分 然后合并就可以了
回复 支持 反对

使用道具 举报

vesalius 发表于 2016-1-22 07:01:14 | 显示全部楼层
校招当场就会说过或没过么?
回复 支持 反对

使用道具 举报

WilliamShi1 发表于 2016-1-22 07:13:42 | 显示全部楼层
LZ 怎么让hashmap实现 可以简单说说吗
回复 支持 反对

使用道具 举报

lpx1989 发表于 2016-1-22 07:14:36 | 显示全部楼层
他叫什么名字?
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2016-1-22 07:35:53 | 显示全部楼层
vesalius 发表于 2016-1-22 07:01
校招当场就会说过或没过么?

我是电面啊
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2016-1-22 07:36:50 | 显示全部楼层
WilliamShi1 发表于 2016-1-22 07:13
LZ 怎么让hashmap实现 可以简单说说吗
. Waral 鍗氬鏈夋洿澶氭枃绔,
不用写code,我就给他说的java是怎么实现的
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2016-1-22 07:37:22 | 显示全部楼层
lpx1989 发表于 2016-1-22 07:14
他叫什么名字?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
听不太清,也没再问
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-22 07:59:41 | 显示全部楼层
大概写了15分钟,感觉,我面试一紧张,可能最少就得25分钟,猜能做完这题了。
  1. public class linkedList_largest_smallest_secondlargest_etc {
  2.        
  3.         public static class Node{
  4.                
  5.                 Node next;
  6.                 int val;
  7.                 Node(int val)
  8.                 {
  9.                         this.val = val;
  10.                 }
  11.         }
  12.        
  13.         public static Node EasyToMakeMistakeQuestion(Node node)
  14.         {
  15.                 Node slow = node;. Waral 鍗氬鏈夋洿澶氭枃绔,
  16.                 Node fast = node;. 鍥磋鎴戜滑@1point 3 acres
  17.                 Node dummy = new Node(0);
  18.                 dummy.next = node;
  19.                 Node operation = dummy;. from: 1point3acres.com/bbs
  20.                
  21.                 while(fast!=null&&fast.next!=null). Waral 鍗氬鏈夋洿澶氭枃绔,
  22.                 {. visit 1point3acres.com for more.
  23.                         fast = fast.next.next;
  24.                         slow = slow.next;
  25.                 }
  26.                 //no need to find the exact middle point
  27.                 .1point3acres缃
  28.                 Node secondHalf = reverse(slow);
  29.                
  30.                 while(secondHalf!=null&&node!=null)
  31.                 {
  32.                         Node temp1 = secondHalf.next;
  33.                         Node temp2 = node.next;
  34.                         operation.next = secondHalf;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  35.                         operation.next.next = node;
  36.                         secondHalf = temp1;
  37.                         node = temp2;
  38.                         operation = operation.next.next;. 1point3acres.com/bbs
  39.                 }
  40.                 operation.next = null;
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  41.                
  42.                 return dummy.next;
  43.         }
  44.        
  45.         public static Node reverse(Node node). from: 1point3acres.com/bbs
  46.         {
  47.                 Node next =null;
  48.                 Node current = node;. 鍥磋鎴戜滑@1point 3 acres

  49.                 while(current!=null)
  50.                 {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  51.                         Node temp = current.next;
  52.                         current.next = next;
  53.                         next = current;
  54.                         current = temp;       
  55.                 }       
  56.                 . 鍥磋鎴戜滑@1point 3 acres
  57.                 return next;
  58.                 . 鍥磋鎴戜滑@1point 3 acres
  59.         }
  60.         . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  61.         public static void main(String[] args). From 1point 3acres bbs
  62.         {
  63.                 Node test = new Node(1);
  64.                 test.next = new Node(2);
  65.                 test.next.next = new Node(3);
  66.                 test.next.next.next = new Node(4);
  67.                 test.next.next.next.next = new Node(5);
  68. . visit 1point3acres.com for more.
  69.                 Node result = EasyToMakeMistakeQuestion(test);-google 1point3acres
  70.                 System.out.println(result.val);
  71.                 System.out.println(result.next.val);.鏈枃鍘熷垱鑷1point3acres璁哄潧

  72.                 System.out.println(result.next.next.val);
  73.                 System.out.println(result.next.next.next.val);
  74.                 System.out.println(result.next.next.next.next.val);

  75.                
  76.         }

  77. }
复制代码

补充内容 (2016-1-22 08:04):
你o(n)是说得space cost吧,这题不可能又o(1)得time complexity解法。
回复 支持 反对

使用道具 举报

lpx1989 发表于 2016-1-22 08:01:07 | 显示全部楼层
maktf 发表于 2016-1-21 19:37
听不太清,也没再问

那个colleboeditor旁边有显示的啊,我感觉我们是一个面试官
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-22 08:13:41 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-22 07:59
大概写了15分钟,感觉,我面试一紧张,可能最少就得25分钟,猜能做完这题了。

用快慢pointer,找到中点,由于奇偶情况,中点不同得问题并不用考虑,因为,1234,12345,最后一个数,可以append到first, half或者second half,结果不变。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后建一个dummy, append一个大得,再append一个小得就可以了。
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2016-1-22 10:27:43 | 显示全部楼层
lpx1989 发表于 2016-1-22 08:01
那个colleboeditor旁边有显示的啊,我感觉我们是一个面试官

哦,没注意看,好像是R开头的
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2016-1-22 10:35:47 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-22 08:13 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
用快慢pointer,找到中点,由于奇偶情况,中点不同得问题并不用考虑,因为,1234,12345,最后一个数,可 ...

15分钟的话有点勉强,他问完基本数据结构的时候已经过了15分钟了,加上走testcase,runtime分析,基本没时间做第二个了
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-22 10:43:45 | 显示全部楼层
maktf 发表于 2016-1-22 10:35
15分钟的话有点勉强,他问完基本数据结构的时候已经过了15分钟了,加上走testcase,runtime分析,基本没 ...

我觉得是,这题不是很简单。.1point3acres缃
我得做法相当于,一道reverse linked list, linked list查环或者linked list查回文,再加上一道leetcode中等难度得linked list manipulation.
这题可能有更好得方法,不知道,你是怎么写得。
回复 支持 反对

使用道具 举报

iammajian 发表于 2016-1-22 10:47:53 | 显示全部楼层
这个不是跟leetcode原题Reorder List基本一样?
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-22 10:50:00 | 显示全部楼层
iammajian 发表于 2016-1-22 10:47
这个不是跟leetcode原题Reorder List基本一样?. From 1point 3acres bbs
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
re ...

挺像得。。我还真没刷过这题。
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2016-1-23 05:16:40 | 显示全部楼层
lpx1989 发表于 2016-1-22 08:01
那个colleboeditor旁边有显示的啊,我感觉我们是一个面试官

你也是出了这道题?
回复 支持 反对

使用道具 举报

lpx1989 发表于 2016-1-23 06:19:32 | 显示全部楼层
maktf 发表于 2016-1-22 17:16
你也是出了这道题?

没有,但是感觉是一个风格。当然我那道更诡异,实现一个Iterator class
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 11:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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