Facebook Interview Question for SDE1s


Country: United States




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

@xyz, he might be a Facebook employee? (maybe from HR...). Just a thought :)

Now, about the question:
- Create a class named Interval
- Since the lists are sorted, we can start the beginning of each list.
** If we find an intersection, we add the result vector the intersection and advance both lists
** If no intersection is found, we advance the iterator of the *lower* interval (i.e. the one with the lowest "start" point)
The worst case complexity is O(N+M) (where N and M is the number of elements in the arrays)

Here is the C++ implementation:

class Interval2
{
public:
    int start;
    int end;
    Interval2()
        : start(0)
        , end(0)
    {
    }
    Interval2(const std::pair<int, int>& p)
        : start(p.first)
        , end(p.second)
    {
    }

    bool intersects(const Interval2& other) const
    {
        return (other.start > start && other.start < end) || (other.end > start && other.end < end);
    }

    static Interval2 createIntersection(const Interval2& a, const Interval2& b)
    {
        Interval2 i;
        i.start = std::max(a.start, b.start);
        i.end = std::min(a.end, b.end);
        return i;
    }
    std::string toString() const { return "(" + std::to_string(start) + "," + std::to_string(end) + ")"; }
};

void mergeAndIntervals(const std::vector<std::pair<int, int> >& v1, const std::vector<std::pair<int, int> >& v2)
{
    // v1 and v2 are sorted
    std::vector<Interval2> andV;
    std::vector<std::pair<int, int> >::const_iterator iter1 = v1.begin();
    std::vector<std::pair<int, int> >::const_iterator iter2 = v2.begin();
    while((iter1 != v1.end()) && (iter2 != v2.end())) {
        const Interval2& interval1 = *iter1;
        const Interval2& interval2 = *iter2;
        if(interval1.intersects(interval2)) {
            andV.push_back(Interval2::createIntersection(interval1, interval2));
            ++iter1;
            ++iter2;
        } else {
            // Advance the lowest interval
            (interval1.start < interval2.start) ? ++iter1 : ++iter2;
        }
    }

    // Print the merged result
    std::for_each(
        andV.begin(), andV.end(), [&](const Interval2& interval) { std::cout << interval.toString() << std::endl; });
}

- PenChief October 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

vector<pair<int, int>> Intersection(vector<pair<int, int>> const &a, vector<pair<int, int>> const &b)
{
	vector<pair<int, int>> out;
	int i = 0;
	int j = 0;
	while (i < a.size() &&
			j < b.size())
	{
		int s1 = a[i].first;
		int e1 = a[i].second;
		int s2 = b[j].first;
		int e2 = b[j].second;
		if (s1 >= s2 &&
			s1 < e2)
		{
			out.push_back(pair<int, int>(s1, min(e1, e2)));
		} else if (s2 >= s1 &&
			s2 < e1)
		{
			out.push_back(pair<int, int>(s2, min(e1, e2)));
		}
		if (e1 < e2) {
			++i;
		} else {
			++j;
		}
	}
	return out;
}

- Alex October 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just checked the number of questions you have asked here, all of them from Facebook.
How is this possible. Are you posting fake questions in the name of Facebook interviews ?

- ano October 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Checked your past records of the questions you have asked. You have asked more than 30 questions all in the name of the same company "Facebook". Aren't all of these questions fake in the name of Facebook ?

- lks October 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@PenChief: cool, don't forget such inputs
A: {[0, 10], [11, 13]}
B: {[2, 12]}
desired output: {[2,12]}

- Chris October 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK I fixed my code with the following logic: instead of moving one element at a time, I "merge" two intervals if they are adjacent so the comparison is done on two intervals: {0,13} and {2,12}

Here is the updated code:

class Interval2
{
public:
    int start;
    int end;
    Interval2()
        : start(0)
        , end(0)
    {
    }
    Interval2(const std::pair<int, int>& p)
        : start(p.first)
        , end(p.second)
    {
    }

    /**
     * @brief return true if merge took place
     */
    bool mergeIfAdjacent(const Interval2& other)
    {
        if(isAdjacent(other)) {
            this->end = other.end;
            return true;
        }
        return false;
    }

    /**
     * @brief adjacent means that this interval ends exactly where the "other" interval starts
     */
    bool isAdjacent(const Interval2& other) const { return (this->end + 1) == other.start; }

    bool intersects(const Interval2& other) const
    {
        return (other.start > start && other.start < end) || (other.end > start && other.end < end);
    }

    static Interval2 createIntersection(const Interval2& a, const Interval2& b)
    {
        Interval2 i;
        i.start = std::max(a.start, b.start);
        i.end = std::min(a.end, b.end);
        return i;
    }
    std::string toString() const { return "(" + std::to_string(start) + "," + std::to_string(end) + ")"; }
};

