Ascending Cards - Google Top Interview Questions

                        Solution in C++ :

int find(int u, vector<int> &root) {
    if (root[u] == u) return u;
    return root[u] = find(root[u], root);
}

void unite(int u, int v, vector<int> &root) {
    u = find(u, root);
    v = find(v, root);
    root[u] = v;
}

vector<int> solve(vector<int> &cards) {
    sort(cards.begin(), cards.end());
    int N = cards.size();
    vector<int> root(N);
    iota(root.begin(), root.end(), 0);
    vector<int> ret(N);

    int cur = 0;

    for (int i = 0; i < N; ++i) {
        ret[cur] = cards[i];
        unite(cur, (cur + 1) % N, root);
        cur = find((cur + 1) % N, root);
        cur = find((cur + 1) % N, root);
        /* if you want to combine the above 2 lines, replace with:
           cur = find((cur = find((cur + 1) % N, root) + 1) % N, root); */
    }

    return ret;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int[] solve(int[] cards) {
        int n = cards.length;
        Arrays.sort(cards);

        int[] res = new int[n];
        Deque<Integer> dq = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            dq.addLast(i);
        }

        int writeIdx = 0;
        for (int c : cards) {
            res[dq.pollFirst()] = c;
            dq.add(dq.pollFirst());
        }

        return res;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, cards):
        n = len(cards)
        # create another list where we simulate the game
        mapping = list(range(n))
        mapping = deque(mapping)
        res = [0] * n

        for card in sorted(cards):
            res[mapping[0]] = card
            mapping.popleft()
            if mapping:
                mapping.append(mapping.popleft())
        return res