Google电面面经

年纪大了好长时间没找个工作，深感自己刷题的能力比不上新一代年轻人。
给的题特别简单，特别简单。自己能力不行。没什么别的可说的。

FindIJK

Input: int[] A

Output: boolean, is there i < j <

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

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

03:58):
A[i] < A[j] < A[k]

补充内容 (2016-9-1 03:59):
A[i] < A[j] < A[k]

大概。。。这样？

1.     public boolean increasingTriplet(int[] nums) {
   
2.         if(nums == null || nums.length < 3) return false;
   
3.         int n = nums.length;
   
4.         int num1 = Integer.MAX_VALUE;
   
5.         int num2 = Integer.MAX_VALUE;
   
6.         for(int i = 0; i < n; i++){
   
7.             if(nums[i] <= num1){
   
8.                 num1 = nums[i];
   
9.             } else if(nums[i] <= num2){
   
10.                 num2 = nums[i];
    
11.             } else {
    
12.                 return true;
    
13.             }
    
14.         }
    
15.   
    
16.         return false;
    
17.     }

复制代码

补充内容 (2016-9-1 04:20):
大概意思就是维护一个 size = 3 的单调栈。。LIS 的常数退化版

youto 发表于 2016-9-1 03:26
lc的原题吧

我感觉是原题，但是刷题刷的不够熟练。没找到，找到的同学告诉一下。就算不是原题也很简单，当时脑袋一下短路了。

lc的原题吧

是 A[i] < A[j] < A[k] 吗？

那就是longest increasing subsequence， 判断长度是否大于等于3.

ytsr 发表于 2016-9-1 03:39
是 A < A[j] < A[k] 吗？

那就是longest increasing subsequence， 判断长度是否大于等于3.

不是你说的这个，你们都想多了。最简单的，判断a[i]<a[j] 一个循环，在判断a[j]<a[k]
一个循环，如果存在这样的i<j<k and a[i]<a[j]<a[k]
返回对的。我不知道我是不是说清楚了。

我确实觉得理解题意最重要，不要一开始就自己吭哧吭哧写。这提这么简单，我竟然一下蒙了，想了一堆乱七八糟的。特别懊恼。不过也好，onsite那么难，反正也过不去。翻篇了~

怎么回事儿？A'['i']' 为什么自动被吞了。补充都不充不上~bug :)

飞翔的小狐狸 发表于 2016-9-1 03:56
不是你说的这个，你们都想多了。最简单的，判断a

你这个复杂度是 O（n^2）, longest increasing subsequence的解法在你这个最长为3的情况下复杂度是 O(n)

这个题在facebook面试中出现过，楼主你给的是暴力解法吧，时间复杂度O(N^2)的，
可以优化到时间复杂度O(N), 空间复杂度O(1),
估计那才是面试官想要的

感觉 这道题的 思路 可以类似 354. Russian Doll Envelopes(这道题 复杂点不过 算法差不多) 做

如果 next 比之前保留的 序列最后一个 大 就加进去 长度＋1
如果 next 比之前保留的 序列最后一个 小 就找到 序列里的 lower bound 然后 替换

补充内容 (2016-9-1 04:16):
lc 那道复杂 点