Google 十一月第一轮电面面经

十一月初第一轮电面，面试的是一个国人小姐姐，

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

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

ay.
最后求大米，谢谢。

个人想法binary search找到正负分界点，然后双指针控制左右遍历，排序到新的array里面，O(logN)+O(N)吧

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

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

多谢楼主！array里面的数都是正数嘛？还是负数也要考虑？

那不是先循环一遍，然后再sort？有更简单的方法么？

c.zhang 发表于 2018-12-1 16:46
多谢楼主！array里面的数都是正数嘛？还是负数也要考虑？

应该是有负数的 毕竟要square

soliloquyyy 发表于 2018-12-1 22:51
那不是先循环一遍，然后再sort？有更简单的方法么？

binary search

dengzeyu147 发表于 2018-12-2 01:05
binary search

binary search 用来排序？那不是nlogn么？还是其他的应用？

soliloquyyy 发表于 2018-12-2 01:10
binary search 用来排序？那不是nlogn么？还是其他的应用？

类似这样 或者跟merge sort那样 你觉得哪个比较快？

1. public static int[] arr(int []arr){
   
2.         int n = arr.length;
   
3.         int l=0,r=n-1,index=n-1;
   
4.         int[] temp = new int[n];
   
5.         while(arr[l]<0 && arr[r]>=0){
   
6.             if(arr[l]*arr[l] > arr[r]*arr[r]){
   
7.                 temp[index--]=arr[l]*arr[l];
   
8.                 l++;
   
9.             }else{
   
10.                 temp[index--]=arr[r]*arr[r];
    
11.                 r--;
    
12.             }
    
13.         }
    
14.         while(arr[l]<0){
    
15.             temp[index--]=arr[l]*arr[l];
    
16.             l++;
    
17.         }
    
18.         while(arr[r]>=0){
    
19.             temp[index--]=arr[r]*arr[r];
    
20.             r--;
    
21.         }
    
22. 
    
23.       
    
24. 
    
25.         return temp;

复制代码

soliloquyyy 发表于 2018-12-2 01:10
binary search 用来排序？那不是nlogn么？还是其他的应用？

mergesort就是 分成两半 negative和positive 你觉得在这个题下 哪个块

dengzeyu147 发表于 2018-12-2 01:46
mergesort就是 分成两半 negative和positive 你觉得在这个题下 哪个块

区别在于如何是不是先需要找到 正负的临界点 ？