Tag: 哈希表

去年我参加了 Google 的初面(电话面试), 可惜没有通过. Google 瑞士的一个软件工程师打电话面试, 电话面试就考了一道算法题, 虽然我也准备了近一个月的时间, 但是我回答的并不完美. 虽然和我联系的Google 是在伦敦, 但是面试的时候手机上显示的是 +41 电话 来自 Google 瑞士, 整个面试大约45分钟. 题目是: 给了一些消息 和对应的日期和时间, 如果消息并不在最近10秒钟内打印过 那么就打印. 同时有可能多条消息到达(1秒之内). 就这么一个题目并没有指定接口, 而我们也不需要把所有消息都保存起来, 并且我们知道 这个 打印函数可能一秒内被调用多次: …

最近在刷题,倒不是为了找工作,主要是为了练练脑子,日子过得太舒服,人脑不动容易变笨. 程序员应该都了解并能熟悉使用 Hash 哈希表,哈希表的插入和查找时间复杂度是O(1), 空间复杂度是O(N).我们来看一道简单的面试题: 给定一个数组,找出相差为2的数对,比如: {1, 3, 5, 6, 9} 输出为: (1, 3), (3, 5) 拿到这题的时候 第一感觉是 暴力是否可行? 暴力搜索 复杂度为 O(N2), 大概代码如下: for i = 0 to len …

背景 经理叫我优化一段代码. 因为发现当数据量太大时 运行时间则会变得很久. 这个代码在软件里已经存在 4年之久了. 最开始我们都不知道是谁写的这代码 但之后发现 竟然是经理自己 4年前写的代码. 他自己都不记得了(代码里没有注释). 算法的目的是将一个密集点集重新按照一定的分辨率筛选. 使得任意两点之间的距离要大于这个采样分辨率 并且点的个数要尽量的多. 原始的实现算法 经理原始的算法 是通过迭代每次选出一个点(为了方便 就选第一个点) 然后把候选集中和此点距离大于分辨率的点记录下来做为下一轮的候选集. 实现则用了LINQ的where 看起来只有O(n) 循环但是 其实是 O(n^2) 因为每次LINQ从当前候选集选出新的点这个操作就是 O(n). public List<Point3F> Resampling(double …