谷歌09/06电面挂经

今天电面谷歌，一个比较友善的白人小哥。开头先自我介绍然后问我简历上某个项目的最大challenge是什么。
然后开始做题。上来问了一个reverse linked list，但是要求不能修改该链表。我说可以递归，说了时空复杂度，然后没让我写代码。接着又问让把空间复杂度优化到sub-linear，我说了可以用时间复杂度n^2的brute force，他问我能不能再优化下时间，保证空间在sub-

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

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

8-9-7 10:44):
谢谢大家的回复和点赞。我之前的描述也许有些偏差，正确的来说不是return reversed linked list而是print the linked list values in reverse order

根据题意描述给了解答．有问题的话欢迎指正，或者给个赞．

1. #include <iostream>
   
2. 
   
3. class LinkedNode
   
4. {
   
5.     public:
   
6.     int val;
   
7.     LinkedNode* next;
   
8.     LinkedNode(int a)
   
9.     {
   
10.         next = NULL;
    
11.         val = a;
    
12.     }
    
13. };
    
14. 
    
15. void solution(LinkedNode* head, int N)
    
16. {
    
17.     vector<LinkedNode*>array;   
    
18.     LinkedNode* h = head;
    
19.    
    
20.     array.push_back(h);
    
21.     for (int i=0; i<N; i++)
    
22.     {        
    
23.         if (i%int(sqrt(N)+1)==0)        
    
24.             array.push_back(h);
    
25.         h = h->next;        
    
26.     }
    
27.     array.push_back(NULL);
    
28.    
    
29.     for (int i=array.size()-2; i>=0; i--)
    
30.     {
    
31.         LinkedNode* p =array[i];
    
32.         vector<int>temp;
    
33.         while (p!=array[i+1])
    
34.         {
    
35.             temp.push_back(p->val);
    
36.             p = p->next;
    
37.         }            
    
38.         for (int j=temp.size()-1; j>=0; j--)
    
39.             cout<<temp[j]<<" ";
    
40.     }   
    
41. }
    
42. 
    
43. int main()
    
44. {
    
45.     LinkedNode* head = new LinkedNode(1);
    
46.     LinkedNode* h = head;
    
47.     h->next = new LinkedNode(2);
    
48.     h = h->next;
    
49.     h->next = new LinkedNode(3);
    
50.     h = h->next;
    
51.     h->next = new LinkedNode(4);
    
52.     h = h->next;
    
53.     h->next = new LinkedNode(5);
    
54.     h = h->next;
    
55.     h->next = new LinkedNode(6);
    
56.     h = h->next;
    
57.     h->next = new LinkedNode(7);
    
58.     h = h->next;
    
59.     h->next = new LinkedNode(8);
    
60.     h = h->next;
    
61.    
    
62.     solution(head,8);
    
63. 
    
64. }

复制代码

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

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

你 amazon 是海投?

wchb2016 发表于 2018-9-7 09:51
你 amazon 是海投?

我是找我的朋友内推的

reverse linked list不能修改该链表是什么操作？

reverse linked list不能改链表是什么操作

这个是面经题，以前好像出现过，当时觉得用sqrt(n)这个很难想到，但是见过了就应该记得了。所以楼主回答不出也是非常正常的。继续加油好了，google年年都可以去冲刺的，来日方长。

walkboy 发表于 2018-9-7 10:34
reverse linked list不能改链表是什么操作

我之前的描述也许有些偏差，正确的来说不是return reversed linked list而是print the linked list values in reverse order

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

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

BZH 发表于 2018-9-7 10:41
这个是面经题，以前好像出现过，当时觉得用sqrt(n)这个很难想到，但是见过了就应该记得了。所以楼主回答不 ...

感谢你的提醒和鼓励，我去找找看

这人是不是搞ACM的……https://cp-algorithms.com/data_structures/sqrt_decomposition.html