## Infosys Interview Question for Program Managers

Country: India
Interview Type: Written Test

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

1. find the longest increasing subsequence(with little change) -> maxlen
2. finally substract the str.len - maxlen

Time Complexity -O(nlogn) and Space Complexity - O(n^2)

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

Its nothing but the longest increasing sub-sequence problem.

``````static int lis( int arr[], int n )
{
int result = 0;
int[] lis = new int[n];

for (int i = 0; i < n; i++ )
lis[i] = 1;

for (int i = 1; i < n; i++ )
for (int j = 0; j < i; j++ )
if ( arr[i] > arr[j] &&
lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;

for (int i = 0; i < n; i++ )
if (result < lis[i])
result = lis[i];

return n-result;
}``````

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

It is longest increasing subsequence problem.

This is a O(n^2) solution.

``````static int lis( int arr[], int n )
{
int result = 0;
int[] lis = new int[n];

for (int i = 0; i < n; i++ )
lis[i] = 1;

for (int i = 1; i < n; i++ )
for (int j = 0; j < i; j++ )
if ( arr[i] > arr[j] &&
lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;

for (int i = 0; i < n; i++ )
if (result < lis[i])
result = lis[i];

return result;
}``````

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

It is longest increasing subsequence problem.

This is a O(n^2) solution.

``````static int lis( int arr[], int n )
{
int result = 0;
int[] lis = new int[n];

for (int i = 0; i < n; i++ )
lis[i] = 1;

for (int i = 1; i < n; i++ )
for (int j = 0; j < i; j++ )
if ( arr[i] > arr[j] &&
lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;

for (int i = 0; i < n; i++ )
if (result < lis[i])
result = lis[i];

return result;
}``````

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.