## Google Interview Question for Software Engineer / Developers

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][0] = 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

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

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

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

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

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

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

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

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

for(int i = 0; i < size; i++)
f[i][1] = 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

good one!

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

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

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[0][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

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[10]={1,2,3,4,5,6,7,8,9,10}, sub[3];

int i;

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

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

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

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[3];

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

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[6]={1,4,9,7,10,6},c[3]={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

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

Apologize, added this to the wrong question.

R

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.

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