Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




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

Interval
 int low
 int high
 int getLow()
 int getHigh()

int getKthSmallestNumber(List<Interval> I, int k){
	int max = 0;

	for(Interval i: I)
		if (max< i.getHigh())
			max=i.getHigh();

	int []A=new int[max];
	for(Interval i : I){
		int x = i.getLow();
		int y = i.getHigh();
		for(;x<=y; x++)
			A[x]++;
	}
	for(int i=0; i<=max; i++){
		if(k<=A[i])
			return i;
		k=k-A[i];
	}
	return null
}

note: in above algo i assume all intervals are positives, If not then find the lowest no. add it to max after completing first for loop and in 2nd for loop add lowest no to both x & y, In 3rd loop return (i-lowest no)

- niraj.nijju April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

TC: O(n)
n: sum total of all ranges

- niraj.nijju April 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

max is no the correct size, what about the overlaps?

- Anonymous April 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

N can be huge for small i

- GS June 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For n intervals create n queues. Fill queue with the elements in between intervals. Find the minimum of all queue first elements and continue till we get ith.
Ex--5-10 and 8-12
q1 : 5,6,7,8,9,10
q2: 8,9,10,11,12
min element array = 5,6,7,8,8,9,9,10,10,11,12

- Nitin April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

finding the minimum from n queue === finding minimum of n numbers. O(n)
(this have to go for each element, so inefficient)

- niraj.nijju April 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Interval
{
public int low;
public int high;
public Interval(int low,int high)
{
this.low = low;
this.high = high;
}
void main() {
Interval [] intervals = new Interval[3];
intervals[0] = new Interval(4,9);
intervals[1] = new Interval(1,6);
intervals[2] = new Interval(5,7);
int max = 0;
//find the maximum number 'max' in all the given intervals
foreach(Interval interval in intervals)
{
if(interval.high > max)
max = interval.high;
}
//creat an array of max elements
int [] countArray = new int[max + 1];

//count how many times each element exists
foreach(Interval interval in intervals)
{
for(int i = interval.low; i <= interval.high; i++)
{
countArray[i] += 1;
}
}
//assume we have to find 7th smallest elt
int ithPos = 12;
int count = 0;
int elt = -1;
for(int i = 1; i < countArray.Length; i++)
{
count += countArray[i];
if(count >= ithPos)
{
elt = i;
break;
}
}
print(elt);

}
}

Any help to figure out the time and space complexity of this code would be much appreciated. Thank you.

- irfan basha sheik April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

expand each of the intervals and insert the elements into BST. To get ith smallest element perform MIN(BST) i times. time complexity = O(nlogn*range) space complexity = O(n*range)

- a April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

HI the best way is to save use the Median of Median Algorithm here. Well you can find the ith smallest number using MOM algo in O(n) time and O(n) space. The O(n) space because we need to save the intervals in some kind of array or list.

- Madhur Mehta April 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

suppose intervals are 5-10 and 8-12
step 1). input into L1,R1 and L2,R2. //here L1 =5, R1 =10, L2=8, R2=12

step 2). Check if L2 < R1, if yes got to step 3 

step 3). make an array[2][4]

step 4). fill the 1st row and 2nd row as in the figure:-

5(L1)		8(L2)		10(R1)		12(R2)
1		4(1+L2-L1)	9 (2*(R1-L2)-1)	11(array[1][3]+R2-R1)

here array[1][3] is filled as twice of difference of R1 and L2 minus 1 because nos. b/w L2 and R1 are present twice.		
			
step 5).
find_Ith_num(int i)
{
if (i <1 or i> array[1][4])
	return -1;
else if(i>=1 && i<= array[1][2])
	return (L1+(i-1))
else if(i>array[1][2] && i<= array[1][3])
	return (L2+ lowerLimit ( (i-array[1][2])/2) )
else if (i > array[1][3] && i <= array[1][4])
	return (R1+ (i-array[1][3]) );
		   
}

time complexity is O(1)
memory complexity is O(1), it is always array[2][4]

- meow April 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

It is not April first yet.

- Anonymous April 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If I'm understanding the problem correctly, we need to take all the values in the interval, put them in order, and maintain the duplicates. Then we get the Nth element.


Naive, destructive approach in a mix of pseudo Python and C++:

