今天面试遇到的情况

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1400 天前的主题，其中的信息可能已经有所发展或是发生改变。

今天面了一家做笔记的厂，是手写代码面，第一个题就是奇偶排序的问题，题目如下

input: [2,1,5,7,4,9,8,5,6] output: [1,5,7,9,5,2,4,8,6]

输入一个整数数组，期望输出的数组里，奇数在前边，偶数在后边

我想这不简单么，我有好几种办法可以实现这个功能，然后我就写下了如下代码

    function filter(originArray) {
        let oddArray = [];
        let evenArray = [];
        originArray.forEach(item => {
            if (item % 2 == 1) {
                oddArray.push(item);
            }
            else {
                evenArray.push(item);
            }
        })
        return oddArray.concat(evenArray);
    }

其实我还有以下办法可以实现

    function filter(originArray) {
        originArray.sort((a, b) => {
            return b % 2 - a % 2;
        })
        return originArray;
    }

    function filter(originArray) {
        return originArray.filter(a => {
            return a % 2 == 1;
        }).concat(originArray.filter(b => {
            return b % 2 == 0;
        }));
    }

但是我没想到，面试官其实是想考察双指针排序的变种，我对这种双指针得问题本来就不熟，就卡在这问题上搞了 20 来分钟，整得我都没脾气了，汗都整出来了，后面又考察了一个问题，我只知道原理，让我手写又一次写错，就尴尬地结束了这一次面试。

可能刚好对方的实际项目中需要解决这类算法的问题，面试没面好是我的问题，

我想说的是，对于一个问题，没能按面试官想的方式解决，是不是就算活不好了？

68 条回复 • 2021-02-01 14:19:57 +08:00

lcc142625

2021-01-28 17:07:03 +08:00

这种呢，不能说你的问题，我也遇到过，就是面的时候卡壳想不出来题解，不过那会我面的滴滴的，起码面试官还给我思路，不至于一直两个人尴尬着，有些问题我回头想，能理解也能做出来，但是面试真就紧张，就会怯场，害，这个别太影响你下回面试，每家面试套路都不一样

cxe2v

2021-01-28 17:11:00 +08:00

@lcc142625 #1 我这个面试官也是给了我提示我才知道他想要用双指针的，也没有说一直尴尬，因为是在网页上写代码，滴滴我面过，运气好到没有做任何题就直接到了终面然后被 pass 了，运气啊真的是实力的一部分

carlclone

2021-01-28 17:13:34 +08:00

啥双指针, 他是想你原地排序吧, O(1)空间复杂度 , 我知道的一个方法是用快排的分区思想, 写起来也不算很简单

v2webdev

2021-01-28 17:14:22 +08:00

这题用双指针怎么做？

carlclone

2021-01-28 17:14:36 +08:00

@carlclone 看错题目了...

lcc142625

2021-01-28 17:19:12 +08:00

emm，运气，看面试官和你对不对眼了，我就是，面试类似走了流程直接过了，莫心焦，我也是面了两个月左右才找到的

lemon94

2021-01-28 17:24:50 +08:00

如果面试官没限定你使用内存的空间，那你的解法没什么问题。
如果限定你原地，那你的方法就不行了。

fiypig

2021-01-28 17:28:22 +08:00 via iPhone

一般来说解决问题以后再来谈优化，你没错的

hello2060

2021-01-28 17:29:57 +08:00 via iPhone

开始写之前多和面试官沟通呗，或者先把思路说一遍，如果是他要的你再开始写。

不过这个题一看你开了新数组应该就不是他要的哈，不然谁都会啊。

类似于快排，一个指针 i 初始化为 0，p=-1,如果偶数 i++，如果是奇数 swap(++p, i); i++
不过他确实要把条件先告诉你，比如不能利用额外空间

djFFFFF

2021-01-28 17:38:59 +08:00

即使是不从算法复杂度（常数优化）的角度考虑，你的做法涉及 array 对象创建（还没指定大小，后续可能涉及 array 扩容），cpu 指令数还是比原地排序要多很多的。当然没多到指数级别就是了。
我是面试官的话，我会觉得你能干活，但不抠细节。所以看你面的是什么岗位以及这个岗位的要求是什么了。

ccvzz

2021-01-28 17:39:52 +08:00

```javascript
function filter(arr) {
const ret = [...arr];
let lo = 0, hi = 0;
// arr[0:lo] is odd
while (hi < ret.length) {
if (ret[hi] % 2 == 0) {
hi++;
} else {
[ret[lo], ret[hi]] = [ret[hi], ret[lo]];
lo++;
hi++;
}
}
return ret;
}
```

双指针做法，我自己测试了一下貌似没啥问题

cxe2v

2021-01-28 17:42:26 +08:00

@djFFFFF #10 你这个说的有道理，原地排序确实省资源，至于面的岗位，面试官也不清楚具体干啥

