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

- hnatsu November 28, 2015 | Flag Reply
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];

- sameer November 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Little Correction....its

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

- sameer November 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

- sameer November 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- blckembr November 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Maybe not

Array1[i] * 10

, but

Array1[i] * 10^k

.

- Yola January 23, 2016 | Flag
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][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];
	}

- blckembr November 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Anon November 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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}

- hankm2004 December 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hankm2004 December 16, 2015 | Flag
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)

- Naor November 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Archy November 22, 2015 | Flag
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).

- Pavel Kalinnikov November 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- blckembr November 20, 2015 | Flag
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;
}

- nnb November 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code does not work with the following input:

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

- hankm2004 December 16, 2015 | Flag
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;
}

- Nabila.ABDESSAIED November 20, 2015 | Flag Reply
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;
}

- Teh Kok How November 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code does not work with the following input:

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

- hankm2004 December 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 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;
  }

- Tewelde December 06, 2015 | Flag Reply
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++){
				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;
	}
}

- kamrultopu February 12, 2016 | Flag Reply
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[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)

- Adi April 03, 2016 | Flag Reply
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[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

- Alborz April 11, 2016 | Flag Reply
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());			
}

- guilhebl May 09, 2016 | Flag Reply
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))

- cdhsiung November 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Too slow.

- Pavel Kalinnikov November 19, 2015 | Flag
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.

- max November 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution is incorrect (((.

- max November 18, 2015 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More