def get_nth_value(intervals, N):

    # Put all the elements into a multiset
    all_values = multiset()
    for interval in intervals:
        for element in interval:
            all_values.add(element)

    # Pop off the items from the front, in sorted order
    ret = None
    for i in xrange(0, N):
        ret = all_values.front()
        all_values.remove(0)

    return ret

- rotinom April 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my solution.
- Create an Interval class that contains just the limits, and some member functions for finding if a value is in range.
- Add each interval to a collection, and sort that collection by the start value
- Now walk through the collection first by column if possible (crossing intervals with the same value), then by row if possible (moving within an interval by one value)
- When you've walked the required distance, you have the value.

This is far easier on memory because you don't need to have every value in every interval stored individually. You just need the interval limits. Think about if you had two intervals of a million values each, my version would require only 4 values to describe that.

This is far easier computationally than listing all values. It would be O(n + m log m), where 'n' is the number of the steps to the index you want, and 'm' is the number of intervals (this is the time required to sort the intervals).

A further improvement would be to dynamically generate an equation that produced the value based on the bounds of the provided intervals. This seems completely possible, but too complicated for me to figure out.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;


public class OverlapInterval {
	public class Interval{
		int start;
		int end;
		public Interval(int start, int end)
		{
			this.start = start;
			this.end = end;			
		}
		public Integer Min()
		{
			return start;
		}
		
		public boolean ValueIsInRange(int value)
		{
			return (value >= start && value <= end);
		}
	}
	List<Interval> intervals;
	public void Add(int start, int end)
	{
		if (intervals == null)
			intervals = new ArrayList<Interval>();
			
		intervals.add(new Interval(start, end));
		Collections.sort(intervals, new IntervalListSort());
	}
	
	private class IntervalListSort implements Comparator<Interval>
	{
		@Override
		public int compare(Interval first, Interval second) {
			return first.Min().compareTo(second.Min());
		}
	}
	
	public int GetValueAtIndex(int index)
	{
		int indexOfInterval = 0;
		int minValidInterval = 0;
		int pathLength = 0;
		int targetIndex = index;	
		
		int curValue = intervals.get(0).Min();
		
		while (pathLength < targetIndex)
		{
			// Check if interval above has this value
			if ((indexOfInterval < (intervals.size() -1))
					&& intervals.get(indexOfInterval + 1).ValueIsInRange(curValue))
			{
				pathLength++;
				indexOfInterval++;
			}
			// Check if min valid interval has this value
			else if (intervals.get(minValidInterval).ValueIsInRange(curValue + 1))
			{
				pathLength++;
				curValue++;
				indexOfInterval = minValidInterval;
			}
			
			else
			{
				int i = 0;
				curValue++;
				// Check if any intervals above have this value, that's the new min interval
				for (i = (minValidInterval + 1); i < intervals.size(); i++)
				{
					if (intervals.get(i).ValueIsInRange(curValue))
					{
						minValidInterval = i;
						pathLength++;
						indexOfInterval = minValidInterval;
						break;
					}
				}
				
				// If we exited that loop without finding a new valid interval, there is a gap
				if (i == intervals.size())
				{
					// Increase interval by 1, find it's min value
					indexOfInterval++;
					curValue = intervals.get(indexOfInterval).Min();	
					minValidInterval = indexOfInterval;
					pathLength++;
				}
			}
		}
		
		return curValue;
	}
}

- static416 April 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int GetIthMin (List<Interval> list, int N)
{
int Min = int.MaxValue;
int Max = int.MinValue;
foreach(Interval interval in list)
{
if (Max < interval.High)
Max = interval.High;
if (Min > interval.Low)
Min = interval.Low;
}

int[] lookup = new int[Max - Min + 1];
foreach (Interval interval in list)
{
int x = interval.Low;
int y = interval.High;
for (; x <= y; x++)
lookup[x-Min]++;
}
int j = 0;
for (int i = 0; i < N; i++)
{
if (lookup[j] == 0)
j++;
lookup[j]--;
}

return j+Min;
}

- Anonymous April 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int GetIthMin (List<Interval> list, int N)
{
int Min = int.MaxValue;
int Max = int.MinValue;
foreach(Interval interval in list)
{
if (Max < interval.High)
Max = interval.High;
if (Min > interval.Low)
Min = interval.Low;
}

int[] lookup = new int[Max - Min + 1];
foreach (Interval interval in list)
{
int x = interval.Low;
int y = interval.High;
for (; x <= y; x++)
lookup[x-Min]++;
}
int j = 0;
for (int i = 0; i < N; i++)
{
if (lookup[j] == 0)
j++;
lookup[j]--;
}

return j+Min;
}

