## Amazon Interview Question for SDE-2s

• 0
of 0 votes

Country: United States
Interview Type: In-Person

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

I feel like theres O(n) solution to this, but currently I'm only able to come up with two solutions:

``````- O(n^2): for each item in A, loop in B finding smaller elements
- O(nlogn):
- Sort array B: O(nlogn)
- for each item in A O(n)
- use modified binary search to find first index less than or equal to current item O(logn)
- the number of items lower than or equal to is the index value.``````

Anyone have a more efficient algo in mind?

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

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

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

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.

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

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

}``````

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

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

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

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

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