V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
cxe2v
V2EX  ›  职场话题

今天面试遇到的情况

  •  
  •   cxe2v · 358 天前 · 8577 次点击
    这是一个创建于 358 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    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
        1
    lcc142625  
       358 天前
    这种呢,不能说你的问题,我也遇到过,就是面的时候卡壳想不出来题解,不过那会我面的滴滴的,起码面试官还给我思路,不至于一直两个人尴尬着,有些问题我回头想,能理解也能做出来,但是面试真就紧张,就会怯场,害,这个别太影响你下回面试,每家面试套路都不一样
    cxe2v
        2
    cxe2v  
    OP
       358 天前
    @lcc142625 #1 我这个面试官也是给了我提示我才知道他想要用双指针的,也没有说一直尴尬,因为是在网页上写代码,滴滴我面过,运气好到没有做任何题就直接到了终面然后被 pass 了,运气啊真的是实力的一部分
    carlclone
        3
    carlclone  
       358 天前
    啥双指针, 他是想你原地排序吧, O(1)空间复杂度 , 我知道的一个方法是用快排的分区思想, 写起来也不算很简单
    v2webdev
        4
    v2webdev  
       358 天前
    这题用双指针怎么做?
    carlclone
        5
    carlclone  
       358 天前
    @carlclone 看错题目了...
    lcc142625
        6
    lcc142625  
       358 天前
    emm,运气,看面试官和你对不对眼了,我就是,面试类似走了流程直接过了,莫心焦,我也是面了两个月左右才找到的
    lemon94
        7
    lemon94  
       358 天前   ❤️ 1
    如果面试官没限定你使用内存的空间,那你的解法没什么问题。
    如果限定你原地,那你的方法就不行了。
    fiypig
        8
    fiypig  
       358 天前 via iPhone
    一般来说解决问题以后再来谈优化,你没错的
    hello2060
        9
    hello2060  
       358 天前 via iPhone   ❤️ 1
    开始写之前多和面试官沟通呗,或者先把思路说一遍,如果是他要的你再开始写。

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

    类似于快排,一个指针 i 初始化为 0,p=-1,如果偶数 i++,如果是奇数 swap(++p, i); i++
    不过他确实要把条件先告诉你,比如不能利用额外空间
    djFFFFF
        10
    djFFFFF  
       358 天前
    即使是不从算法复杂度(常数优化)的角度考虑,你的做法涉及 array 对象创建(还没指定大小,后续可能涉及 array 扩容),cpu 指令数还是比原地排序要多很多的。当然没多到指数级别就是了。
    我是面试官的话,我会觉得你能干活,但不抠细节。所以看你面的是什么岗位以及这个岗位的要求是什么了。
    ccvzz
        11
    ccvzz  
       358 天前   ❤️ 1
    ```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
        12
    cxe2v  
    OP
       358 天前
    @djFFFFF #10 你这个说的有道理,原地排序确实省资源,至于面的岗位,面试官也不清楚具体干啥
    djFFFFF
        13
    djFFFFF  
       358 天前
    @cxe2v 那我觉得面试官自己也没想好他的面试方式是否正确,是否能帮公司招到合适的人。
    devfeng
        14
    devfeng  
       358 天前 via Android
    可能是你面试经验少了,现在都这个套路,给一个算法题,给出最优解才能接着聊。ps.之前面试遇到个差不多的题,也是双指针,要求奇数在奇数位,偶数在偶数位。
    ttys001
        15
    ttys001  
       358 天前
    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
        16
    chocovon  
       358 天前   ❤️ 1
    我倒是觉得,如果是面对某个性能要求不高的业务问题,你的代码才是好代码,做到了就事论事,没有引入不必要的复杂性
    isRealLeven
        17
    isRealLeven  
       358 天前
    也许是你刷题刷少了。本来题目不难,而且说明了双指针。应该很快就能做出来
    javapythongo
        18
    javapythongo  
       358 天前
    @ccvzz 题目要求奇偶顺序后,还要求相对奇数 /偶数之间的相对位置大小不能变
    cxe2v
        19
    cxe2v  
    OP
       358 天前
    @isRealLeven #17 对的,就是题刷少了,算法题真的刷得少
    wjploop
        20
    wjploop  
       358 天前   ❤️ 4
    理解题意确实很重要,咋一看我以为“奇数序列”和“偶数序列”要求有序,若是这样,改变了“两个数的比较规则”而已,用常用的排序方法就行,时间复杂度必然大于等于 nlogn (不考虑桶排序)。
    既然没有要求,时间复杂度就可以降到 O(n)了,作为面试题,这题的应该隐含了一个硬性要求“空间复杂度为 O(1)”。 那么,确实是用双指针的做法了。简单的思路就是,
    假设目标序列为左边奇数右边偶数,
    设立左右指针,左指针指向 0, 右指针指向 len - 1
    左指针往右移动一直遇到偶数停住 i,右指针往左移动直到遇到奇数停住 i,交换这两位置的数
    不断重复以上操作,直到两指针相遇结束
    javapythongo
        21
    javapythongo  
       358 天前
    这样子吗?
    ```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
        22
    javapythongo  
       358 天前
    感觉我写的这个还不如你的空间换时间
    crazyxtcn
        23
    crazyxtcn  
       358 天前
    @javapythongo 我觉得这个问题很重要,我开始以为输出要求不改变在原数组中的相对位置,然后在 leetcode 上搜了一下,发现有原题,没要求相对位置,不要求相对位置就很简单了
    ezksdo
        24
    ezksdo  
       358 天前 via iPhone   ❤️ 1
    这和快排有啥区别,直接让比较函数偶数比基数大不就行了吗
    YouLMAO
        25
    YouLMAO  
       358 天前 via Android
    排序个 jb,2 个 for 循环,先打奇数再打偶数,6 行代码,最优的时间和空间复杂度
    YouLMAO
        26
    YouLMAO  
       358 天前 via Android
    出题的人连最优算法都不知道,指针个屁
    chienius
        27
    chienius  
       358 天前 via iPhone
    双路快速排序了解一下,其实就是快排分区算法
    mccreefei
        28
    mccreefei  
       358 天前
    快排 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
        29
    onyourroad  
       358 天前
    多刷点 leetcode 就好了。
    yazoox
        30
    yazoox  
       358 天前
    @crazyxtcn 题目编号是?
    wjploop
        31
    wjploop  
       358 天前
    @crazyxtcn 要是还有条件要求排序稳定(排序后相对位置不变),得牺牲空间或时间吧。牺牲空间就是楼主的做法了,牺牲时间可以用插入排序,时间复杂度要 n 平方了
    lwlizhe
        32
    lwlizhe  
       358 天前
    话说这题要不要排序啊,

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

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

    要排序的话,好像所有人都做错了
    lwlizhe
        33
    lwlizhe  
       358 天前
    @lwlizhe 好吧,确实有人问了下奇偶相对的问题……当我没说
    e583409
        34
    e583409  
       358 天前
    面试的目的是什么?
    linvon
        35
    linvon  
       358 天前   ❤️ 1
    首先这就是个奇偶区分的问题,不是什么排序,双指针是最简单的解法,快排啥的就扯远了
    其次从性能上来说,你的解法确实存在些问题,不如自己分析一下各种解法的时间和空间复杂度。
    算法面试就是这样,不服的话也没办法,啃吧
    kiripeng
        36
    kiripeng  
       358 天前
    给他整个三路排序
    buffzty
        37
    buffzty  
       358 天前
    我记得没错的话快排里有用到跟原地排序的算法.
    你这个题没有要求奇偶数组再排序 只要 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
        38
    buffzty  
       358 天前   ❤️ 1
    不能直接发代码是真的恶心.交流体验极差
    hello2060
        39
    hello2060  
       358 天前 via iPhone
    @linvon 快排没问题啊,线性复杂度,三行代码,而且能保证左边部分的相对顺序。
    ssynhtn
        40
    ssynhtn  
       358 天前 via Android
    说实话我觉得这个题挺好,难度不太高不至于面试时紧张想不出来,又对基础有一定考察
    CEBBCAT
        41
    CEBBCAT  
       358 天前 via Android
    @buffzty 可以发 gist
    CEBBCAT
        42
    CEBBCAT  
       358 天前 via Android
    @Livid 考虑不考虑检测到两行 ``` 就提示使用 gist ?
    iCineon
        43
    iCineon  
       358 天前
    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
        44
    cxe2v  
    OP
       358 天前
    @linvon #35 你说得对,双指针确实是消耗时间和资源最少的解法,我可能没有那么追求极致吧,我想要的是快速解决问题
    huang119412
        45
    huang119412  
       358 天前
    剑指 offer 原题,根本不是考察怎么做出结果,而是要你找到最好的方法,这种没 [背过题 ] 就无了,就是一次快排,不过 pivot 变成了是否是奇偶数。这类还有第 K 个大、小的数。回溯法寻找路径,动态规划找最优值,更不要说那些单调栈、队列的题,不背几乎不可能找到最好的方法。背题对个人没什么太大成长,但是大环境趋势。
    cxe2v
        46
    cxe2v  
    OP
       358 天前
    @huang119412 #45 也不一定说背题没成长吧,背的多见得多了,可能会影响工作中的思维,但是有几个写代码的是需要研究代码最优解如何实现的呢?
    crazyxtcn
        47
    crazyxtcn  
       358 天前
    @yazoox 905
    linglongll
        48
    linglongll  
       358 天前
    58 同城前端 2 面题 其实你如果灵活点的话可以问问面试官 别头铁硬做 有时候面试官也是考察你的一些交流能力的
    hyq
        49
    hyq  
       358 天前
    我觉得这个题分两部分,一个是排序算法本身,快排,堆排等各种方式。另一个就是考比较函数。
    排序算法本身不必说,就那么几种形式,书本上都有。
    这个比较函数灵活性就比较大了,楼主那种方式虽然能实现,但没有答到点子上,写个简单的函数,同时判断奇偶与大小就行。

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

    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
        50
    500miles  
       358 天前
    @javapythongo

    else 里面的 for 循环可以省掉吗? arr[r] 和 arr[l] 直接交换就可以吧
    javapythongo
        51
    javapythongo  
       358 天前
    @500miles 应该可以,我以为交换后,还要保证奇 /偶数原来的相对位置,但是这道题应该没有这样要求
    rodrick
        52
    rodrick  
       357 天前
    双指针,右边先开始找到第一个奇数,然后左边再找第一个偶数,然后交换这样吧,就是快排的思路,如果需要排序的话还要多加一下判断大小的条件?其实就是个思路问题。。刷过就会没刷过不会很正常,算法这玩意,就当八股文看就行
    teawithlife
        53
    teawithlife  
       357 天前
    @buffzty #37 我觉得你的思路是对的,但是实现上可能有点问题,比如数据变成
    arr := []int{2, 1, 5, 7, 4, 6, 8, 5, 6}
    出来的结果就不对了
    play.golang.org/p/8nk_2P3ycP2
    nnd
        54
    nnd  
       357 天前
    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
        55
    xlzpx  
       357 天前
    @cxe2v pass 是通过了还是没通过。。。
    cxe2v
        56
    cxe2v  
    OP
       357 天前
    @xlzpx #55 被 pass 了指没通过,passed 代表已通过
    lvzx
        57
    lvzx  
       357 天前
    他的目的是想你 O(n)时间 O(1)空间复杂度做出来,你直接开个数组写太简单了,肯定会 follow up 的
    dinghmcn
        58
    dinghmcn  
       357 天前 via Android
    类似于快速排序的扫一遍就可以
    roselia
        59
    roselia  
       357 天前
    刚刚在公司的时候我就一直在想到底要怎么样才可以,回家后才做出来,哎,自己的算法真的太差了,很担心明天的面试

    ```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
        60
    buffzty  
       357 天前
    @teawithlife 不好意思,我的思路是错的.用快排重写了一下. https://play.golang.org/p/MUAdUXXk5_w
    但是并不能保证后面偶数的顺序,只能这样了
    waytoexplorewhat
        61
    waytoexplorewhat  
       357 天前 via Android
    我怎么觉得你的问题不是双指针,而是沟通,在解决问题之前应该先澄清问题,有什么需求、输入、输出是什么、约束是什么,这些讨论清楚了才应该开始思考问题的解决
    cfwyy
        62
    cfwyy  
       357 天前
    leetcode 有类似题目。
    用 python 来解就一行,直接排序就完了,不知道会不会被鄙视 - -

    return sorted(arr,key=lambda x:x%2,reverse=True)
    cxe2v
        63
    cxe2v  
    OP
       357 天前
    @cfwyy #62 会被鄙视,你这跟我写的第二个 function 是一个方法
    cxe2v
        64
    cxe2v  
    OP
       357 天前
    @waytoexplorewhat #61 我想说的重点不是面试,我是想说工作中遇到这种问题,需要抠细节吗?
    iwukong
        65
    iwukong  
       356 天前
    国内吗 现在国内面试也全算法啦?
    cxe2v
        66
    cxe2v  
    OP
       356 天前
    @iwukong #65 是的,国内现在稍微好点的厂面试都要面算法了
    lewinlan
        67
    lewinlan  
       355 天前 via Android
    仔细一看根本就没有排序啊只是交换位置而已,肯定是双指针了,如果我是面试官我也不接受其他解法……
    maocat
        68
    maocat  
       354 天前
    ```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

    ```
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2388 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 117ms · UTC 04:48 · PVG 12:48 · LAX 20:48 · JFK 23:48
    ♥ Do have faith in what you're doing.