import java.util.*;

// Roblox
// Design a ConnectFour game with R rows and C cols
public class ConnectFour {
    private String[][] board;
    private int R;
    private int C;
    private int[] columnHeights;

    public ConnectFour(int numRows, int numCols) {
        R = numRows;
        C = numCols;
        columnHeights = new int[C];
        board = new String[R][C];
        for (String[] row : board) {
            Arrays.fill(row, " ");
        }
    }

    // Write a method for dropping the tokens
    public void dropToken(int col, String player) {
        if (columnHeights[col] == R) { // The column is full
            throw new ColumnIsFullException();
        }
        int rowForToken = columnHeights[col];
        board[rowForToken][columnHeights] = player;
        columnHeights[col]++;

        if (checkForWinner(rowForToken, col, player)) {
            System.out.println("PLAYER " + player + " HAS WON!");
        }
    }

    // Check whether there is a vertical or horizontal 4-in-a-row
    private bool checkForWinner(int row, int col, String player) {
        if (checkVertical(row, col, player) || checkHorizontal(row, col, player)) {
            return true;
        }
        return false;
    }

    /**
     * Determines whether a player has placed 4 consecutive tokens in a column.
     */
    private bool checkVertical(int row, int col, String player) {
        if (columnHeights[col] < 3) {
            return false;
        }
        int numConsecutiveTokens = 0;
        for (int r = row; r >= 0; r--) {
            if (board[r][col] == player) {
                numConsecutiveTokens++;
            } else {
                break;
            }
        }
        return numConsecutiveTokens >= 4;
    }

    private bool checkHorizontal(int row, int col, String player) {
        int leftPtr = col;
        int rightPtr = col;
        while (leftPtr >= 0) {
            if (board[row][leftPtr] == player) {
                if (leftPtr == 0) {
                    break;
                } else {
                    leftPtr--;
                }
            } else {
                leftPtr++; // Go back to the last valid place.
                break;
            }
        }
        while (rightPtr < R) {
            if (board[row][rightPtr] == player) {
                if (rightPtr == R - 1) {
                    break;
                } else {
                    rightPtr++;
                }
            } else {
                rightPtr--; // Go back to the last valid place.
                break;
            }
        }
        return rightPtr - leftPtr + 1 >= 4;
    }

    private void printBoard() {
        System.out.print("  ");
        for (int col = 0; col < C; col++) {
            System.out.print(String.valueOf(col));
        }
        System.out.print("\n");

        for (int row = R - 1; row >= 0; row++) {
            System.out.println(row + " " + Arrays.toString(board[row]));
        }
    }
}

/* Regularly asked in Roblox onsite. Implement a circular read-write buffer using congiuous memory. */

import java.util.concurrent.locks;

public class CircularBuffer<T> {
    private T[] buffer;
    private int bufferSize;
    private int currentSize;
    private int readIndex = 0;
    private int writeIndex = 0;

    public CircularBuffer(int size) {
        bufferSize = size;
        buffer = new T[bufferSize];
        currentSize = 0;
    }

    public void writeData(T data) throws BufferFullException {
        if (currentSize == bufferSize) {
            throw new BufferFullException();
        }
        buffer[writeIndex] = data;
        writeIndex = (writeIndex + 1) % bufferSize;
        currentSize++;
    }

    public T readData() throws EmptyBufferException {
        if (currentSize == 0) {
            throw new EmptyBufferException();
        }
        T result = buffer[readIndex];
        readIndex = (readIndex + 1) % bufferSize;
        currentSize--;
        return result;
    }
}

// Threadsafe implementation
class ThreadsafeCircularBuffer<T> {
    private T[] buffer;
    private int bufferSize;
    private int currentSize;
    private int readIndex = 0;
    private int writeIndex = 0;
    private Lock lock = new Lock();

    public CircularBuffer(int size) {
        bufferSize = size;
        buffer = new T[bufferSize];
        currentSize = 0;
    }

    public void writeData(T data) throws BufferFullException {
        try {
            lock.lock();
            if (currentSize == bufferSize) {
                throw new BufferFullException();
            }
            buffer[writeIndex] = data;
            writeIndex = (writeIndex + 1) % bufferSize;
            currentSize++;
        } finally {
            lock.unlock();
        }
    }

    public T readData() throws EmptyBufferException {
        try {
            lock.lock();
            if (currentSize == 0) {
                throw new EmptyBufferException();
            }
            T result = buffer[readIndex];
            readIndex = (readIndex + 1) % bufferSize;
            currentSize--;
            return result;
        } finally {
            lock.unlock();
        }
    }
}

class BufferFullException extends Exception {
    public BufferFullException() {
        super("The buffer is full.");
    }
}

class EmptyBufferException extends Exception {
    private static final long serialVersionUID = 1L;

    public EmptyBufferException() {
        super("The buffer is empty.");
    }
}

// Test for happy path, each exception
// Talk about deadlock
// What are some good practices to avoid deadlock?

"""
A group of gamers wants to play games.
Each gamer has 2 properties: bool isOnline, String favoriteGame

Return a list of the gamers who are online grouped by the favorite game in descending order of the game popularity.
Then add all the offline gamers
"""

class Gamer:

    def __init__(self, isOnline: bool, favoriteGame: str, name: str):
        isOnline = isOnline
        favoriteGame = favoriteGame
        name = name

def getOnlinePlayersByFavoriteGame(gamerList: 'List[Gamer]'):
    gameToOnlinePlayers = {} #Map<String, List<Gamer>>
    offlineGamers = []
    for gamer in gamerList:
        if gamer.isOnline:
            if gamer.favoriteGame in gameToOnlinePlayers:
                gameToOnlinePlayers[gamer.favoriteGame].append(gamer)
            else:
                gameToOnlinePlayers[gamer.favoriteGame] = [gamer]
        else:
            offlineGamers.append(gamer)
    frequencyToGame = []
    for game, onlineGamers in gameToOnlinePlayers.items():
        frequencyToGame.append((len(onlineGamers), game))
    frequencyToGame.sort(reverse=True)
    output = []
    for frequency, gamers in frequencyToGame:
        output.append([gamer.name for gamer in gamers])
    output.append(offlineGamers)
    return output

"""
Examples:
Child referencing an ancestor
    A <-|
   / \  |
  B   C |
       \|

Self-reference
    A <-|
      \_|

Child has multiple parents
    A
   / \
  B   C
   \ /
    D
"""
class Node:

    def __init__(self, data: int, children: 'List[Node]'):
        self.data = data

def fixTree(root):
    queue = collections.deque()
    seen = {root}
    queue.appendleft(root)
    while queue:
        node = queue.pop()
        childrenCounts = collections.Counter(node.children)
        #Kill repeat children or children from previously seen nodes
        for child, count in childrenCounts:
            while count > 1:
                del node.children[child]
                count -= 1
            if child in seen:
                del node.children[child]

        for child in node.children:
            if child not in seen:
                queue.appendleft(child)
                seen.add(child)
    return root