## Google Interview Question for Software Engineer / Developers

• 0
of 0 votes

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

Backtracking would not be doable for moderate size of n even (like 100).

DP can solve it in O(n^2 k) time. The idea is: for each i-th element (0<=i<=n-1) and j-th index (0<=j<=k-1), count[i][j] stores the number of ways a subsequence of length j+1 can be constructed considering elements [0,i-1]. Initialize count[i] = 1 for all i.

``````The recurrence is like:
count[i][j] = sum { count[a][b] such that value[a] < value[i], for 0<=a<=i-1,
0<=b<=j-1}``````

For input, 1 4 6 2 5 9 and k = 3
output: 10
1 4 6
1 4 5
1 2 5
2 5 9
4 5 9
1 5 9
1 2 9
4 6 9
1 6 9
1 4 9

Comment hidden because of low score. Click to expand.
0
of 0 votes

looks good
but dont u mean
count[i][j] = sum { count[a][j-1] such that value[a] < value[i], for 0<=a<=i-1}?

Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, you are right. It was a typo in my original post. Thanks.

Comment hidden because of low score. Click to expand.
0
of 0 votes

The idea is cool, but I think at least the initialization is not correct. b/c the number of ways a subsequence of length j+1 can be constructed considering elements [0,i-1] for [i,0] is not 1, it's i. Pls correct me if not correct.

Comment hidden because of low score. Click to expand.
0
of 0 votes

This is wrong. You should consider the length of the entire increasing subsequence, not just stop when you reach k=3. For example, it's 1469 (not 146, 469), 1459 (not 145, 459), 1259 (not 125, 259), etc. In fact the output should be 0 in your example because there is no increasing subsequence that is k=3. V's answer above is also wrong.

Comment hidden because of low score. Click to expand.
0
of 0 votes

DP solves it in O(n * n * K).

``````int solve(int a[], int size, int K)
{
int f;

memset(f, 0, sizeof(f));

for(int i = 0; i < size; i++)
f[i] = 1;

for(int i = 1; i < size; i++)
for(int j = 0; j < i; j++)
if (a[i] > a[j])
for(int k = 1; k <= K - 1; k++)
f[i][k+1] += f[j][k];

int sum = 0;
for(int i = 0; i < size; i++)
sum += f[i][K];

return sum;
}

int main()
{
int a[] = {1, 4, 6, 2, 5};
int K = 3;

cout << solve(a, sizeof(a) / sizeof(int), K) << endl;
}``````

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

backtracking would do..
p.s: i think 1,2,6 is not a valid subsequence for the above example

``````start with subsequence(A,n,k,v,0);

