Google Interview Question Software Engineer / Developers
Creating a max-heap of first k elements will not be O(k). It will be O(k(log(k))) infact.
Straight forward soln:
//Merge both arrays
int[] c = new int[a.length+b.length];
int j=0;
for(int i=0;i<a.lenght;i++)
c[j++]=a[i];
for(int i=0;i<b.lenght;j++)
c[j++]=b[i];
//Sort
Collections.sort(c);
//Return kth Element
return c[k-1];
Simply merge the two arrays and then apply Quick-Select on the resultant array to find the kth minimum element.
I think solutions above assume that arrays are sorted, but they are not as per question. I would just create a BST and store number of nodes in subtree in the root / internal nodes. Then one can find kth element in log(n) time by ignoring one half of tree, comparing k with number of nodes in the children.
I assume you meant "balanced" BST - otherwise you can't guarantee log(n) operation. Still, it'd be O(n logn) to create BST.
Simplest approach is to merge unsorted arrays, and use median-of-medians to get O(n) worst case order statistics.
A O(n) solution:
1. Use linear time selection to get first k elements in first array. If the length of array is less than k, then use the whole array.
2. Use linear time selection to get first k elements in second array. If the length of array is less than k, then use the whole array.
3. Combine those 2*k element into a new array.
4. Use linear time selection again to find kth element in this new array.
Assuming that n is length of first array and m is length second array. C is a constant number when using linear time selection.
Time complexity: O(max(n,m,2*k,C))
Space complexity: O(2*k)
I don't think this is correct. Selecting the k'th element is linear. Running k'th selection k times is not. Worst case this is n^2 I think when k=n.
Strictly speaking for this question there's no need to merge the complete arrays - O(n). Instead, we can just do a straight search (in both arrays simultaneously) for the k-th element, which would take only O(2k) = O(k).
In most real world cases, though, it'd probably be best to merge the array first.
int findKthElement(int* arr1, int size1, int* arr2, int size2, int k)
{
if (k > size1 + size2) {
cout << "\n\nk is greater than the size of the arrays. Aborting." << endl;
return -1;
}
int i=0, j=0;
// Go over both arrays while they both last
while (i<size1 && j<size2) {
if (arr1[i] < arr2[j]) {
if (1 + i + j == k)
return arr1[i];
i++;
}
else {
if (1 + i + j == k)
return arr2[j];
j++;
}
}
// Continue with whichever array still hasn't reached end (if required)
while (i<size1 && i+j<k) {
if (i++ + j==k)
return arr1[i];
}
while (j<size2 && i+j<k) {
if (i + j++==k)
return arr2[j];
}
// If we've reached here, it means we've gone over
return -1;
}
You can do it in O(log k).
Assuming kth element in 1st array, look at the k/2 element in 1st array and compare it with k/2 and k/2 + 1 element from second array, if the first element lies between them then its the solution, if it is greater, look for k/4th element and compare it to 3k/4 and 3k/4 + 1th element of second element and continue.
int minHeapify(int* array, int i, int length)
{
int left = ((i+1)*2) - 1;
int right = (i+1) * 2;
int largestindex = i;
if (left <= length && array[left] < array[i])
{
largestindex = left;
}
if (right <= length && array[right] < array[largestindex])
{
largestindex = right;
}
if (largestindex != i)
{
int temp = array[largestindex];
array[largestindex] = array[i];
array[i] = temp;
minHeapify(array, largestindex, length);
}
return array[i];
}
int main()
{
int array1[] = {1,3,7};
int array[] = {4,9,10};
int find = 3;
int min1 = 0;
int min2 = 0;
int retVal = 0;
for (int i = 0 ; i < find; i++)
{
int val1 = minHeapify(array1, min1, 2);
int val2 = minHeapify(array, min2, 2);
if (val1<=val2)
{
retVal = val1;
min1++;
}
else
{
retVal = val2;
min2++;
}
}
printf("\r\n -->> %d", retVal);
return 0;
}
Basically, call min heapify on both the arrays and see which has the smaller element, get the next smallest element in the array that has the smallest number
Aaah missed a step, need to build minHeap first
here is the updated code
Last login: Mon Jun 6 02:28:25 on ttys000
Nitin-Bhatts-MacBook-Pro:~ nitinbhatt$ cd code/
Nitin-Bhatts-MacBook-Pro:code nitinbhatt$ clear
Nitin-Bhatts-MacBook-Pro:code nitinbhatt$ cd algo/
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ clear
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ls
heap.cpp merge.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
heap.cpp: In function ‘void maxHeapify(int*, int, int)’:
heap.cpp:34: error: ‘i’ was not declared in this scope
heap.cpp:43: error: ‘largestindex’ was not declared in this scope
heap.cpp:45: error: ‘largerindex’ was not declared in this scope
heap.cpp:48: error: ‘largestindex’ was not declared in this scope
heap.cpp:50: error: ‘largestIndex’ was not declared in this scope
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
heap.cpp: In function ‘void maxHeapify(int*, int, int)’:
heap.cpp:34: error: ‘i’ was not declared in this scope
heap.cpp:43: error: ‘largestindex’ was not declared in this scope
heap.cpp:48: error: ‘largestindex’ was not declared in this scope
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
heap.cpp: In function ‘void maxHeapify(int*, int, int)’:
heap.cpp:43: error: ‘largestindex’ was not declared in this scope
heap.cpp:48: error: ‘largestindex’ was not declared in this scope
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
heap.cpp: In function ‘void maxHeapify(int*, int, int)’:
heap.cpp:41: error: ‘largerindex’ was not declared in this scope
heap.cpp:45: error: ‘largerindex’ was not declared in this scope
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
8 3 2 5 7 4 6 9 1
Comparing [8] with [3]
Comparing [7] with [3] SWAPPING
Comparing [6] with [2] SWAPPING
Comparing [5] with [2]
Comparing [4] with [1] SWAPPING
Comparing [3] with [1] SWAPPING
Comparing [2] with [0]
Comparing [1] with [0] SWAPPING
Comparing [0] with [0]
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
8 3 2 5 7 4 6 9 1
Comparing [8] with [3]
Comparing [7] with [3] SWAPPING
Comparing [6] with [2] SWAPPING
Comparing [5] with [2]
Comparing [4] with [1] SWAPPING
Comparing [3] with [1] SWAPPING
Comparing [2] with [0]
Comparing [1] with [0] SWAPPING
Comparing [0] with [0]
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1
9 8 6 7 3 4 2 5 1 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
heap.cpp: In function ‘int main()’:
heap.cpp:45: error: ‘heapify_max’ was not declared in this scope
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ clear
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
heap.cpp:44: error: expected `)' before ‘{’ token
heap.cpp: In function ‘void buildHeap(int (*)())’:
heap.cpp:55: error: return-statement with a value, in function returning 'void'
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
8 3 2 5 7 4 6 9 1
8 3 2 5 7 4 6 9 1
8 3 2 5 7 4 6 9 1
8 3 2 5 7 4 6 9 1
8 3 2 5 7 4 6 9 1
8 3 2 5 7 4 6 9 1
8 3 2 5 7 4 6 9 1
8 3 2 5 7 4 6 9 1
8 3 2 5 7 4 6 9 1
8 3 2 5 7 4 6 9 1 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
8 3 2 5 7 4 6 9 1 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
8 3 2 5 7 4 6 9 1
8 3 2 5 7 4 6 9 1 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
8 3 2 5 7 4 6 9 1
8 3 2 5 7 4 6 9 1 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
heap.cpp: In function ‘void buildmaxHeap(int*, int)’:
heap.cpp:43: error: expected ‘,’ or ‘;’ before ‘for’
heap.cpp:43: error: ‘i’ was not declared in this scope
heap.cpp:43: error: expected `;' before ‘)’ token
heap.cpp: In function ‘int main()’:
heap.cpp:58: error: ‘buildMaxHeap’ was not declared in this scope
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
heap.cpp: In function ‘void buildmaxHeap(int*, int)’:
heap.cpp:45: error: ‘mapHeapify’ was not declared in this scope
heap.cpp: In function ‘int main()’:
heap.cpp:58: error: ‘buildMaxHeap’ was not declared in this scope
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vu heap.cpp
-bash: vu: command not found
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ :45
-bash: :45: command not found
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
heap.cpp: In function ‘int main()’:
heap.cpp:58: error: ‘buildMaxHeap’ was not declared in this scope
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ clear
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
8 3 2 5 7 4 6 9 1
9 8 6 5 7 4 2 3 1 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ clear
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
4 1 3 2 16 9 10 14 8 7
16 14 10 8 7 9 3 2 4 1 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
heap.cpp: In function ‘void heapSort(int*, int)’:
heap.cpp:55: error: array must be initialized with a brace-enclosed initializer
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
4 1 3 2 16 9 10 14 8 7
16 14 10 8 7 9 3 2 4 1 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
4 1 3 2 16 9 10 14 8 7
16 14 10 8 7 9 3 2 4 1 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
4 1 3 2 16 9 10 14 8 7
16 14 10 8 7 9 3 2 4 1 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
4 1 3 2 16 9 10 14 8 7
14 8 10 4 7 9 3 2 1 16 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
4 1 3 2 16 9 10 14 8 7
14 8 10 4 7 9 3 2 1 16 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
4 1 3 2 16 9 10 14 8 7
14 10 9 4 7 8 3 2 1 16 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
4 1 3 2 16 9 10 14 8 7
1 2 3 4 7 8 9 10 14 16 Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ clear
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ls
a.out heap.cpp merge.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
4 1 3 2 16 9 10 14 8 7
1 2 3 4 7 8 9 10 14 16
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ clear
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ls
a.out heap.cpp merge.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi heap.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ clear
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ls
a.out heap.cpp merge.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ rm a.out
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ clear
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ls
heap.cpp merge.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi findnthlargest.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi findnthlargest.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ findnthlargest.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi findnthlargest.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ findnthlargest.cpp
findnthlargest.cpp: In function ‘int main()’:
findnthlargest.cpp:37: error: too many initializers for ‘int [2]’
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi findnthlargest.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ findnthlargest.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
-->> 1
-->> 3
-->> 7Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ clear
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ls
a.out findnthlargest.cpp heap.cpp merge.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi findnthlargest.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ findnthlargest.cpp
findnthlargest.cpp: In function ‘int main()’:
findnthlargest.cpp:49: error: ‘array2’ was not declared in this scope
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi findnthlargest.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ findnthlargest.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
-->> 4Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ clear
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ls
a.out findnthlargest.cpp heap.cpp merge.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi findnthlargest.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ findnthlargest.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
-->> 4Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ clear
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ls
a.out findnthlargest.cpp heap.cpp merge.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi findnthlargest.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ g++ findnthlargest.cpp
Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ ./a.out
-->> 4Nitin-Bhatts-MacBook-Pro:algo nitinbhatt$ vi findnthlargest.cpp
#include <iostream>
using namespace std;
int minHeapify(int* array, int i, int length)
{
int left = ((i+1)*2) - 1;
int right = (i+1) * 2;
int largestindex = i;
if (left <= length && array[left] < array[i])
{
largestindex = left;
}
if (right <= length && array[right] < array[largestindex])
{
largestindex = right;
}
if (largestindex != i)
{
int temp = array[largestindex];
array[largestindex] = array[i];
array[i] = temp;
minHeapify(array, largestindex, length);
}
return array[i];
}
void buildMinHeap(int* array, int length)
{
int start = (length/2);
for (int i = start; i >=0; i--)
{
minHeapify(array, i, length);
}
}
int main()
{
int array1[] = {7, 3, 1};
int array[] = {10, 9, 4};
int find = 3;
int min1 = 0;
int min2 = 0;
int retVal = 0;
buildMinHeap(array1, 2);
buildMinHeap(array, 2);
for (int i = 0 ; i < find; i++)
{
int val1 = minHeapify(array1, min1, 2);
int val2 = minHeapify(array, min2, 2);
if (val1<=val2)
{
retVal = val1;
min1++;
}
else
{
retVal = val2;
min2++;
}
}
printf("\r\n -->> %d", retVal);
return 0;
}
Hello!
Here is mine code for this problem:
#include <stdio.h>
int findElement( int *a, int *b, size_t sizeA, size_t sizeB, int pos );
int haveIndex( int *a, size_t sizeA, int index);
int maxValue( int *a, size_t sizeA, int *b, size_t sizeB );
int main (int argc, const char * argv[])
{
int a[] = { 3, 1, 7 };
int b[] = { 4, 9 };
int k = -1;
int pos = 5;
k = findElement(a, b, sizeof(a)/sizeof(int), sizeof(b)/sizeof(int), pos);
if ( k == -1 )
printf("Not found\n");
else
printf("Element under position %d: %d\n", pos, k);
return 0;
}
int findElement( int a[], int b[], size_t sizeA, size_t sizeB, int pos )
{
if ( pos > sizeA +sizeB )
return -1;
int element = -1;
int i = 0, j, k = 0, m = 0;
int tmp = -1;
int tmpJ = -1;
int usedIndexesA[sizeA];
int usedIndexesB[sizeB];
int mValue = maxValue(a, sizeA, b, sizeB);
for ( i=0; i<sizeA; i++ )
usedIndexesA[i] = -1;
for ( i=0; i<sizeB; i++ )
usedIndexesB[i] = -1;
for ( i=0; i<pos; i++ )
{
tmp = mValue;
for ( j=0; j<sizeA; j++ )
{
if ( haveIndex(usedIndexesA, sizeA, j) == 1 )
{
if ( tmp > a[j] )
{
tmpJ = j;
tmp = a[j];
}
}
}
for ( j=0; j<sizeB; j++ )
{
if ( haveIndex(usedIndexesB, sizeB, j) == 1 )
{
if ( tmp > b[j] )
{
usedIndexesB[m] = j;
tmpJ = -1;
tmp = b[j];
}
}
}
usedIndexesA[k] = tmpJ;
if ( usedIndexesA[k] != -1 && k < sizeA-1 )
k++;
if (usedIndexesB[m] != -1 && m < sizeB-1 )
m++;
element = tmp;
printf("Element: %d | Index: %d\n", element, i);
}
return element;
}
int haveIndex( int *a, size_t sizeA, int index)
{
int i = 0;
for ( i=0; i<sizeA; i++ )
{
if ( a[i] == index )
return 0;
}
return 1;
}
int maxValue( int *a, size_t sizeA, int *b, size_t sizeB )
{
int tmp = a[0];
for ( int i=0; i<sizeA; i++ )
if ( tmp < a[i] )
tmp = a[i];
for ( int i=0; i<sizeB; i++ )
if ( tmp < b[i] )
tmp = b[i];
return tmp;
}
O(n) approach to solve above problem using Quick sort methodology.
anandtechblog.blogspot.com/2010/07/median-of-unsorted-array.html
const int MaxNum=100;
int myarr[MaxNum];
void findKthElementIndex(int givenum,vector<int>& parray)
{
int pivot=rand()% parray.size() ;
vector<int> leftarry;
vector<int> rightarry;
for(int i=0;i<parray.size();i++)
{
if (myarr[parray[i]]<myarr[parray[pivot]])
leftarry.push_back(parray[i]);
else
rightarry.push_back(parray[i]);
}
if (leftarry.size()==givenum-1)
cout<<myarr[pivot];
else if(leftarry.size()<givenum-1)
{
findKthElementIndex(givenum-leftarry.size(),rightarry);
}
else if(leftarry.size()>givenum-1)
{
findKthElementIndex(givenum,rightarry);
}
}
int main()
{
freopen("in.txt","r",stdin);
int num,givenum;
int count=0;
while(scanf("%d %d",&num,&givenum)!=EOF)
{
cout<<"case:"<<count++<<endl;
vector<int> indexarray;
for(int i=0;i<num;i++)
{
scanf("%d",&myarr[i]);
indexarray.push_back(i);
}
findKthElementIndex(givenum,indexarray);
}
return 0;
}
As we all know, we can modify the quick sort to find the k'th largest element in an array with the time complexity O(n). Now given two arrays, we can modify one array method to fit two arrays with some consideration about the index of an element. Here is the code.
#include <iostream>
using namespace std;
void swap(int* a1, int* a2, int n, int i, int j)
{
if (i < n)
{
int temp = a1[i];
if (j < n)
{
a1[i] = a1[j];
a1[j] = temp;
}
else
{
a1[i] = a2[j - n];
a2[j - n] = temp;
}
}
else
{
int temp = a2[i - n];
if (j < n)
{
a2[i - n] = a1[j];
a1[j] = temp;
}
else
{
a2[i - n] = a2[j - n];
a2[j - n] = temp;
}
}
}
int partition(int* a1, int* a2, int n, int start, int end)
{
int num;
if (end < n)
{
num = a1[end];
}
else
{
num = a2[end - n];
}
int i = start;
int j = end - 1;
while (i <= j)
{
int t;
if (i < n)
{
t = a1[i];
}
else
{
t = a2[i - n];
}
if (t <= num)
{
++i;
}
else
{
while (i <= j)
{
int tt;
if (j < n)
{
tt = a1[j];
}
else
{
tt = a2[j - n];
}
if (tt > num)
{
--j;
}
else
{
swap(a1, a2, n, i, j);
++i;
--j;
break;
}
}
}
}
swap(a1, a2, n, i, end);
return i;
}
int findk(int* a1, int* a2, int n, int k, int start, int end)
{
if (start == end)
{
if (start < n)
{
return a1[start];
}
else
{
return a2[start - n];
}
}
int p = partition(a1, a2, n, start, end);
if (p == k)
{
if (p < n)
{
return a1[p];
}
else
{
return a2[p - n];
}
}
else if (p > k)
{
return findk(a1, a2, n, k, start, p - 1);
}
else
{
return findk(a1, a2, n, k, p + 1, end);
}
}
int main()
{
int n, m, k;
int a1[1000];
int a2[1000];
cin >> n >> m >> k;
for (int i = 0; i < n; ++i)
{
cin >> a1[i];
}
for (int i = 0; i < m; ++i)
{
cin >> a2[i];
}
if (k < 1 || k > n + m)
{
cerr << "k is not valid" << endl;
return 0;
}
int result = findk(a1, a2, n, k - 1, 0, m + n - 1);
cout << result << endl;
return 0;
}
Simple merge the 2 arrays.Construct a max heap of first k elements .THIS WILL BE O(k).Now traverse thru ur merged array and compare each elemnt with top of the heap.If its bigger the reject it or else if smaller then replace (delete top,insert the smaller element and call heapify).
- Shiraj Pokharel June 04, 2011