Google Interview Question
Software Engineer / DevelopersThis is also DP approach but extra memory.It takes 2 for loops only.
#include <stdio.h>
int max_len = 1;
int array[] = {1, 3, 4, 5, 6, 7};
#define SIZE(a) sizeof(a)/sizeof(a[0])
int map[100][100];
int main()
{
int i, j;
memset(map, 0, sizeof(int)*100*100);
for(i=1;i<SIZE(array);i++) {
for(j=0;j<i;j++) {
int diff = array[i] - array[j];
if(map[j][diff] == 0) {
map[i][diff] = 2;
} else {
int new_len = map[j][diff] + 1;
printf("%d %d--\n", j, diff);
map[i][diff] = new_len;
max_len = new_len > max_len ? new_len : max_len;
}
}
}
printf("%d\n", max_len);
return 0;
}
Here is my O(n^2) solution in c++.
1. compare every number to every number ahead of it and use the difference as key to increment a value in a hash table. this is n^2
2. max sequence is the biggest value in the hash table
int biggestSequence(int* numArray, int mSize)
{
unordered_map<int, int> numSequences;
for (int i=0; i<mSize; i++)
{
for (int j=i+1; j<mSize; j++)
{
numSequences[numArray[j]-numArray[i]] += 1;
}
}
unordered_map<int,int>::iterator it;
int maxSeq = 0;
int maxConst = 0;
for(it=numSequences.begin(); it!=numSequences.end(); it++)
{
if((*it).second > maxSeq)
{
maxSeq = (*it).second;
maxConst = (*it).first;
}
}
// Plus 1 because initial number not included. 1,2,3 would give 2 instead of 3
return maxSeq+1;
}
maxConst is unused so you can get rid of it.
Your solutions seems absolutely wrong to me. How could
numSequences[numArray[j]-numArray[i]] += 1
keeps track of the constraint that every number in arithmetic progression has same difference. For example, if input is 2 4 13 15, your output seems to be 2 as there are two of such numbers with diff = 2 (4-2, 15-13).
I'd do this:
1. create a directed graph G=(V, E) where V = A and E =(i,j) and store the difference d = A[j] - A[i] in a adjacency matrix, if d > 0 => O(n^2).
2. for every node, do a DSF based on the first difference => O(n^2).
For example, if the array is 1 7 3 8 6 5 12 7, the first difference for third node (3) is 5 (8-3); the next one will be 3 (6-3); and so on. In DFS algorithm, the next node will be visited if there's a edge having the weight equal with the first distance. Of course, a list of indexes will be stored and it will be reseted when a longer list is found.
@S
If we are checking to see if series of numbers are incrementing by constant, why do we need to create a graph. If A,B,C are in the series, why find A,C difference, we are not going to traverse that way right?
currentMax = 0; overallMax; curdif;
for(int i=1; i<count; i++)
{
diff = array[i] - array[i-1];
if(curdif == diff)
//increment currentMax
currentMax++;
else
{
if(currentMax > overalMax)
overallMax = currentMax;
}
}
I might have missed edge cases.
I guess you didn't even run your code for some naive input like
[2,3,5,7,8,11] for which output should be 4 (2->5->8->11). This looks like some recurrence/dynamic programming problem.
Here is brute force, it maybe used to verify the correctness of your dynamic algorithm. Will create dynamic solution for this problem.
void printLongestArithmeticProgression(int* arr, int length){
int value = 0;
int offset = 0;
list<int> maxSequence;
list<int> curSequence;
for( int i =0; i < length-1; i++ ){
for( int k = i+1; k < length; k++ ){
curSequence.clear();
offset = arr[k] - arr[i];
value = arr[k];
curSequence.push_back( arr[i] );
curSequence.push_back( arr[k] );
for( int j = k+1; j < length; j++ ){
if( arr[j] - value == offset ){
value = arr[j];
curSequence.push_back(value);
}
}
if( curSequence.size() > maxSequence.size() ){
maxSequence.clear();
copy(curSequence.begin(), curSequence.end(), back_inserter(maxSequence) );
}
}
}
curSequence.clear();
printList(maxSequence);
}
I think my algorithm is correct, here's the compiled code written in C#, should be easy to change to C++ or java:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace FindLongestAP
{
class APInfo
{
// stores the start index of the original data set for the AP found
internal int startIndex;
// stores the end index of the original data set for the AP found
internal int endIndex;
// stores the difference for the the AP found
internal int diff;
};
class Program
{
static void Main(string[] args)
{
int[] data = new int[] {2, 3, 5, 7, 8, 4, 9, 5, 10, 6};
APInfo apInfo = FindLongestAPInfo(data);
for (int i = apInfo.startIndex; i <= apInfo.endIndex; i++)
{
Console.Write("{0} ", data[i]);
}
}
/// <summary>
/// The main idea is scanning the data set to find the complete AP, then compare the
/// current found AP with the longest one found so far, if the current one is longer,
/// then update the longest one with the current one. After finished scanning the whole
/// data set, then the longest AP is determined. O(N) complexity.
/// </summary>
/// <param name="data"></param>
/// <returns></returns>
static APInfo FindLongestAPInfo(int[] data)
{
if (data == null || data.Length < 2)
{
return null;
}
// Initialize
APInfo currentAPInfo = new APInfo();
currentAPInfo.startIndex = 0;
currentAPInfo.endIndex = 1;
currentAPInfo.diff = data[1] - data[0];
APInfo longestAPInfo = new APInfo();
longestAPInfo.startIndex = 0;
longestAPInfo.endIndex = 1;
longestAPInfo.diff = data[1] - data[0];
for (int i = 2; i < data.Length; i++)
{
int diff = data[i] - data[i - 1];
if (diff == currentAPInfo.diff)
{
currentAPInfo.endIndex = i;
}
else
{
// complete AP detected, check whether longer than current longest
if (currentAPInfo.endIndex - currentAPInfo.startIndex > longestAPInfo.endIndex - longestAPInfo.startIndex)
{
longestAPInfo.startIndex = currentAPInfo.startIndex;
longestAPInfo.endIndex = currentAPInfo.endIndex;
}
// update currentAPInfo to start a new one
currentAPInfo.startIndex = i - 1;
currentAPInfo.endIndex = i;
currentAPInfo.diff = diff;
}
}
return longestAPInfo;
}
}
}
looks like I mis-understanding to constaint that the sequences of numbers are continious.
Recurrence:
C(j, s) = { (Max( C(j - k, s) ) for k: 1 ... j) ->
if ( k > 0)
1 + C(j - k, s)
else
(A[j] - A[0] == s)? 1 : 0
}
where C(j, s) means the number of steps of "s" up to Jth element.
Init C(0, s) = 0 for s: 0... (a[N] - a[0])
for 0 ... N
for 1 ... a[N] - a[0]
find max (C ( j, s)) so far
answer is "j and s" forming the max C(j, s). easy to track down. loop might be modified to follow the sequence of i1 < i2 .. < ik yielding C(j, s) on a seperate list based on "s" values.
O(n^3) time.
DP, o(n^2)
// before passing into this function, A is sorted
// which takes additional n*logn time
int biggestArithmeticSequence(int* A, int n)
{
int max = 0;
vector<unordered_map<int,int>> disMap(n);
for(int i=1; i<n; i++)
{
for(int j=i-1; j>=0; j--)
{
int dis = A[i]-A[j];
int cmax = 1;
if (disMap[j].find(dis) != disMap[j].end())
{
cmax += disMap[j][dis];
}
disMap[j][dis] = cmax;
if (cmax > max)
{
max = cmax;
}
}
}
return max;
}
Here's my solution with O(n):
struct APInfo
{
int startIndex;
int endIndex;
int diff;
};
APInfo* FindLongestAPInfo(int* data, int length)
{
if (data == null || length < 2)
{
return null;
}
// Initialize
APInfo* currentAPInfo = new APInfo();
currentAPInfo->startIndex = 0;
currentAPInfo->endIndex = 1;
currentAPInfo->diff = data[1] - data[0];
APInfo* longestAPInfo = new APInfo();
longestAPInfo->startIndex = 0;
longestAPInfo->endIndex = 1;
longestAPInfo->diff = data[1] - data[0];
for (int i = 2; i < length; i++)
{
int diff = data[i] - data[i-1];
if (diff == currentAPInfo->diff)
{
currentAPInfo->end = i;
}
else
{
// complete AP detected, check whether longer than current longest
if (currentAPInfo->end - currentAPInfo->start > longestAPInfo->end - longestAPInfo->start)
{
longestAPInfo->start = currentAPInfo->start;
longestAPInfo->end = currentAPInfo->end;
}
// update currentAPInfo to start a new one
currentAPInfo->start = i-1;
currentAPInfo->end = i;
currentAPInfo->diff = diff;
}
}
return longestAPInfo;
}
Why do u need to post a code that is NOT compilable? You used "start"/"end", but your structure member has different names. Besides, who ask for your code without a little explanation? Thanks.
Here's my DP solution with O(n^3). Assume, we've optimum solution for array a[0,1,2,....,k]. To get solution for index = k+1, we can put a[k+1] next in a sequence ending with a[j] for 0 <= j <= k. So, if diff = a[k+1] - a[j], we need to look up sub-problem solution for index = j to search for diff, and taking the max value to get a maximum sequence.
- buried.shopno April 03, 2011I put my code here : ideone.com/9Ammx
Run it for possible inputs, and report if you find any bug. Thanks.