Google Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
5
of 5 vote

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.

I put my code here : ideone.com/9Ammx
Run it for possible inputs, and report if you find any bug. Thanks.

- buried.shopno April 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This 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;
}

- aka July 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

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.

- Anonymous April 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nevermind this will only return the max length of the sequence and not the sequence.

- Anonymous April 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- LOL April 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 April 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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?

- Kishore April 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ignore earlier comment. Misread question.

- Kishore April 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Kishore April 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anonymous April 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Okay, I mistook the question as finding longest sequential numbers with AP.

- Kishore April 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- m@}{ April 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}

- apple change April 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

looks like I mis-understanding to constaint that the sequences of numbers are continious.

- apple chang April 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem is similar to LIS (Longest Increasing Subsequence). The only change you need to make is that for every state (i,j), you also need to store the starting number of the AP of which (i,j) is the last number.

- Sriram April 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please have a look in this paper compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf

- Domino effect July 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- yemre_ankara November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There is a very good solution which is (n^2) .
it is similar to the solution of finding palindromes in n^2 (not the DP one)
just cponsider each number as an average then start from i-1 and i+1 if the verage ius same include them else do incement decrement pointers according to your need

- Geek January 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int dp[n][n];
memset(dp, 0, sizeof(dp));
for (int j=n-1; j>=0; j--)
{
        int i = j-1,k = j+1;
        while (i>=0 && k< n)
        {
               if (a[j] - a[i] > a[k] - a[i]) k++; 
               if (a[j] - a[i] < a[k] - a[i]) { dp[i][j] = 2; i--; } 
               else { dp[i][j] = dp[j][k] + 1 ; i++; k--; }
              
        }
         return dp[0][n-1];
}

- Anonymous August 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- BIN December 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}

- apple chang April 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anonymous April 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@apple: you probably didn't understand the problem itself. Your solution doesn't give correct answer.

Here's few input for you to test:
1 0 -1 2 3 4 -3 5 6 7 => output: 7
2 3 5 7 8 4 9 5 10 6 => output: 5
1 1 1 2 2 3 3 4 4 5 => output: 5

- buried.shopno April 04, 2011 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More