Facebook Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




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

Can you pls explain a bit further. I dont think I understood whats the question here

- Saurabh January 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have added an example in the question

- rahul January 22, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Saurabh January 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 January 22, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 January 22, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- rahul January 22, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous January 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Its a classical problem of Interval Tree with the tweak of merging the intervals in case of overlap

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

- Lareb January 27, 2019 | 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