# 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).&#x20;

**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

```python
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**

```
4
ACQUIRE 364
ACQUIRE 84
RELEASE 84
RELEASE 364

out:0
```

```
4
ACQUIRE 364
ACQUIRE 84
RELEASE 84
RELEASE 364

out:0
```

```
4
ACQUIRE 364
ACQUIRE 84
RELEASE 364
RELEASE 84

out: 3
```

```
6
ACQUIRE 123
ACQUIRE 364
ACQUIRE 84
RELEASE 84
RELEASE 364
ACQUIRE 456

out: 7
```

```
8
ACQUIRE 123
ACQUIRE 364
ACQUIRE 84
RELEASE 84
RELEASE 364
ACQUIRE 789
RELEASE 456
RELEASE 123

out: 7
```

```
4
ACQUIRE 364
ACQUIRE 84
ACQUIRE 364
RELEASE 364

out: 3
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/trees-and-graphs/proper-locking.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.