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

Shopee SG 前端面试算法题

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

    一面:

    Itersection of Multiple Arrays
    
    Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
    Output: [3,4]
    
    Input: nums = [[1,2,3],[4,5,6]]
    Output: []
    
    实现一个时间复杂度为 O(n) 的算法
    
    第 1 条附言  ·  154 天前
    目前还没有人写得出来时间复杂度为 O(n) 的算法,哪怕是空间换了时间。
    43 条回复    2022-05-07 11:06:03 +08:00
    ChevalierLxc
        1
    ChevalierLxc  
       157 天前
    [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]].toString().split(',')
    这样展开成一个 array?
    leokino
        2
    leokino  
       157 天前   ❤️ 1
    子数组如果元素不重复直接计数然后刷一遍找出现三次的。如果元素重复就保持两个数组。都是 O(n) 的,很简单。然后一般面试不让泄题的,不过这种题无所谓吧。
    cuvii
        3
    cuvii  
       157 天前
    这么简单?
    leokino
        4
    leokino  
       157 天前
    @leokino 三次 -> 对应次数
    neilyoone
        5
    neilyoone  
       157 天前
    不知道前端用不用 python, python 很好解.
    wd
        6
    wd  
       157 天前 via iPhone
    循环然后建一个 map 计数就行了,最后一个数组的时候看看 map 和数组数量比较下
    Wongbrah
        7
    Wongbrah  
       157 天前   ❤️ 1
    nums.reduce((result, currentArray) => result.filter(num => currentArray.includes(num)))
    NathanInMac
        8
    NathanInMac  
       157 天前
    @Wongbrah 老哥你自己数数你这个复杂度是多少
    Araell
        9
    Araell  
       157 天前 via Android
    怎么想都是 O(n * m) 啊
    bzw875
        10
    bzw875  
       157 天前   ❤️ 1
    ```
    const getItersection = (arr) => {
    const result = [];
    for (let i in arr[0]) {
    const tmp = arr[0][i];
    let has = 1;
    for (let j = 1; j < arr.length; j++) {
    if (arr[j].includes(tmp)) {
    has++;
    }
    }
    if (has === arr.length) {
    result.push(tmp);
    }
    }
    return result;
    };
    ```
    zhengjian
        11
    zhengjian  
       157 天前
    zhengjian
        12
    zhengjian  
       157 天前
    好吧,原来是 LeetCode 2248 ,刚提交通过了,😂

    https://leetcode.com/problems/intersection-of-multiple-arrays/solution/by-nehzil-9383/
    YARU
        13
    YARU  
       157 天前
    rioshikelong121
        14
    rioshikelong121  
       156 天前   ❤️ 1
    这个 N 其实指的应该是总的元素个数对吧。 说下思路吧。
    循环同时维护一个数据结构 (Map. Object) 以元素为 key 进行计数不就行了。

    ```javascript
    function interaction(arrays){

    const counter = {};

    for (let i = 0; i < arrays.length; i++) {
    const array = arrays[i];
    //avoid repeated count in one array.
    const cache = {};

    for (let j = 0; j < array.length; j++) {
    const element = array[j];

    if (!(element in counter)) {
    counter[element] = 1;
    } else if (!(element in cache)) {
    counter[element] += 1;
    cache[element] = true;
    }

    }
    }


    return Object.entries(counter).filter((v, i) => (v[1] >= arrays.length)).map((v) => v[0]);

    }


    ```
    richardwong
        15
    richardwong  
       156 天前   ❤️ 1
    /**
    *
    * @param {number[][]} nums
    * @return {number[]}
    */
    var intersection = function (nums) {
    let res = [];
    // pojo {} 对象的 key 顺序默认是有序的,而 map 的 key 顺序,是按其 set 的顺序来的
    // 所以这里使用 {} 而非 new Map()
    const map = {};
    for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums[i].length; j++) {
    // 根据题意,内层数组已经去重过
    const ele = nums[i][j];
    let count = map[ele];
    if (count > 0) {
    // 记录每个元素出现的次数
    map[ele] = ++count;
    } else {
    map[ele] = 1;
    }
    }
    }
    // 出现次数跟外层数组长度一致,即为交集中的元素
    Object.keys(map).forEach((el) => {
    if (map[el] === nums.length) {
    res.push(el);
    }
    });
    return res;
    };

    作者:YUFENGWANG
    链接: https://leetcode-cn.com/problems/intersection-of-multiple-arrays/solution/by-yufengwang-776k/
    来源:力扣( LeetCode )
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    CookCoder
        16
    CookCoder  
       155 天前
    求交集么
    rongchuan
        17
    rongchuan  
       155 天前
    挺简单的...碰到这个题只能说运气太好...
    rongchuan
        18
    rongchuan  
       155 天前   ❤️ 1
    @rongchuan
    js 在代码这里,不谢,多刷刷题吧...
    /**
    * @param {number[][]} nums
    * @return {number[]}
    */
    var intersection = function(nums) {
    const m =nums.length;
    const arr=nums.flat();
    const map =new Map();
    const result =[];
    for(let i =0;i<arr.length;i++){
    map.set(arr[i],map.has(arr[i])? map.get(arr[i])+1:1);
    if(map.get(arr[i])===m)
    result.push(arr[i])
    }
    result.sort((a,b)=>a-b);
    return result;
    };
    YadongZhang
        19
    YadongZhang  
    OP
       155 天前 via Android
    @rongchuan

    空间换时间
    jackbrother
        20
    jackbrother  
       154 天前
    你运气真好
    YadongZhang
        21
    YadongZhang  
    OP
       154 天前
    目前还没有人写得出来时间复杂度为 O(n) 的算法,哪怕是空间换了时间。
    biubiuF
        22
    biubiuF  
       154 天前
    如果不含重复元素的话用数组字典就行,时间复杂度就是 o(n)
    rongchuan
        23
    rongchuan  
       154 天前
    @YadongZhang ...我写的这么简单,就一个 for 循环,这还不是 O(n)啊...我感觉这里你没理解对,可以简单试试,你随便输个测试 case ,debug 看看堆栈,是不是 O(n)。还有一点就是,前端算法面试一般只需要考虑时间就行,没人会让你写限制空间多少的代码的,要考虑空间的话就不可能用 js 写。我这里声明这么多变量就是为了好看,方便面试官看懂这个代码。
    YadongZhang
        24
    YadongZhang  
    OP
       154 天前 via Android   ❤️ 2
    @rongchuan

    sort 就已经不是 O (n) 了
    rongchuan
        25
    rongchuan  
       154 天前
    @YadongZhang ...你要这么说的话.flat 就不是 O(n)了,严格来说是 O(3n),但算法复杂度不算常量的呀....O(3n)还是 O(n)
    YadongZhang
        26
    YadongZhang  
    OP
       154 天前 via Android
    @rongchuan

    js 内置 sort 算法的时间复杂度是 O(n*lgn),不管是用 Merge Sort 还是 Tim Sort ,所以上述算法的整体时间复杂度应该是 O(n*lgn),常数这种情况下是可以忽略的

    如果有优化的方法,可以用 @richardwong 提到的 obj 来有序遍历,而不是 Map ,最后的结果就不用重新排序了
    rongchuan
        27
    rongchuan  
       154 天前   ❤️ 1
    @YadongZhang 这道面试算法是想实现求交集,关键算法是用哈希表这一步,所以他说的复杂度也是指的哈希表这一步的复杂度,而且 js 的 sort 也不一定是 nlogn 。打个比方,一些稍微复杂的算法,会有很多这种类似操作,不是算法核心的点都可以用语法糖写,因为是算法面试,不是在优化系统,也不是算法竞赛(即使是算法竞赛,也是用 c++的一些库来写,同样是语法糖,不过效率高一点),要严格扣的话,可以把这些语法糖代码写在 main 执行函数里,关键代码单独写成函数,那这个函数就是严格 O(n)的了,因为像 leetcode 一类的刷题平台,他是帮你把 main 函数写了,真要是扣到常量级的复杂度,那肯定是你自己写 main 函数,就能这么操作了
    YadongZhang
        28
    YadongZhang  
    OP
       154 天前 via Android
    @rongchuan

    是的,论查找一个元素,HashMap 和 HashSet 的 O (1) 时间复杂度优于数组的线性查找 O(n) 和二分查找 O(lgn)
    4kingRAS
        29
    4kingRAS  
       153 天前
    没细想,不过估计最终大概是个 O ( c*n )的东西
    metrue
        30
    metrue  
       153 天前
    const intersection = (nums = []) => {
    let m = {}
    nums.forEach((arr, idx) => {
    if (idx === 0) {
    arr.forEach((c) => {
    m[c] = true
    })
    } else {
    const nm = {}
    arr.forEach((c) => {
    if (m[c] === true) {
    nm[c] = true
    }
    })
    m = nm
    }
    })
    return Object.keys(m)
    }


    随手写了一下,很丑陋的进行了 object 的 reference 重写.
    zhzy0077
        31
    zhzy0077  
       153 天前
    这题没说要有序 leetcode 的题目要求有序
    对于无序输入你要有序输出只能在 O(N)的排序里想法子 如果不对数组数字设限制的话是不可能的 OP 也别想着难倒所有人了
    DonkeyBenjamin
        32
    DonkeyBenjamin  
       153 天前
    I don't know how to write js, so here is my first python attempt (which passed)

    https://leetcode.com/submissions/detail/692241616/

    ```python
    class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
    num_count = [0 for _ in range(1000)]
    for arr in nums:
    for num in arr:
    num_count[num-1] += 1

    l = len(nums)
    result = [i+1 for i in range(1000) if num_count[i] == l]
    return result
    ```
    pigmen
        33
    pigmen  
       152 天前
    如果最后不要求顺序的话?比如 3,4 输出为 4,3
    O(n) 应该很简单?
    YePiaoling
        34
    YePiaoling  
       152 天前
    @leokino +1
    拿数组记一下就可以了
    jayLink
        35
    jayLink  
       152 天前
    数组记录下标
    ```
    func intersection(nums [][]int) []int {
    arr:=[10001]int{} //数组存储结果不排序
    m:=len(nums)
    for i:=0;i<len(nums);i++{
    for j:=0;j<len(nums[i]);j++{
    arr[nums[i][j]]++
    }
    }

    res:=[]int{}
    for i,v:=range arr{
    if v==m{
    res = append(res,i)
    }
    }
    return res
    }
    ```
    zhzbql
        36
    zhzbql  
       152 天前
    function itersection(nums) {
    let indexToNumValue = {}
    let len = nums.length
    nums.forEach((subArray, subArrayIdx) => {
    subArray.forEach(v => {
    indexToNumValueV = indexToNumValue[v]
    if (indexToNumValueV) {
    if (!indexToNumValueV.indexToParent[subArrayIdx]) {
    indexToNumValueV.len += 1
    indexToNumValueV.indexToParent[subArrayIdx] = 1
    }
    }
    else indexToNumValue[v] = { len: 1, indexToParent: { [subArrayIdx]: 1 } }
    })
    })
    return Object.keys(indexToNumValue).filter(key => indexToNumValue[key].len >= len)
    }
    brucep
        37
    brucep  
       151 天前
    计数排序,时间复杂度 O(n),空间复杂度 O(n)。
    上面有朋友给了 lc 的题目链接,数组元素的取值范围和数组长度是一个范围的,符合计数排序的要求
    brucep
        38
    brucep  
       151 天前
    附上代码
    /**
    * 2248. Intersection of Multiple Arrays
    * Solution: Counting Sort
    * Time Complexity: O(n)
    * Space Complecity: O(n)
    * @param {number[][]} nums
    * @return {number[]}
    */
    var intersection = function(nums) {
    const counts = new Array(1000 + 10).fill(0);
    for (const numArr of nums) {
    for (const num of numArr) {
    counts[num]++;
    }
    }
    return counts.map(
    (val, idx) => val === nums.length ? idx : 0
    ).filter(val => val !== 0);
    };
    surmon
        39
    surmon  
       150 天前
    一个 Map 不就完了
    jzz7280
        40
    jzz7280  
       150 天前
    function intersection(nums) {
    let repeat = new Set()
    let reset = new Set()
    const result = []
    nums.forEach((item, index) => {
    item.forEach(val => {
    if (index === 0) {
    repeat.add(val)
    } else if (repeat.has(val)) {
    reset.add(val)
    if (index+1 === nums.length) {
    result.push(val)
    }
    }
    })
    if (index !== 0) {
    repeat = reset
    reset = new Set()
    }
    })
    return result
    }
    tingyunsay
        41
    tingyunsay  
       150 天前
    @surmon 楼主意思是要 O(n)时间复杂度,结果要有序输出,会有一个 sort
    afutureus
        42
    afutureus  
       149 天前 via iPhone
    @tingyunsay 不可能啊。

    极端情况,输入只有一个列表。

    输入无序,输出有序,那么必须经过排序算法。

    基于比较的算法 至少 nlogn 。

    其它算法,不给数据范围等于耍流氓 :(
    tingyunsay
        43
    tingyunsay  
       149 天前
    @afutureus 有这种情况,他的数字若是限制在 0 ~ n 的,可以申请一个长度为 n 的数组,直接写入到对应的位置标记个 1 ,未写入的为 0 ,最后从 0 到 n 扫描结果,非 0 的加入结果,这样总体是算是 O(2n),也有序。不过感觉他这题目也没限制...
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2101 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 86ms · UTC 12:34 · PVG 20:34 · LAX 05:34 · JFK 08:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.