找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

[ 名企面试题收录 ] 【守望者 名企笔试题目】google经典笔试题目

2014-09-24 12:17| 发布者: zhouy | 查看: 1112 | 收藏

摘要: 1) 一个range的序列(链表或数组),如, , , 写程序合并有重叠的range,比如上面的序列合并为, , 如果这个序列不是静态的,而是一个数据流,如何 处理?   后来听说了interval tree,不过还是不太清楚具体如何解 ...
      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一个机器处理一个区域,另外要考虑前端处理机的负载不要成为瓶颈,所以让每个机器自己判断此多边形是否包含。

你有新的观点?  

已有0参与讨论

赞过此文的人

推荐阅读

[守望者 内推职位]中电科网络信息安全有限责任公司
[守望者 内推职位]中电科网络信息安全
中国电子科技集团公司第三十研究所(以下简称:三十所)创建于1965年,是集通
[守望者 猎头职位] 某民机航电公司  研发技术副总监 VxWorks软件高级工程师 Linux软件 ...
[守望者 猎头职位] 某民机航电公司 研
以下职位为猎头职位。有兴趣可将简历发送到362528717@qq.com或者加QQ交流,匹
[猎头职位] 高级嵌入式系统架构师
[猎头职位] 高级嵌入式系统架构师
高级嵌入式系统架构师
[猎头职位] 英国金融公司 liquid(利源软件)Linux C++高级开发
[猎头职位] 英国金融公司 liquid(利源
Liquid Capital Group 是一家总部位于伦敦的专门从事金融衍生品交易和做市业
[猎头职位] 系统测试__安全产品测试
[猎头职位] 系统测试__安全产品测试
系统测试__安全产品测试
【守望者 内推职位】腾讯平台架构后台开发工程师
【守望者 内推职位】腾讯平台架构后台
守望者:腾讯后端开发,职位在深圳,年薪30~35W,成都主要为游戏开发相关职位
[猎头职位] 加拿大 宏利金融  .Net 高级开发
[猎头职位] 加拿大 宏利金融 .Net 高
守望者:本职位为金融开发相关陪伴,要求有较强的架构设计能力,开发能力,分
[内部推荐]重庆金鑫智慧java高级程序员
[内部推荐]重庆金鑫智慧java高级程序员
守望者:重庆金鑫智慧是重庆南桐矿业集团公司旗下的子公司,有专业的队伍进行

行业聚焦  面试交流  职位推荐  开发视频   技术交流  腾讯微博  新浪微博

友情链接:课课家教育  阿里云  鲜果  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