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

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

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

    昨天,远程视频面试。

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

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

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

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

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

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

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

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


    ```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  
       345 天前
    没刷过力扣,想了三分钟有了思路,感觉不是很难。
    Tompes
        31
    Tompes  
       345 天前
    全排列属于很常规的题了,出这题应该也是想让你过的
    reducm
        32
    reducm  
       345 天前
    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  
       345 天前
    一看就是递归
    再看一下,数组长度 1-6 ,那就换总写法吧
    写 6 个 if ,2 写 2 层 for ,3 写 3 层 for
    https://leetcode.cn/submissions/detail/425663532/
    Nazz
        34
    Nazz  
       345 天前
    @mqtdut1 简单粗暴 👍🏻
    gitignore
        35
    gitignore  
       345 天前
    递归咯,每个数插在前一个全排列的缝隙里

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