## Google Interview Question for Research Scientists

Country: United States

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

My C# solution

``````public int[] GenerateMaxSecuence(int[] a1, int[] a2, int k)
{
if (a1.Length + a2.Length < k)
return null;

int[] result = new int[k];
int index = 0;
int i1 = 0;
int i2 = 0;

while (index < result.Length)
{
int available = (a1.Length - i1) + (a2.Length - i2);
int maxIndex1 = GetMaxIndex(a1, i1, k, available);
int maxIndex2 = GetMaxIndex(a2, i2, k, available);

if (maxIndex2 >= a2.Length || (maxIndex1 < a1.Length && a1[maxIndex1] >= a2[maxIndex2]))
{
result[index] = a1[maxIndex1];
i1 = maxIndex1 + 1;
}
else
{
result[index] = a2[maxIndex2];
i2 = maxIndex2 + 1;
}

index++;
k--;
}

return result;
}

private int GetMaxIndex(int[] a, int startIndex, int k, int available)
{
int maxIndex = startIndex;
int runner = startIndex;

while (runner < a.Length && (available >= k))
{
if (a[runner] > a[maxIndex])
maxIndex = runner;

runner++;
available--;
}

return maxIndex;
}``````

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

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;
}``````

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

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];``````

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

Little Correction....its

max( Array1[i] * 10 + function(i + 1, j, k - 1), ...)
max(Array2[j] * 10 + function(i, j + 1, k - 1), ...)

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

correction:
if (k <= 0) {
return 0;
}

.........................
why careercup doesnt allow to change comment/code :(

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

@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?

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

Maybe not

``Array1[i] * 10``

, but

``Array1[i] * 10^k``

.

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

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][b-1]*10, memo[i][b-1]);
}
else if (b == 0) {
memo[i][a][b] = Math.max(A[a-1] + memo[i-1][a-1]*10, memo[i][a-1]);
} 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];
}``````

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

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)

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

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}

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

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;
}``````

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

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)

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

Its don't work in border case
For example:
k = 3
first array: 869
second: 175

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

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

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

@Pavel Can you code it and put it up to testing?

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

``````#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;
}``````

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

This code does not work with the following input:

array 1 = {3,4,5,6}
array 2 = {2,1,5,3,8,9}

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

``````#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;
}``````

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

``````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;
}``````

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

This code does not work with the following input:

array 1 = {3,4,5,6}
array 2 = {2,1,5,3,8,9}

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

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++){
}
}
else{
int maxIndex = 0;
int maxVal = arr;
for( int i = 0 ; i < size- k + 1 ; i++){
if( arr[i] > maxVal){
maxIndex = i;
maxVal = arr[i];
}
}
int[] rightArray = Arrays.copyOfRange(arr, maxIndex+1, size);
//System.out.println(numberList.toString());
if( k > 1)
//System.out.println(numberList.toString());
}

return numberList;
}
}``````

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

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 = bisect(state, index, state, len(state)) # 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].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].append(i)

kToReturn = *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)``````

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

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*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*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``````

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

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());
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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))

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

Too slow.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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.

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

This solution is incorrect (((.

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.