V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Exsole
V2EX  ›  程序员

面试快结尾了突然来个手写算法题,结果没写出来。

  •  
  •   Exsole · 2023-04-18 09:25:38 +08:00 · 8052 次点击
    这是一个创建于 564 天前的主题,其中的信息可能已经有所发展或是发生改变。

    昨天,远程视频面试。

    感觉前面的问题回答得挺好的,突然发了个网址,让我在线写代码。

    一个全排列的算法,事后我查了是 leetcode 第 46 道原题,中等难度。

    https://leetcode.cn/problems/permutations/

    拿到题,最开始想直接数组遍历,逐步迭代,当前全排列基于上一个排列插入新数字的生成新的结果。

    结果磕磕绊绊,没写出完整。面试官最后让我说下思路。。。

    唉,郁闷了一晚上没睡着。

    41 条回复    2023-04-20 09:10:39 +08:00
    CQdake
        1
    CQdake  
       2023-04-18 09:29:01 +08:00
    1 、思路讲明白大概就可以了,说不定其他面试者连面试的问题都回答不上呢,到时候工作还是你的。
    exmario
        2
    exmario  
       2023-04-18 09:43:37 +08:00
    +1 ,本来就是考思路,谁还能直接手写代码一遍过啊
    aLazarus
        3
    aLazarus  
       2023-04-18 09:45:30 +08:00
    如果没思路的话,可以试一下申请换题
    Exsole
        4
    Exsole  
    OP
       2023-04-18 09:47:41 +08:00
    @aLazarus #3 还可以这么要求。。 第一次听说。
    poemcorner
        5
    poemcorner  
       2023-04-18 09:50:02 +08:00
    不想再郁闷一晚上就把 hot100 刷五六遍
    leon0918
        6
    leon0918  
       2023-04-18 09:56:35 +08:00
    如果前面回答的挺好的,这种情况也有机会过
    dogfight
        7
    dogfight  
       2023-04-18 09:58:05 +08:00
    chatgpt
    Exsole
        8
    Exsole  
    OP
       2023-04-18 10:02:41 +08:00
    @dogfight #7
    chatGPT 回答面试八股文,解算法题,都比人类强。
    面试的时候,遇到一些问题,我真想直接回答:“ 这种问题问下 chatGPT ,它的答案更好 ”。
    Nazz
        9
    Nazz  
       2023-04-18 10:11:18 +08:00
    DFS 可解, 虽然效率不高, 但 leetcode 不卡时间
    Erroad
        10
    Erroad  
       2023-04-18 10:14:58 +08:00
    说考思路的认真的?这种 hot100 还是回溯模板题,我面的几家答不出都是挂啊
    Biggoldfish
        11
    Biggoldfish  
       2023-04-18 10:18:57 +08:00 via Android
    考思路的认真的+1

    这种常见题不准备也该一遍秒啊,再说有思路写成代码才多久
    emSaVya
        12
    emSaVya  
       2023-04-18 10:25:07 +08:00
    出这种题说明是真的想要你的。没 ac 可惜了。
    bigxianyu
        13
    bigxianyu  
       2023-04-18 10:35:05 +08:00
    backing , 不过有一些公司思路更重要,实现不是全部
    northbrunv
        14
    northbrunv  
       2023-04-18 10:36:44 +08:00
    楼主郁闷的应该是"简单题"没写出来,有相当大的机会然而没把握住。换成难题你就不会郁闷了。
    iOCZ
        15
    iOCZ  
       2023-04-18 10:41:30 +08:00
    一般就 DFS 啥的
    dswyzx
        16
    dswyzx  
       2023-04-18 10:47:22 +08:00 via iPhone
    这题还真得 dfs ,还有个变种是数组有相同数字哎,只能说面试官有点找事吧
    Litccc
        17
    Litccc  
       2023-04-18 11:12:49 +08:00
    回溯模板题,现在面试基本都要考算法题的,楼主多刷刷吧
    Nazz
        18
    Nazz  
       2023-04-18 11:14:27 +08:00
    DFS 也能写得非常高效, 0ms AC
    https://leetcode.cn/submissions/detail/425576450/
    SeaTac
        19
    SeaTac  
       2023-04-18 11:21:46 +08:00
    这种题只要求讲思路过分了吧
    至少要写出能过基本 test case 的代码
    chenshun00
        20
    chenshun00  
       2023-04-18 11:28:32 +08:00
    @emSaVya 这么说的话,不来两数之和嘛
    optional
        21
    optional  
       2023-04-18 11:29:52 +08:00 via iPhone
    感觉是放水题
    coyoteer
        22
    coyoteer  
       2023-04-18 11:41:46 +08:00
    全排列 dfs 最简单啦
    hankai17
        23
    hankai17  
       2023-04-18 12:01:17 +08:00
    不刷题的话 应该不好想
    如果前面答得好 也没什么
    baislsl
        24
    baislsl  
       2023-04-18 12:42:50 +08:00
    @Nazz DFS 不重不漏, 已经是最优解法了
    k9982874
        25
    k9982874  
       2023-04-18 12:50:51 +08:00
    直接递归完事
    dudubaba
        26
    dudubaba  
       2023-04-18 12:52:27 +08:00
    不刷题在面试这种几分钟的紧张氛围里没几人写的出来。
    ccagml
        27
    ccagml  
       2023-04-18 13:33:49 +08:00 via Android
    可惜了,不是出 hard 感觉就是要你了
    JasonLaw
        28
    JasonLaw  
       2023-04-18 14:11:20 +08:00


    ```python
    class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
    def gen_permutations(nums) -> List[List[int]]:
    if len(nums) == 1:
    return [nums]
    permutations = []
    for i in range(len(nums)):
    for p in gen_permutations(nums[0:i] + nums[i + 1:]):
    permutations.append([nums[i]] + p)
    return permutations

    res = gen_permutations(nums)
    return res
    ```
    laowudxf
        30
    laowudxf  
       2023-04-18 14:19:28 +08:00
    没刷过力扣,想了三分钟有了思路,感觉不是很难。
    Tompes
        31
    Tompes  
       2023-04-18 14:27:02 +08:00
    全排列属于很常规的题了,出这题应该也是想让你过的
    reducm
        32
    reducm  
       2023-04-18 14:49:21 +08:00
    LeetCode 46 题的题目描述为:给定一个不含重复数字的数组 nums ,返回其所有可能的全排列。你可以按任意顺序返回答案。

    解题思路:

    该题可以使用回溯算法来解决,回溯算法解决的问题都可以抽象成树结构,每个节点表示一个状态,每个节点的子节点表示在该状态下可以转移到的所有状态。

    在本题中,我们可以将每个元素看作一个节点,然后每个节点的子节点是剩下的元素,表示选择了该元素后可以继续选择哪些元素。因此,我们可以使用回溯算法来遍历这棵树,找到所有的解。

    具体实现时,我们可以使用一个数组来保存当前选择的元素,使用一个布尔数组来标记每个元素是否已经被选择过,然后按照如下步骤进行回溯:

    如果选择的元素数量等于原始数组的长度,说明已经选择了所有元素,将当前选择的元素列表加入最终结果中。

    遍历原始数组,对于每个未被选择过的元素,将其加入选择列表中,并将其标记为已选择,然后递归进入下一层。

    回溯时,将选择列表中最后一个元素删除,并将其标记为未选择。

    重复上述步骤,直到遍历完所有状态。

    Java 代码实现:

    class Solution {
    public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, new ArrayList<>(), used, res);
    return res;
    }

    private void backtrack(int[] nums, List<Integer> temp, boolean[] used, List<List<Integer>> res) {
    if (temp.size() == nums.length) {
    res.add(new ArrayList<>(temp));
    return;
    }
    for (int i = 0; i < nums.length; i++) {
    if (!used[i]) {
    temp.add(nums[i]);
    used[i] = true;
    backtrack(nums, temp, used, res);
    used[i] = false;
    temp.remove(temp.size() - 1);
    }
    }
    }
    }

    时间复杂度:O(n×n!),其中 n 表示数组的长度,n! 表示全排列的总数,因为每个全排列包含 n 个元素,因此总共需要枚举 n×n! 个状态。

    空间复杂度:O(n),其中 n 表示数组的长度,空间复杂度取决于递归调用栈的深度和存储当前选择的元素的列表。在最坏情况下,递归调用栈的深度为 n ,因此空间复杂度为 O(n)。
    mqtdut1
        33
    mqtdut1  
       2023-04-18 16:01:26 +08:00
    一看就是递归
    再看一下,数组长度 1-6 ,那就换总写法吧
    写 6 个 if ,2 写 2 层 for ,3 写 3 层 for
    https://leetcode.cn/submissions/detail/425663532/
    Nazz
        34
    Nazz  
       2023-04-18 16:22:20 +08:00
    @mqtdut1 简单粗暴 👍🏻
    gitignore
        35
    gitignore  
       2023-04-18 16:31:54 +08:00
    递归咯,每个数插在前一个全排列的缝隙里

    [0, 1] => [ [ 0, 1 ], [ 1, 0 ] ]

    [0 , 1, 2] 相当于在上面每个数组的每个缝隙插入 2:

    [0, 1] 插入 2 得到 [2, 0, 1], [0, 2, 1], [0, 1, 2]
    [1, 0] 插入 2 得到 [2, 1, 0], [1, 2, 0], [1, 0, 2]
    Exsole
        36
    Exsole  
    OP
       2023-04-18 16:34:14 +08:00
    @gitignore #35
    我就是这么思考的。 结果写着写着卡壳了。
    kjstart
        37
    kjstart  
       2023-04-18 21:38:40 +08:00
    全排列一般用回溯, 找几个经典的题解把常见算法看看就可以了. 从第一位开始全试一遍, 下一层去掉正在使用的数字, 重复上面的步骤.
    littleBink
        38
    littleBink  
       2023-04-19 01:09:46 +08:00
    我最后面试官给了一道签到题:tom is a cat 倒序输出 cat is a tom 。一看题目以为面试官这是送我 offer ,结果折腾了五分钟,差点没写出来,总是有小细节遗漏了😂
    WashFreshFresh
        39
    WashFreshFresh  
       2023-04-19 09:37:02 +08:00
    @grahamsa0503 好久没刷题确实不熟练,像这个就是有好几种解法。
    JasonLaw
        40
    JasonLaw  
       2023-04-20 09:04:24 +08:00
    littleBink
        41
    littleBink  
       2023-04-20 09:10:39 +08:00 via iPhone
    @JasonLaw 谢谢。面试官不让用 api ,需要全部自己实现。我思路基本上是清楚的,就是实现的时候有些细节总是疏忽😂
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2531 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 10:19 · PVG 18:19 · LAX 03:19 · JFK 06:19
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.