【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2146|回复: 17
收起左侧

Amazon 电面

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

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

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

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

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

本帖被以下淘专辑推荐:

sjh00700 发表于 2016-1-22 06:22:02 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
大概是先反转后半部分 然后合并就可以了
回复 支持 反对

使用道具 举报

vesalius 发表于 2016-1-22 07:01:14 | 显示全部楼层
关注一亩三分地微博:
Warald
校招当场就会说过或没过么?
回复 支持 反对

使用道具 举报

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实现 可以简单说说吗

不用写code,我就给他说的java是怎么实现的
回复 支持 反对

使用道具 举报

 楼主| maktf 发表于 2016-1-22 07:37:22 | 显示全部楼层
lpx1989 发表于 2016-1-22 07:14
他叫什么名字?

听不太清,也没再问
回复 支持 反对

使用道具 举报

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.         {.1point3acres缃
  15.                 Node slow = node;
  16.                 Node fast = node;
  17.                 Node dummy = new Node(0);
  18.                 dummy.next = node;
  19.                 Node operation = dummy;
  20.                
  21.                 while(fast!=null&&fast.next!=null)
  22.                 {
  23.                         fast = fast.next.next;
  24.                         slow = slow.next;
  25.                 }
  26.                 //no need to find the exact middle point
  27.                 . 1point 3acres 璁哄潧
  28.                 Node secondHalf = reverse(slow);. Waral 鍗氬鏈夋洿澶氭枃绔,
  29.                
  30.                 while(secondHalf!=null&&node!=null)
  31.                 {
  32.                         Node temp1 = secondHalf.next;
  33.                         Node temp2 = node.next;
  34.                         operation.next = secondHalf;
  35.                         operation.next.next = node;
  36.                         secondHalf = temp1;
  37.                         node = temp2;
  38.                         operation = operation.next.next;
  39.                 }
  40.                 operation.next = null;
  41.                
  42.                 return dummy.next;
  43.         }
  44.        
  45.         public static Node reverse(Node node)
  46.         {
  47.                 Node next =null;
  48.                 Node current = node;

  49.                 while(current!=null)
  50.                 {
  51.                         Node temp = current.next;
  52.                         current.next = next;. Waral 鍗氬鏈夋洿澶氭枃绔,
  53.                         next = current;
  54.                         current = temp;       
  55.                 }       
  56.                
  57.                 return next;
  58.                
  59.         }
  60.         . 鍥磋鎴戜滑@1point 3 acres
  61.         public static void main(String[] args)
  62.         {
  63.                 Node test = new Node(1);. visit 1point3acres.com for more.
  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.                 Node result = EasyToMakeMistakeQuestion(test);
  69.                 System.out.println(result.val);
  70.                 System.out.println(result.next.val);-google 1point3acres

  71.                 System.out.println(result.next.next.val);
  72.                 System.out.println(result.next.next.next.val);
  73.                 System.out.println(result.next.next.next.next.val);.鐣欏璁哄潧-涓浜-涓夊垎鍦

  74.                 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  75.         }
  76. . visit 1point3acres.com for more.
  77. }.1point3acres缃
复制代码

补充内容 (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分析,基本没 ...

我觉得是,这题不是很简单。
我得做法相当于,一道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→…. from: 1point3acres.com/bbs
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基本一样?
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.1point3acres缃
你也是出了这道题?

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-21 12:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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