0
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ The current question title is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. \$\endgroup\$ – Toby Speight Jan 16 at 8:02
  • \$\begingroup\$ Welcome to the code review site where we review working code to provide suggestions on how the code may be improved. Pseudo-code is considered off-topic because it is not working code. \$\endgroup\$ – pacmaninbw Jan 16 at 15:42
7
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Yea, I found his mistake. Check my edit! \$\endgroup\$ – KaPy3141 Jan 15 at 19:10
  • \$\begingroup\$ It also throws OOB accesses \$\endgroup\$ – butt Jan 15 at 19:12
  • 1
    \$\begingroup\$ Rextester is one I've used for a while. \$\endgroup\$ – Linny Jan 15 at 19:25
  • \$\begingroup\$ I have declared on the statement that it was pseudocode, It wasn't running on against test cases. Actually it would be better for me to test against test cases to clarify the solution. \$\endgroup\$ – Neslihan Bozer Jan 15 at 19:42
  • \$\begingroup\$ @butt The code challenge wasn't running on against test cases. It would be easier for me sharing my screen and running it in IDE. Because it is an algorithm challenge I think it was enough as the format. It is written on a notepad similar link. You can compare it with every detail of writing in an IDE. But coding challanges doesn't go on IDE. It is alwys writtten on similar to text pad or shared text editor.Of course, it is easier to write on an IDE. \$\endgroup\$ – Neslihan Bozer Jan 15 at 19:52
2
\$\begingroup\$

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;
| improve this answer | |
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.