脸熟initial面经，感觉好像被面试官黑了

上周的Initial interview, 本来是电面，因为我在local，所以可以去office面。 全程～45mins。我提前40分钟就到了。面试官是亚洲女生， 听不出口音到底是国人还是韩国妹子。先几分钟介绍了一下她在做什么。

1， remove zeros。一个array里有零，要你in place把非零项都移到左边，最后array右边尾巴是什么样可以不用管，还要返回有多少个非零项，要求是O（n）。讨论了几种做法，她要求不能用额外的space。最后定了

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

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

retur

补充内容 (2017-6-28 01:01):
打错了，O（n）时间，O（1）space。字数超了

补充内容 (2017-6-28 01:03):
不知道为什么贴上代码好多字被删了。有两行是nums［i］不是nums

第一题 真的是高频，lc easy 通过率很高，我估计你是想的太久了。。。

stealop 发表于 2017-6-29 22:37
对收尾指针就是这个，一个loop就是       int pointer = 0;
        for(int i=0; i < nums.length;i++) ...

I think all 3 ways can be accomplished by a single loop. Actually, I can see that using multiple loop fits the thinking process better, but the single loop way is equivalent by check the same condition.

1. // might have unneeded writing (one pass)
   
2. void moveLeft1(vector<int>& nums) {
   
3.   int pointer = 0;
   
4.   for (int num : nums)
   
5.     if (num) nums[pointer++] = num;
   
6. }
   
7. 
   
8. // do not preserve non-zero order (one pass)
   
9. void moveLeft2(vector<int>& nums) {
   
10.   int i = 0, j = nums.size();
    
11.   while (i < j) {
    
12.     if (nums[i]) ++i;
    
13.     else if (!nums[j]) --j;
    
14.     else swap(nums[i++], nums[j--]);
    
15.   }
    
16. }
    
17. 
    
18. // preserve non-zero order and minimum writing (two passes)
    
19. void moveLeft3(vector<int>& nums) {
    
20.   int i = 0, j = 0;
    
21.   while (i < nums.size()-1 && j < nums.size()) {
    
22.     if (nums[i]) ++i;
    
23.     else if (!nums[j = i+1]) ++j;
    
24.     else swap(nums[i++], nums[j++]);
    
25.   }
    
26. }
    

复制代码

scredwood 发表于 2017-6-29 05:03
这也太抠细节了吧。。。。请问最后一个LOOP 的解法是啥？收尾指针是不是这个意思？

while (left < rig ...

这是我一上来就写的两个 loop的 做法

        int fast = 0, current = 0;

        while(fast < nums.length && current < nums.length) {
            while(fast < nums.length && nums[fast] == 0) {
                fast++;
            }
            if(fast == nums.length) return;
            int temp = nums[fast];
            nums[fast] = nums[current];
            nums[current] = temp;
            fast++;
            current++;
        }

补充内容 (2017-6-29 22:54):
面试官说不好

LZ 第一题 不是双指针最快吗。。。

LZ 第一题 不是双指针最快吗。。。

第一题是高频move zeroes。估计可能其他人都做的特别快而影响了你

david.fang 发表于 2017-6-27 15:39
第一题是高频move zeroes。估计可能其他人都做的特别快而影响了你

不完全是LC的move zeros。 只要求in place改array使前面全是非零项，后边不管了。不用把zeros都移到后面。估计没有直接秒而是纠结了一下，多讨论了几种不efficient的方法。。？

f1371342385 发表于 2017-6-27 15:30
LZ 第一题 不是双指针最快吗。。。

怎么用two pointers?

巫山云似盖 发表于 2017-6-27 15:52
怎么用two pointers?

一个从头开始指向非0的index 一个从尾开始指向是0的index 交换？

int removeElement(int A[], int n, int elem) {
    int begin=0;
    for(int i=0;i<n;i++) if(A[i]!=elem) A[begin++]=A[i];
    return begin;
}
leetcode 27

左右指针均从左开始，左指针找第一个0，右指针找左指针右起第一个非0，呼唤，左右指针分别加一，重复上述过程至指针到尾