We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Alt and Tab Simulation

Number: 3538

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an initial order of n windows represented by an array (where the first element is at the top) and a list of queries where each query brings the corresponding window to the top, simulate the alt+tab behavior and return the final state of the window order.

Key Insights

  • Every query “brings a window to the top” by removing it from its current position and reinserting it at the beginning.
  • If a window is queried more than once, only its most recent move matters since it ends up higher than its previous positions.
  • The windows that never appear in queries remain in their initial order and are placed below the windows that were queried.
  • Instead of simulating each move explicitly—which could be expensive—we can track the last query index (timestamp) for each window and then reconstruct the final ordering.

Space and Time Complexity

Time Complexity: O(n + m + k log k) where n = number of windows, m = number of queries, and k = number of unique queries (k ≤ n).
Space Complexity: O(n) for the dictionary and the resulting arrays.

Solution

We can optimize the simulation by avoiding expensive removals in the list. The idea is to record the last occurrence (timestamp) of each window in the queries. For every window that appears in the queries, its final position is entirely determined by the time it was last queried—the later the query, the closer to the top. All windows that were never moved remain in their original order and are placed below the moved windows.
The steps are:

  1. Iterate over queries and store the index (timestamp) for each window’s most recent query.
  2. For windows that have been queried, collect their (timestamp, window) pairs and sort them in descending order.
  3. Build the final ordering as the sorted queried windows (in the order determined by their last query) followed by the windows that were never queried (preserving their initial order).

Code Solutions

# Function to simulate Alt+Tab behavior
def alt_tab_simulation(windows, queries):
    # Dictionary to store the most recent index (timestamp) of each queried window
    last_query = {}
    for index, window in enumerate(queries):
        last_query[window] = index  # Update to latest query index
    
    # Collect the queried windows along with their last query timestamps
    accessed = []
    for window, timestamp in last_query.items():
        accessed.append((timestamp, window))
    
    # Sort the queried windows in descending order by their timestamp
    accessed.sort(reverse=True)  # Most recent query comes first
    
    # Prepare the final order: queried windows appear at the top
    final_order = [window for timestamp, window in accessed]
    
    # Then, add windows that were never queried, preserving the initial order
    for window in windows:
        if window not in last_query:
            final_order.append(window)
    
    return final_order

# Example Usage:
windows1 = [1, 2, 3]
queries1 = [3, 3, 2]
print(alt_tab_simulation(windows1, queries1))  # Output: [2, 3, 1]

windows2 = [1, 4, 2, 3]
queries2 = [4, 1, 3]
print(alt_tab_simulation(windows2, queries2))  # Output: [3, 1, 4, 2]
← Back to All Questions