狗家店面4.10

刚刚面完狗家店面，发个面经攒人品。
第一题。给一个String[], 将重复的行给删除，不需要顺序一样。
e.g
1 23 34 1 5                 1 1 5 23 34
1 5 34 23 1   输出       1 2 3
1 2 3                         4 5 6 7
4 5 6 7
输出的

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

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

的index

用两个hashmap。一个存index --> value。一个存value --> index(用list表示,并保持ascending order)

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

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

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

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

Ramily 发表于 2018-4-11 03:43
谢谢楼主分享！第二题有说对什么数据结构的操作吗？ 看到logn我就想到binary search 不知道能不能用

我用的是binary search在list中查找然后插入或者删除的。不然就要O(n)的时间复杂度了

感觉第一题考的是hash算法？ https://stackoverflow.com/questions/18021643/hashing-a-set-of-integers-in-an-order-independent-way， 按照题主的方法的话， 空间复杂度会比较高吧。

谢谢楼主分享， 祝楼主好运！

谢谢楼主分享！第二题有说对什么数据结构的操作吗？ 看到logn我就想到binary search 不知道能不能用

陈sisyphus 发表于 2018-4-11 03:19
感觉第一题考的是hash算法？ https://stackoverflow.com/questions/18021643/hashing-a-set-of-integers-in ...

应该是的。空间复杂度的话。如果数字有范围限制的话，就还好了

楼主是residency的项目吗？我看你帖子都好几轮电面了。。

我觉得就算是hash算法，怎么着也得把每个字符串都扫一遍吧，m*n还能再低下去？压缩空间倒是有可能

第二题不能用 Map<Long, PriorityQueue<Long>>吗 key是number，priorityqueue存的是index

qqzhao18 发表于 2018-4-11 06:07
第二题不能用 Map吗 key是number，priorityqueue存的是index

那如果某个number的index被其他number覆盖了，就比较难操作了吧