Marking the Event Timeline

TIP103 Unit 3 Session 1 (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. Since overwrites are allowed, placement is valid at any in-bounds position. 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 `place_event(t, event, start)` to place the `event` on `t` at the specified
   index and return the new state of `t`.
4. 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 valid in-bounds positions
      (i.e., any index where the event fits within the length of `timeline`).
   3. For each placement:
      1. Generate the new state of `t` after placing `event` at that position.
      2. If the resulting string matches `timeline`, return the list of indices.
      3. Otherwise, add the new state and updated index list to the queue.
   4. If no solution is found after `10 * timeline.length` turns, return an empty array.
5. 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
    visited = set()
    visited.add(tuple(['?'] * t_len))

    def place_event(t, 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):
            new_t = place_event(current_t, i)
            new_indices = indices + [i]

            state_key = tuple(new_t)
            if state_key in visited:
                continue
            visited.add(state_key)

            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]