대기열의 처음 K 요소 반전

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

큐 문제의 첫 번째 K 요소를 뒤집기 위해 우리는 변발 및 숫자 k, 큐의 표준 연산을 사용하여 큐의 처음 k 요소를 반전시킵니다.

예

입력:
대기열 = 10-> 15-> 31-> 17-> 12-> 19-> 2
k = 3
출력:
대기열 = 31-> 15-> 10-> 17-> 12-> 19-> 2

입력:
대기열 = 12-> 14-> 16-> 7-> 9
k = 2
출력:
대기열 = 14-> 12-> 16-> 7-> 9

대기열의 처음 K 요소를 뒤집는 알고리즘

큐의 처음 k 개 요소를 뒤집기 위해 스택을 사용할 수 있습니다.

1. 대기열의 처음 k 요소를 제거하고 스택으로 푸시합니다.
2. 스택의 모든 요소를 ​​팝하고 대기열의 끝으로 푸시합니다.
3. 대기열의 전면에서 요소를 팝 아웃 (n – k)하고 대기열의 끝으로 푸시합니다. 여기서 n은 대기열의 총 요소 수입니다.
4. 먼저 큐의 k 요소가 반전되고 큐의 요소를 인쇄합니다.

대기열의 처음 K 요소 반전에 대한 설명

예를 들어,
대기열 = 10-> 7-> 4-> 3
k = 2

1단계

대기열의 처음 k 요소를 제거하고 스택으로 푸시합니다.
대기열 = 10-> 7-> 4-> 3 및 스택 = null
반복 1
대기열 = 7-> 4-> 3 및 스택 = 10
반복 2
대기열 = 4-> 3 및 스택 = 7-> 10

2단계

스택의 모든 요소를 ​​팝하고 대기열의 끝으로 푸시합니다.
queue = 4-> 3 및 stack = 7-> 10
반복 1
대기열 = 4-> 3-> 7 및 스택 = 10
반복 2
대기열 = 4-> 3-> 7-> 10 및 스택 = null

3단계

대기열의 전면에서 (n – k) 요소를 꺼내 대기열의 끝으로 푸시합니다.
대기열 = 4-> 3-> 7-> 10
반복 1
대기열 = 3-> 7-> 10-> 4
반복 2
대기열 = 7-> 10-> 4-> 3

핀

JAVA 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class ReversingTheFirstKElementsOfAQueue {
    private static void reverseKElements(Queue<Integer> queue, int k) {
        if (k < 0 || k >= queue.size() || queue.isEmpty()) {
            System.out.println("Invalid Input");
            return;
        }

        int n = queue.size();

        // remove first k elements of queue and push in stack
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < k; i++) {
            int curr = queue.poll();
            stack.push(curr);
        }
        
        // Pop out elements from stack and add to the end of the queue
        while (!stack.isEmpty()) {
            int curr = stack.pop();
            queue.add(curr);
        }

        // Remove first (n - k) elements of the queue and add them to the end
        for (int i = 0; i < n - k; i++) {
            int curr = queue.poll();
            queue.add(curr);
        }

        // Print the elements of the queue
        for (Integer i : queue) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        Queue<Integer> q1 = new LinkedList<>();
        int k1 = 3;
        q1.add(10);
        q1.add(15);
        q1.add(31);
        q1.add(17);
        q1.add(12);
        q1.add(19);
        q1.add(2);
        reverseKElements(q1, k1);

        // Example 2
        Queue<Integer> q2 = new LinkedList<>();
        int k2 = 2;
        q2.add(12);
        q2.add(14);
        q2.add(16);
        q2.add(7);
        q2.add(9);
        reverseKElements(q2, k2);
    }
}

31 15 10 17 12 19 2 
14 12 16 7 9

C ++ 코드

#include<bits/stdc++.h> 
using namespace std;

void reverseKElements(queue<int> &queue, int k) {
    if (k < 0 || k >= queue.size() || queue.empty()) {
        cout<<"Invalid Input"<<endl;
        return;
    }
    
    int n = queue.size();
    
    // remove first k elements of queue and push in stack
    stack<int> st;
    for (int i = 0; i < k; i++) {
        int curr = queue.front();
        queue.pop();
        st.push(curr);
    }
    
    // Pop out elements from stack and add to the end of the queue
    for (int i = 0; i < k; i++) {
        int curr = st.top();
        st.pop();
        queue.push(curr);
    }
    
    // Remove first (n - k) elements of the queue and add them to the end
    for (int i = 0; i < n - k; i++) {
        int curr = queue.front();
        queue.pop();
        queue.push(curr);
    }
    
    // Print the elements of the queue
    for (int i = 0; i < n; i++) {
        int curr = queue.front();
        queue.pop();
        cout<<curr<<" ";
        queue.push(curr);
    }
    cout<<endl;
}

int main() {
    // Example 1
    queue<int> q1;
    int k1 = 3;
    q1.push(10);
    q1.push(15);
    q1.push(31);
    q1.push(17);
    q1.push(12);
    q1.push(19);
    q1.push(2);
    reverseKElements(q1, k1);

    // Example 2
    queue<int> q2;
    int k2 = 2;
    q2.push(12);
    q2.push(14);
    q2.push(16);
    q2.push(7);
    q2.push(9);
    reverseKElements(q2, k2);
}

31 15 10 17 12 19 2 
14 12 16 7 9

대기열의 처음 K 요소를 반전시키기위한 복잡성 분석

시간 복잡성 = O (n + k)
공간 복잡성 = 확인) 
여기서 n은 큐의 요소 수입니다.

참조