CareerCup

A bidirectional BFS, maintaining the a hash table of explored nodes for each and the hops to get to that node. Whenever the frontier node of either BFS touches a node that is in the explored set of explored nodes for the other, the total hops is the sum of from each BFS to the connecting node.

This problem is similar to some other dynamic programming problems, all of which are looking for the largest cumulative sum sub-array. In this case, we're not looking for the largest cumulative sum, but the most positive a[right_idx] - a[left_idx].


General solution:

The crux of the solution is to keep a left pointer, and run right pointers forward, cumulatively summing the elements as we go. If our cumulative sum is larger than any we've found so far, we replace that best result with the new one. We stop each of these cumulative runs when the cumulative sum drops to zero. When the cumulative sum drops to zero, we move the left pointer to the location of the right pointer and begin another forward run with the right pointer.

We stop the whole process when the right pointer reaches the end.

Specific solution:

In this case, we don't compute a cumulative sum, but the a[right_idx] - a[left_idx].

The complexity will be O(n) in compute, since for each new run, we move the left pointer to meet the right pointer. Memory use will be O(1) in memory since the only auxiliary data structures we need are pointers and the best difference.

def buy_low_sell_high(stock_trace):
    best_diff = 0
    best_left = -1
    best_right = -1
    
    left_idx = 0
    right_idx = 0
    while right_idx < len(stock_trace) - 1:
        right_idx = left_idx + 1
        
        # run, right pointer
        while right_idx < len(stock_trace) - 1:
            diff = stock_trace[right_idx] - stock_trace[left_idx]
            if diff > best_diff:
                best_diff = diff
                best_left = left_idx
                best_right = right_idx
            elif diff <= 0:
                # move left pointer to right pointers location
                left_idx = right_idx
                # start a new run
                break
        
            right_idx += 1
    
    print("best return: {}".format(best_diff))
    print("buy at  (val, idx): ({},{})".format(stock_trace[best_left], best_left))
    print("sell at (val, idx): ({},{})".format(stock_trace[best_right], best_right))

Some inputs

stock_trace1 = [
 0.010813118732461158,
 7.848782642974635,
 6.412165671008653,
 2.41400198901051,
 7.380876605993766,
 7.050665938613819,
 1.545930172530945,
 4.890855121484591,
 4.007390799132676,
 4.959796684292704,
 8.252891965307231,
 1.2789829911948636,
 3.0432514514857867,
 6.694507808651309,
 9.400862760505838,
 0.5439483796581279,
 5.538854666259302,
 0.15483879273656131,
 5.923645176042162,
 1.6929368892019125
]

stock_trace2 = [
 7.848782642974635,
 6.412165671008653,
 2.41400198901051,
 7.380876605993766,
 7.050665938613819,
 1.545930172530945,
 4.890855121484591,
 4.007390799132676,
 4.959796684292704,
 8.252891965307231,
 0.010813118732461158,
 1.2789829911948636,
 3.0432514514857867,
 6.694507808651309,
 9.400862760505838,
 0.5439483796581279,
 5.538854666259302,
 0.15483879273656131,
 5.923645176042162,
 1.6929368892019125
]

stock_trace3 = [
 7.848782642974635,
 6.412165671008653,
 2.41400198901051,
 7.380876605993766,
 7.050665938613819,
 1.545930172530945,
 4.890855121484591,
 4.007390799132676,
 4.959796684292704,
 8.252891965307231,
 1.2789829911948636,
 3.0432514514857867,
 6.694507808651309,
 9.400862760505838,
 0.5439483796581279,
 5.538854666259302,
 0.010813118732461158,
 0.15483879273656131,
 5.923645176042162,
 1.6929368892019125
]

The outputs

print("Stock Trace 1")
buy_low_sell_high(stock_trace1)
print("Stock Trace 2")
buy_low_sell_high(stock_trace2)
print("Stock Trace 3")
buy_low_sell_high(stock_trace3)

Stock Trace 1
best return: 9.390049641773377
buy at  (val, idx): (0.010813118732461158,0)
sell at (val, idx): (9.400862760505838,14)
Stock Trace 2
best return: 9.390049641773377
buy at  (val, idx): (0.010813118732461158,10)
sell at (val, idx): (9.400862760505838,14)
Stock Trace 3
best return: 8.121879769310974
buy at  (val, idx): (1.2789829911948636,10)
sell at (val, idx): (9.400862760505838,13)

We can do this in O(n) with O(1), constant, memory using the original array, by swapping elements.

We need two pointers, one starting at index zero (the right index), and one starting at n-1 (the right index).

We test each element at a[left_idx] to see if it's zero.

If it equal to zero, we swap it with the element at a[right_idx], or the element at the left size of the last zero we moved to the end. Since we put a zero at that index, we have to decrement right_idx.

If that element at the left_idx is not zero, we increment the right pointer.

We stop when the two pointers are at the same location.

def move_zeros_to_end(a):
    n = len(a)
    right_idx = n - 1
    left_idx = 0
        
    while left_idx < right_idx:
        if a[left_idx] == 0:
            a[left_idx], a[right_idx] = a[right_idx], a[left_idx]
            right_idx -= 1
        else:
            left_idx += 1
    
    return a