Interview Questions

 

In this post we will review 2 interview questions. These were served to a colleage of mine on a job interview. His answers are the second solutions to each question. Looks quite smart to me, but he did not pass the test. I could not find the reason. Maybe you can?

Question 1: Buildings Heights

An array contains integer numbers specifying the max allowed height of a building in each location (index). 

We need to find a combination of buildings heights so that it follows the heights restrictions, and no two buildings have the same height.

Solution Alternative 1: Sorting

The first possible solution is to sort the array, and keep a set of used heights.

def find_building_heights(max_heights):
    sorted_heights = sorted(max_heights)
    building_heights = [0] * len(max_heights)
    used_heights = set()

    for i in range(len(sorted_heights)):
        height = sorted_heights[i]

        while height in used_heights:
            height -= 1

        if height <= 0:
            return None

        building_heights[i] = height
        used_heights.add(height)

    return building_heights


max_heights = [5, 3, 4, 6, 1, 10, 10, 10]
result = find_building_heights(max_heights)
if result:
    print("The building heights are:", result)
else:
    print("It's not possible to assign unique building heights.")

Solution Alternative 2: No Sorting

We can do this without sorting, and just keep a set of the used heights.

def find_building_heights(max_heights):
    building_heights = [0] * len(max_heights)
    used_heights = set()

    for i in range(len(max_heights)):
        height = max_heights[i]

        while height in used_heights and height > 0:
            height -= 1

        if height <= 0:
            return None

        building_heights[i] = height
        used_heights.add(height)

    return building_heights


max_heights = [5, 3, 4, 6, 1, 77, 77, 77]
result = find_building_heights(max_heights)
if result:
    print("The building heights are:", result)
else:
    print("It's not possible to assign unique building heights.")

Question 2: Post Office

We have queue of packages numbered 1 to n. 

Whenever a person arrives, and asks for his package, we move all the packages from the queue to a shelf until we get to his package. 

If the package is already on the shelf, just give it  to him. 

Given a list of the requested packages numbers, find the max items on the shelf.

Solution 1: Simulation

This solution is the naive one, just simulate the whole process.

def max_items_on_shelf(n, requests):
    queue = list(range(1, n + 1))
    shelf = set()
    max_shelf_size = 0

    for request in requests:
        if request in shelf:
            shelf.remove(request)
        else:
            while queue and queue[0] != request:
                shelf.add(queue.pop(0))

            if queue and queue[0] == request:
                queue.pop(0)

        max_shelf_size = max(max_shelf_size, len(shelf))

    return max_shelf_size


n = 7
requests = [4, 3, 8, 2, 1, 5]
print(max_items_on_shelf(n, requests))

Solution 2: Shortcut

This solution uses the understanding that the number of packages on the shelf is the number of items that should be removed minus the number of items that were already removed.

def max_items_on_shelf(requests):
    max_difference = 0

    for index, package in enumerate(requests):
        difference = package - (index + 1)
        max_difference = max(max_difference, difference)

    return max_difference


requests = [4, 3, 2, 10, 1, 5]
print(max_items_on_shelf(requests))