Facebook coding interview [closed]

Question

I have joined the Facebook interview recently. And the following question has been asked on the coding interview.

Given a sequence of numbers and a total target, return whether there exists a continuous sub-sequence that sums up to target.
[1, 3, 1, 4, 23], 8 : True (because 3 + 1 + 4 = 8)
[1, 3, 1, 4, 23], 7 : False

I have written the exact pseudo-code to solve the solution. Which describes the inside of the method. The approach is the sliding window.

The start and end index starts from 0 and through the array it continues to increment the end index and keep adding the existing value array[end] to the temp value if the temp is smaller than the target sum. If every time checks if temp reached the target value, it is it returns true, else if it is bigger form the temp it starts to increment the start index and shrink the window form the beginning. And decreasing the exact value from the temp. And keep checking if it is equal to the target value after it is decreased.

After the interview result came, they told me that "I have solved it wrong because the sequence must be contiguous". I am %100 sure that this is the correct answer, and they saying is I was wrong and I should try 12 months later.

Please put your comment about my solution? What would be the problem to cause misunderstanding?

// [1, 3, 1, 4, 23]

int start  = 0
int end  = 0

int total = 0;
int target = 8;

while(end < arr.length){

  total += arr[end]; // 1 3 1 4 = 9

  while(total>=target){

     total-=arr[start]; // 8

     start++;

     if(total == target){
       return true;
     }

  }
  end++;
}

return false;

Answer 1

I am %100 sure that this is the correct answer,

I'm not so sure... I dumped your code into an online compiler*. I made very minor adjustments, moving target to a parameter and adding semicolons which aren't a big deal since you probably didn't have a compiler when writing it. I did not modify your code beyond that and treated it like a black-box.

import java.util.Arrays;

class Main {
  static boolean test(int[] arr, int target) {

    int start = 0;
    int end = 0;

    int total = 0;

    while (end < arr.length) {

      total += arr[end]; // 1 3 1 4 = 9

      while (total >= target) {

        total -= arr[start]; // 8

        start++;

        if (total == target) {
          return true;
        }

      }
      end++;
    }

    return false;
  }

  static class Input {
    int[] sequence;
    int target;

    Input(int[] sequence, int target) {
      this.sequence = sequence;
      this.target = target;
    }
  }

  public static void main(String[] args) {
    Input[] inputs = new Input[] { 
      new Input(new int[]{1, 3, 1, 4, 23}, 8),
      new Input(new int[]{1, 3, 1, 4, 23}, 7),
      new Input(new int[] {}, 0), 
      new Input(new int[] {}, 1),
      new Input(new int[] { 0 }, 0), 
      new Input(new int[] { 0 }, 1),  
      new Input(new int[] { 1 }, 1), 
      new Input(new int[] { -1 }, -1), 
      new Input(new int[] { Integer.MAX_VALUE }, Integer.MAX_VALUE),
      new Input(new int[] { 1, Integer.MAX_VALUE }, Integer.MAX_VALUE),
      new Input(new int[] { Integer.MIN_VALUE }, Integer.MIN_VALUE),
      new Input(new int[] { 1, 1, 1 }, 2),
      new Input(new int[] { 1, 1 }, 2),
      new Input(new int[] { 1, 0, 1 }, 2),
    };

    for (Input input : inputs) {
      System.out.print(String.format("%s, %d => ", Arrays.toString(input.sequence), input.target));
      try {

      System.out.println(
          test(input.sequence, input.target));
      } catch (Exception e) {
        System.out.println("Caught exception: " + e.getMessage() );
      }
    }
  }
}

That produced this output:

OpenJDK Runtime Environment (build 10.0.2+13-Ubuntu-1ubuntu0.18.04.4)
[1, 3, 1, 4, 23], 8 => true
[1, 3, 1, 4, 23], 7 => false
[], 0 => false
[], 1 => false
[0], 0 => true
[0], 1 => false
[1], 1 => false
[-1], -1 => Caught exception: Index 1 out of bounds for length 1
[2147483647], 2147483647 => false
[1, 2147483647], 2147483647 => false
[-2147483648], -2147483648 => Caught exception: Index 1 out of bounds for length 1
[1, 1, 1], 2 => false
[1, 1], 2 => false
[1, 0, 1], 2 => false

• Your code was initially not wrapped into a method. Try to make it look like production quality code. That's ostensibly what the interview is looking at and writing all day.
• Since it wasn't in a method, it implies you didn't consider writing tests.
• Writing tests made it trivial to reveal cases that threw exceptions.
• You didn't specify what should happen with an empty list which implies you didn't ask about that.
• ^^^ same with overflows. "Inputs that may cause overflows will cause undefined behavior" is a perfectly acceptable precondition in an interview IF you acknowledge that you have recognized this possibility, have a notion of how to handle it, and the interviewer allows it.
• It's also possible to yield incorrect answers with fairly trivial inputs, e.g. [1, 1]

*I do not recommend this online IDE, it felt very buggy. If someone has a better alternative I would be grateful.

Answer 2

I don't know Java, but I still found your challenge interesting! So I translated your code to Python and tried to beat it:

def your_search(seq, target):
    start, end, total  = 0,0,0

    while (end < len(seq)):
        total += seq[end]
        while (total>=target):
            total-=seq[start]
            start+=1
            if (total == target):
                return True
        end+=1
    return False

Here is my attempted improvement:

def segment_search(seq,target,i=0, s=0, total=0):
    try:
        while total<target:
            total += seq[i]
            i+=1
    except:
        return False

    if total == target:
        return True, s, i
    else:
        return segment_search(seq,target,i,s+1, total-seq[s])

And here is the performance test:

seq = [1, 2, 6, 7, 3, 4, 6, 8, 2, 3, 6, 2, 6, 8, 4, 1, 5, 7, 3, 4, 1, 2, 1, 4, 6, 8, 9, 5, 4, 7, 1, 2, 4, 5, 2, 6, 7, 3, 8, 4, 2, 5]*10
def wrapper(func,seq):
    for target in range(sum(seq)):
        func(seq,target)

In [55]: %timeit wrapper(your_search,seq)
10 loops, best of 3: 54.8 ms per loop

In [56]: %timeit wrapper(segment_search,seq)
10 loops, best of 3: 26.9 ms per loop

It's around double as fast in Python and arguably more elegant! I hope my proposed idea helps for Java as well!

EDIT: I didn't read your text, just the code. There is nothing wrong with your code. It's actually quite brilliant! Sometimes the testers should be tested instead.. But to make sure, I will check it again. If you don't hear from me it means I haven't found a mistake. By the way, this forum is meant for code performance suggestions..

edit2:

I found your mistake!The argument "continuous" was misleading! Instead you failed by never checking if moving to the right finds the correct total. Your if statement was hidden in a loop. See comments:

// [1, 3, 1, 4, 23]

int start  = 0
int end  = 0

int total = 0;
int target = 8;

while(end < arr.length){

  total += arr[end]; 

  while(total>=target){ //remove the "="

     total-=arr[start]; 

     start++;

     if(total == target){   // put this outside of the loop
       return true;
     }

  }
  end++;
}

return false;

Answer 3

int start  = 0
int end  = 0

int total = 0;
int target = 8;

while(end < arr.length){

  total += arr[end]; // 1 3 1 4 = 9


/* Adding this part is enough as well */
     if(total == target){
       return true;
     }
/* Adding this part is enough as well */

  while(total>=target){

     total-=arr[start]; // 8

     start++;

     if(total == target){
       return true;
     }

  }
  end++;
}

return false;