void mergeAndIntervals(const std::vector<std::pair<int, int> >& v1, const std::vector<std::pair<int, int> >& v2)
{
    // v1 and v2 are sorted
    std::vector<Interval2> andV;
    std::vector<std::pair<int, int> >::const_iterator iter1 = v1.begin();
    std::vector<std::pair<int, int> >::const_iterator iter2 = v2.begin();
    while((iter1 != v1.end()) && (iter2 != v2.end())) {
        Interval2 interval1 = *iter1;
        while((iter1 + 1) != v1.end() && interval1.mergeIfAdjacent(*(iter1 + 1))) {
            ++iter1;
        }
        Interval2 interval2 = *iter2;
        while((iter2 + 1) != v2.end() && interval2.mergeIfAdjacent(*(iter2 + 1))) {
            ++iter2;
        }
        if(interval1.intersects(interval2)) {
            andV.push_back(Interval2::createIntersection(interval1, interval2));
        }
        // Advance the lowest interval
        (interval1.start < interval2.start) ? ++iter1 : ++iter2;
    }

    // Print the merged result
    std::cout << "Intersections:" << std::endl;
    std::for_each(
        andV.begin(), andV.end(), [&](const Interval2& interval) { std::cout << interval.toString() << std::endl; });
    std::cout << "Intersections___END:" << std::endl;
}

- PenChief October 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

two ways to solve it:
1. merge two arrays, time:O(m+n)
2. binary search every element in the other array, O(n*logm)
option depends the size of two arrays
below is the 2nd implementation

class Solution {
 
    public static void main(String[] args) {
      Interval[] a = {new Interval(1,2), new Interval(5,7)};
      Interval[] b = new Interval[]{new Interval(2,7)};
      List<Interval> res = Intersection(a,b);
      for(Interval i : res){
        System.out.println(i.start);
        System.out.println(i.end);
      }
    }
        
      
      
    public static List<Interval> Intersection(Interval[] i1, Interval[] i2) {
      if (i1 == null || i2 == null) return null;
      int index1 = 0;
      int index2 = 0;
      
      List<Interval> result = new ArrayList<>();
      for (Interval interval : i2) {
        Integer start = search(i1, interval.start, 0);
        Integer end = search(i1, interval.end, 1);
        if (start == null || end == null) {
          break;
        }
        result.add(new Interval(start, end));
      }
      return result;
    }
    
    public static Integer search(Interval[] i, int x, int type) {
      int low = 0;
      int high = i.length - 1;
      int mid;
      while (low <= high) {
        mid = (low + high) / 2;
        if (i[mid].start < x && i[mid].end > x) {
          return x;
        } else if (i[mid].start == x && type == 0) {
          return x;
        } else if (i[mid].end == x && type == 1) {
          return x;
        } else if (i[mid].start > x) {
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
        if (type == 1) {
          if (high < 0) { return null;}
          else return i[high].end;
        } else {
          if (low == i.length) return null;
          else return i[low].start;
        }
    }
  }

- zyfo2 October 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK. For the case of A: {[0, 10], [11, 13]} and B: {[2, 12]}, the intersection should look like {[2, 10], [11, 12]}, not {[2,12]}. Am I missing anything?

- Alex October 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex, that's a correct observation, your code is elegant and works correct ;-)

Depending on interval definition and whether it's closed or open and whether you want to merge those "connected" intervals, the case I mentioned is valid or not. It's more of a "think about it" and to encourage thinking of the other case, not mentioned, which is
A = {[0, 1], [3, 5]},
B = {[0, 10]},
where the result would be {[0,1], [3,5]}

- Chris October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex this is very neat code. One observation, when

s1== s2

it will save same interval twice. You can fix this by changing to

s2 > s1

in else if block

- pkr October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex this is very neat code. One observation, when

s1== s2

it will save same interval twice. You can fix this by changing to

s2 > s1

in else if block

- pkr October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK. Yes, there are definitely things to ask the interviewer. I just thought that
if {[0, 10], [11, 13]} + {[2, 12]} = {[2,12]}
then {[1,2], [5,7]} + {[2,6]} = {[2,6]}.
But in the description, there is {[1,2], [5,7]} + {[2,6]} = {[5,6]}.

- Alex October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@pkr. Thank you!
I'm not sure how the same interval can be saved twice. Can you please provide me with an input to produce this?
Along with s1 == s2, there is another condition: s2 < e1.

- Alex October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex: right, I read the post again, actually it seems they work with half open or open intervals, as the notation (a,b) suggests ... anyway, I used, wrongly, the notation for closed intervals and meant that ...

- Chris October 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<Interval> Intersactions(final List<Interval> intervalA, final List<Interval> intervalB) {
    int i = 0, j = 0;
    final List<Interval> intersaction = new ArrayList<>();
    while (i < intervalA.size() && j < intervalB.size()) {
      final int start = Math.max(intervalA.get(i).getStart(), intervalB.get(j).getStart());
      final int end = Math.min(intervalA.get(i).getEnd(), intervalB.get(j).getEnd());

      if (end > start) {
        intersaction.add(new Interval(start, end));
      }
      if (intervalA.get(i).getEnd() < intervalB.get(j).getEnd()) {
        i++;
      } else {
        j++;
      }
    }
    return intersaction;
  }

- Abereham October 15, 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