Facebook Interview Question for Software Engineers


Country: United States




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

@Jerm, good point.
====
how this isn't as simple as sorting the array and then returning the (percent * array length)th element in the array? Maybe I'm not understanding the problem correctly.
=====
because, the problem is about getting it done from a stream.
======
Give you an unsorted integer ***iterator***
=====
What is one thing that is certain about iterator? They can be iterated upon. What is not certain about an iterator? That, they will end.

Surprised? Not so. For example, if we create an iterator, that returns you next prime number, where do you think the iterator ends? Well, nowhere.

primes = seq ( 2 ) ->{
   prime_cache = $.prev 
   last = prime_cache[-1] + 1 
   //  en.wikipedia.org/wiki/Bertrand%27s_postulate 
   end = last * 2 
   last + index( [ last : end ] ) :: {  !exists ( prime_cache ) :: {  $.item /? $.$.item  }  }
}

That is an iterator, so... how you are going to find the % stuff right at any iteration? You would be out of memory very soon.

In fact, here is an trivial god knows what it would do iterator :

god_knows = seq( random(100) ) -> { random(100 ) }

This generates in infinite stream of random numbers between [0,100). Now?
:-)

- NoOne June 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Isn't this the same as selecting the k^{th} element of an unsorted list, which can be done in $O(n)$ time using the linear select algorithm

- Hicham June 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What you are looking for : [ cs.stackexchange.com/questions/57542/find-pth-percentile-of-a-stream-of-numbers ]
However, there is a neat other way. If the numbers are within a range ( well, all integers supported by machine naively will be ), then you can have a sorted dictionary with integers as key, and count of the integers as value.

That will compress the data, and any time, you want to calculate a certain %, it can be easily doable ( there is a formula ).

- NoOne June 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone explain how this isn't as simple as sorting the array and then returning the (percent * array length)th element in the array? Maybe I'm not understanding the problem correctly.

- Jerm June 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

assume n is the length of the sequence, potentially infinite, p is the percentile given

This question is quite interesting as NoOne pointed out it's not just selecting kth element due to:
- n is not known until the iterator finally terminates
- there is no random access to the elemnts
- the number of elements may not fit into memory
- k is not known, if n is not known, because k is given as percentile

Options:
1) convert to array and find k-th element: does not deserve further comments. But it's O(n) space and O(n) runtime with quickselect.

2) slect the kth element (with array, binary tree, etc.) takes O(n*p) space and O(n*p*lg(n*p)) time, since p < 1 O(n) and O(n*lg(n)) so, still not better with space if n is getting close to infinite

3) probabilistic approach 1:
model a PMF (probability mass function) that represents the data seen so far. If the values in the stream have a small range, I'd count the occurence of every value. Alternatively I'd create intervals which creates a histogram. I can calculate the "estimated" p*n th element, by going to the right interval. I can be more exact by interpolating the value using linear, spline, etc. interpolation within the interval of interest. Interpolation only works, if the PMF is nearly continous.

The size of the intervals will define the memory consumption and error.

If I know the data distribution in advance, e.g. that it's normal, poisson, ... I could even get along with only the mean and standard deviation, both of wich can be computed online
in O(1)

- ChrisK June 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Before we go to code, few things to note:
1) We dont know the size hence a naive approach would be to store all elements in BST and then return the element at proper position
2) Or we can still use a BST but remove the elements from the tree which we know are before the position desired for eg: if the position is 50% then our tree will never be more than size of n/2 Or n * .5 since every time we add two elements we know the position will shift by one hence we can get rid of older elements at that point since we dont care about them.
In other words p(n, d) <= p(N+1, d) .. your index of desired position will only increase as size increases.
The below solution returns the desired number by using BST in O(log(N)) in best case and O(N) in worst case with memory of O(n*percent/100)

public class Solution {
  public int findNumber(Interator<Integer> itr, double percent) {
    if(percent <= 0) {
      throw new IllegalArgumentException("percent has to be positive");
    }
    int size = 0;
    Node root;
    while(itr.hasNext()) {
      if(root == null) {
        root = new Node();
        root.value = itr.next();
      }
      else {
        root.add(itr.next());
      }
      size++;
      if(size * percent >= 1 && root != null) {
        root = root.removeMin();
        size--;
      }
    }
    return root != null ? root.removeMin().value : Integer.MIN_VALUE;
  }

  private static class Node {
    public int value;
    public Node leftChild;
    public Node rightChild;

    public void add(int v) {
      if(this.value >= v) {
        if(this.leftChild == null) {
          Node n = new Node();
          n.value = v;
          this.leftChild = n;
        }
        else this.leftChild.add(v);
      }
      else {
        if(this.rightChild == null) {
          Node n = new Node();
          n.value = v;
          this.rightChild = n;
        }
        else this.rightChild.add(v);
      }
    }

    public Node void removeMin() {
      if(this.leftChild == null) {
        return this.rightChild;
      }
      else {
        Node n = this;
        while(n.leftChild != null && n.leftChild.leftChild != null) {
          n = n.leftChild;
        }
        n.leftChild = n.leftChild.rightChild;
        return this;
      }
    }
  }
}

- nk June 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There was a slight bug in my code above so fixing it:

public class Solution {
  public int findNumber(Interator<Integer> itr, double percent) {
    if(percent <= 0) {
      throw new IllegalArgumentException("percent has to be positive");
    }
    int size = 0;
    Node root;
    while(itr.hasNext()) {
      if(root == null) {
        root = new Node();
        root.value = itr.next();
      }
      else {
        root.add(itr.next());
      }
      size++;
      if(size * percent >= 1 && root != null) {
        root = root.removeMin();
        size--;
      }
    }
    return root != null ? root.getMin().value : Integer.MIN_VALUE;
  }

  private static class Node {
    public int value;
    public Node leftChild;
    public Node rightChild;

    public Node getMin() {
      Node n = this;
      while(n.leftChild != null) {
        n = n.leftChild;
      }
      return n;
    }

    public void add(int v) {
      if(this.value >= v) {
        if(this.leftChild == null) {
          Node n = new Node();
          n.value = v;
          this.leftChild = n;
        }
        else this.leftChild.add(v);
      }
      else {
        if(this.rightChild == null) {
          Node n = new Node();
          n.value = v;
          this.rightChild = n;
        }
        else this.rightChild.add(v);
      }
    }

    public Node void removeMin() {
      if(this.leftChild == null) {
        return this.rightChild;
      }
      else {
        Node n = this;
        while(n.leftChild != null && n.leftChild.leftChild != null) {
          n = n.leftChild;
        }
        n.leftChild = n.leftChild.rightChild;
        return this;
      }
    }
  }
}

- nk June 22, 2017 | 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