djFFFFF

2021-01-28 17:47:50 +08:00

@cxe2v 那我觉得面试官自己也没想好他的面试方式是否正确，是否能帮公司招到合适的人。

devfeng

2021-01-28 17:55:26 +08:00 via Android

可能是你面试经验少了，现在都这个套路，给一个算法题，给出最优解才能接着聊。ps.之前面试遇到个差不多的题，也是双指针，要求奇数在奇数位，偶数在偶数位。

ttys001

2021-01-28 17:56:53 +08:00

x = [2,1,5,7,4,9,8,5,6]
def odd_even(x: list, l: int, h: int) -> list:
for i in range(l, h):
for j in range(i, h):
if x[j]%2 == 0 and x[j+1]%2 == 1:
x[j], x[j+1] = x[j+1], x[j]
return x
odd_even(x, 0, len(x)-1)
这叫冒泡法嘛？

chocovon

2021-01-28 17:59:43 +08:00

我倒是觉得，如果是面对某个性能要求不高的业务问题，你的代码才是好代码，做到了就事论事，没有引入不必要的复杂性

isRealLeven

2021-01-28 18:03:24 +08:00

也许是你刷题刷少了。本来题目不难，而且说明了双指针。应该很快就能做出来

javapythongo

2021-01-28 18:04:29 +08:00

@ccvzz 题目要求奇偶顺序后，还要求相对奇数 /偶数之间的相对位置大小不能变

cxe2v

2021-01-28 18:08:10 +08:00

@isRealLeven #17 对的，就是题刷少了，算法题真的刷得少

wjploop

2021-01-28 18:08:53 +08:00

理解题意确实很重要，咋一看我以为“奇数序列”和“偶数序列”要求有序，若是这样，改变了“两个数的比较规则”而已，用常用的排序方法就行，时间复杂度必然大于等于 nlogn （不考虑桶排序）。
既然没有要求，时间复杂度就可以降到 O(n)了，作为面试题，这题的应该隐含了一个硬性要求“空间复杂度为 O(1)”。那么，确实是用双指针的做法了。简单的思路就是，
假设目标序列为左边奇数右边偶数，
设立左右指针，左指针指向 0，右指针指向 len - 1
左指针往右移动一直遇到偶数停住 i，右指针往左移动直到遇到奇数停住 i，交换这两位置的数
不断重复以上操作，直到两指针相遇结束

javapythongo

2021-01-28 18:23:35 +08:00

这样子吗？
```java
public static void main(String[] args) {
int[] arr = {2, 1, 5, 7, 4, 9, 8, 5, 6};
int l = 0;
int r = 0;
while (r < arr.length) {
if (arr[r] % 2 == 0) {
r++;
} else {
int odd = arr[r];
for (int i = r; i > l; i--) {
arr[i] = arr[i - 1];
}
arr[l] = odd;
l++;
r++;

}
}
System.out.println(Arrays.toString(arr));
}
```

javapythongo

2021-01-28 18:24:43 +08:00

感觉我写的这个还不如你的空间换时间

crazyxtcn

2021-01-28 18:25:31 +08:00

@javapythongo 我觉得这个问题很重要，我开始以为输出要求不改变在原数组中的相对位置，然后在 leetcode 上搜了一下，发现有原题，没要求相对位置，不要求相对位置就很简单了

ezksdo

2021-01-28 18:30:59 +08:00 via iPhone

这和快排有啥区别，直接让比较函数偶数比基数大不就行了吗

YouLMAO

2021-01-28 18:32:43 +08:00 via Android

排序个 jb，2 个 for 循环，先打奇数再打偶数，6 行代码，最优的时间和空间复杂度

YouLMAO

2021-01-28 18:33:54 +08:00 via Android

出题的人连最优算法都不知道，指针个屁

chienius

2021-01-28 18:42:43 +08:00 via iPhone

双路快速排序了解一下，其实就是快排分区算法

mccreefei

2021-01-28 19:14:28 +08:00

快排 partition 思路
```java
public int[] sort(int[] data) {
int left = 0 , right = data.length - 1, cur = 0;
while (cur < right) {
if (data[cur] % 2 == 1) {
swap(data, cur++, left++);
} else {
swap(data, cur, right--);
}
}
return data;

}
private void swap(int[] data, int i, int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
```

onyourroad

2021-01-28 19:17:28 +08:00

多刷点 leetcode 就好了。

yazoox

2021-01-28 19:26:42 +08:00

@crazyxtcn 题目编号是？

wjploop

2021-01-28 19:51:49 +08:00

@crazyxtcn 要是还有条件要求排序稳定（排序后相对位置不变），得牺牲空间或时间吧。牺牲空间就是楼主的做法了，牺牲时间可以用插入排序，时间复杂度要 n 平方了

lwlizhe