- Anonymous April 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Segment Tree?

- Anonymous April 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class MinHeap {
public static void main(String[] args) {
Queue<Integer> queue = new PriorityQueue<>();
Scanner scanner = new Scanner(System.in);
while (true) {
int i = scanner.nextInt();
int j = scanner.nextInt();
for (int j2 = i; j2 <= j; j2++) {
queue.add(j2);
}
System.out.println("to stop enter n");
String s = scanner.next();
if (s.equalsIgnoreCase("N")) {
break;
}
}
System.out.println("enter ith smallest element");
int ith = scanner.nextInt();
int i = 1;
while (!queue.isEmpty()) {
int ii = queue.remove();
if (ith == i) {
System.out.println("the smallest no is : " + ii);
break;
}
i++;
}
scanner.close();
}
}

- Anonymous April 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class MinHeap {
	public static void main(String[] args) {
		Queue<Integer> queue = new PriorityQueue<>();
		Scanner scanner = new Scanner(System.in);
		while (true) {
			int i = scanner.nextInt();
			int j = scanner.nextInt();
			for (int j2 = i; j2 <= j; j2++) {
				queue.add(j2);
			}
			System.out.println("to stop enter n");
			String s = scanner.next();
			if (s.equalsIgnoreCase("N")) {
				break;
			}
		}
		System.out.println("enter ith smallest element");
		int ith = scanner.nextInt();
		int i = 1;
		while (!queue.isEmpty()) {
			int ii = queue.remove();
			if (ith == i) {
				System.out.println("the smallest no is : " + ii);
				break;
			}
			i++;
		}
		scanner.close();
	}
}

- Srinivas April 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I did this way:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

class FinSmallNumberFromArray{
	static int[][] matrix		= {
					{5,6},
					{1,9},
					{2,6}
					};

	static Set<Integer> listSet	= new HashSet<Integer>();

	public static void getIth(int position){
		Object[] valuesArray = listSet.toArray();
		System.out.println("E:"+valuesArray[(position-1)]);
	}

	public static void main(String[] args){
		int numLines	= matrix.length;
		for(int i=0;i<numLines;i++){
			int startBucle	= matrix[i][0];
			int endBucle	= matrix[i][1];
			System.out.println("S:"+startBucle+",E:"+endBucle);
			for(int c=startBucle;c<=endBucle;c++){
				System.out.print(" "+c+" ");
				listSet.add(c);
			}
			System.out.println(" ");
		}
		/*
		Iterator iter	= listSet.iterator();
		while(iter.hasNext()){
			System.out.println(iter.next());
		}
		*/
		getIth(1);
	}
}

- oscar.valenzuela.b April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can't we do like this:
Assumption, there are i interval which contains total n numbers.

1. mark each of interval (5,10) as (5s,10e)
2. sort all of them : 5s,8s,10e,12e
3. iterate over sort element and find the k position.
while iterating if there are 2 starts then make the count double if 3 starts then make it thrice , and so on. similarly when end comes, keep removing those start count.


complexity will be i + i(lgi) = o(ilgi)

e.g: find 5th min element from following intervals (5,10), (8,12), (14,18)
sort them : 5s,8s,10e,12e,14s,18e,

5th element will be 8, // ( from 5s to just before 8s) = 3 and as there are 2 starts 5th element will be 8

12 th element will be 14 : // ( from 5s to just before 8s) = 3, (8s to just 10 e) = 6,
till (after 10e to 12e) = 2,

- om May 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a. Create a min-heap of intervals based on opening values. O(n)
b. Retrieve the min element from the set of intervals in O(1). It will be the first element from the min interval of the heap.
c. Check for heap property and sink the interval down if needed in O(log n) time.
d. Repeat steps b and c for i number of times. The element retrieved in ith iteration is the required ith smallest element.

Time complexity - O(i * log n) [i>>>n], space complexity - O(n)

- kishoreblack May 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

