Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
"Now, the kth element can be in A[k/2 + 1] to A[k] or B[1] to B[k/2]."
This is wrong. Should be A[k/2 + 1] to A[k] or B[1] to B[k].
This is wrong!!
You said:
"
If A[k/2] < B[k/2], it means these A[1] to A[k/2] elements are part of first k elements.
"
Well, not necessarily
consider the case
A[] = {2,3,4,5,6,7}
B[] = {1,6,9,10,11,12}
Consider k = 4
now comparing 4 & 10 , 10 is greater
So by your algo algo {2,3,4} should be three smallest
but answer should be {1,2,3}
Answer must be either in of the array and within first k elements in each so total data to be looked at is 2k
Correct solution will eliminate half of it after each iteration. Its easy to see how it can be done!
Think more!
using namespace std;
#include <iostream>
int main()
{
int k = 5;
int a[] = {1, 5, 7, 8, 10, 15, 17, 20, 25, 38, 50, 61, 95, 200, 305, 645};
int b[] = {6, 10, 18, 20, 31, 57, 107, 117, 210, 510, 608, 730, 850};
int la, ra, ma;
int lb, rb, mb;
//index starts from 1; subtract 1 for actual index
ra = rb = k;
while (ra+rb != k) {
if (a[ra-1] == b[rb-1] && ra+rb==k)
break;
if (a[ra-1] > b[rb-1]) {
la = k - rb;
ra = (la + ra) / 2;
}
else {
lb = k - ra;
rb = (lb + rb) / 2;
}
}
if (ra == 0)
cout << b[rb-1];
else if (rb == 0)
cout << a[ra-1];
else if (a[ra-1] > b[rb-1])
cout << a[ra-1];
else
cout << b[rb-1];
cout << endl;
cout << "la ra: " << la << " " << ra << endl;
cout << "lb rb: " << lb << " " << rb << endl;
}
fill or delete some elements ,make the 2 array with same size k, problem turn into find (m+n)/2 th elements in2sorted array(with size m and n), i remember it'sO(max(logm,logn)) ,in this case k=m=n , so its done. not sure, maybe works :)
/*
* Two sorted array. Find kth smallest element
O(logK)
*/
static int findKFromTowSortedArray(int []a , int [] b, int k){
int i = Math.min(k, a.length - 1);
int j = Math.min(k, b.length - 1);
int medianA, medianB;
int medianAindex, medianBindex;
//pre condition: i<k, j<k;
while (i+j > k){
int d = Math.abs(i-j);
if (i> j){
medianAindex = (k + d) /2 +1;
medianBindex = (k - d) /2 +1;
}else{
medianAindex = (k - d) /2 +1;
medianBindex = (k + d) /2 +1;
}
medianA = a[medianAindex -1]; // -1, becaue array is 0-based
medianB = b[medianBindex -1];
if (medianA < medianB){
j = medianBindex -1;
}else {
i = medianAindex -1;
}
}
return Math.max(a[i-1], b[j-1]);
}
I did not wrote code for it .... but i think this will work.
Take the first k elements from each array(I mean just index). then do the comparison.
arr1_si = 0;
arr1_ei = k;
arr2_si = 0;
arr2_ei = k;
if (arr1[arr1_si] > arr2[arr2_ei)
---------------------k is in arr2;
if (arr1[arr1_ei] < arr2[arr2_si])
---------------------k is in arr1;
Now run this same logic by dividing the array from k to k/2 to k/4 to k/8 .........(diving and arr#_si & arr#_ei will be chosen as index)....
Each stage if cross comparison occurs then get a flag for it,,,,,,,,
At each stage when we are diving the array do this boundary check only ..... by this we will getting closer to the value set who actually serves for making kth element in the merged array
public static int findKthValue(int[] a, int[] b, int k) {
int alen = a.length;
int blen = b.length;
int d = k;
if (k > alen + blen) return -1;
if (alen == 0) { return b[k-1]; }
if (blen == 0) { return a[k-1]; }
int i;
int j;
i = k > alen ? alen-1 : k-2;
j = k - i -2;
while (true) {
if (a[i] > b[j]) {
if (j == blen-1 || a[i] <= b[j+1]) return a[i];
if (j+d < blen && i-d > -2) { j += d; i -= d; }
} else {
if (i == alen-1 || b[j] <= a[i+1]) return b[j];
if (i+d < alen && j-d > -2) { i += d; j -= d; }
}
if (i == -1) return b[j];
if (j == -1) return a[i];
d = d/2;
if (d == 0) d = 1;
}
}
O(logK)
I dont think you need these 2 lines:
if (alen == 0) { i = -1; }
if (blen == 0) { i = k-1; }
someone please do some commenting or explain the algo...
not able to make out anything out of it
/**
*
*/
package com.amazon;
/**
* @author Gaurav Gupta
*
*/
public class KthElementofTwoSortedArrays {
public long[] mergeSortedArrays(long[] aSortedArray,long[] bSortedArray) throws Exception{
long[] finalMergeArray = new long[aSortedArray.length+bSortedArray.length];
try{
//copying the b array into the final array to make a single array for insertion sort
for (int i = 0; i < bSortedArray.length; i++) {
finalMergeArray[i] = bSortedArray[i];
}
//seeing if the length of the final array is still addition of two array's length
System.out.println(finalMergeArray.length);
//performing insertion sort
for (int i = 0; i < aSortedArray.length; i++) {
for (int j = 0; j < finalMergeArray.length; j++) {
if(aSortedArray[i]<finalMergeArray[j]){
for (int j2 = finalMergeArray.length-1; j2 >= j+1; j2--) {
finalMergeArray[j2]=finalMergeArray[j2-1];
}
finalMergeArray[j] = aSortedArray[i];
break;
}
}
}
return finalMergeArray;
}catch(Exception ex){
ex.printStackTrace();
throw ex;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
try{
long[] aSortedArray = {1,3,5,34,56,78,90,123};
long[] bSortedArray = {2,4,9,67,87,90,156,273};
long[] finalMergedArray = null;
//get the merged sorted array
KthElementofTwoSortedArrays obj = new KthElementofTwoSortedArrays();
finalMergedArray = obj.mergeSortedArrays(aSortedArray, bSortedArray);
System.out.println("final merged array is formed as : "+finalMergedArray);
long finalValue = finalMergedArray[(int) (new Long(args[0])-1)];
System.out.println("the value of the "+args[0]+"th array object is : "+finalValue);
}catch (Exception e) {
// TODO: handle exception
System.out.println("An Exception has occuered : "+e.getMessage());
}
}
}
Time complexity: Log(k)
int firstK(vector<int> &a, vector<int> &b, size_t k)
{
if (a.size() + b.size() < k){
return -1;
}
int aidx = k < a.size() - 1 ? k : a.size() - 1;
int bidx = k < b.size() - 1 ? k : b.size() - 1;
int ahead = 0, atail = aidx, bhead = 0, btail = bidx;
while (aidx+bidx+2 != (int)k){
if (aidx+bidx+2 > (int)k){
if (a[aidx] > b[bidx]){
atail = aidx;
aidx = (ahead + aidx)/2;
}
else{
btail = bidx;
bidx = (bhead + bidx)/2;
}
}
else{
if (a[aidx] > b[bidx]){
bhead = bidx;
bidx = (btail + bidx)/2;
}
else{
ahead = aidx;
aidx = (atail + aidx)/2;
}
}
}
return (b[bidx]>a[aidx] ? b[bidx] : a[aidx]);
}
If array A is of size m, B is of size n, just consider first k elements of A and first k elements of B. Now A is of size k and B is of size k. Find the median of the merged array of these two arrays using median finding algorithm.
Check my video in youtube with username ThrillAndJoyAlgos for median finding problem.
FindElementKth(A, B : array ; K : wanted position)
e = k/2
x = e
y = e
While e > 1
e = e / 2
if A[y] < B[x]
y = y + e
x = x - e
else
x = x + e
y = y - e
endWhile
if A[y] < B[x]
B[x] is the one !!!
else
A[y] is the one !!!
class Program
{
static void Main(string[] args)
{
Int32[] first = { 10,20, 80 };
Int32[] second = { 30, 40,50,60,70,90 };
Int32 Kth = 9;
Int32 iCounter = 1;
Int32 firstArrayIndex = 0;
Int32 secondArrayIndex = 0;
Int32 arrNum = 0;
if (Kth > first.Length + second.Length)
Console.WriteLine("Error");
else
{
while (iCounter <= Kth)
{
if (firstArrayIndex < first.Length && (secondArrayIndex >= second.Length || first[firstArrayIndex] < second[secondArrayIndex]))
{
firstArrayIndex++;
arrNum = 1;
}
else if (secondArrayIndex < second.Length)
{
secondArrayIndex++;
arrNum = 2;
}
if (iCounter == Kth)
{
if (arrNum == 1)
Console.WriteLine(first[firstArrayIndex - 1] + " from first Array");
else
Console.WriteLine(second[secondArrayIndex - 1] + " from second Array");
}
iCounter++;
}
}
Console.WriteLine("done..");
Console.ReadLine();
}
Compare A[k/2] and B[k/2].
- Kalyan May 24, 2012If A[k/2] < B[k/2], it means these A[1] to A[k/2] elements are part of first k elements.
Now, the kth element can be in A[k/2 + 1] to A[k] or B[1] to B[k/2].
Hence, we reduced the problem to half its original size.
Repeating the comparison of mid-elements of this subproblem, we reduce it to further half.
Hence at the end of logK iterations, the lesser value will be the kth element.
So, complexity is O( log K)