2021-01-28 20:12:15 +08:00

话说这题要不要排序啊，

比如说 {2,1,5,7,4,9,8,5,6} 这串

正确答案应该是{1，5，5，7，9，2，4，6，8}

要排序的话，好像所有人都做错了

lwlizhe

2021-01-28 20:15:29 +08:00

@lwlizhe 好吧，确实有人问了下奇偶相对的问题……当我没说

e583409

2021-01-28 21:04:02 +08:00

面试的目的是什么？

linvon

2021-01-28 21:43:48 +08:00

首先这就是个奇偶区分的问题，不是什么排序，双指针是最简单的解法，快排啥的就扯远了
其次从性能上来说，你的解法确实存在些问题，不如自己分析一下各种解法的时间和空间复杂度。
算法面试就是这样，不服的话也没办法，啃吧

kiripeng

2021-01-28 22:13:22 +08:00

给他整个三路排序

buffzty

2021-01-28 22:14:17 +08:00

我记得没错的话快排里有用到跟原地排序的算法.
你这个题没有要求奇偶数组再排序只要 2 个循环就好了
1. 遍历数组将奇数顺序放到头部,偶数逆序放到尾部
2. 遍历偶数数组并翻转
```go
package main

import "fmt"

func main() {
arr := []int{2, 1, 5, 7, 4, 9, 8, 5, 6}
length := len(arr)
head := 0
tail := length - 1
for i := 0; i < tail; i++ {
if arr[i]&1 == 1 {
arr[i], arr[head] = arr[head], arr[i]
head++
} else {
arr[i], arr[tail] = arr[tail], arr[i]
tail--
}
}
tail--
for i := length - 1; i > tail; i-- {
arr[i], arr[tail] = arr[tail], arr[i]
tail++
}
fmt.Println(arr)
}
```

buffzty

2021-01-28 22:15:21 +08:00

不能直接发代码是真的恶心.交流体验极差

hello2060

2021-01-28 22:28:03 +08:00 via iPhone

@linvon 快排没问题啊，线性复杂度，三行代码，而且能保证左边部分的相对顺序。

kx5d62Jn1J9MjoXP

2021-01-28 22:44:05 +08:00 via Android

说实话我觉得这个题挺好，难度不太高不至于面试时紧张想不出来，又对基础有一定考察

CEBBCAT

2021-01-28 22:49:35 +08:00 via Android

@buffzty 可以发 gist

CEBBCAT

2021-01-28 22:50:40 +08:00 via Android

