Alt and Tab Simulation - Practice Coding Problems

Alt and Tab Simulation - Problem

There are n windows open numbered from 1 to n. We want to simulate using Alt + Tab to navigate between the windows.

You are given an array windows which contains the initial order of the windows (the first element is at the top and the last one is at the bottom).

You are also given an array queries where for each query, the window queries[i] is brought to the top.

Return the final state of the array windows after all queries are processed.

Input & Output

Example 1 — Basic Alt+Tab Simulation

$ Input: windows = [1,2,3], queries = [3,1,3]

› Output: [3,1,2]

💡 Note: Start with [1,2,3]. Query 3 moves it to front: [3,1,2]. Query 1 moves it to front: [1,3,2]. Query 3 moves it to front: [3,1,2].

Example 2 — Single Query

$ Input: windows = [1,2,3,4,5], queries = [4]

› Output: [4,1,2,3,5]

💡 Note: Only window 4 is queried, so it moves to the front while others maintain their relative order.

Example 3 — Multiple Same Queries

$ Input: windows = [2,1,3], queries = [1,1,1]

› Output: [1,2,3]

💡 Note: Window 1 is brought to front on first query [1,2,3], subsequent queries of same window don't change the order.

Constraints

1 ≤ windows.length ≤ 10³
1 ≤ queries.length ≤ 10⁵
1 ≤ windows[i], queries[i] ≤ 10⁶
All elements in windows are unique
All queries[i] exist in windows

Visualization

Tap to expand

Understanding the Visualization

Initial Windows

Windows in original stack order [1,2,3]

Process Queries

Each query brings a window to the front

Final State

Final window order after all queries

Key Takeaway

🎯 Key Insight: Process queries in reverse order to avoid expensive array shifting operations and achieve linear time complexity.

Asked in

M Microsoft 35 G Google 28 🍎 Apple 22

The key insight is that Alt+Tab simulation can be optimized by processing queries in reverse order to avoid expensive array operations. The brute force approach directly simulates each move with O(n×m) time complexity. The optimal reverse processing approach constructs the final result in O(n+m) time by determining the final position of each window without intermediate moves. Time: O(n+m), Space: O(n+m).

Common Approaches

Approach	Time	Space	Notes
✓ Reverse Processing	O(n + m)	O(n + m)	Process queries in reverse to avoid repeated array modifications
Brute Force Simulation	O(n × m)	O(1)	Directly simulate each query by finding and moving windows
Hash Map with Position Tracking	O(n × m)	O(n)	Use hash map to track positions for faster lookups

Reverse Processing — Algorithm Steps

Create set of queried windows
Process queries in reverse order
Add remaining windows in original order
Return the constructed result

Visualization

Tap to expand

Step-by-Step Walkthrough

Reverse Queries

Process queries from last to first

Track Queried

Use set to avoid duplicates

Add Remaining

Append non-queried windows

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool contains(int* arr, int size, int val) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == val) return true;
    }
    return false;
}

int* solution(int* windows, int windowsSize, int* queries, int queriesSize, int* returnSize) {
    int* result = (int*)malloc(windowsSize * sizeof(int));
    int* queried = (int*)malloc(windowsSize * sizeof(int));
    int queriedCount = 0;
    int resultCount = 0;
    
    // Process queries in reverse to get final order
    for (int i = queriesSize - 1; i >= 0; i--) {
        int query = queries[i];
        if (!contains(queried, queriedCount, query)) {
            result[resultCount++] = query;
            queried[queriedCount++] = query;
        }
    }
    
    // Add remaining windows that were never queried
    for (int i = 0; i < windowsSize; i++) {
        int window = windows[i];
        if (!contains(queried, queriedCount, window)) {
            result[resultCount++] = window;
        }
    }
    
    *returnSize = resultCount;
    free(queried);
    return result;
}

int* parseArray(char* str, int* size) {
    int* arr = (int*)malloc(100 * sizeof(int));
    *size = 0;
    
    char* token = strtok(str, "[],");
    while (token != NULL) {
        arr[*size] = atoi(token);
        (*size)++;
        token = strtok(NULL, "[],");
    }
    
    return arr;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    line1[strcspn(line1, "\n")] = 0;
    line2[strcspn(line2, "\n")] = 0;
    
    int windowsSize, queriesSize;
    int* windows = parseArray(line1, &windowsSize);
    int* queries = parseArray(line2, &queriesSize);
    
    int returnSize;
    int* result = solution(windows, windowsSize, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(windows);
    free(queries);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Single pass through windows and queries, no nested operations

✓ Linear Growth

Space Complexity

O(n + m)

Set to track queried windows plus result array

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Reverse Processing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler