search

Proper Locking

Write a program that given a list of N (0 <= N <= 1,000,000) lock acquire and release events (counting from 1). checks if there were any problems (acquire-release order violation, dangling acquired lock acquiring a lock twice or releasing a free lock), and if so, tells the earliest time that could be detected. Note that there's no limit on how many nested locks may be acquired at any given moment. More formally, you are given an array of strings where each string is either "ACQUIRE t or 'RELEASE X". where all Xs are integers in the range [1...1000000]

Return:

  • 0, if there were no lock-related problems even after program termination

  • N+1, if the only issue after program termination were dangling acquired locks

  • K, in case event number K violated any of the principles (release a lock not acquired previously, acquire an d lock OR violate lock acquire-release ordering).

The Idea: Using a stack as our primarly datastructure serves as a natural fit. That is, we can only release if we've previously acquired the same id. We can always acquire unless we've already acquired the same id. Finally, a proper sequencing emplies that our stack is empty in the end.

Complexity: O(n) time and space

def get_event_info(event, i):
    words = event.split()
    return [i, words[0], int(words[1])]


def check_log_history(events):
    stack = []
    acquired = set()
    for i, event in enumerate(events):
        i, type, id = get_event_info(event, i)
        if type == "ACQUIRE" and acquired.__contains__(id):
            return i+1
        elif type == "ACQUIRE":
            stack.append({"time": i, "action": type, "id": id})
            acquired.add(id)
        elif type == "RELEASE":
            if not stack or stack[-1]["id"] != id or stack[-1]["action"] != "ACQUIRE":
                return i + 1
            else:
                stack.pop()
                acquired.remove(id)
    if stack:
        return len(events) + 1
    else:
        return 0

Testing

PreviousLeaf NodesNextNumber of Cities at each Distance

Last updated