Facebook Initial code challenge

facebook.go

// Problem: Given a sequence of nonnegative integers A and an integer T, return whether there is a *continuous sequence* of A that sums up to exactly T

// Example:
// [23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20
// [1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8
// [1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7
 
// Note: We are looking for an O(N) solution. There is an obvious O(N^2) solution which is a good starting point but is not the final solution we are looking for. It’s important for the code to be as efficient as possible


package main

import (
  "fmt"
  "unsafe"
)

func on2(data []int, sum, iter int) bool {
  var current int
  
  for i := 0; i < iter; i++ {
    current = data[i];
    
    for j := i+1; j <= iter; j++ {
      if current == sum {
        return true
      }
      
      if current > sum || j == iter {
        break
      }
      
      current = current + data[j]
    }
  }
  
  return false
}

var (
  sequences = map[int][]int{
    20: []int{23, 5, 4, 7, 2, 11},
    8: []int{1, 3, 5, 23, 2},
    7: []int{1, 3, 5, 23, 2},
  }
)

func oNSeq(data []int, sum, iter int) bool {
  current := data[0]
  start := 0
  
  for i := 1; i <= iter; i++ {
    
    for current > sum && start < (i-1) {
      current = current - data[start]
      start = start + 1
    }
    
    fmt.Println(current, sum)
    if current == sum {
      return true
    }
    
    if i < iter {
      current = current + data[i]
    }
  }
  
  return false
}

func main() {

  for sum, ints := range sequences {
    
    subs := unsafe.Sizeof(ints)/unsafe.Sizeof(ints[0])
    if oNSeq(ints, sum, int(subs)) {
      fmt.Printf(
        "Sum %d was %s in %+v\n",
        sum,
        "found",
        ints,
      )
    } else {
      fmt.Printf(
        "Sum %d was %s in %+v\n",
        sum,
        "not found",
        ints,
      ) 
    }
  }
}