price.cpp

#include <cassert>
#include <vector>

// Given some price information at discrete time intervals, returns a suitable
// value for the price at a given time interval. You may assume that times is
// sorted in ascending order, and that there are at least two datapoints (i.e.
// prices for at least two times).
auto stock_price(int time, std::vector<int> const &times,
                 std::vector<float> const &prices) -> float {
    return 0;
}

auto main() -> int {
    // Some sample time and price data. You might want to call stock_price for
    // different time arguments to test your function.
    auto const times = std::vector<int>{1, 3, 6, 11, 17, 20};
    auto const prices =
        std::vector<float>{100.00, 106.00, 109.00, 104.00, 107.00, 113.00};
}

price.py

from typing import List


def stock_price(time: int, times: List[int], prices: List[float]) -> float:
    """
    Given some price information at discrete time intervals, returns a suitable
    value for the price at a given time interval. You may assume that times is
    sorted in ascending order, and that there are at least two datapoints (i.e.
    prices for at least two times).
    """
    return 0


if __name__ == "__main__":
    # Some sample time and price data. You might want to call stock_price for
    # different time arguments to test your function.
    times  = [     1,      3,      6,     11,     17,     20]
    prices = [100.00, 106.00, 109.00, 104.00, 107.00, 113.00]

Sample solutions:

from typing import List
import bisect


def interpolate(x: int, x1: int, x2: int, y1: float, y2: float) -> float:
    return y1 + (x - x1) * (y2 - y1) / (x2 - x1)


def stock_price(t: int, times: List[int], prices: List[float]) -> float:
    if t < times[0]:
        i = 0
    elif t > times[-1]:
        i = len(times) - 2
    else:
        i = bisect.bisect_left(times, t) - 1

    if t == times[i]:
        return prices[i]

    return interpolate(t, times[i], times[i + 1], prices[i], prices[i + 1])


if __name__ == "__main__":
    times  = [     1,      3,      6,     11,     17,     20]
    prices = [100.00, 106.00, 109.00, 104.00, 107.00, 113.00]

    for time, price in zip(times, prices):
        assert stock_price(time, times, prices) == price

    assert stock_price(2, times, prices) == 103.00
    assert stock_price(4, times, prices) == 107.00
    assert stock_price(5, times, prices) == 108.00

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

auto interpolate(int x, int x1, int x2, float y1, float y2) -> float {
    return y1 + (x - x1) * (y2 - y1) / (x2 - x1);
}

auto stock_price(int t, std::vector<int> const &times,
                 std::vector<float> const &prices) -> float {
    int i;
    if (t < times.front()) {
        i = 0;
    } else if (t > times.back()) {
        i = times.size() - 2;
    } else {
        auto earliest_after_t = std::lower_bound(times.begin(), times.end(), t);
        i = std::distance(times.begin(), earliest_after_t) - 1;
    }

    if (t == times[i]) {
        return prices[i];
    }

    return interpolate(t, times[i], times[i + 1], prices[i], prices[i + 1]);
}

auto main() -> int {
    auto const times = std::vector<int>{1, 3, 6, 11, 17, 20};
    auto const prices =
        std::vector<float>{100.00, 106.00, 109.00, 104.00, 107.00, 113.00};

    for (auto i = 0; i < times.size(); ++i) {
        assert(stock_price(times[i], times, prices) == prices[i]);
    }

    assert(stock_price(2, times, prices) == 103.00);
    assert(stock_price(4, times, prices) == 107.00);
    assert(stock_price(5, times, prices) == 108.00);
}

Worst-case time complexity is $O(\log{n})$, dominated by the cost of binary searching times for the first time after t. Space complexity is constant.

Sample solution using the interp function from NumPy:

from typing import List
import numpy as np


def stock_price(t: int, times: List[int], prices: List[float]) -> float:
    """
    Given some price information at discrete time intervals, return a suitable
    value for the price at a given time interval. You may assume that times is
    sorted in ascending order, and that there are at least two datapoints (i.e.
    a price at at least two times).
    """
    return np.interp(t, times, prices)


if __name__ == "__main__":
    times  = [     1,      3,      6,     11,     17,     20]
    prices = [100.00, 106.00, 109.00, 104.00, 107.00, 113.00]

    for time, price in zip(times, prices):
        assert stock_price(time, times, prices) == price

    assert stock_price(2, times, prices) == 103.00
    assert stock_price(4, times, prices) == 107.00
    assert stock_price(5, times, prices) == 108.00

One note about this solution compared to the last one is that np.interp will simply return the first/last price for times before/after the range of given information. For example, at t = 21 the price returned will be 113.00 instead of 115.00.

Other nice financial-themed problems:

• Number of orders in the backlog
• Stock Price Fluctuation