1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
,矩形的4个角都是1.
leetcode里面有类似的题,我给了类似的答案,复杂度是O(n^3),感觉面试官不是很满意。不知道有没有复杂度更少的算法。
2.有高矮不一的一群人,随机排列。排完之后每个人记下比自己前面比自己高的人的数目。之后把队打乱,跟据高度和比自己高的人的数目还原原来的队列。
我给了一个O(n^2)的算法,在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的算法。
想法是这样,首先将所有人排个序,从小到大,从最矮的开始往园数组插,
对于位置在原数组位置x的人,他前面有n个人比他高,而比他矮的人都已经放到位了,比他高的人都还没放,所以我们就数空位从前数n个,已经放了人的地方跳过,那就得到x了。
但是这样的做法是n^2(在放数找位置这一步需要O(n)的时间)有人提如果用interval tree存空格的话找到第K个空格只需要O(lgn)时间,那么总的复杂度就是O(nlogn)。
Interval tree 找第k个空格的用法
Every node stores the number of open spaces at its range, we will be able to locate the kth empty space in lgn time (the above image has node that stores the minmum element of the range, we change that to the number of free spaces, and update corresponding spaces when every we do insert).
From:
https://hellosmallworld123.wordpress.com/2014/04/18/google%E4%B8%A4%E9%81%93%E9%A2%98/
相关推荐
这是Google的15道面试题与答案,word文档!大家感兴趣的看看吧!呵呵!希望对各位有帮助!
Google21道面试题 Google公司的面试 google面试题2 GOOGLE面试题--答案
21道经典的Google面试题,全英文题目,涉及到多方面的知识
16道C语言面试题例子 死循环(Infinite loops) 数据声明(Data declarations) 位操作(Bit manipulation) 访问固定的内存位置(Accessing fixed memory locations) 中断(Interrupts) 代码例子(Code examples...
15道Google面试题(含答案)[汇编].pdf
三个更新点,做数学题是重点 为了让用户更方便地了解 Bard 更新变化,Google 上线了 experiment updates(实验更新)界面,展示 Bard 的最新消息。 相比其他厂商“提高系统稳定性,优化系统流畅度”的更新对联,...
IT各类面试题 google百度北电华为腾讯试题及面试 网络工程师面试题 java软件工程师面试试题集合 130道ASP[1] NET面试题 软件工程面试题 数据库面试笔试题集 数据结构面试大全 JAVA面试题
常见算法笔试或面试题 笔试面试专栏:字符串 数组 vc题集 十道海量数据处理面试题与十个方法大总结 google全程面试题 其他一些公司的面试题
Google 招聘的21道题目
资源涵盖了140道题,有一定的技术难度,希望对你面试有帮助
2019HR实用经典面试笔试题库合集(51...9_200个名企的面试题详解(微软+谷歌+联合利华).doc 面试邀约之HR招聘面试流程与技巧(含STAR原则).doc 面试邀约之HR电话面试邀约技巧.doc 面试邀约之电话筛选及通知面试话术.doc
据说是阿尔卡特(中国)的面试题目 世界大公司面试题——微软的面试题 世界大公司面试题——微软的面试题 Google:21道能力倾向测试面试题
分析:这是去年google 的一道面试题。 我看到这道题目时,第一反应就是每次push 一个新元素时,将栈里所有逆序元素排序。这样栈顶元素将 是最小元素。但由于不能保证最后push 进栈的元素最先出栈,这种思路设计的...
google百度北电华为腾讯试题及面试.rar 网络工程师面试题.rar java软件工程师面试试题集合.rar 数据库面试笔试题集+一.doc JAVA面试题.doc 130道ASP[1].NET面试题.doc 软件工程面试题.doc 数据结构面试大全.txt
先来道数学题 首先是逻辑和数学方面。 小哥给两种AI提了一个相同的问题: 小明6岁那年,他的妹妹是他年龄的一半,同时他妈妈的年龄是他妹妹的10倍。今年小明60岁,那么他妈妈今年多少岁? 读者朋友可以活动一下脑筋...
南京大学一个高手整理的 我偷来给大家分享 适合想接触ACM但ACM又难的编程者使用 题目全中文的 只要把题目在GOOGLE上一搜就有答案了
推荐使用Google浏览器,因为它的打印功能非常出色,可以轻松地打印50道题目,每一页都有25道题目。如果你觉得某些电脑的打印数量不一致,也可以尝试使用其他浏览器进行打印。 除了打印答案之外,还有一项功能是显示答案...