狗家 offer 已签，分享下心得和 filter

感谢楼主~~~~ 受益良多~~~~

hellowglados 发表于 2018-10-2 21:37
我是转专业，还是到的美国才转的专业。
因为没有 cs 基础，也没有自信去找实习。
面试很难拿，但是准备 ...

我也是转专业的，好受鼓舞啊~~~~楼主好棒~~~~

带白板擦点个赞。。。

楼主~~~恭喜恭喜
有这么好的结果都是因为你的辛勤付出！！！棒棒棒

我也马上就要onsite了~~~想求问你发的onsite面经贴的第一题
原题和follow up2的思路，向楼主学习
感恩感恩~~~

黑人小哥：
Input: list of points(x, y)
返回一个点，使得其右上角的点的数目为最大。就是找最左下的点。
follow up:
input 再给一个 point找到离给的point 最近的点。
follow up：
要找许多个点的最近的点。

oo小天使oo 发表于 2018-10-3 08:36
楼主~~~恭喜恭喜
有这么好的结果都是因为你的辛勤付出！！！棒棒棒

我没发过面经诶。

不过我分享下我的思路。
第一问，sort points by x，sort points by y. (2 nlogn)
create 2 dictionaries, num_right = {point: 此点右边点的数量}, num_top = {point: 此点上边点的数量} (2n)
find the point that max(num_right[point] + num_top[point]) (n)
在用数学证明，这个点和要求的点是一个点。
时间复杂度 = nlogn

follow up:
简单的方法的就是分 bucket。每个点在自己所在的 bucket 和周围 8 个 buckets 的中的点找最近点。
还一个方法稍微复杂点，
xx = array sort points by x，
yy = array sort points by y.
先 bs 在 xx 找到离 target x 方向最短的点，
在 bs 在 yy 找到离 target y 方向最短的点。
这个两个点中取最近的点 local_min
local_min_length = local_min 与 target 的距离
再在 xx 中对在 [target_x - local_min_length, target_x + local_min_length] 这个区间里的点找有没有跟近的。
yy 同理。
最后找到的点就是。
找每个点的时间复杂度接近 logn
n 个点就是 nlogn
加上前面 sort 的 nlogn
最后时间复杂度 nlogn

只是提供个人的一点思路，不保证正确。
祝好～

麻烦问下楼主准备谷歌之前刷了多少题啊? 花多久准备谷歌的啊? 最近要面了, 很虚

a0106660 发表于 2018-10-3 10:27
麻烦问下楼主准备谷歌之前刷了多少题啊? 花多久准备谷歌的啊? 最近要面了, 很虚

Leetcode 心得旁边的数量就是说我自己刷的数量。
第一遍 250， 第二遍 280。

很有用的信息！

油猴这个太有用了, 赞楼主

感谢楼主！