Marking the Event Timeline - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 1 Advanced (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the input to the problem?
  • A: The inputs are two strings: event, which needs to be placed on the timeline, and timeline, which represents the target state we want to achieve.
• Q: What is the output?
  • A: The output is an array of indices representing the positions where the event was placed on the timeline to transform it into the timeline string. If it's not possible, return an empty array.
• Q: What are the constraints?
  • A: The event must be fully contained within the boundaries of the timeline when placed. The transformation must be achieved within 10 * timeline.length turns.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a breadth-first search (BFS) approach to explore all possible ways of placing the event on the timeline. Track the placements and determine if the timeline can be fully transformed into the target string within the allowed number of turns.

1. Initialize the string `t` as a list of `?` characters with the same length as the `timeline`.
2. Create a queue to manage the states of `t` and the sequence of indices where `event` has been placed.
3. Define a function `can_place(t, event, start)` to check if `event` can be placed on `t` starting at index `start`.
4. Define a function `place_event(t, event, start)` to place the `event` on `t` at the specified index and return the new state of `t`.
5. Perform a BFS:
   1. Initialize the BFS with the initial state of `t` and an empty list of indices.
   2. For each state, attempt to place `event` at all possible positions.
   3. If the resulting string matches `timeline`, return the list of indices.
   4. If no solution is found after `10 * timeline.length` turns, return an empty array.
6. Return the result.

⚠️ Common Mistakes

• Not correctly checking if the event can be placed at a given position.
• Forgetting to track the number of turns and exceeding the allowed limit.
• Failing to explore all possible placements of the event during the BFS.

I-mplement

from collections import deque

def mark_event_timeline(event, timeline):
    t_len = len(timeline)
    event_len = len(event)
    queue = deque([(['?'] * t_len, [])])
    max_turns = 10 * t_len
    
    def can_place(t, event, start):
        for i in range(event_len):
            if t[start + i] != '?' and t[start + i] != event[i]:
                return False
        return True

    def place_event(t, event, start):
        new_t = t[:]
        for i in range(event_len):
            new_t[start + i] = event[i]
        return new_t
    
    turns = 0
    while queue and turns < max_turns:
        current_t, indices = queue.popleft()
        for i in range(t_len - event_len + 1):
            if can_place(current_t, event, i):
                new_t = place_event(current_t, event, i)
                new_indices = indices + [i]
                if ''.join(new_t) == timeline:
                    return new_indices
                queue.append((new_t, new_indices))
        turns += 1
    
    return []

# Example usage
print(mark_event_timeline("abc", "ababc"))     # Output: [0, 2]
print(mark_event_timeline("abca", "aabcaca"))  # Output: [3, 0, 1]