Amazon Interview Question for SDE-2s


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?

- tnutty2k8 August 31, 2017 | Flag Reply
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

- Sunny August 31, 2017 | Flag Reply
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.

- Chris August 31, 2017 | Flag Reply
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;
	}

}

- noob September 26, 2017 | Flag Reply
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)

- choops October 25, 2017 | Flag Reply
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);
}

- seb April 23, 2018 | Flag Reply


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