Google Interview Question
Software Engineer / Developerslooks good
but dont u mean
count[i][j] = sum { count[a][j-1] such that value[a] < value[i], for 0<=a<=i-1}?
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.
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.
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;
}
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();
}
}
}
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.
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
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]
}
}
}
#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);
}
only if sorting allowed problems becomes to finding the subset of length K in given sert of length L where K<=L
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;
}
The question says - find the number of ways in which you can select the sequences of length k. I think the answer is [nCk] .
//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;
}
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
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.
For input, 1 4 6 2 5 9 and k = 3
- buried.shopno February 11, 2011output: 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