狗家onsite面经

感谢分享

楼主请问一下 给定n个点，count到底有多少个与x，y轴平行的正方形是由这n个点组成的。这题怎么做啊？

楼主说说第二轮怎么做的？ 谢谢

21kekeke 发表于 2018-4-7 14:26
楼主请问一下 给定n个点，count到底有多少个与x，y轴平行的正方形是由这n个点组成的。这题怎么做啊？

这道题和leetcode上的Number of Corner Rectangle是类似的做法。把所有的点按照y坐标存到一个hash表里，每个entry是一个数组。然后按y坐标大小从大到小遍历每个数组，枚举所有的点对，假设现在是a和b点在y＝r上，那么算出它们的距离d，在r＋d的那个hash表的数组里找有没有对应的c和d两点，和a，b组成正方形。为了让这个查找变成O（1），你可以把数组改成另一个hash表，这样就变成了一个2维的hash表了，一个y坐标，一个x坐标。复杂度是O（n^2）。
这个还可以优化到O（n^1.5），可以参考leetcode上的答案。

rhwfyf 发表于 2018-4-7 14:42
楼主说说第二轮怎么做的？ 谢谢

第二轮用到两个c++里的map就好了。
第一个map的key是timestamp，第二个map里的key是price。有一个小情况是同一个price可能会有好几个timestamp，要额外处理一下。

actionlee 发表于 2018-4-7 20:42
这道题和leetcode上的Number of Corner Rectangle是类似的做法。把所有的点按照y坐标存到一个hash表里， ...

太感谢了！

actionlee 发表于 2018-4-6 13:49
我面试的时候答的是用一个2维的hash table。row作为第一个维度的key，col作为第二个维度的key。这样可以 ...

楼主好牛，请问可不可以讲一下具体这个balanced binary tree是怎么构建的？针对sparse matrix这道题。

actionlee 发表于 2018-4-7 20:46
第二轮用到两个c++里的map就好了。
第一个map的key是timestamp，第二个map里的key是price。有一个小情况 ...

这里应该是有多支股票吧？

actionlee 发表于 2018-4-6 14:31
先说可以解这个问题的算法：随便选一个单词W，然后guess它和秘密单词S的相似度，得到一个值。这里我们ass ...

不太理解楼主这里说的iterate over每个单词W，那这样每个W都跟S算距离，最后不是会调用guess function很多次么？

第五题我有一个很骚的做法，依次传入26个字符，这样你知道要你猜的单词由哪几个字母组成，然后遍历一遍字典，O(n)时间复杂度，O(1) extra space