Design Tic-Tac-Toe and QPS data structures

You are given two independent coding problems that focus on data structure and API design.

Problem 1: Generalized Tic-Tac-Toe Game with Simple AI

Design a Tic-Tac-Toe game that supports a generalized board size and a customizable win condition.

Implement a class TicTacToe with the following behavior:

• The game is played by two players, labeled 1 and 2.
• The board has rows rows and cols columns.
• A player wins if they have K of their marks in a line, where a line can be:
• A horizontal line
• A vertical line
• A main diagonal (top-left to bottom-right)
• An anti-diagonal (top-right to bottom-left)

API

TicTacToe(int rows, int cols, int K)

• Initializes the game board with the given dimensions and win condition K.
• All cells are initially empty.

int move(int row, int col, int player)

• row, col are 0-indexed coordinates on the board.
• player is either 1 or 2.
• Places the player's mark at (row, col).
• Returns:
• 0 if no one has won after this move,
• 1 if player 1 wins as a result of this move,
• 2 if player 2 wins as a result of this move,
• -1 if the move is invalid (out of bounds or the cell is already occupied).

You should design the data structures so that each move call is efficient even when the board is large.

Constraints (you may assume):

• 1 <= rows, cols <= 1000
• 1 <= K <= max(rows, cols)
• Total number of moves ≤ rows * cols.

Follow-up: Random-Move AI

Extend the design with a very simple AI that chooses a random legal move for a given player.

You are given a helper function:

int randInt(int low, int high)

which returns a uniform random integer in the inclusive range [low, high].

Add a method:

pair<int, int> getNextMove(int player)

• Returns a pair (row, col) corresponding to an empty cell where player can play next.
• The AI should pick uniformly at random among all currently empty cells.
• If there is no legal move (the board is full or the game is already over), you may return a special value, such as (-1, -1).

Design this so that getNextMove runs efficiently, even on a large board with many moves already played.

Problem 2: Query QPS from KV Store Request Logs

A key-value (KV) store receives a large number of requests. Each request is logged with a timestamp (in seconds). You want to support efficient queries about the queries per second (QPS) over arbitrary time ranges.

You are given an initially empty log. Implement a data structure that supports the following operations:

void record(long timestamp)

• Called once for each request handled by the KV store.
• timestamp is an integer representing seconds since some fixed epoch.
• Timestamps are not guaranteed to be contiguous but you may assume they are non-decreasing (each new call has timestamp >= previous timestamp).

double getQPS(long startTime, long endTime)

• Returns the average QPS in the inclusive time interval [startTime, endTime].
• Formally, if count requests have timestamps t such that startTime <= t <= endTime, then:

QPS = count / (endTime - startTime + 1)

• You should support many getQPS queries efficiently after recording a large volume of data.

Constraints (you may assume):

• Up to N = 10^6 calls to record.
• Up to Q = 10^6 calls to getQPS.
• Timestamps fit in a 64-bit signed integer.

Follow-up 1: Efficient Arbitrary-Time Queries

The naive implementation might scan all timestamps within [startTime, endTime] for each query, which is too slow when Q is large.

Design and describe a more efficient approach that:

• Uses reasonable additional memory.
• Supports getQPS(startTime, endTime) in sublinear time in N (for example, O(log N) per query).

Your design should be implementable using common data structures (arrays, lists, hash maps, trees, etc.).

Follow-up 2: Trade Accuracy for Less Memory

Now suppose memory is tight and you are allowed to sacrifice precision to save space. Instead of storing every individual timestamp, you can approximate the QPS.

Design a modified scheme that:

• Uses significantly less memory than the exact solution.
• Returns an approximate QPS for any [startTime, endTime] query.
• Clearly states what is being approximated (for example, grouping multiple seconds into a time range / bucket) and what kind of error might be introduced.

You should:

• Describe the data you would store (e.g., buckets or ranges instead of individual timestamps).
• Explain how getQPS will be computed from this aggregated data.
• Reason about the trade-off between memory usage, accuracy, and query performance.