QuoraOA没那么难嘛（还是要感谢提前在地里读了题！）

都说Quora的OA时间短（70min）题难，所以在地里读了不少原题，其中hard题（伪hard）有很多帖子只给题目不给解答，或者说了跟没说一样，真不知道给谁看的（白眼，还那么多大米）。比如我在准备过程中刷到"给定array，和一串query，求query指定的区间内指定数字出现的次数之和"这道题，几乎刷不到答案，唯一我看到的答案那位大佬给的什么建一个hashmap什么vector什么pair的还是有点宽泛实在搞不懂，我当时就安慰自己一定不会遇到这题。害！根据考试第一定律不复习啥考啥的原则，我这次真遇到了。。。但是压力使人才思敏捷，最终我还是在20min做完了4道题（847分），希望能拿一个面试吧。。。以下是原题和解答（详尽而免费），按照惯例不设限，欢迎白嫖，欢迎随手赏点大米，谢谢大家。
1. 给定array，找出所有连续三元素组成的tuple，使得其中有且仅有两个元素相同。
2. 给定n个小朋友围成圈和区间k，从k号小朋友开始枪杀(?)，然后往下数k个小

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

每一个元素，然后额外的，当前arr[idx]的值p要额外+1：dict[p][idx] += 1。这样就给每个元素建立了从1到每个pos的区间个数和的DP cache。设query为(from, to, k), 则最终输出dict[k][to] - dict[k][from-1]之和即可。时间复杂度降为O(m'n)，m'为所有待查询值的种类。由于可能有很多同一个k值重复查询，使得m'<<m，因此得到了一定的优化。Medium。
求撒点五常大米，谢谢大家！

楼主牛b，我70分钟勉强做完了4道。。。宁20分钟就做完了，请接受我的膝盖！

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

mzpyeah 发表于 2019-10-16 16:58
就是算固定长度的子矩阵的和，然后把最大和的元素都取出来，去重，结束

计算所有某固定大小的矩阵的和-->选出和最大的矩阵-->去除该矩阵中重复元素-->再次改子矩阵的和？？对不

lz 看不到额。。加了大米 可以给看一些不

ge就服你 发表于 2019-10-15 12:38
lz 看不到额。。加了大米 可以给看一些不

?我没设积分限制啊 为什么会看不到（我论坛新人 不太知道为什么有看不到的情况）

以及我看很多人用各种奇怪谐音代替公司名称或LeetCode及题目序号，这都是为啥啊？？？挠头.gif

mzpyeah 发表于 2019-10-15 13:14
?我没设积分限制啊 为什么会看不到（我论坛新人 不太知道为什么有看不到的情况）

可能是系统设定吧。lz能不能复制粘贴回复下~感谢

mzpyeah 发表于 2019-10-15 13:18
以及我看很多人用各种奇怪谐音代替公司名称或LeetCode及题目序号，这都是为啥啊？？？挠头.gif

防 引渡仁？

mzpyeah 发表于 2019/10/16 04:13:53
1. 给定array，找出所有连续三元素组成的tuple，使得其中有且仅有两个元素相同。
2. 给定n个小朋友围成圈和区间k，从k号小朋友开始枪杀(?)，然后往下数k个小朋友并杀害，直到最后仅剩...

lz牛逼 子数字数字

lz问一下 。 第三问啥意思 有点绕。

ge就服你 发表于 2019-10-16 12:03
lz问一下 。 第三问啥意思 有点绕。

就是算固定长度的子矩阵的和，然后把最大和的元素都取出来，去重，结束