Amazon 电面

一个白人，说话语速比较快，但好在没什么口音，反正自我介绍我是没听懂。没问简历，直接让我介绍linkedlist和相关操作，又问了和a

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

了个O(n)的算法，追问是要求space O(1)
就这样吧……

大概写了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;
    
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.                
    
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;
    
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. 
    
50.                 while(current!=null)
    
51.                 {
    
52.                         Node temp = current.next;
    
53.                         current.next = next;
    
54.                         next = current;
    
55.                         current = temp;       
    
56.                 }       
    
57.                
    
58.                 return next;
    
59.                
    
60.         }
    
61.        
    
62.         public static void main(String[] args)
    
63.         {
    
64.                 Node test = new Node(1);
    
65.                 test.next = new Node(2);
    
66.                 test.next.next = new Node(3);
    
67.                 test.next.next.next = new Node(4);
    
68.                 test.next.next.next.next = new Node(5);
    
69. 
    
70.                 Node result = EasyToMakeMistakeQuestion(test);
    
71.                 System.out.println(result.val);
    
72.                 System.out.println(result.next.val);
    
73. 
    
74.                 System.out.println(result.next.next.val);
    
75.                 System.out.println(result.next.next.next.val);
    
76.                 System.out.println(result.next.next.next.next.val);
    
77. 
    
78.                
    
79.         }
    
80. 
    
81. }
    

复制代码

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

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

大概是先反转后半部分 然后合并就可以了

校招当场就会说过或没过么？

LZ 怎么让hashmap实现 可以简单说说吗

他叫什么名字？

vesalius 发表于 2016-1-22 07:01
校招当场就会说过或没过么？

我是电面啊

WilliamShi1 发表于 2016-1-22 07:13
LZ 怎么让hashmap实现 可以简单说说吗

不用写code，我就给他说的java是怎么实现的

lpx1989 发表于 2016-1-22 07:14
他叫什么名字？

听不太清，也没再问

maktf 发表于 2016-1-21 19:37
听不太清，也没再问

那个colleboeditor旁边有显示的啊，我感觉我们是一个面试官