Facebook Interview Question Software Engineer / Developers
I did not made the question clear, My bad. It was "finding largest monotonically increasing *contiguous* sequence in an integer array" .. and obviously a "contiguous" sequence can be found in O(n) trivially ...
if the current max increasing sequence length is n then we can skip next n/2 elements and check further n/2+1 elements that if they are increasing ,then we check n/2 elements that we just skipped if they are also incresing then we have now aincresing sequence og lenght n+1;
else if this skipped n/2 is not increasing then from that n+n/2 index we come back to check how much we ca take in and again start at 2n+1
else if that further n/2 elements were not increasing we just left n elements.and moove further.
I have some hunch on that we can divide and conquer like from the middle element look for the spread on both sides and not the length of longest sequence. Then consider the remaining parts not explored and only when the length of the current maximum is less then the length of the remaining part.
I think the above mentioned algorithm work, but cannot prove its complexity.
#include <iostream>
#include <cmath>
using namespace std;
int LMIS_DivideAndConquer(int a[],int begin, int end){
if(begin==end){
return 1;
}
int mid = (begin+end)/2;
int LMIS_begin = mid;
int LMIS_end = mid;
// Search backword
while(LMIS_begin>begin && (a[LMIS_begin-1]<a[LMIS_begin])){
(LMIS_begin--);
}
// Search forword
while(LMIS_end<end && (a[LMIS_end+1]>a[LMIS_end])){
(LMIS_end++);
}
int LMIS_length = LMIS_end-LMIS_begin+1;
if((LMIS_begin-begin)>LMIS_length){
int length_temp = LMIS_length>LMIS_DivideAndConquer(a,begin,LMIS_begin-1);
if(length_temp>LMIS_length){
LMIS_length = length_temp;
}
}
if((end-LMIS_end)>(LMIS_end-LMIS_begin)){
int length_temp = LMIS_length>LMIS_DivideAndConquer(a,LMIS_end+1,end);
if(length_temp>LMIS_length){
LMIS_length = length_temp;
}
}
return LMIS_length;
}
int main(){
int a[] = {1,2,3,4,-1,1,2,3,4,5,6,1,2,3,4,5};
cout << LMIS_DivideAndConquer(a,0,(sizeof(a)/sizeof(int))-1) << " = 7?" << endl;
system("pause");
}
find first best seq; lets say length is bLen;
compare a[2*bLen] with a[2*bLen +1];
If 1st is bigger than 2nd
[Step A] you don't need to look at bLen to 2*bLen -1; again compare a[3*bLen +2] and [3*bLen+3] and so on
Else
check a[bLen] to a[2*bLen] is monotonically increasing.
If it is increasing
set new bLen to the next best length we just found
Else
Goto [step A] with starting index as where the monotonically increasing broke.
This in worst case requires accessing all data in the array.
but on average, it will skip at lot of it.
Don't know how to get faster than O(n). Please put a working function if you do. Here are two possible solutions:
int LongestIncreasingSequence(int *a, int n)
{
if (n == 1)
{
return 1;
}
else
{
int m = LongestIncreasingSequence(a + 1, n - 1);
if (a[0] < a[1])
{
return m + 1;
}
else
{
return m;
}
}
}
int LongestIncreasingSequenceNonRec(int *a, int n)
{
int curr = 1;
int best = 1;
int prev = a[0];
for (int i = 1; i < n; i++)
{
if (prev < a[i])
{
curr++;
}
else
{
if (curr > best)
{
best = curr;
}
curr = 1;
}
prev = a[i];
}
return best;
}
I doubt it can be O(n). My dynamic programing solution takes O(n^2):
int find_increase_subsequence(int *a, int len)
{
int *d = NULL;
int i, j;
int global_max = 0;
d = new int[len];
if (!d) goto exit;
for (i = 0; i < len; i++)
{
int max = 1;
for (j = 0; j < i; j++)
{
if (a[j] < a[i] && d[j] + 1 > max)
{
max = d[j] + 1;
}
}
d[i] = max;
if (max > global_max)
{
global_max = max;
}
}
exit:
if (d)
{
delete [] d;
d = NULL;
}
return global_max;
}
it is O(n) solution
def conseq(arr):
cur_start,cur_end,cur_size=0,0,1
max_start,max_end,max_size=0,0,0
n=len(arr)
if n==0: return (0,0,0)
for i in range(1,n):
if arr[i]>arr[i-1]:
cur_size+=1
cur_end=i
else:
cur_start=i
cur_end=i
cur_size=1
if cur_size> max_size:
max_size=cur_size
max_start=cur_start
max_end=cur_end
return (max_size,max_start,max_end)
if __name__=='__main__':
arr=[-4, -2, 1, 2, 3, 4, 6, 7, 8, 2, 3, 4, 5, 6, 7]
print conseq(arr)
A simple implementation
seq = [-4, -2, 1, 2, 3, 4, 6, 7, 8, 2, 3, 4, 5, 6, 7]
start = [0 for i in range(len(seq))]
for i in range(1, len(seq)):
if seq[i] > seq[i - 1]:
start[i] = start[i - 1]
else:
start[i] = i
max_len = -2 ** 31
for i in range(len(seq)):
if i - start[i] + 1 >= max_len:
max_len = i - start[i] + 1
print max_len
int findLongestMonotonicallyIncreasingSequence(int[] in) {
int a = 0, b = in.length - 1, max = 0;
while (a < b) {
int expected = b - a;
int actual = in[b] - in[a];
if (actual == expected) {
if ((b - a) > max) {
max = b - a + 1;
}
a = b + 1;
b = in.length - 1;
} else {
b--;
}
}
return max;
}
int findLongestMonotonicallyIncreasingSequence(int[] in) {
int a = 0, b = in.length - 1, max = 0;
while (a < b) {
int expected = b - a;
int actual = in[b] - in[a];
if (actual == expected) {
if ((b - a) > max) {
max = b - a + 1;
}
a = b + 1;
b = in.length - 1;
} else {
b--;
}
}
return max;
}
As far as i can think i will map it to LCS problem. In order to do so reverse the given sequence and find the longest common subsequence between the duo. Now, since the LCS problem can be solved using DP in O(n*m), one can say this would take O(n*m). But question says "not the usual O(n) in worst case," i dont know whether a O(n) is possible also? If it is can somebody suggest the algo?
- hary February 24, 2010