well most of the above implementation uses O(n) space where n is the max number eg if intervals are {1 10},{2,50},{3,1000},{7,10000} and I need the 10th smallest number. most algorithms consumes a lot of time and space.

I can think of linked list based approach using space O(i): ith element
and running time O(i*k) where k are number of intervals with their low <=ith current element(if present) so it removes the unnecessary intervals processing.

count is counter of number of elements in list
1)create a DLL of first interval for first i elements if #elements if less than i put all in DLL.
in our example we put 1 to10
2)for each of the next interval until Low of interval is <=i
get the location from where elements may repeat go to left side until u get low(j) and keep decrementing count
so I need to add elements from this position
in our example we came to node after 2 and count is 2
we insert one more 2 after 2 and skip 3 then insert 3 between 3 and 4 then skip all 4 then insert 4
increment count when ever we skip or insert and when count ==i reject everything in front and all other numbers

so in our case our list will be 1 2 2 3 3 4 4 5 5 6
repeat for next interval(3 , 1000)
move left in search of 3 found count is 5
insert 3 increment count skip 4 increment count insert 4 increment count....
stop when count ==i
we get 1 2 2 3 3 3 4 4 4 5
next interval starts at 7 so we are done
output 5

- gopsguru June 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int KthSmallestSortedIntervals(Interval[] intervals, int k)
        {
            int min = int.MaxValue;
            int max = int.MinValue;

            foreach (Interval interval in intervals)
            {
                min = Math.Min(min, interval.End);
                max = Math.Max(interval.End, max);
            }
            
            for (int i = min; i <= max; ++i)
            {
                foreach (Interval interval in intervals)
                {
                    if (i >= interval.Start && i <= interval.End)
                        if (--k == 0)
                            return i;
                }
            }
            return -1;

}

- Ram July 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

interval: low,high,getLow,getHigh

public class smallest_num {

	public static void main(String args[])
			{
		     List<interval> list = new ArrayList<interval>();
		     list.add(new interval(5,10));
		     list.add(new interval(8,12));
		     list.add(new interval(11,15));
		     int min,max,k=15;
		     min=list.get(0).getLow();
		     max=list.get(list.size()-1).getHigh();
		     int []arr=new int[max-min+1];
		     for(interval i:list)
		     {
		    	 int x=i.getLow();
		    	 int y=i.getHigh();
		    	 for(;x<=y;x++)
		    		 arr[x-min]++;
		    		 
		     }
		     for(int i=0,j=0;i<max-min+1;i++)
		     {
		    	 j=j+arr[i];
		    	 if(k<=j)
		    	 {
		    		 k=i+min;
		    		 break;
		    	 }
		    		 
		     }
		     System.out.println(k);
		     
		      
			}
	
}

- shikha September 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think this can be done in O(nlogn) worst case where n is just the number of intervals (not the sum of their ranges).

Suppose we have a single interval [a,b] and we want to find the k-th element (k=1,2,3,...) in this interval. There's no point in iterating over the entire range, the k-th element is just
element[k] = b - ((b-a+1)-k) = a + k - 1

What if we knew that all the elements in the interval [a,b] appear twice, what is the k-th element? In this case the k-th element can be calculated by
element[k] = b - (2*(b-a+1)-k)/2 = b - (b-a+1) - k/2 = a -1 + k/2

In general, if we know that each element in [a,b] appears m times then the k-th element is
element[k] = b - (m*(b-a+1)-k)/m = a - 1 + k/m

The observation above implies that by knowing the interval and the number of times each element appears inside the interval, we can find the k-th element in O(1) time.


