Google Interview Question
Research ScientistsCountry: United States
O((m+n)*K) solution
public int[] findMax(int[] a,int [] b,int K)
{
int i1=0;
int i2=0;
int []ret=new int[K];
for(int i=0;i<K;i++)
{
int r=K-i;
int an=a.length-i1;
int bn=b.length-i2;
int maxa=0;
int maxai=-1;
for(int j=0;j<an && bn+an-j>=r ;j++)
{
if(maxai==-1 || a[i1+j]>maxa)
{
maxai=j;
maxa=a[i1+j];
}
}
int maxb=0;
int maxbi=-1;
for(int j=0;j<bn && an+bn-j>=r;j++)
{
if(maxbi==-1 || b[i2+j]>maxb)
{
maxb=b[i2+j];
maxbi=j;
}
}
if((maxai!=-1 && maxbi==-1)||(maxa>maxb))
{
i1+=maxai+1;
ret[i]=maxa;
}
else if((maxai==-1 && maxbi!=-1)||(maxb>maxa))
{
i2+=maxbi+1;
ret[i]=maxb;
}
else
{
ret[i]=maxa;
maxa=0;
for(int j=0;j<=maxai;j++)
{
if(a[i1+j]>maxa)
maxa=a[i1+j];
}
maxb=0;
for(int j=0;j<=maxbi;j++)
if(b[i2+j]>maxb)
maxb=b[i2+j];
if(maxa>maxb)
i2+=maxbi+1;
else
i1+=maxai+1;
}
}
return ret;
}
F(i, j, k) = max { 10 * Array1[i] * F(i + 1, j , k - 1), F(i + 1, j + 1, k) } if Array1[i] > Array2[j]
max { 10 * Array2[j] * F(i, j + 1, k - 1), F(i + 1, j + 1, k) } else
So this can be solved using Dynamic Programming with time and space complexity of O(m * n * k) [Not sure if this can be solved without using DP in more efficiently]
int function(int* Array1, int i, int* Array2, int j, int k)
{
// Check for i & j moving out of bound
if (k <= 0) {
return 0;
}
if (DP[i][j][k]) {
return DP[i][j][k];
}
if (Array1[i] > Array2[j]) {
return DP[i][j][k] = max( 10 * Array1[i] * function(i + 1, j, k - 1), function(i + 1, j + 1, k) )
} else {
return DP[i][j][k] = max( 10 * Array[j] * function(i, j + 1, k - 1), function(i + 1, j + 1, k) );
}
}
ANS : DP[0, 0, k];
Little Correction....its
max( Array1[i] * 10 + function(i + 1, j, k - 1), ...)
max(Array2[j] * 10 + function(i, j + 1, k - 1), ...)
correction:
if (k <= 0) {
return 0;
}
.........................
why careercup doesnt allow to change comment/code :(
@sameer I understand your solution and I think it should work, but when I implemented it in java, it returned wrong result (for the example above). I added all of the fixes from your comments. How do you intend to handle corner cases when i or j are out of bounds?
Almost same as @sameer's, in java, no recursion
public static int getMaxNumber(int[] A, int[] B, int K) {
//trivial cases are when K=0, when nothing used from first array, when nothing used from second array
int[][][] memo = new int[K+1][A.length+1][B.length+1];
for (int i = 0; i <= K; i++) {
for (int a = 0; a<= A.length; a++) {
for (int b = 0; b <= B.length; b++) {
if (i==0) {
memo[i][a][b] = 0;
continue;
}
if (a == 0 && b == 0) {
memo[i][a][b] = 0;
continue;
}
if (a == 0) {
memo[i][a][b] = Math.max(B[b-1] + memo[i-1][0][b-1]*10, memo[i][0][b-1]);
}
else if (b == 0) {
memo[i][a][b] = Math.max(A[a-1] + memo[i-1][a-1][0]*10, memo[i][a-1][0]);
} else {
memo[i][a][b] = Math.max(A[a-1] + memo[i-1][a-1][b]*10,
Math.max(B[b-1] + memo[i-1][a][b-1]*10
,memo[i][a-1][b-1]));
}
}
}
}
return memo[K][A.length][B.length];
}
Need one adjustment. When you can choose either a or b the real choice is
ChooseA = max( choose a, don't choose a)
ChooseB = max(choose b, don't choose b)
Memo k,a,b = max(chooseA, chooseB)
I am not sure this algorithm would work for the following cases(Maybe I am wrong):
In this algorithm, the sum of number is dependent on which way a next number is merged with previous sum. (whether left or right).
array 1 = {3,4,5,6}
array 2 = {2,1,5,3,8,9}
Here is C++ solution. I am not proud of this algorithm but could not come up with the working algorithm for the following input:
array 1 = {3,4,5,6}
array 2 = {2,1,5,3,8,9}
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
struct node {
int value;
int pos;
int source;
bool visited;
node(int v, int p, int s):value(v), pos(p), source(s), visited(false){}
};
bool compare(node& a, node& b)
{
return (a.value > b.value);
}
bool search_max(vector<node>& list, int pos_a, int pos_b, int length_a, int length_b, vector<int>& result, int k)
{
if (result.size() == k)
return true;
int left_a = length_a - pos_a - 1;
int left_b = length_b - pos_b - 1;
if ((left_a+left_b) < (k - result.size()))
return false;
int new_a = pos_a;
int new_b = pos_b;
for (int i = 0; i< list.size(); i++)
{
if (list[i].visited)
continue;
if (list[i].source == 1 && list[i].pos > pos_a)
{
new_a = list[i].pos;
} else if (list[i].source == 2 && list[i].pos > pos_b)
{
new_b = list[i].pos;
} else {
continue;
}
list[i].visited = true;
result.push_back(list[i].value);
if (search_max(list, new_a, new_b, length_a, length_b, result, k))
return true;
result.pop_back();
list[i].visited= false;
new_a = pos_a;
new_b = pos_b;
}
return false;
}
void find_max_with_relative_order(vector<int>& array1, vector<int>& array2, int k)
{
int pos_a = INT_MIN;
int pos_b = INT_MIN;
vector<node> merged;
vector<int> result;
for (int i = 0; i < array1.size(); i++)
merged.push_back(node(array1[i], i, 1));
for (int i = 0; i < array2.size(); i++)
merged.push_back(node(array2[i], i, 2));
sort(merged.begin(), merged.end(), compare);
search_max(merged, pos_a, pos_b, array1.size(), array2.size(), result, k);
if (result.size() == k)
{
for (int i =0; i <result.size(); i++)
cout<<result[i];
cout<<endl;
} else {
cout<<"failed to find number"<<endl;
}
}
int main() {
vector<int> array1, array2;
array1.push_back(3);
array1.push_back(4);
array1.push_back(6);
array1.push_back(5);
array2.push_back(9);
array2.push_back(1);
array2.push_back(2);
array2.push_back(5);
array2.push_back(8);
array2.push_back(3);
find_max_with_relative_order(array1, array2, 5);
array1.clear();
array2.clear();
array1.push_back(3);
array1.push_back(4);
array1.push_back(5);
array1.push_back(6);
array2.push_back(2);
array2.push_back(1);
array2.push_back(5);
array2.push_back(3);
array2.push_back(8);
array2.push_back(9);
find_max_with_relative_order(array1, array2, 5);
return 1;
}
Here is my o(n) solution:
1. Build the biggest number with length k from each array. example: k=5, A=(9,1,2,5,8,3) , B=(3,4,6,5,0,0,0,0) we will build the number 92583 from the first array and 34650 from the second array.
How can we build the biggest number from an arrayA ? Build 10 stacks, one stack to each digit. We need to pass from right to left on the arrayA, and add the indexes of the digits to the stacks. Indexes of digit 7 will be inserted to stack 7.
Now build the biggest number is very easy, check the index in stack 9, if it can be added to the number continue with 9, else, try 8... Until you have k digits in number.
2. Now we have 2 biggest numbers, how can we answer the question ?
Create 2 integers i=0,j=0 and we will pass the 2 biggest numbers we created .
if arrayA[i]>arrayB[j] add arrayA[i] to the new number we create (the answer to the question) and i++, else add arrayB[j] to the new number, j++.
Done - o(n)
This task can be solved in O(N + M) time.
First, it is obvious, that a greedy algorithm should be used, i.e. the first digit should be as big as possible and as left as possible in respective array.
Let us divide both arrays into 10 buckets, where a bucket number i (0 <= i <= 9) should contain a list of all i's positions in the respective array.
Algorithms performs K steps, each finds a max. possible digit for the current position. We should maintain 2 indices - one for the rightmost digit taken from the first array, and one for the second array. Initially these indices are both zero (or -1 depending on implementation). On each of K steps go through 10 buckets of both arrays in decreasing order of digit and try to find a position such that (number of remaining elements in the respective array after this index) + (number of remaining elements in the other array) is at least K-T, where T is a number of performed steps. When iterating through buckets, if we meet a position that is to the left of current rightmost index for the respective array, we can drop this position and never consider it again. Otherwise, if it is to the right of the rightmost position, we immediately discard it, put to the resulting array, and go to the next step immediately.
It is easy to see, that each element will be considered only once: it will either be dropped, or put into result. Thus, the complexity has an order of total number of elements = O(N + M).
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include<iterator>
#include<algorithm>
using namespace std;
vector<unsigned> parse() {
string s;
cout << "enter the elements of the array" << endl;
getline(cin, s);
stringstream data(s);
vector<unsigned> a { istream_iterator<unsigned>(data), istream_iterator<
unsigned>() };
return a;
}
void table_ending(vector<unsigned> a, unsigned b, unsigned e,
vector<unsigned>&v, unsigned k, unsigned j) {
while (b < a.size() and v.size() < k) {
if (e > j) {
auto biggest = max_element(a.begin() + b, a.begin() + e);
b = distance(begin(a), biggest) + 1;
v.push_back(*biggest);
unsigned n = (a.size() - b) - j + 1;
e = min((unsigned) (a.size() - b), n) + b;
} else {
v.push_back(a[b]);
b++;
}
}
}
int main() {
vector<unsigned> v, a, b;
unsigned k, an(0), bn(0), b1(0), b2(0), e1, e2;
string s;
a = parse();
//cout << "enter the elements of the array" << endl;
b = parse();
cout << "give the lengh of the number" << endl;
cin >> k;
unsigned j = k, n = a.size() + b.size() + 1 - k;
e1 = min((unsigned) a.size(), n);
e2 = min((unsigned) b.size(), n);
while (b1 < a.size() and b2 < b.size() and v.size() < k) {
auto biggest1 = max_element(a.begin() + b1, a.begin() + e1);
auto biggest2 = max_element(b.begin() + b2, b.begin() + e2);
unsigned b11 = distance(begin(a), biggest1) + 1;
unsigned b22 = distance(begin(b), biggest2) + 1;
if ((*biggest1 > *biggest2)
or (*biggest1 == *biggest2
and (b22 == b.size()
or *max_element(a.begin() + b11,
a.begin() + b11 + e1)
>= *max_element(b.begin() + b22,
b.begin() + b22 + e2)))) {
b1 = b11;
v.push_back(*biggest1);
} else {
b2 = b22;
v.push_back(*biggest2);
}
j--;
n = (a.size() - b1) + (b.size() - b2) - j + 1;
e1 = min((unsigned) (a.size() - b1), n) + b1;
e2 = min((unsigned) (b.size() - b2), n) + b2;
}
table_ending(a, b1, e1, v, k, j);
table_ending(b, b2, e2, v, k, j);
copy(v.begin(), v.end(), ostream_iterator<unsigned>(cout ," "));
return 0;
}
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include<iterator>
#include<algorithm>
using namespace std;
vector<unsigned> parse() {
string s;
cout << "enter the elements of the array" << endl;
getline(cin, s);
stringstream data(s);
vector<unsigned> a { istream_iterator<unsigned>(data), istream_iterator<
unsigned>() };
return a;
}
void table_ending(vector<unsigned> a, unsigned b, unsigned e,
vector<unsigned>&v, unsigned k, unsigned j) {
while (b < a.size() and v.size() < k) {
if (e > j) {
auto biggest = max_element(a.begin() + b, a.begin() + e);
b = distance(begin(a), biggest) + 1;
v.push_back(*biggest);
unsigned n = (a.size() - b) - j + 1;
e = min((unsigned) (a.size() - b), n) + b;
} else {
v.push_back(a[b]);
b++;
}
}
}
int main() {
vector<unsigned> v, a, b;
unsigned k, an(0), bn(0), b1(0), b2(0), e1, e2;
string s;
a = parse();
//cout << "enter the elements of the array" << endl;
b = parse();
cout << "give the lengh of the number" << endl;
cin >> k;
unsigned j = k, n = a.size() + b.size() + 1 - k;
e1 = min((unsigned) a.size(), n);
e2 = min((unsigned) b.size(), n);
while (b1 < a.size() and b2 < b.size() and v.size() < k) {
auto biggest1 = max_element(a.begin() + b1, a.begin() + e1);
auto biggest2 = max_element(b.begin() + b2, b.begin() + e2);
unsigned b11 = distance(begin(a), biggest1) + 1;
unsigned b22 = distance(begin(b), biggest2) + 1;
if ((*biggest1 > *biggest2)
or (*biggest1 == *biggest2
and (b22 == b.size()
or *max_element(a.begin() + b11,
a.begin() + b11 + e1)
>= *max_element(b.begin() + b22,
b.begin() + b22 + e2)))) {
b1 = b11;
v.push_back(*biggest1);
} else {
b2 = b22;
v.push_back(*biggest2);
}
j--;
n = (a.size() - b1) + (b.size() - b2) - j + 1;
e1 = min((unsigned) (a.size() - b1), n) + b1;
e2 = min((unsigned) (b.size() - b2), n) + b2;
}
table_ending(a, b1, e1, v, k, j);
table_ending(b, b2, e2, v, k, j);
copy(v.begin(), v.end(), ostream_iterator<unsigned>(cout ," "));
return 0;
}
long buildmax(vector<long>& a, vector<long>& b, size_t size)
{
long maxA = 0, maxB = 0, result = 0;
size_t indexA = 0, indexB = 0;
for (size_t i = 0; i < size; i++)
{
result *= 10;
for (size_t i = indexA; i < a.size(); i++)
if (a[i] >= maxA)
{
maxA = a[i];
indexA = i;
}
for (size_t i = indexB; i < b.size(); i++)
if (b[i] >= maxB)
{
maxB = b[i];
indexB = i;
}
if (maxA > maxB)
{
result += maxA;
indexA++;
maxA = 0;
} else {
result += maxB;
indexB++;
maxB = 0;
}
}
return result;
}
Here is my solution. It is lengthy but i think in interview they want to see your design also not only the code that only solve.
public class CareerCup {
public String maxNumber(int[] arr1, int[] arr2, int k){
HashMap<Integer,ArrayList<Integer>> procMapArr1 = GetProcessingMap(arr1,k);
HashMap<Integer,ArrayList<Integer>> procMapArr2 = GetProcessingMap(arr2,k);
int mid = (k+1)/2;
//System.out.println(mid);
int[] result = new int[k];
for(int i = 1 ; i <= k;i++){
//System.out.println(" check: " + procMapArr1.get(i).toString());
//System.out.println(" check: " + procMapArr2.get(k-i).toString());
int[] temp = findMaxNumber(procMapArr1.get(i),procMapArr2.get(k-i));
if( IsBigger(temp,result)){
for(int j = 0 ; j<temp.length;j++){
result[j] = temp[j];
}
}
}
return Arrays.toString(result);
}
private boolean IsBigger(int[] temp, int[] result) {
int size1 = temp.length;
int size2 = temp.length;
if( size1 == size2){
int i = 0;
while( i<size1 && temp[i] == result[i]){
i++;
}
if( i == size1)
return false;
return temp[i] > result[i];
}
return size1 > size2;
}
private int[] findMaxNumber(ArrayList<Integer> arrayList1,ArrayList<Integer> arrayList2) {
//System.out.println("hi");
int size1 = 0;
int size2 = 0;
if( arrayList1 != null)
size1 = arrayList1.size();
if( arrayList2 != null)
size2 = arrayList2.size();
int[] retArray = new int[size1+size2];
int indexArr1 = 0 ;
int indexArr2 = 0 ;
int currentIndex = 0 ;
while(true){
if( indexArr1 < size1 && indexArr2 < size2 ){
if( arrayList1.get(indexArr1) > arrayList2.get(indexArr2)){
retArray[currentIndex++]= arrayList1.get(indexArr1);
indexArr1++;
}
else {
retArray[currentIndex++]= arrayList2.get(indexArr2);
indexArr2++;
}
}
else if ( indexArr1 < size1){
retArray[currentIndex++]= arrayList1.get(indexArr1);
indexArr1++;
}
else if ( indexArr2 < size2 ){
retArray[currentIndex++]= arrayList2.get(indexArr2);
indexArr2++;
}
else {
break;
}
}
//System.out.println(Arrays.toString(retArray));
return retArray;
}
private HashMap<Integer, ArrayList<Integer>> GetProcessingMap(int[] arr,int k) {
HashMap<Integer,ArrayList<Integer>> hmap = new HashMap<Integer,ArrayList<Integer>>();
for( int i = 1 ; i <= k;i++){
ArrayList<Integer> temp = GetArrayNumber(arr,i);
hmap.put(i, temp);
}
System.out.println(hmap.toString());
return hmap;
}
private ArrayList<Integer> GetArrayNumber(int[] arr, int k) {
//System.out.println(Arrays.toString(arr) + " k: " + k);
ArrayList<Integer> numberList = new ArrayList<Integer>();
int size = arr.length;
if( size < k )
return null;
//int currentSize = 0;
if( size == k ){
for(int i = 0 ; i < size;i++){
numberList.add(arr[i]);
}
}
else{
int maxIndex = 0;
int maxVal = arr[0];
for( int i = 0 ; i < size- k + 1 ; i++){
if( arr[i] > maxVal){
maxIndex = i;
maxVal = arr[i];
}
}
numberList.add(arr[maxIndex]);
int[] rightArray = Arrays.copyOfRange(arr, maxIndex+1, size);
//System.out.println(numberList.toString());
if( k > 1)
numberList.addAll(GetArrayNumber(rightArray,k-1));
//System.out.println(numberList.toString());
}
return numberList;
}
}
My runtime should be O(k * log j), where j is the maximum times a number repeats in n or m
My python solution basically looks for the largest number that be chosen from either of the arrays provided there are enough items left to fulfill remaining k after that number is chosen from either array.
I keep a running count of how many items can be chosen from n or m using nLeft or mLeft.
nArray is an array of lenght 10 where every index say i, contains a position p and array 'a'. 'a' is the indexes where i appeared in n. p is the index in a which is the smallest index of i in n which we can consider next. similarly mArray.
for every k i consider numbers from 9 to 1 in each array and check if i can choose it.
my code:
from bisect import bisect
def shiftCurrIndex(array, index):
for state in array:
state[0] = bisect(state[1], index, state[0], len(state[1])) # O(lg n)
def getSmallestIndex(indexState):
i, indexes = indexState
if indexes and i < len(indexes):
return indexes[i]
return -1
def largestNum(n, m, k):
nArray = [[0, []] for i in range(10)]
mArray = [[0, []] for i in range(10)]
nLeft = len(n)
mLeft = len(m)
if (nLeft + mLeft) < k:
return []
for i in range(len(n)):
v = n[i]
nArray[v][1].append(i) # This step can be optimized
# to be O(1) by starting with
# linked list and then converting
# it to an array afterwards
for i in range(len(m)):
v = m[i]
mArray[v][1].append(i)
kToReturn = [0]*k
for indexInK in range(k):
indexLeftForK = k - indexInK -1
for i in range(9, -1, -1):
iMinN = getSmallestIndex(nArray[i])
iMinM = getSmallestIndex(mArray[i])
remainN = -1
if iMinN != -1 and (mLeft + (len(n) - iMinN - 1)) >= indexLeftForK:
remainN = len(n) - iMinN - 1
remainM = -1
if iMinM != -1 and (nLeft + (len(m) - iMinM - 1)) >= indexLeftForK:
remainM = len(m) - iMinM - 1
if remainM == -1 and remainN == -1:
continue
elif remainN != -1 and (remainM == -1 or remainN < remainM):
nLeft = remainN
shiftCurrIndex(nArray, iMinN)
kToReturn[indexInK] = i
break
else:
mLeft = remainM
shiftCurrIndex(mArray, iMinM)
kToReturn[indexInK] = i
break
return kToReturn
print largestNum([3,4,5,6], [2,1,5,3,8,9], 5)
print largestNum([3,4,6,5], [9,1,2,5,8,3], 5)
print largestNum([],[], 5)
print largestNum([1,2,3], [3,5,4], 0)
print largestNum([2,3,4,5,3,5,3,7,5,7,8,4,3,9,8,6], [9,8,6,3,5,7,4,3,6,8,5,4,3,5], 10)
Here is a recursive function in python using hashmap to boost up the speed.
HASH = {}
def find_max(A1, A2, k):
# Base Cases
if k == 0:
return None
if k == 1:
print A1, A2, k, max(A1+A2)
return max(A1+A2)
if len(A1) + len(A2) < k:
return None
# Recursive
key = (tuple(A1),tuple(A2),k)
if key in HASH:
return HASH[key]
else:
candidates = []
if len(A1):
m = find_max(A1[1:], A2, k)
if m is not None: candidates.append(m)
m = find_max(A1[1:], A2, k-1)
if m is not None: candidates.append(A1[0]*pow(10,k-1)+m)
if len(A2):
m = find_max(A1, A2[1:], k)
if m is not None:
candidates.append(m)
m = find_max(A1, A2[1:], k-1)
if m is not None: candidates.append(A2[0]*pow(10,k-1)+m)
if len(candidates):
result = max(candidates)
else:
result = None
print A1, A2, k, candidates, '=>', result
HASH[key] = result
return result
I came up with a Greedy algorithm for this problem, the idea is to consider all available elements of both arrays as a single pool of available elements. Once you pick a highest available, all the elements before and including that index should be flagged as not available for next iteration. Take care you measure the available K window remaining to not pick elements beyond that limit. Algorithm is returning the right response, please let me know if someone spot any edge cases or errors.
Java implementation:
public static void runSolution() {
int a1[] = {3, 4, 6, 5};
int a2[] = {9, 1, 2, 5, 8, 3};
System.out.println(getMaxKDigitNumber(a1, a2, 5));
}
public static int getMaxKDigitNumber(int[] a1, int[] a2, int k) {
if (a1 == null || a2 == null || a1.length == 0 || a2.length == 0) {
return -1; // error
}
int n = a1.length;
int m = a2.length;
int p = n + m; // pool size
if (k > p) {
return -1; // error
}
int i1 = 0, i2 = 0; // current indexes for each array
int c = 0; // count of how many picked elements so far
int h = 0; // highest element temp var.
int ih = -1; // index of highest found for this iteration
boolean foundInFirstArray = false; // flag to tell where the highest was found if first or last array
boolean[] usedA1 = new boolean[n]; // track used elements from first array.
boolean[] usedA2 = new boolean[m]; // track used elements from 2nd array.
int countSkipped = 0; // temp var used to count skipped elements of pool.
StringBuilder sb = new StringBuilder();
int ptemp = 0;
while (c < k) {
h = 0;
ih = -1;
ptemp = p;
for (int i = i1; ptemp >= (k - c) && i < a1.length; i++) {
if (!usedA1[i] && a1[i] > h) {
h = a1[i];
ih = i;
foundInFirstArray = true;
}
ptemp--;
}
ptemp = p;
for (int i = i2; ptemp >= (k - c) && i < a2.length; i++) {
if (!usedA2[i] && a2[i] > h) {
h = a2[i];
ih = i;
foundInFirstArray = false;
}
ptemp--;
}
countSkipped = 0;
if (foundInFirstArray) {
// mark all as used till ith element
for (int i = 0; i <= ih && i < a1.length; i++) {
if (!usedA1[i]) {
usedA1[i] = true;
countSkipped++;
}
}
sb.append(a1[ih]);
i1 = ih + 1;
} else {
// mark all as used till ith element
for (int i = 0; i <= ih && i < a2.length; i++) {
if (!usedA2[i]) {
usedA2[i] = true;
countSkipped++;
}
}
sb.append(a2[ih]);
i2 = ih + 1;
}
p = p - countSkipped;
c++;
}
return Integer.parseInt(sb.toString());
}
This can be solved using greedy method with a max-heap.
1. push all elements to a max-heap
2. pop one integer from the max-heap, if (number of elements to the right + number of elements in the other array) is still greater than k - 1, output the element to the result. Otherwise, pop another element (2nd largest)... repeatedly until the element is found. When the element is found, unused, greater elements have to be pushed back.
3. Update the start of the array to the location of the picked element + 1, k--, and then repeat 2... until the length of the result equals to K
2 and 3 are nested loop and overall it's = O(K(M+N)log(M+N))
1. Get longest decreased subsequence from arr1.
2. Get longest decreased subsequence from arr2. If you have few longest subsequences, choose the biggest one.
3. Merge two subsequences like in merge sort in decreased order.
My C# solution
- hnatsu November 28, 2015