void subsequence(int A[],int n, int k, vector<int> v, int idx)
{
if(v.size() == k)
{
for(int i=0;i<v.size();i++) cout << " " << v[i];
cout << endl;

return;
}

for(int i=idx;i<n;i++)
{
if(v.size() == 0 || A[i] > v[v.size()-1])
{
v.push_back(A[i]);
subsequence(A,n,k,v,i+1);
v.pop_back();
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

good one!

Comment hidden because of low score. Click to expand.
0
of 0 votes

need to add one more variable, which stores the index of last element in the vector. So if A[i] > v[v.size()-1] && i > indexOfLast, we push back.

Comment hidden because of low score. Click to expand.
0
of 0 votes

just do a LIS on the problem ,
increase the Global count if a lis exceed length k
This is O(n^2) time and O(1) space

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

Solution in Python using DP O(n^2 k) solution.

``````#!/usr/bin/env python

A = [1,4,6,2,5,9]
n = len(A)
k = 3
T = [[0 for j in range(n)] for i in range(k)]

for x in range(n):
T[x] = 1

for i in range(1,k):
for j in range(n):
curr = A[j]
count = 0
for x in range(j):
if A[x] < A[j]:
count += T[i-1][x]
T[i][j] = count

count = sum(T[k-1])
print 'Total no. of ways:',count``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

subsequences if the array is sorted??
if so, why not 2 4 5, 2 4 6....etc..??
if no, then why is 1 2 6 an answer?

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

a Java alternative which take less parameter (because it is Java :).) Simply call subsequence3("146259"); in your main function. It will output as @buried.shopno stated earlier.

``````/**
* Print all increased subsequence size 3 given
* an unsorted array of integer.
* @param nums
*/
public static void subsequence3(String nums){
StringBuffer bf_ = new StringBuffer();
for(int i=0;i<nums.length()-1;i++){
bf_.append(nums.charAt(i));
subsequence3(nums,bf_,i+1);
bf_.setLength(0);
}
}

private static void subsequence3(String nums, StringBuffer bf_, int bgn){
//base case 1
if (bf_.length() == 3){
System.out.print(bf_.toString()+ " ");
return;
}
//base case 2
if (bgn >= nums.length())
return;
//recursive case
char c = bf_.charAt(bf_.length()-1);
for(int i=bgn;i<nums.length();i++)
{
//Check if nums[i] is greater thaan last digit
if(nums.charAt(i) > c){
bf_.append(nums.charAt(i));    // add nums[i]
subsequence3(nums,bf_,i+1);
bf_.setLength(bf_.length()-1); // remove nums[i]
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess it said "integer" value as input. Do your program work with integer numbers?
Also, it looks a backtracking solution. Could it solve big input case, say n = 1000? I'm convinced with buried's solution. Is there a faster approach to solve it?
Thanks.

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

#include <stdio.h>

/* Prints all the subarrays of length r */

/* @params: a, given array */
/* @params: n, a length */
/* @params: sub, sub array */
/* @params: r, sub length */
/* @params: i, current index of a */
/* @params: j, current index of sub */

void subarray(int a[], int n, int sub[], int r, int i, int j)
{
if(j == r) /* current index of sub r, print sub */
{
int k;

printf("( ");

for(k = 0; k < r; k++)
printf("%d ", sub[k]);

printf(")\n");
}
else
{
if(i < n)
{
sub[j] = a[i];

subarray(a, n, sub, r, i + 1, j + 1); /* Include current element */
subarray(a, n, sub, r, i + 1, j); /* Override the current element */
}
}

}

int main()
{
int n=10, r=3;

int a={1,2,3,4,5,6,7,8,9,10}, sub;

int i;

subarray(a, n , sub, r, 0, 0);
}

Comment hidden because of low score. Click to expand.
0
of 0 votes

only if sorting allowed problems becomes to finding the subset of length K in given sert of length L where K<=L

Comment hidden because of low score. Click to expand.
0
of 0 votes

corrected code I took the liberty to modify it

``````/* Prints all the subarrays of length r */

/* @params: a, given array */
/* @params: n, a length */
/* @params: sub, sub array */
/* @params: r, sub length */
/* @params: i, current index of a */
/* @params: j, current index of sub */

void subarray(int a[], int n, int sub[], int r, int i, int j, int val)
{
if(j == r) /* current index of sub r, print sub */
{
int k;

printf("( ");

for(k = 0; k < r; k++)
printf("%d ", sub[k]);

printf(")\n");
}
else
{
if((i < n) && (val < a[i]))
{
sub[j] = a[i];

subarray(a, n, sub, r, i + 1, j + 1, a[i]); /* Include current element */
}

if( i < n)
subarray(a, n, sub, r, i + 1, j, val); /* Override the current element */

}

}

int main()
{
int n=6, r=3;

int a[]={1,4,6,2,5,7}, sub;

int i;

subarray(a, n , sub, r, 0, 0, 0);

return 0;
}``````

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

The problem can be solved in O(nlogn*K) check the problem INCSEQ on spoj using AVL trees or segment trees or Fenwick trees

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

The question says - find the number of ways in which you can select the sequences of length k. I think the answer is [nCk] .

Comment hidden because of low score. Click to expand.
0
of 0 votes

first understand the question, pls!

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

//n- size of the main array
//k - size of subsequence

int i,j,k=3,a={1,4,9,7,10,6},c={0,0,0};
int m=0;
int n=6,p;
for (i=0;i<(n-k);i++)
{
c[m]=a[i];
for (j=i+1;j<n;j++)
{
if (a[j] > c[m] && m!=(k-1))
{
c[++m]=a[j];
if ( m == (k-1))
{
for (p=0;p<k;p++)
printf("%d ",c[p]);
printf("\n");
m--;
}
}
}
m=0;
}

Comment hidden because of low score. Click to expand.
0
of 0 votes

this code is wrong..ignore it...

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

1. Sort it, and print it in groups of k elements
2. Make a HashMap where, heightes number of the set is key and linked-list of set is the value... Keep inserting, in appropriate posiotns

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

This solution uses a Hashtable, where hash[n] stores the number of consecutive from elements {x,...,n}. For simplicity we'll assume no duplicates.

1) Create cache variables maxCounts and startIndexOfMax

2) For a number n:

``````hash[n] = hash[n-1] > 0 ? hash[n-1]+1 : 0;
int i = 1;
while(hash[n+i] != null)
{
hash[n+i] = hash[n+i-1] + 1;
i++;
}``````

3) Of course update maxCounts and startOfMax if necessary.

Worst case performance is if values are in reverse order (5,4,3,2,1). In which case shuffle or start reading from the tails.

R

Comment hidden because of low score. Click to expand.
0
of 0 votes

Apologize, added this to the wrong question.

R

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