Facebook Interview Question Software Engineer Interns
Country: United States
Interview Type: Phone Interview
It is classical case for Interval Tree with a tweak of merging intervals in case of overlap.
Algo:
1. Create a node with interval. Maintain min & max
2. Insert the node in tree based on min of the node
3. Check if the intervals overlap with the parent
a. If yes - Merge the Interval with the interval of the parent
b. If No - Keep it as it is.
4. After each insertion increase the count and verify if root interval is equal to [0-1]
class Interval {
int low, high;
}
class Node {
Interval i;
int max, min;
Node left, right, parent;
}
Node root = null;
Node newNode(Interval i) {
Node temp = new Node();
temp.i = i;
return temp;
}
Node insert(Node root, Interval i) {
if (root == null) return newNode(i);
if (Interval.min <= root.min) root.left = insert(root.left, Interval i);
else root.right = insert(root.right, Interval i);
if (root.left != null) root.left.parent = root;
if (root.right != null) root.right.parent = root;
Node parent = root;
if (!(interval.max < i.min || interval.max < i.min)) {
while (parent != null) {
Interval interval = parent.interval;
if (i.min <= interval.min) {
if (i.max >= interval.min) {
parent.interval.min = i.min;
parent.interval.max = Math.max(i.max, interval.max));
}
} else {
if (i.min <= interval.max) {
parent.interval.min = interval.min;
parent.interval.max = Math.max(i.max, interval.max));
}
}
i = parent.interval;
parent = parent.parent;
}
}
return root;
}
public int CalculateDropCount() {
int count = 0;
while (true) {
Drop drop = new Drop();
if (root != null) {
if (root.interval.min == 0 && root.interval.max == 1) return count;
}
insert(root, new Interval(drop.loc - drop.radius, drop.loc + drop.radius));
count++;
}
return 0;
}
here's my hacky attempt. I used something "like" an interval tree, but not really...
class drop
{
public float x;
public float r;
static Random rnd = new Random( );
public drop( )
{
x = (float) rnd.NextDouble( ) * 10 - 5.0f;
r = (float) rnd.NextDouble( ) * 0.2f;
}
}
class Range
{
public float min;
public float max;
public Range( KeyValuePair<float,float> kvp )
{
min = kvp.Key;
max = kvp.Value;
}
public Range( float _min, float _max )
{
min = _min;
max = _max;
}
public bool AttemptUnion( Range r )
{
if ( r.max < min || r.min > max ) return false;
// note this is very different than the intersection
min = Math.Min( min, r.min );
max = Math.Max( max, r.max );
return true;
}
public bool DoesIntersect( Range range )
{
if ( range.max < min || range.min > max )
return false;
return true;
}
public bool IsEncompassedByInputRange( Range r )
{
return ( r.min <= min && r.max >= max );
}
}
static SortedList<float, float > RangeList = new SortedList<float, float>( );
static void InsertRange( Range r )
{
int nMergedIncomingAt = -1;
for( int i = 0 ; i < RangeList.Count ; i++ )
{
Range ri = new Range( RangeList.ElementAt(i) );
if ( r.IsEncompassedByInputRange( ri ) )
{
return;
}
bool bUnioned = ri.AttemptUnion( r );
if ( bUnioned )
{
RangeList.RemoveAt( i );
RangeList.Add( ri.min, ri.max );
nMergedIncomingAt = i;
break;
}
}
if( nMergedIncomingAt == -1 )
{
RangeList.Add( r.min, r.max );
return;
}
// if we merged the incoming, we have to see if we can merge anything else
//
for ( int i = nMergedIncomingAt ; i < RangeList.Count - 1 ; i++ )
{
Range ri = new Range( RangeList.ElementAt(i) );
Range rn = new Range( RangeList.ElementAt(i+1));
bool bUnioned = ri.AttemptUnion( rn );
if ( bUnioned )
{
// since the list is sorted, we'll never adjust the lower edge,
// but will instead always increase the upper edge. Therefore,
// we never need to change i.
RangeList.RemoveAt( i ); // decreased count, so next one should be i
RangeList.RemoveAt( i );
RangeList.Add( ri.min, ri.max );
// just keep going
}
else
{
// couldn't union it, time to stop looking
break;
}
}
}
static void Main( string [] args )
{
int numCalls = 0;
Range DesiredRange = new Range( 0.0f, 1.0f );
while ( true )
{
numCalls++;
drop d = new drop( );
Range dropRange = new Range( d.x - d.r, d.x + d.r );
bool bIntersected = DesiredRange.DoesIntersect( dropRange );
if ( !bIntersected ) continue;
InsertRange( dropRange );
// the range is continuous from 0-1 only if there is ONE value in the RangeList AND
// it encompasses the range
if( RangeList.Count == 1 && DesiredRange.IsEncompassedByInputRange( new Range( RangeList.ElementAt( 0 ) ) ) )
{
break;
}
}
Console.WriteLine( "Took " + numCalls + " calls to drop( ) to get the range" );
}
Based on the updates to the question and assuming Drop() function randomly generates location and radius float values, here is one possible implementation
Logic:
=====
We keep track of lower and higher range that Drop function ever generated values for using 2 variables when lower reaches 0 and higher reaches 0.99, we exit the method.
For example
First drop method generated location = 0.20 and radius = 0.17
Lower = location - radius (0.20 - 0.17) = 0.03
Higher = location . + radius (0.20 + 0.17) = 0.37
Since lower is not yet reached 0 and higher not yet covered till 0.99, we make another call to the function.
Say 2nd call drop method generated location = 0.15 and radius = 0.30
Lower = location - radius (0.15 - 0.30) = - 0.15
Higher = location . + radius (0.15 + 0.30) = 0.45
We calculate the final lower value to be minimum between existing lower and lower from the last call to Drop() method. Same goes for the higher as well.
When both lower and higher reaches the expected values, we quit the program and report the number of calls.
Program:
=======
public class IntervalCoverage {
public static void main(String args[]) {
System.out.println("Number of calls made: " + numCalls());
}
private static int numCalls(){
Drop firstDrop = Drop();
int numOfCalls = 1;
float lower = firstDrop.location - firstDrop.radius;
float higher = firstDrop.location + firstDrop.radius;
System.out.println("first lower: " + lower + " higher: " + higher);
Drop current = null;
while(true) {
current = Drop();
System.out.println("Received location: " + current.location + " radius: " + current.radius);
numOfCalls++;
float currentHigher = current.location + current.radius;
System.out.println("Calculated lower: " + (current.location - current.radius)
+ " higher: " + (current.location + current.radius));
if(currentHigher < 1) {
lower = Math.min(lower, current.location - current.radius);
higher = Math.max(higher, currentHigher);
} else {
System.out.println("Ignoring this drop as Higher is above 0.9");
}
System.out.println("lower: " + lower + " higher: " + higher);
if((lower <= 0 && higher > 0.99) || numOfCalls > 1000)
break;
}
return numOfCalls;
}
private static Drop Drop(){
//Generate random values of location and radius
Random r = new Random();
return new Drop(r.nextFloat(), r.nextFloat());
}
}
class Drop {
float location;
float radius;
Drop(float location, float radius){
this.location = location;
this.radius = radius;
}
}
Output:
=======
first lower: -0.8709638 higher: 0.9397204
Received location: 0.822552 radius: 0.55689883
Calculated lower: 0.2656532 higher: 1.3794508
Ignoring this drop as Higher is above 0.9
lower: -0.8709638 higher: 0.9397204
Received location: 0.17664707 radius: 0.13852155
first lower: -0.8709638 higher: 0.9397204
Received location: 0.822552 radius: 0.55689883
Calculated lower: 0.2656532 higher: 1.3794508
Ignoring this drop as Higher is above 0.9
lower: -0.8709638 higher: 0.9397204
Received location: 0.17664707 radius: 0.13852155
Calculated lower: 0.038125515 higher: 0.31516862
lower: -0.8709638 higher: 0.9397204
.......
Calculated lower: 0.9019634 higher: 0.9935021
lower: -0.8709638 higher: 0.9935021
Number of calls made: 33
I think there are some cases missing - I guess you are assuming that the ranges of the current call always overlap with the previous ones - what if the first range and the second range do not overlap and both fall within 0 and 1.
For ex. first call gives range 0.1, 0.3 and second call gives range 0.4, 0.5. The points [0.3, 0.4) are not covered. Does your algorithm handle this?
@rahul, you got a valid point. My code does not handle the use case when the ranges do not overlap.
The immediate solution that comes to mind is to use additional space like a bit/boolean array where the bits are flipped to 1 if they fall in the range. Once all the bits between [0,1) are flipped, the program ends.
I will update the code to cover your use case.
@saurabh, but then again , there are infinite points on a real line, how do you check whether a point is covered using a bit - like the interval can be really really small something like - [0.111, 0.112) that is not covered. I guess one approach seeing your solution is to keep track of points not covered instead of points that are covered.
Its a classical problem of Interval Tree with the tweak of merging the intervals in case of overlap
- Lareb January 27, 2019class Interval { int low, high; } class Node { Interval i; int max, min; Node left, right, parent; } Node root = null; Node newNode(Interval i) { Node temp = new Node(); temp.i = i; return temp; } Node insert(Node root, Interval i) { if (root == null) return newNode(i); if (Interval.min <= root.min) root.left = insert(root.left, Interval i); else root.right = insert(root.right, Interval i); if (root.left != null) root.left.parent = root; if (root.right != null) root.right.parent = root; Node parent = root; if (!(interval.max < i.min || interval.max < i.min)) { while (parent != null) { Interval interval = parent.interval; if (i.min <= interval.min) { if (i.max >= interval.min) { parent.interval.min = i.min; parent.interval.max = Math.max(i.max, interval.max)); } } else { if (i.min <= interval.max) { parent.interval.min = interval.min; parent.interval.max = Math.max(i.max, interval.max)); } } i = parent.interval; parent = parent.parent; } } return root; } public int CalculateDropCount() { int count = 0; while (true) { Drop drop = new Drop(); if (root != null) { if (root.interval.min == 0 && root.interval.max == 1) return count; } insert(root, new Interval(drop.loc - drop.radius, drop.loc + drop.radius)); count++; } return 0; }