黑车公司面经

写个 黑车 公司面经吧， 上周面的，这周还没有给消息， 估计已经挂了，当然除非 开挂 了..
看完recruiter发过来onsite 要面的人， 一共5轮,  四个南亚 人口仅次于或者实际上已经超过了我国的国家的人 和 一个土耳其大哥..心里边顿时凉了半截。
所以也就非常轻松的去了。

1. design 一个hashHeap..  具体的scenario 忘了， 好像是一堆task, 每个 task 有一个priority，
    当需要update 一个task 的priority 的时候， 用 hashHeap 来access 某一个element, 然后重新siftUp or siftDown, 来维持整个堆的特性

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

内容 (2017-7-26 05:24):
应该是有些难度， 当然小弟才疏学浅。 不过anyway 了， 面试这个东西， 大部分情况是看个眼缘..放平心态就好..

补充内容 (2017-7-26 05:25):
第二题小弟面试的时候和面试官确认过了， 没有啥其他假设， 就是单纯的 insert, delete, update, max...顺序random..

这题有坑。如果这种数据结构存在的话，那就可以设计出O(n)的排序算法。

首先insert所有元素，这个按照假设，可以O(n)搞定。然后不停的call max(), 假设max返回的是(key, value)对的话，call完max，delete掉max对应的element，delete操作也是O(1)的。重复这个过程，直到为空，就能(奇迹般的)在O(n)的时间复杂度下把一个数组给排序好了。通过比较进行的排序算法是有下界的，不会比O(n*logn)更快，所以这个题要么是有其他假设楼主忘了，要么就是一个坑。

全O(1)那道问题我怀疑有些潜在的假设他并没告诉你。如果value是integer且落在某个不是特别大的范围内可以开数组count每个值出现的次数，insert, update, delete的时候去操作counter数组，用一个max变量指向counter数组里不为零的最大index。如果value是任意值的话基本上应该是没法做到始终O(1)的，或者他能保证max只会被call一次

第二题， 所有的操作都是用O(1).  有高手share一下思路吗？ 关键是max()怎么保证O(1) 我的想法是使用PriorityQueue维护一个从大到小的queue，但是只要用Heap就立马不是O(1)了. 还有就是自己维护一个LinkedList, 保持有序，但是插入的时候也不能保证O(1)。请高手指点。

楼主第四题是lc的unique path2么

第四题打印的话就是bfs？

问下楼主第二题是怎么答得，谢谢

第四题 直接动态规划， 第2题 4种操作O（1） 是不是有点过分了

这个黑车公司面经真的不简单啊

coding部分好像都是leetcode原题或者变种

第二题挺好玩的，insert和delete是基本操作，用hash实现，update可以先delete再insert，max其实就是维护一个链表，insert的时候如果比表头大就插入，delete的时候和表头相等就delete。其实就是一个hash表，加一个log

补充内容 (2017-7-25 12:04):
不对, 得记录次大元素才行