Menu Sidebar
Menu

Interview Question

Special Array With X Elements Greater Than or Equal X

求一个数字x, 数组中的数字大于等于x的数字个数正好是x. 如果有x, 返回x, 否则返回 -1. 这个题首先看肯定是O(n^2)能解决的, 就是暴力破解. 然后这题一看x是对大小有考量, 肯定用binary search能优化, 用二叉肯定要先找边界, 所以看题知道边界是[0, n]. 然后再看用哪种二叉搜索, 这题因为答案唯一(题中给了, 不给的话自己prove很难, 我估计着狗家这题肯定是没告诉你答案必然唯一的, 如果想不到答案必然唯一, 这题很难在短时间写出来.), 剩下的就直接就写出来了..

Correct a Binary Tree

给一个二叉树, 其中有一个node是invalid, 这种invalid是他的右子树连到了右边的任意node. 求删除这个错误的子树后的树. 这个题主要是读懂题, 理解这种invalid只能发生在某个node的右子树上. 然后查重要用set. 就没了

Maximum Size Subarray Sum Equals k

给一个arr, 求最大的size的subarray的和是k的. 这个题的简单版本是 Subarray Sum Equals K , 升级版本是 Minimum Operations to Reduce X to Zero 这个题的精髓是找到pre sum. 所以最初的版本code如下: 由pre[j] – pre[i] == k可以看出, 我们找的是2个数字的差等于k, 那么可以看成是2sum问题, 在2sum问题中, 用HashMap优化速度. 需要注意的是, 有可能同一个sum出现在很多个位置, 因为我们找的是max, 所以要找最开始的(最远)的i.

Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.