1) 一个range的序列(链表或数组),如[1,3], [2,6], [8,10],[15,18] 写程序合并有重叠的range,比如上面的序列合并为[1,6], [8,10], [15,18] 如果这个序列不是静态的,而是一个数据流,如何 处理? 后来听说了interval tree,不过还是不太清楚具体如何解决,有大牛能详细说说么? 2) 利用快速排序的划分方法,把数组分成三部分,< val, = val, val。 后来发现 programming peals 上有原题.. 3) 对于google查询的词组成的动态的数据流,在任意时刻取出10个完全随机的查询。 当时死活没答上来,后来在板上发现是经典的 reservior sampling,早点到板上看面经就好了.. 4) 把一个字符串转换成32bit的整数 = 要注意处理溢出的情况 5) 在一个数组中寻找三个数,使得它们的和为0 这个是找两个和为0的数的扩展 6) 大概是用一位数组来表示二维数组,但是每一行的元素个数可以不同,实现get,set函数 这个算是比较简单的 7) 已知每个待查找的字符串长度为10,如何在一个很长的字符串的序列里快速查找这样的字符串 当时的思路是,遍历字符串把所有长度为10的的字符串算出累加值, 类似于 sum = a0 * 10 + a1 * 10^2 + ... + a9 *10^9,然后用这个sum 做hash,面试官ms觉得还马马虎虎。应该有更好的办法。 8) 写程序生成边长为n的如下的方阵 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 = 顺时针生成即可,注意边界条件 9) 应用程序的re-order的buffer的设计,如果满了可以丢弃 大概是应用程序需要in order的数据包,但是收到的数据可能是乱序的(类似于IP分片,每一个数据片有一个序列号,但是不同的数据片 到达应用程序的顺序可能和发送的顺序不一样,引起乱序)。然后有 一个buffer,可以存放几个数据片,问如何设计算法通过这个buffer 把数据片变成有序。说了仿照IP分片重组,设置timer再加上ack来做, 面试官好像不太满意。 10) 假设有很多多边形,最大的是地球,每一个国家可以认为是一个多边形,每一个省 ,市,区,小区,楼都可以认为是一个多边形,这些多边形之间要么是相互包含的,要么是互相没有交集的,(不存在overlap的情况)。给出一个多边形,要求写程序求出最小的包含它的多边形。已知有现成的函数可以判断两个多边形是否相互包含, iscontained(poly p1, poly p2)。 如何加速?如果在多机的情况下呢? 可以用树结构表示包含的关系。可以用二分搜索做加速。多机的话可以range一个机器处理一个区域,另外要考虑前端处理机的负载不要成为瓶颈,所以让每个机器自己判断此多边形是否包含。 |
行业聚焦 面试交流 职位推荐 开发视频 技术交流 腾讯微博 新浪微博
友情链接:课课家教育 阿里云 鲜果 W3Cfuns前端网 中国企业家 环球企业家 投资界 传媒梦工场 MSN中文网 Android开发者社区 cnbeta 投资中国网 又拍云存储 美通说传播 IT茶馆 网商在线 商业评论网 TechOrange IT时代周刊 3W创新传媒 开源中国社区 二维工坊 Iconfans 推酷 智能电视网 FreeBuf黑客与极客 财经网 DoNews 凤凰财经 新财富 eoe移动开发者社区 i黑马 网易科技 新浪科技 搜狐IT 创业家 创业邦 腾讯财经 福布斯中文网 天下网商 TechWeb 雷锋网 新浪创业 和讯科技 品途O2O 极客公园 艾瑞网 抽屉新热榜 卖家网 人民网通信频道 拉勾网 创新派 简单云主机
手机版|黑名单|守望者 成才网 在线教育 linux 高级程序设计 C/C++ 大数据
( 蜀ICP备14029946号 )
成都守望者科技有限公司 © 2013-2016 All Rights Reserved