@Livid 考虑不考虑检测到两行 ``` 就提示使用 gist ？

iCineon

2021-01-29 08:46:54 +08:00

vector<int> sortedArray(vector<int>& nums){
int n=(int)nums.size();
int l=0,r=n-1,i=0;
while (l<r && i<n) {
if (nums[i]%2==0) {
swap(nums[i++], nums[r--]);
}else{
swap(nums[i++], nums[l++]);
}
if (i>=r)break;
}
reverse(nums.begin()+1+l, nums.end());
return nums;
}

cxe2v

2021-01-29 09:00:13 +08:00

@linvon #35 你说得对，双指针确实是消耗时间和资源最少的解法，我可能没有那么追求极致吧，我想要的是快速解决问题

huang119412

2021-01-29 09:37:03 +08:00

剑指 offer 原题，根本不是考察怎么做出结果，而是要你找到最好的方法，这种没 [背过题 ] 就无了，就是一次快排，不过 pivot 变成了是否是奇偶数。这类还有第 K 个大、小的数。回溯法寻找路径，动态规划找最优值，更不要说那些单调栈、队列的题，不背几乎不可能找到最好的方法。背题对个人没什么太大成长，但是大环境趋势。

cxe2v

2021-01-29 09:40:18 +08:00

@huang119412 #45 也不一定说背题没成长吧，背的多见得多了，可能会影响工作中的思维，但是有几个写代码的是需要研究代码最优解如何实现的呢？

crazyxtcn

2021-01-29 10:14:08 +08:00

@yazoox 905

linglongll

2021-01-29 10:23:51 +08:00

58 同城前端 2 面题其实你如果灵活点的话可以问问面试官别头铁硬做有时候面试官也是考察你的一些交流能力的

hyq

2021-01-29 10:46:32 +08:00

我觉得这个题分两部分，一个是排序算法本身，快排，堆排等各种方式。另一个就是考比较函数。
排序算法本身不必说，就那么几种形式，书本上都有。
这个比较函数灵活性就比较大了，楼主那种方式虽然能实现，但没有答到点子上，写个简单的函数，同时判断奇偶与大小就行。

并且在实际中，排序的思路也是这样的，比较函数与排序算法一般都是分开实现的。如果面试官不懂这个道理，就怼他。

a = [1,2,3,4,5,6,7,8]

a.sort((a,b)=> {
if (a==b){return 0}
if(a%2==1 && b%2==0){return -1}
if(a%2 == 0 && b%2 == 1) {return 1}
if (a<b){return -1};
return 1
})

500miles

2021-01-29 10:59:51 +08:00

@javapythongo

else 里面的 for 循环可以省掉吗? arr[r] 和 arr[l] 直接交换就可以吧

javapythongo

2021-01-29 11:56:31 +08:00

@500miles 应该可以，我以为交换后，还要保证奇 /偶数原来的相对位置，但是这道题应该没有这样要求

rodrick

2021-01-29 13:06:40 +08:00

双指针，右边先开始找到第一个奇数，然后左边再找第一个偶数，然后交换这样吧，就是快排的思路，如果需要排序的话还要多加一下判断大小的条件？其实就是个思路问题。。刷过就会没刷过不会很正常，算法这玩意，就当八股文看就行

teawithlife

2021-01-29 13:44:42 +08:00

@buffzty #37 我觉得你的思路是对的，但是实现上可能有点问题，比如数据变成
arr := []int{2, 1, 5, 7, 4, 6, 8, 5, 6}
出来的结果就不对了
play.golang.org/p/8nk_2P3ycP2

nnd

2021-01-29 13:45:13 +08:00

func sortFilter(nums []int) []int {
j := 0
for i,v := range nums {
if v %2 != 0 {
if i != j {
nums[i],nums[j] = nums[j],nums[i]
}
j++
}
}
return nums
}

go 代码

xlzpx

2021-01-29 16:42:56 +08:00

@cxe2v pass 是通过了还是没通过。。。

cxe2v

2021-01-29 17:12:29 +08:00

@xlzpx #55 被 pass 了指没通过，passed 代表已通过

lvzx

2021-01-29 17:35:20 +08:00

他的目的是想你 O(n)时间 O(1)空间复杂度做出来，你直接开个数组写太简单了，肯定会 follow up 的

dinghmcn

2021-01-29 17:52:06 +08:00 via Android

类似于快速排序的扫一遍就可以

roselia

2021-01-29 19:21:00 +08:00

刚刚在公司的时候我就一直在想到底要怎么样才可以，回家后才做出来，哎，自己的算法真的太差了，很担心明天的面试

```javascript
function sort(array) {
let i = 0;
let left = 0;
let j = array.length - 1;
let right = array.length - 1;

while (left < right && i < array.length && j >= 0) {
while (j >= 0 && array[j] % 2 === 1) {
j--;
}
[array[right], array[j]] = [array[j], array[right]];
right--;
j--;
while (i < array.length && array[i] % 2 === 0) {
i++;
}
[array[left], array[i]] = [array[i], array[left]];
left++;
i++;
}
}
```

总结了一下，确实是快速排序类型的解法

buffzty

2021-01-29 22:59:54 +08:00

@teawithlife 不好意思,我的思路是错的.用快排重写了一下. https://play.golang.org/p/MUAdUXXk5_w
但是并不能保证后面偶数的顺序,只能这样了

waytoexplorewhat

2021-01-30 01:38:12 +08:00 via Android

我怎么觉得你的问题不是双指针，而是沟通，在解决问题之前应该先澄清问题，有什么需求、输入、输出是什么、约束是什么，这些讨论清楚了才应该开始思考问题的解决

cfwyy

2021-01-30 09:42:57 +08:00

leetcode 有类似题目。
用 python 来解就一行，直接排序就完了，不知道会不会被鄙视 - -

return sorted(arr,key=lambda x:x%2,reverse=True)

cxe2v

2021-01-30 11:20:10 +08:00

@cfwyy #62 会被鄙视，你这跟我写的第二个 function 是一个方法

cxe2v

2021-01-30 11:21:31 +08:00

@waytoexplorewhat #61 我想说的重点不是面试，我是想说工作中遇到这种问题，需要抠细节吗？

iwukong

2021-01-30 14:14:20 +08:00

国内吗现在国内面试也全算法啦？

cxe2v

2021-01-30 14:48:59 +08:00

@iwukong #65 是的，国内现在稍微好点的厂面试都要面算法了

lewinlan

2021-01-31 23:33:39 +08:00 via Android

仔细一看根本就没有排序啊只是交换位置而已，肯定是双指针了，如果我是面试官我也不接受其他解法……

maocat

2021-02-01 14:19:57 +08:00

```python
class Solution(object):
def sort(self, array):
"""
:param array:
"""
length = len(array)
i, j = 0, length - 1
while i < j:
i2 = array[i] % 2 == 0
j2 = array[j] % 2 == 0
if i2 and j2:
j -= 1
elif not i2 and not j2:
i += 1
elif i2 and not j2:
d = array[i]
array[i] = array[j]
array[j] = d
i += 1
j -= 1
else:
i += 1
j -= 1

```