Huawei OD Interview Algorithm Problem – Basketball Game (Deque Simulation)

The problem describes a linear bucket (a deque) that holds numbered basketballs; balls are inserted from the right side and can be removed from either the left or right side, with the constraint that when only one ball remains it must be taken from the left.

Input: Two lines – the first line lists the insertion order of ball numbers separated by commas, and the second line lists the desired removal order, also comma‑separated.

Output: If the desired removal sequence can be achieved, output a string of operations using "L" for a left removal and "R" for a right removal; otherwise output "NO".

Example: Input: 4,5,6,7,0,1,2 6,4,0,1,2,5,7 Output: RLRRRLL

Solution approach: Simulate the process with two double‑ended queues – one for the insertion order and one for the target removal order. After each insertion, repeatedly check the front and back of the bucket against the next required removal; record "L" or "R" accordingly. If at any point neither end matches the required ball, the sequence is impossible.

Reference code (C++):

#include <iostream>
#include <deque>
#include <sstream>
#include <string>
using namespace std;
int main() {
    string pushInput, popInput;
    getline(cin, pushInput);
    getline(cin, popInput);
    stringstream pushStream(pushInput), popStream(popInput);
    deque
pushList, popList;
    string token;
    while (getline(pushStream, token, ',')) pushList.push_back(stoi(token));
    while (getline(popStream, token, ',')) popList.push_back(stoi(token));
    deque
bucket;
    string output;
    size_t i = 0;
    for (int pushNum : pushList) {
        bucket.push_back(pushNum);
        while (!bucket.empty()) {
            if (bucket.front() == popList[i]) {
                bucket.pop_front();
                ++i;
                output += "L";
            } else if (!bucket.empty() && bucket.back() == popList[i]) {
                bucket.pop_back();
                ++i;
                output += "R";
            } else {
                break;
            }
        }
    }
    if (output.length() == pushList.size()) cout << output << endl;
    else cout << "NO" << endl;
    return 0;
}

Reference code (Java):

import java.util.ArrayDeque;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] pushInput = scanner.nextLine().split(",");
        String[] popInput = scanner.nextLine().split(",");
        scanner.close();
        ArrayDeque
pushList = new ArrayDeque<>();
        ArrayDeque
popList = new ArrayDeque<>();
        for (String s : pushInput) pushList.add(Integer.parseInt(s));
        for (String s : popInput) popList.add(Integer.parseInt(s));
        ArrayDeque
bucket = new ArrayDeque<>();
        StringBuilder output = new StringBuilder();
        for (int pushNum : pushList) {
            bucket.add(pushNum);
            while (!bucket.isEmpty()) {
                if (bucket.peek().equals(popList.peek())) {
                    bucket.poll();
                    popList.poll();
                    output.append("L");
                } else if (!bucket.isEmpty() && bucket.peekLast().equals(popList.peek())) {
                    bucket.pollLast();
                    popList.poll();
                    output.append("R");
                } else {
                    break;
                }
            }
        }
        if (output.length() == pushList.size() + popList.size()) {
            System.out.println(output);
        } else {
            System.out.println("NO");
        }
    }
}