狗狗面经

1. 输入为一个只包含integer的array, 找到最长的subarray满足a(n) + 1 = a(n+1).
e.g.,

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

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

  [1,2,3,5,7],
Output: 4


分析speedup

谢谢楼主分享！ 请问输入变成一个树的意思是？ 给一个root，然后出array吗？ 有没有规定是什么树？

1. 扫一遍数组，O(n)，follow up 的树没理解，不知道是指找出最长分支，还是可以经过根节点的路径
2. 我觉得最快二分，O(lgn)

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

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

yl89757jj 发表于 2018-1-24 10:48
谢谢楼主分享！ 请问输入变成一个树的意思是？ 给一个root，然后出array吗？ 有没有规定是什么树？

没有规定。 可以有不止两个children

JuneYan 发表于 2018-1-24 23:00
没有规定。 可以有不止两个children

所以可以先分层遍历吗

如果是树，a(n) + 1 = a(n + 1)这里的n指的就是层数了？

1.     int smallestMissingValue(int[] nums){
   
2.         int left = 0, right = nums.length, mid = 0;
   
3.         while(left + 1 < right){
   
4.             mid = left + (right - left) / 2;
   
5.             if(getDiff(nums, mid) == 0) left = mid;
   
6.             else if(getDiff(nums, mid) > 0){
   
7.                 right = mid - 1;
   
8.             }
   
9.         }
   
10.         return nums[left] + 1;
    
11.     }
    
12. 
    
13.     // get the difference between the value difference and index difference
    
14.     private int getDiff(int[] nums, int index){
    
15.         return (nums[index] - nums[0]) - (index - 0);
    
16.     }

复制代码

Binary Search reference code

第一题follow up是LC伍肆玖?

如果是k路树的话,是Lintcode陆壹玖