Facebook编码采访

Question

我最近参加了脸谱网的采访。下面的问题是在编码面试中提出的。

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

我写了精确的伪码来解决这个问题。它描述了方法的内部。方法是滑动窗口。

起始和结束索引从0开始，并通过数组继续增加结束索引，如果临时值小于目标和，则继续将现有值数组结束添加到临时值。如果每次检查temp是否达到目标值，则返回true；否则，如果temp较大，则会开始增加启动索引，并从开始时收缩窗口。并降低了温度的精确值。并在目标值减少后继续检查它是否等于目标值。

面试结果出来后，他们告诉我，“我解决错了，因为序列必须是连续的”。我确信这是正确的答案，他们说我错了，12个月后我应该试一试。

请你对我的解决方案发表意见？造成误解的问题是什么？

// [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

我确信这是正确的答案，

我不太确定..。我把你的代码转储到了一个在线编译器中*。我做了非常小的调整，将目标移动到一个参数，并添加分号，这并不是什么大问题，因为在编写它时您可能没有编译器。除此之外，我并没有修改您的代码，而是把它当作一个黑匣子。

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

产生了这一产出：

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

• 您的代码最初没有包装到方法中。试着让它看起来像生产质量代码。表面上，这就是面试整天在看和写的东西。
• 因为它不是在方法中，它意味着您没有考虑编写测试。
• 编写测试使得揭示抛出异常的案例变得微不足道。
• 您没有指定空列表应该发生什么，这意味着您没有问到这个问题。
• ^^与溢出相同。在面试中，如果你承认自己已经认识到了这种可能性，对如何处理它有一个概念，并且面试官允许的话，“可能导致溢出的输入会导致不确定的行为”是一个完全可以接受的先决条件。
• 也有可能用非常琐碎的输入产生错误的答案，例如1，1

*我不推荐这个在线IDE，它感觉很糟糕。如果有人有更好的选择，我将不胜感激。

Answer 2

我不懂Java，但我仍然觉得你的挑战很有趣！因此，我将您的代码翻译成Python，并试图击败它：

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

以下是我尝试的改进：

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])

下面是性能测试：

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

它在Python中的速度大约是它的两倍，而且可以说更优雅！我希望我提出的想法对Java也有帮助！

编辑:我没有读你的文字，只是代码。你的代码没有什么问题。它真的很棒！有时测试人员应该进行测试。但是为了确保，我会再检查一次。如果你没收到我的消息，那就意味着我没有发现一个错误。顺便说一句，这个论坛是为代码性能建议而设的。

edit2：

我发现了你的错误！“毗连”的论点是误导人的！相反，您失败了，因为您从不检查向右移动是否找到正确的总数。您的if语句隐藏在循环中。见评论：

// [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){ //removed the "="

     total-=arr[start]; 

     start++;

  }

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

  end++;
}

return false;