Facebook | Phone screen | Mth smallest & Left most index of 1
Anonymous User
1363
MetaPhone ScreeningInterview

Question 1:
Given k sorted arrays of possibly different sizes, find m-th smallest value in the merged array.

Example 1:

Input: [[1, 3], [2, 4, 6], [0, 9, 10, 11]], m = 5
Output: 4
Explanation: The merged array would be [0, 1, 2, 3, 4, 6, 9, 10, 11].  
The 5-th smallest element in this merged array is 4.

Example 2:

Input: [[1, 3, 20], [2, 4, 6]], m = 2
Output: 2

Example 3:

Input: [[1, 3, 20], [2, 4, 6]], m = 6
Output: 20
My solution 
def m_smallest(lists, M: int) -> int:
    if not lists:
        return -1

    min_heap = []

    for i, l in enumerate(lists):
        if l:
            heapq.heappush(min_heap, (l[0], i, 1))

    candidate = -1
    while min_heap and M > 0:
        min_val, i, j = heapq.heappop(min_heap)

        if j < len(lists[i]):
            heapq.heappush(min_heap, (lists[i][j], i, j + 1))

        candidate, M = min_val, M - 1

    return candidate


def _test(lists, M, expected):
    actual = m_smallest(lists, M)

    assert actual == expected, 'Wrong answer, expected: {}, actual: {}'.format(expected, actual)
    print('Accepted')


if __name__ == '__main__':
    lists, M = [[1, 3], [2, 4, 6], [0, 9, 10, 11]], 5
    _test(lists, M, 4)

    lists, M = [[1, 3, 20], [2, 4, 6]], 2
    _test(lists, M, 2)

    lists, M = [[1, 3, 20], [2, 4, 6]], 6
    _test(lists, M, 20)

Question 2:
Leftmost column index of 1

My solution 
def leftmost_index(grid) -> int:
    if not grid or not grid[0]:
        return -1

    i, j = 0, len(grid[0]) - 1
    result = -1

    while i < len(grid) and j >= 0:
        if j == 0:
            break

        if grid[i][j]:
            result = j
            j -= 1
        else:
            i += 1

    return result


def _test(grid, expected):
    actual = leftmost_index(grid)

    assert actual == expected, 'Wrong answer'
    print('Accepted')


if __name__ == '__main__':
    grid = [[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1], [0, 0, 0, 0]]
    _test(grid, 1)

    grid = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
    _test(grid, -1)
	
	grid = [[]]
    _test(grid, -1)
Comments (2)