Now, the end points of all the intervals induce a partition of the real line into intervals. For instance if we have 2 intervals [a,b] and [c,d] such that a<=c<=b<=d then the real line is partitioned into 5 intervals [-infinity,a], [a,c], [c,b], [b,d] and [d, infinity] . We can discard the infinity intervals as they contribute nothing. We also know for each interval how many times each element appears in it (using the intersections of the original input intervals):
[a,c] - each element appears once (c should appear twice but we'll count his other appearance in [c,b])
[c,b] - each element except c appears twice (c appears once because we already counted one of his appearances in [a,c])
[b,d] - each element appears once except b which does not appear at all (we counted b's 2 appearances in [c,b])

Knowing how many appearances of numbers there are in each interval allows us to count the total number of elements up until any point (a,b,c and d). We want to find the k-th element and suppose we counted elements_c<k elements until point c but then after adding the elements of the interval [c,b], the total number of elements is elements_b>=k. This means that the k-th element must lie within the interval [c,b] and we can use our initial observations to find it in O(1) worst case complexity.

So basically it comes down to the following steps:
1. Build an interval end points array (if the intervals are [a1,b1],[a2,b2],...,[an,bn] then the points array is {a1,a2,...,an,b1,b2,...,bn}). For each point maintain information whether it's an interval starting point (a1,a2,...,an) or an ending point (b1,...,bn).

2. Sort the points array using the following strategy according to their values. For equal values sort according to whether it's a starting or ending point - start points will appear before end points for equal values.

3. The points array from steps (1)-(2) represents a partition of the real line. Iterate over it while maintaining a counter that's incremented whenever we encounter a starting point and decremented whenever we encounter an ending point. This counter represents the number of intersecting original intervals for each interval in the points partition. This will allow us to use our previous observations to count the total number of elements up until each point throughout the iteration.

4. Once we reach a point in the points array for which the total number of elements exceeds k, then we know that the k-th element must lie within interval [point[i-1],point[i]]. We'll use our initial observations to extract it in O(1).


Code (Java):

Interval Class

public static class Interval {
		private int start;
		private int end;
			
		private void validateInput(int start, int end){
			if (start>end){
				throw new IllegalArgumentException("start cannot be greater than end");
			}			
		}
			
		public Interval(int start, int end){
			validateInput(start,end);
			this.start = start;
			this.end = end;
		}
			
		public int getStart(){return start;}
		public int getEnd(){return end;}
	}

IntervalPoint class (for the points array)

public class KthElementInIntervals {
	
	private static class IntervalPoint implements Comparable<IntervalPoint> {
		public enum Type implements Comparable<Type> {
			OPEN, CLOSE;
		}
		
		private int value;
		private Type type;
		
		public IntervalPoint(int value, Type type){
			this.value = value;
			this.type = type;
		}
		
		public int getVaule(){return value;}
		public Type getType(){return type;}
		
		@Override
		public int compareTo(IntervalPoint ip){
			int b1 = (this.getVaule()<ip.getVaule()) ? -1 : (this.getVaule()==ip.getVaule()) ? 0 : 1;
			int b2 = (this.getType()==ip.getType()) ? 0 : (this.getType()==Type.OPEN) ? -1 : 1;
			
			return (2*b1) + b2;
		}
		
		@Override
		public String toString(){
			return "(" + String.valueOf(this.getVaule()) + "," + this.getType() + ")";
		}
	}

A method for building the IntervalPoint[] array (the interval end points array which represents a partition)

private static IntervalPoint[] getIntervalPointArray(Set<Interval> intervals){
		if (intervals==null){
			return new IntervalPoint[0];
		}
			
		IntervalPoint[] res = new IntervalPoint[intervals.size()*2];
		int i=0;
		for (Interval interval : intervals){
			res[i++] = new IntervalPoint(interval.getStart(),IntervalPoint.Type.OPEN);
			res[i++] = new IntervalPoint(interval.getEnd(),IntervalPoint.Type.CLOSE);
		}
			
		return res;
	}

The main method for retrieving the k-th element from a set of intervals:

public static int getKthElement(Set<Interval> intervals, int k){
		if (k<1){
			throw new IllegalArgumentException("k must be positive");
		}
		IntervalPoint[] points = getIntervalPointArray(intervals);
		Arrays.sort(points);
		int overlap = 0;
		int elements=0;
		for (int i=0;i<points.length;i++){
			if (i>0){
				int d = (points[i].getVaule() - points[i-1].getVaule())*overlap + 
					   	((points[i-1].getType()==IntervalPoint.Type.OPEN) ? 1 : 0);
				elements += d;
				if (elements>=k){
					int p = elements-k;
					return points[i].getVaule() - (p/overlap);
				}
			}
			if (points[i].getType()==IntervalPoint.Type.OPEN){overlap++;}
			else {overlap--;}
		}
		
		throw new IllegalArgumentException("k is greater than the total number of elements");
	}

Note: In the method above when we calculate the number of elements in the current interval - d, we reduce 1 if the previous point was a starting point because we've already counted it in the previous iteration.

Complexity: Let n be the number of intervals (the size of the set of the intervals) then the worst-case run-time complexity is O(nlogn). Space complexity is O(n).

- IvgenyNovo April 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the final Note (before the complexity analysis) - we add 1 to d if the previous point was a starting point because we didn't account for it in the previous iteration. Sorry for the confusion.

- IvgenyNovo April 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about

[5,10], [8, 13], [7,15]

?

9 appears 3 times and is not an endpoint. Your algorithm seems to ignore that. (Of course, I probably misunderstood what you are doing).

- Anonymous April 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Anonymous, the algorithm doesn't ignore the three nines, the code above accounts for all of them.

To make the algorithm clearer, lets take your example: {[5,10],[8,13],[7,15]} and suppose we want to find the 10th element (which is 9 in this case):

1. First of all we build the end points array and sort it, it should look like this:
points = {(5,start),(7,start),(8,start),(10,end),(13,end),(15,end)}
2. We set the overlap count to 0 (overlap = 0) and the elements count to 0 as well (elements = 0).

3. Start iterating over the points array. In the first iteration the element is (5,start) and because it's just the first element the only thing we do is increment the overlap counter as the point (5,start) is an interval starting point, so overlap = 1.

4. In the next iteration, the point is (7,start). Because it's not the first iteration we want to count the number of elements the interval [5,7] contributes.How much does it contribute?
It contributes (point[1].value - point[0].value)*overlap + ((point[0].type == start) ? 1 : 0) = (7-5)*1 + 1 = 3 elements (elements = 3). Notice that we add 1 if point[0].type is start, this is because we increment the overlap counter only in the end of the iteration so in the previous iteration we did not count the additional point[0].value appearance which results from opening the previous interval (In fact, when we calculate how many elements each interval contributes we actually count the amount of elements without the first element because we accounted for it in the previous iteration except maybe 1 appearance in case the previous point was a starting point). This is also the reason why we count 7 only once even though it appears twice for our input intervals, we'll count its other appearance in the next iteration.
We check whether the total number of elements is greater/equal to k and its not because elements=3<10=k, that tells us that the 10th element is not in the interval [5,7].
Once again because the current point (7,start) is a starting point we increment the overlap counter by 1 (overlap = 2). By the end of the second iteration:
elements = 3, overlap = 2.
3. In the third iteration the point is (8,start). Once again we want to calculate how many elements the interval [point[1],point[2]] = [7,8] contributes and we also know that each element in this interval should appear twice because the overlap counter is 2 which means that 2 of the input intervals overlap on the interval [7,8]. How much does [7,8] contribute? The same calculation as before:
(point[i].value - point[i-1].value)*overlap + ((point[i-1].type == start) ? 1 : 0) = (8-7)*2 + 1 = 3 (elements +=3 => elements = 6). Again, notice that we add 1 because point[i-1].type == start - this accounts for the missing 7 from the previous iteration. Also notice that once again we count only 2 appearances of 8 while in fact there should be 3, we'll account for the other appearance of 8 in the next iteration (like we did for 7).
Once again we check whether the number of elements we encountered so far is greater/equal to k but its not: elements=6<10=k.
Because (8,start) is a starting point we increment the overlap counter again so in the end of this iteration:
elements = 6, overlap = 3

5. The next iteration point is (10,end). We calculate how many numbers it contributes:
(point[3].value - point[2].value)*overlap + (point[2].type == start) ? 1 : 0 = (10-8)*3 + 1 = 7 (elements += 7 => elements = 13). Once again we added the missing appearance of 8 from the previous iteration.
We check whether the total number of elements is greater/equal to k and this time it is: elements = 13>10 = k. This means that the 10th number is one of the numbers in the interval [point[2].value,point[3].value] = [8,10].

How do we find it? Because the overlap counter is equal to 3, it means that every element except the first in the interval [8,10] appears 3 times. The first element - 8, appears once because the previous iteration point is a starting point (8,start) so we counted this extra 8 only in the current iteration. The elements the current interval ([8,10]) contributes to our count are 8,9,9,9,10,10,10 (7 numbers in total). We saw 6 elements until the previous point so we want to extract the 10-6 = 4th element from the elements in the current interval. Extracting the 4th element from the beginning of the current interval is equivalent to extracting the 3rd element from the ending of this interval which is exactly the technique used in the following formula:
d = elements - k = 13 - 10 = 3
kth_element = points[3].value - (d/overlap) = 10 - (3/3) = 10 - 1 = 9.

So the value we return is 9 as expected.


Hopefully, it makes it a bit clearer. The key here is to understand that when we count elements in an interval [a,b], we account for a only by adding 1 if it's a start point in one of the original intervals, we do not count it multiple times because we already did so in the previous iteration.

- IvgenyNovo April 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is brilliant! +10

- Anonymous April 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Constructive criticism:

I think this is the wrong approach for an interview (and maybe even for "real" software development). Why? It fails the "cocktail napkin test". In other words, I should be able to explain, or sketch out a solution simply enough to fit on a cocktail napkin.

Unless it is a nontrivial problem (which this is a trivial problem), then you should be able to explain it simply, elegantly, and fit it into no more than ~20 lines of code.

Interviewers are not typically looking for the "best possible solution". Neither is production work. The mark of good code, is that it simple enough for the person to come behind you in 6 months, and understand within a few minutes, what the heck you did.

Frankly, I didn't even read that wall of text, because I went right to the code. Then I started reading your code, and gave up. It's just too much.

- rotinom April 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

rotinom, I respectfully disagree.

First of all, the algorithm and the code are pretty trivial. The heart of the algorithm, the method getKthElement(), is just 24 lines of code, the rest is pretty trivial (Interval and IntervalPoint classes, building an interval end points array) and is simply done to provide fully working code. It isn't particularly hard to explain either, especially when you can communicate verbally and have the ability to draw on a board - options which I don't have when posting an answer on this site.

Second of all, the goal in these type of interview questions, especially in big companies like Amazon or Google, isn't to provide a fully working trivial napkin solution. It is to see how a candidate tackles a problem, what's his thinking process, does he recognize the challenge the problem offers and finally - can he formulate his ideas into a working efficient solution.
For the question above, it's pretty obvious that the interviewer wasn't shooting for any solution that depends on the ranges of the intervals - that's pretty much a brute-force approach which may pass the "cocktail napkin test" but probably won't impress the interviewer all that much. The line of thinking here should be - how do I solve this using only the intervals themselves, not their elements? Do I really need to iterate over each interval element? Can I know how many times each element appears using the intervals alone? That was my approach to solving this problem and it didn't take a lot of time to come up with the solution above.


I can accept the criticism for my lack of ability to provide a clear explanation but I don't think my approach to solving this problem was wrong.

- IvgenyNovo April 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@rotinom: I agree with what you are trying to say: giving highly complex solutions to problems which have simple and "reasonable" solutions can have a negative effect on your job prospects. Disagree that it applies here.

This is actually a SIMPLE solution (coming up with it is a different matter).

The presentation/explanation might be better, but the solution can be easily explained using a whiteboard/some figures in no more than 10-15 minutes. As to the code, you can cut through the extra fluff (irrelevant in an interview) and code up only the relevant details and can do so in another 10-15 minutes. So depending on how long it takes you to think, you could do this in under 35 minutes.

One suggestion for you. Throw your cocktail napkin away. Don't let it prevent you from coming up with solutions which will move you from a "MAYBE HIRE" to "STRONG HIRE". Don't change your problem solving style just because you are in an interview setting. The interviewer is always looking for how you tackle/think about the problem, recognize potential problems with obvious solutions, how you communicate your ideas etc.

And, this is not a trivial problem. Don't conflate the complexity of a problem with the complexity of a trivial solution (brute force). A brute force algorithm is almost never a good idea in either an interview or in production.

Ivgeny realized the problem of brute force and tackled it and came up with a solution which does not rely on brute force. In fact, O(n log n) is optimal. This is a positive trait: try to do better than the first solution that comes to mind.

What you say applies to very complicated solutions, requiring long amounts of explanation and thought to even come up with. The solution in question is simple enough for an interview. In fact I would go so far as to say that the interviewer would be aware of this solution, and expect this solution, but only from the very best candidates (perhaps 2-3 candidates in a 1000)

Moreover, if the solution is getting too complex, the interviewer will direct you away from it. And if the interviewer can understand where you were going, that won't be a negative.

Anyway, this turned out to be too long. Thanks for reading through.

- Le snob. April 05, 2014 | Flag
Comment hidden because of low score. Click to expand.


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