Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
a) Sort array B
b) For each element in A, search for the last occurrence of that element in B. The index will give you the number of elements in B less than or equal to the element in A - this could be done in O( log n ) - binary search.
The whole complexity should be : a) O(nlogn) for sorting B b) O(nlogn) for finding less than or equal to elements in B
I would differentiate the sizes of the array, if |A| and |B| are about the same size we can sort both and perform a merge like operation:
int j = 0;
for(int i = 0; i < a.size(); i++) {
while(j < b.size() && b[j] <= a[i]) j++;
result[i] = j;
}
If we can do radix sort, we end up with a linear algorithm.
If B forms an unsorted sequence of consecutive elements such that B[i]-1 is contained in B except when B[i] = min(B), we can create a histogram in O(|B|) and query that in O(1) for a total space complexity of O(|B| + |A|)
I don't think there is a truly linear approach to this problem because finding one rank in an unsorted array is O(n). Here we kind of need to find m ranks, so sorting seems the best to optimize querying the rank multiple times, if no special constraints are given.
How ever the emphasis of "unsorted" in the question is interesting.
import java.util.Arrays;
public class ElementsLessThanOrEqual
{
public static void main(String[] args)
{
int[] a = {0, 1, 7};
int[] b = {1};
ElementsLessThanOrEqual e = new ElementsLessThanOrEqual();
e.find(a, b);
}
public int[] find(int[] a, int[] b)
{
Arrays.sort(b);
int[] c = new int[a.length];
for(int i=0;i<a.length;i++)
{
c[i] = findHelper(a[i], b);
System.out.println(Arrays.toString(c));
}
return c;
}
public int findHelper(int a, int[] b)
{
int lo = 0;
int hi = b.length-1;
while(lo <= hi)
{
int mid = lo + (hi-lo)/2;
if(b[mid]<=a)
{
int p = mid;
while(p<b.length && b[p]<=a)
p++;
return p;
}
else
{
hi = mid-1;
}
}
return -1;
}
}
Here's my python solution, which is nlogn and follows this process:
1) First sort B (nlogn)
For each element in A (O(n)) :
2) Perform binary search (logn) on B looking for the rightmost element that is less than or equal to the element of interest in a .
a= [1,2,3,4,7,9]
b= [0,1,2,1,1,4]
import bisect
def le(a,b):
b=sorted(b)
print b
count = []
for n in a:
i = bisect.bisect_right(b,n)
if i:
count.append(i)
return count
le(a,b)
C++:
-First sort Element of the second array
-Then make an upperbound binary search in this last
void printVec( const std::vector<std::uint32_t>& vec)
{
for( uint32_t val : vec ){
std::cout << val << ",";
}
std::cout << std::endl;
}
void printCountElLessOrEqualThan( std::vector<uint32_t>& a, std::vector<uint32_t>& b )
{
std::sort( std::begin(b), std::end(b));
std::vector<uint32_t> outputVec;
for( uint32_t val : a ){
auto iter = std::upper_bound(std::begin(b), std::end(b), val);
outputVec.push_back(std::distance(std::begin(b), iter));
}
printVec(outputVec);
}
I feel like theres O(n) solution to this, but currently I'm only able to come up with two solutions:
Anyone have a more efficient algo in mind?
- tnutty2k8 August 31, 2017