Zoox Coding题目汇总

由于最近在准备zoox的面试，收集了下常见的面试题，汇总在下面方便大家看。
1. Roller Coaster，过山车： thread-1032995-1-1.html
2. LC 227 & LC1419:  thread-1030019-1-1.html
3. Trading Stock （因为没积分，我不知道是哪题，所以把所有LC的trading stock都记录下来了）
    LC 121 - 123， 188， 2291， 714， 309
   强烈推荐看看这个帖子，我看完有种悟了的感觉  

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
ndex，然后看对应的y在不在hash table里面，如果有且index ！= m，x，n，那就是一个答案。Time Complexity：O（n^3).
      欢迎大家提供其他思路。

===============
求米看面经

4，只要输出一种方案的话，用两个hashtable记录m*x, y-n, O(n^2)

leetcode 发表于 2024-07-10 07:20:11
4，只要输出一种方案的话，用两个hashtable记录m*x, y-n, O(n^2)

对哦，厉害👍。空间复杂度是O（n^2）
你这思路也可以求出所有的答案，hashtable里面存下所有mx的index pair不就可以了么？

微信用户_e0m4o 发表于 2024-7-10 08:30
对哦，厉害👍。空间复杂度是O（n^2）
你这思路也可以求出所有的答案，hashtable里面存下所有mx的in ...

那样 worse case就不是O(N^2)了

leetcode 发表于 2024-7-10 10:20
4，只要输出一种方案的话，用两个hashtable记录m*x, y-n, O(n^2)

请问如何快速判断不重复使用数字？

比如相同结果的y-n 可以出现在不同的index组合，其中一些和mx的有重复，有些没有。
直接的做法是保存所有y-n的index, 然后找和当前mx index不相交的。但这样复杂度就高了。

Richardftd 发表于 2024-7-21 07:36
请问如何快速判断不重复使用数字？

比如相同结果的y-n 可以出现在不同的index组合，其中一些和mx的有 ...

这个题最坏情况会退化成O(n^4),比如整个数组全是0的情况，那么任意4个数的组合都满足，那么一共就会有C(n,4) 种。用哈希表优化，只能在暴力的时候根据实际数据优化掉一些不必要的方案check，只能说是做些常数级的剪枝优化，所以感觉这题基本就是用哈希表先O(n^2) 存储下所有mx的key-val对，其中m, x是可以互换的。然后O(n^2)暴力枚举n, y，这2个是减法关系，不能互换，然后根据y - n 的值去上述哈希表里查询，有值再去遍历val里的所有pair 去判重下标。