Cover image
Brian T. Liao
Jun 20, 2019 • 1 min read

Notes on Software Engineering Interviews

Some useful links:

Search an Infinitely Sized List

The idea is we double our lower and upper bounds until the element is in the bounds. The element is not in the array of infinite numbers only if the number is less than the smallest number. If the element is larger, then we will keep doubling.

The complexity will be O(log(p)) where p is the last high number greater than the element. Doubling takes O(log(p)) and binary search takes O(log(p)).

def find_elm(arr, elm):
    low, high, cur = 0, 1, arr[0]
    while cur < elm:
        low = high
        high = 2 * high
        cur = arr[high]
    return binary_search(arr, low, high, elm)

def binary_search(arr, low, high, elm):
    if low < high:
        mid = low + (high - low) // 2
        if arr[mid] == elm:
            return mid
        if arr[mid] < elm:
            return binary_search(arr, low, mid - 1, elm)
        else: # arr[mid] >= elm
            return binary_search(arr, mid + 1, high, elm)
    return -1

I’ll see if I can write some stuff and have it help me practice!

Post by: Brian T. Liao