IBM Interview Question Software Engineer / Developers
Here is my approach
1) Create a min heap tree of first k elements and keeping track of the max element in the tree
2) Now scanning the other elements from left to right, if any elements is greater than the max number in the tree, remove the min elements from the tree and insert that one and reheapify.
Time Complexity = nlog(k)
What is the solution using your method for:
1, 2, 10, 12, 8,9,11
(2, 10, 12) or (8, 9, 11)?
@ibnipun10 I did not understand your method first we need k increasing sequence with max sum.
You said max heap
1,5,2,8,7,6,11
k=3
initial heap contain 1,5,2 which is not increasing sequence.
now 8 is there remove 5 and got 1,2,8
now remove 8 and insert
1,2,11
but answer 5,8,11
Well below is my standard DP method
Find longest increasing sequence with max sum
here recurrence equation
sum[i] = input[i] + sum[j]
where 0=<j<i-1 and input[i]>input[j]
sum[i]= input[0] if i=0
Now check last k item of each sum[i]
Hi Mayank,
I said min heap, having pointer the max element in the heap
for 1,5,2,8,7,6,11
Initially : 1,5,2 max = 5
next 8 => (remove 1) 2,5,8 max = 8
next 7 => which is less than 8 therefore do nothing
next 6 => which is less than 8 therefore do nothing
next 11 => (remove 2) 5,8,11 max =11
Seq = 5,8,11
k, Adding to the previous approach
After traversing the array we can save the pointer to the last inserted element let say j
Now again create a heap starting with j+1 element
This can be done till the end of the array
The max sum heap will be the one
for 1,2,10,12,8,9,11
one heap is 2,10,12
other will be 8,9,11
therefore 8,9,11
@ibnipun10
Are you sure your idea will take care of the constrain that "k number needs to be in increasing order"
1,5,2,8
next 8 => (remove 1) 2,5,8 max = 8
here your invariant is not true
Use 2 min-heaps. Scan the array's elements. Keep track of the max element for each heap and the current number of elements. Current heap should be the heap with the maximum. If the next element is greater than the max, then if the number of elements in the current heap is < k, add it to the heap, otherwise replace it with the minimum. If the next element is less than the max of current heap add it to the second heap. If the next element is less than the both maximums, overwrite the heap with the minimum sum. Change the current heap, when another becomes greater.
I checked Fiddler's logic with various inputs
I think he is right
And the time complexity : O(n)
Oh, I think we need to use two queues instead of heaps, and in this case the time complexity should be O(n). :)
What will be your output for this input -. 2,5,8,6,8,9 ?
I think it will wrongly output 5,8,9 .
Please correct me if i did not understand the algorithm ..
@fiddler.g
I am also not able to understand your approach . If possible could you explain us with an example.
One more input which will give wrong result is -> 4,5,9,7,8,10 ...
The output of the algorithm would be ( according to my understanding ) 5,9,10 instead of 7,8,10 ..
I think if a new element could be added to both the queues , we should check as to which queue it should be added to maximize the sum ..
@fiddler.g
I still have some doubts regarding your algorithm .
Consider the following input
10,50,80,20,70,68,69
As per the algorithm the output will be 10,50,80 , however , the output should be 50,68,69 ..
I think the step mentioned by you which says "If the next element is less than the both maximums, overwrite the heap with the minimum sum." needs to be refined ..
Please comment ..
10,50,80,20,70,68,69
As per the algorithm the output will be 10,50,80 , however , the output should be 50,68,69 ..
But shouldn't it be 10, 50, 68, 69 instead of just 50,68,69?
<pre lang="java" line="1" title="CodeMonkey68377" class="run-this">class KIncreasing {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = {1,5,2,8,7,6,11};
int k = 3;
findKIncrasing(input, k);
}
private static void findKIncrasing(int[] input, int k) {
// TODO Auto-generated method stub
int[] sums = new int[input.length];
int[] sol = new int[input.length];
int[] size = new int[input.length];
sums[0] = input[0];
size[0] = 1;
sol[0] = -1;
int max = Integer.MIN_VALUE;
int index = -1;
for (int i = 1; i < input.length; i++) {
for (int j = 0; j < i; j++) {
if (input[i] > input[j] && sums[i] < input[i] + sums[j]) {
sums[i] = input[i] + sums[j];
size[i] = 1 + size[j];
sol[i] = j;
}
}
if (size[i] >= k) {
int j = k;
int m = i;
int sum = 0;
while (j > 0) {
sum = sum + input[m];
m = sol[m];
j--;
}
if (sum > max) {
index = i;
max = sum;
}
}
}
if (index == -1) {
System.out.print("No sequence of size k");
return;
}
System.out.println("max:" + max);
System.out.println("index:" + index);
System.out.print("sequence:-");
printSeq(index, input, sol, k);
}
private static void printSeq(int index, int[] input, int[] sol, int k) {
// TODO Auto-generated method stub
if ( k == 0)
return;
printSeq(sol[index], input, sol, k-1);
System.out.printf("%3d,", input[index]);
}
}
</pre><pre title="CodeMonkey68377" input="yes">
</pre>
Read the input array. with the first k elements form a min heap. Keep a track of the max element in the heap. Read the other elements sequentially. If the current element is >max then replace it with the input element. If the input element is >max then replace the min with this element. Keep doing till input is exhausted. The elements in the heap are the solution
Input: 1 2 10 12 8 9 11 9 9 10
k=3
Heap: 1 2 10 max=10 min=1
Read : 12 12>max
Heap: 2 10 12 max=12 min=10
Read : 8 8>min
Heap: 8 10 12 max=12 min=8
Read : 9 9>min
Heap: 9 10 12 max=12 min=9
Read: 11 >min
Heap: 10 11 12 max=12 min=10
Read: 9
Read: 9
Read: 10
Solution: 12,11,10
Yes. With a segment tree or something else we can make one trans in logn time instead of n.
So n*k*logn is achievable.
It could also be done in n*k time with a monotonically decreasing stack. But this is far too difficult to explain.
Rectifying the above algo
Sort the array and also store there indexes
Input: 1 2 10 12 8 9 11 9 9 10
k=3
Sort: (1,0) (2,1) (8,4) (9,5) (9,7)(9,8)(10,2)(10,9)(11,6)(12,3)
Now form a heap
keep max and min
Heap: (1,0) (2,1) (8,4) max=(8,4) min=(1,0)
if the element we are now reading is >max and also its index is greater than the max of heap replace it with the current element
I suspect you meant "...replace the min with the current element" at the end.
If so, here's a counter-example:
Input: 1 2 4 5 3
k=3
Sort: (1, 0) (2, 1) (3, 4) (4, 2) (5, 3)
We won't add (4, 2) or (5, 3) because the index is smaller than that of (3, 4).
If anyone thinks I misinterpreted the algorithm please let me know.
Do you mind posting your n^2 solution? I don't think it's easy to do it correctly.
I have one n*k*logn and one n*k algorithm though.
<pre lang="java" line="1" title="CodeMonkey11169" class="run-this">//Sorry In previous code I forgot to initialize the table
class KIncreasing {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = {6,3,4,1,7,8};
int k = 4;
findKIncrasing(input, k);
}
private static void findKIncrasing(int[] input, int k) {
// TODO Auto-generated method stub
int[] sums = new int[input.length]; //lonngest sum
int[] sol = new int[input.length]; //finding path
int[] size = new int[input.length]; //size of sequence
//Forgot to Initialize this in previous code
for (int i = 0; i < input.length; i++) {
sums[i] = input[i];
size[i] = 1;
sol[i] = -1;
}
int max = Integer.MIN_VALUE;
int index = -1;
for (int i = 1; i < input.length; i++) {
for (int j = 0; j < i; j++) {
if (input[i] > input[j] && sums[i] < input[i] + sums[j]) {
sums[i] = input[i] + sums[j];
size[i] = 1 + size[j];
sol[i] = j;
}
}
if (size[i] >= k) {
int j = k;
int m = i;
int sum = 0;
while (j > 0) {
sum = sum + input[m];
m = sol[m];
j--;
}
if (sum > max) {
index = i;
max = sum;
}
}
}
if (index == -1) {
System.out.print("No sequence of size k");
return;
}
System.out.println("max:" + max);
System.out.println("index:" + index);
System.out.print("sequence:-");
printSeq(index, input, sol, k);
}
private static void printSeq(int index, int[] input, int[] sol, int k) {
// TODO Auto-generated method stub
if (k == 0)
return;
printSeq(sol[index], input, sol, k - 1);
System.out.printf("%3d,", input[index]);
}
}
</pre><pre title="CodeMonkey11169" input="yes">
</pre>
What a shame. Some people make a trivial problem difficult. All you DP lovers..Check this -
1) First the first k=3 max numbers => Heap or traverse or whatever. I'd traverse cause its O(n) only.
2) Sum up the k numbers. Sum_K_Largest(given_list) is same as Max_SumOf_K(given_list).
This seems like a graph problem. I'll explain my algorithm with the example of sequence 10,12,8,9,11. Create a directed graph with numbers as nodes and edge between two nodes a and b exists if a < b and a is present in sequence before b. Do a topological sort of the graph and the graph will be like : 8 --> 9 -->11, 10 -->12 , 10 -->11 and now compute for every node sum from different paths. For example: Sum(8) = 0 + 8, Sum(9) = Max(0,Sum(8)) + 9 = 17 , Sum(10) = 0+10 , Sum(11) = Max(Sum(10),Sum(9))+11 = 28 , Sum(12) = Max(0,Sum(10))+12 = 22.
Now, we know the max sum is 28 and so we can retrace the nodes used to compute the sum. This can easily be customized for any k.
yes.. i think its a graph problem too.. here is my variant. created a directed graph as follows: for any number a, an edge exists from a to another number b if b exists on the left of a and b is the largest number less than a. draw edges like this and form a directed graph. Then pick out nodes which have 0 (zero) incoming edges. these nodes represent the numbers were an increasing subsequence would end. Follow the paths from these nodes and calculate their sum for each path. the path with maximum sum gives the result. time complexity is O(n^2) and space complexity is O(n+e), e is the number of edges.
@first Anonymous
Your algorithm is essentially the same as MaYanK's which is also wrong. You two haven't take k into consideration.
Your last sentence "This can easily be customized for any k." is not true.
@second Anonymous
how would you do "calculate their sum for each path."? If you just trivially try all paths, then it's an exponent-time algorithm. If you use DP without considering k AT EACH STAGE, then it's just the same as the first Anonymous which is wrong.
It's good that you two think of graphs. But your graph is essentially the same as DP which uses the topological ordering of the numbers.
@ftfish
I think we can go along similar lines .
Complexity of finding all monotonically increasing subsequeces = O (n^2) ..
Total number of increasing subsequences = O (n )
hence finding what is asked in the question is O ( n*k ).
total complexity is O ( n^2 + n*k ) .. i.e O (n^2)
Please comment
Sorry , total number of increasing subsequences will be O (n^2).
Hence , total complexity will be O ( k*n^2 )
I can't get your idea. what if the whole sequence is increasing? For this case there're 2^n increasing subsequences.
public class test {
public static void main(String[] arg){
int[] array = {10,50,80,20,70,68,69};
maxSum(array,3);
}
public static void maxSum(int[] array,int k){
int[] valueArray = new int[k];
int kIndex =0;
int sum = array[0];
valueArray[kIndex] = array[0];
for(int i =1; i<array.length;i++){
if(array[i] > valueArray[kIndex]){
if(kIndex < k -1 ){
valueArray[++kIndex] = array[i];
}else{
kIndex = 0;
sum -= valueArray[kIndex];
System.out.println("sum -- = "+sum);
valueArray[kIndex] = array[i];
}
for(int j =0; j<k;j++)
System.out.print(valueArray[j]+", ");
System.out.println();
sum += valueArray[kIndex];
System.out.println("sum = "+sum);
}
}
int total = 0;
for(int j =0; j<k;j++){
System.out.print(valueArray[j] +",");
total += valueArray[j];
}
System.out.println("\ntotal = "+total);
}
<pre lang="java" line="1" title="CodeMonkey95283" class="run-this">class test {
public static void main(String[] arg){
int[] array = {10,50,80,20,70,68,69,100};
maxSum(array,3);
}
public static void maxSum(int[] array,int k){
int[] valueArray = new int[k];
int kIndex =0;
int sum = array[0];
valueArray[kIndex] = array[0];
for(int i =1; i<array.length;i++){
if(array[i] > valueArray[kIndex]){
if(kIndex < k -1 ){
valueArray[++kIndex] = array[i];
}else{
kIndex = 0;
sum -= valueArray[kIndex];
valueArray[kIndex] = array[i];
}
}
}
int total = 0;
for(int j =0; j<k;j++){
System.out.print(valueArray[j] +", ");
total += valueArray[j];
}
System.out.println("\n total = "+total);
}
}
</pre>
Ingore the sum variable in the above code.
Logic is,
1. Create a array 'valueArray' of size K
2. Scan the input array and add the increasing elements to the valueArray
3. If you reach the end of the valueArray, start replacing the elements in valueArray from the beginning
4. Sum up the elements in the valueArray which give the maximum sum
DP. For each A=0,...,k find the best solution whose last number is at position B=1,...,n. Maximize over A=k and all B.
- Anonymous July 25, 2010