山景城古狗面试，面经总结

都是medium题，但前两轮都被干蒙了，低估面试难度了，刷题还是没下够功夫

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

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

附件里有过去几个月出现超过两次的面经题总结


补充内容 (2018-6-29 01:23):
第一轮解法很简单，记录c是之前最小值，(a<b)是之前a和b都最小的二元递增数，每遍历一个新数就看它是不是大于b，不是就更新abc

[1] Longest Increasing Subsequence, nlgk， k是最长LIS。 如果说不用的话， 那就是用stack找右边第一个比自己大的，类似739， 或者trapping rain water里面你找右边最大的高度那种
[2] 没看太明白
[3] 编码解码， 0-9 只有9个数字， 然后还要【#0-9】再代表10个， 然后【*0-9】再代表10个。。大概这样吧。 比如 【0-9】=【A-J】，然后#0 = K， #1 = L， 类推
[4] 从前到后的高度受前面的最低高度影响， 举例【5,4,3,2,1,2,3,4,5】即使你现在有2个5，2个4， 2个3，2个2， 你也只能各塞进去一个。这个高度其实就变成了【5,4,3,2,1,1,1,1,1,1】。箱子排序然后从后朝前吧。。
[5] 也不是特别明白

题也太难了8

第一轮如果只是返回true还是false的话，参考LC 334题，一个for loop扫一遍，记录一个small跟big2个flag，数组里有存在3个数在2个flag里面的3段就是true，不然就是false

第一题翻了翻，是脸家的tag，利口散伞丝。

第五题，拓扑排序，扫一遍可解。

第一题与 最长上升子序列 很相近啊，有O(nlogn)的解法。还有更好的方案嘛？

电话的那个好像leetcode有原题

第一輪的問題是只要return true或是false嗎？ 如果是的話，那應該O(n)就能解了。for掃過去，保持一個當前最小值，以及符合p<q且a[p]<a[q]的a[q]最小值，之後只要遇到當前的值大於a[q]最小值的就return true; 不然跑完都沒就false。

john0312 发表于 2018-6-28 00:10
第一輪的問題是只要return true或是false嗎？ 如果是的話，那應該O(n)就能解了。for掃過去，保持一個當前最 ...

比如 [3,4,1,5],到1这里你怎么整，还是要用dp才行

第一轮 是不是可以用binary tree？

第四轮，首先对于山洞的每个位置i，可以得出能到达i的最大高度maxHeight【i】= min{h【j】}，0<=j<i。其次，既然是只要求最多能塞几个，可以直接把箱子排序之后从矮到高往里塞，每个箱子找最深的i使得maxHeight【i】大于它高度，作为它塞的位置。注意到maxHeight是个单调不增的数组，复杂度就是NlogN的。

太空牛仔 发表于 2018-6-28 04:22
比如 [3,4,1,5],到1这里你怎么整，还是要用dp才行

这里你已经有了[3,4]，由于不需要返回这个数组是什么，只需要知道数组的长度，所以用1替换掉3即可，参考LC 300题