Leetcode 528 — Facebook Interview Question

import random
class Solution:

    def __init__(self, w: List[int]):
        self.sums = []
        curr_sum = 0
        for item in w:
            curr_sum += item
            self.sums.append(curr_sum)

    def pickIndex(self) -> int:
        target = random.randint(1, self.sums[-1])
        lo = 0
        hi = len(self.sums) - 1
        res = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            val = self.sums[mid]
            if val == target:
                return mid
            elif val < target:
                lo = mid + 1
            else:
                res = mid
                hi = mid - 1
        return res