Razer Interview Question: Similar to this: Given an arr... | Glassdoor

Interview Question

Software Engineer Interview San Francisco, CA

Similar to this: Given an array of integers eg

  [1, 2, -3, 1] find whether there is a sub-sequence that sums to 0 and return it (eg [1, 2, -3] or [2, -3, 1]). Return the start and end of sequence of each range. Can it be solved in less than order n^2 time?
Answer

Interview Answer

1 Answer

0

let data = [4, -3, 2, -2, 3, 4, -8, 6, 2, -3, -5, 2, 4, 3]
func crossingZero(a : [Int]) {
    var diff:[Int:Int] = [:]
    var prevSum = 0
    for (index, element) in a.enumerate() {
        let sum = prevSum + element
        if diff[sum] == nil {
            diff[sum] = index
        } else {
            print(diff[sum]! + 1, index)
        }
        prevSum = sum
    }
    diff
}

crossingZero(data)

Interview Candidate on Oct 26, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.