React Native Offline Data Sync

Implementing "Offline-First" capability is one of the most challenging parts of mobile development. A robust sync engine must handle local changes, remote updates, and resolve conflicts when the same data is modified on both sides.

In this challenge, you will implement a synchronization function syncData that reconciles a local state with a remote state based on a lastSync timestamp.

Data Structures

interface SyncItem {
  id: number;
  data: string;
  timestamp: number; // Unix timestamp in milliseconds
  deleted?: boolean; // Flag for soft deletions
}

interface SyncResult {
  merged: SyncItem[]; // Final reconciled list of items (excluding deleted ones)
  conflicts: {
    id: number;
    local: SyncItem;
    remote: SyncItem;
    winner: "local" | "remote";
  }[];
  toUpload: SyncItem[]; // Local modifications that need to be sent to server
  toDownload: SyncItem[]; // Remote modifications that need to be saved locally
}

Rules for Sync

1. Modified Since Sync: An item is considered "modified" if its timestamp is greater than lastSync.
2. Unchanged: If neither local nor remote version was modified since lastSync, keep the item as is in merged.
3. One-Sided Modification:
   • If only the local item was modified, add it to merged (unless deleted) and toUpload.
   • If only the remote item was modified, add it to merged (unless deleted) and toDownload.
4. Conflict (Both Modified):
   • If both versions were modified, use Last-Write-Wins (LWW): the version with the higher (or equal) timestamp wins.
   • Add the conflict details to the conflicts array.
   • Add the winner to merged (unless deleted).
   • If local wins, add it to toUpload. If remote wins, add it to toDownload.

Example

Input:

{
  "local": [{"id": 1, "data": "local_v", "timestamp": 100}],
  "remote": [{"id": 1, "data": "remote_v", "timestamp": 90}],
  "lastSync": 80
}

Output:

{
  "merged": [{"id": 1, "data": "local_v", "timestamp": 100}],
  "conflicts": [{"id": 1, "local": {...}, "remote": {...}, "winner": "local"}],
  "toUpload": [{"id": 1, "data": "local_v", "timestamp": 100}],
  "toDownload": []
}

Constraints

• 1 <= local.length, remote.length <= 1000
• Timestamps are positive integers.
• All IDs are unique within their respective lists.

Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

---

Examples

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

---

Constraints

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

---

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

---

Examples

Example 1:

Input:  s = "()"
Output: true

Example 2:

Input:  s = "()[]{}"
Output: true

Example 3:

Input:  s = "(]"
Output: false
Explanation: '(' must be closed by ')' not ']'.

Example 4:

Input:  s = "([)]"
Output: false
Explanation: Brackets are interleaved — invalid order.

Example 5:

Input:  s = "{[]}"
Output: true
Explanation: Properly nested.

---

Constraints

• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'

Implement OAuth 2.0 Authorization Code Flow

OAuth 2.0 is the industry-standard protocol for authorization. The Authorization Code Flow is the most commonly used flow, designed for secure server-side applications.

In this challenge, you will implement the logic for an Authorization Server that handles two main endpoints:

1. /authorize: Validates the request and returns an authorization_code.
2. /token: Exchanges the authorization_code for an access_token.

The Flow Steps:

1. Client Application redirects the user to the Authorization Server.
2. Authorization Server validates the client_id and redirect_uri, then issues an authorization_code.
3. Client Application sends a POST request to the /token endpoint with the authorization_code, client_secret, and redirect_uri.
4. Authorization Server validates the code and secret, then returns an access_token.

Requirements:

• Handle state parameter to prevent CSRF.
• Implement expiration for Authorization Codes (codes should only be valid once and for a short time).
• Validate that the redirect_uri in the token phase matches the one used in the authorization phase.

Example

Input (Authorize): { "client_id": "abc", "redirect_uri": "https://callback.com", "state": "xyz" } Output: { "code": "AUTH_CODE_123", "state": "xyz" }

Input (Token): { "client_id": "abc", "client_secret": "secret123", "code": "AUTH_CODE_123", "redirect_uri": "https://callback.com" } Output: { "access_token": "JWT_TOKEN_456", "token_type": "Bearer", "expires_in": 3600 }

Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo" Output: true Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo" Output: false

Constraints:

• 1 <= s1.length, s2.length <= 10^4
• s1 and s2 consist of lowercase English letters.

Design a Message Queue

Design a distributed, durable, and highly scalable message queue system similar to Apache Kafka or RabbitMQ. The system must support asynchronous communication between multiple producers and consumers through a Publish-Subscribe (Pub-Sub) or Point-to-Point model.

Requirements

Functional Requirements

1. Produce Messages: Producers can send messages to specific named "topics".
2. Consume Messages: Consumers can subscribe to one or more topics.
3. Durability: Messages must be persisted to disk to handle server crashes without data loss.
4. Consumer Groups: Support multiple consumers in a group where each message is delivered to only one member of the group (load balancing).
5. Replayability: Consumers should be able to "seek" back in time and re-read messages within a retention period.

Non-Functional Requirements

1. Scalability: The system should scale horizontally by partitioning topics across multiple servers (brokers).
2. High Throughput: Capable of handling millions of messages per second.
3. Ordering: Maintain strict ordering of messages within a single partition.
4. Fault Tolerance: Replicate messages across multiple brokers to ensure availability.

System Components to Consider

• Broker: The server that stores messages.
• Topic: A category or feed name to which messages are published.
• Partition: A topic is split into partitions for parallelism.
• Offset: A unique identifier for each message within a partition.
• ZooKeeper/KRaft: Metadata and leader election management.

Examples

Example Scenario:

1. Producer P1 sends { "type": "order", "id": 123 } to topic orders.
2. The broker appends this message to a partition of the topic and assigns it an offset.

Implement K-Nearest Neighbors

Problem Description

Implement the K-Nearest Neighbors (KNN) classification algorithm from scratch. Given labeled training data, classify new test points by finding the K closest training points and using majority voting.

Requirements

1. Compute Euclidean distance between points
2. For each test point, find the K nearest training points
3. Return the majority class label among the K neighbors
4. Break ties by choosing the smaller label

Function Signature

function knn(
  X_train: number[][],
  y_train: number[],
  X_test: number[][],
  k: number
): { predictions: number[] }

Parameters

• X_train: 2D array of training features (n_samples x n_features)
• y_train: 1D array of class labels (integers)
• X_test: 2D array of test features
• k: Number of neighbors to consider

Example

Input:
  X_train = [[1,1],[2,2],[3,3],[6,6],[7,7],[8,8]]
  y_train = [0,0,0,1,1,1]
  X_test = [[4,4],[7,6]]
  k = 3

Output:
  predictions = [0, 1]

Explanation:
  For [4,4]: 3 nearest are [3,3],[2,2],[1,1] -> labels [0,0,0] -> predict 0
  For [7,6]: 3 nearest are [7,7],[6,6],[8,8] -> labels [1,1,1] -> predict 1

Constraints

• 1 <= k <= n_samples
• 1 <= n_samples <= 10,000
• 1 <= n_features <= 100
• Labels are non-negative integers

Design Circular Queue

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Implementation the MyCircularQueue class:

• MyCircularQueue(k) Initializes the object with the size of the queue to be k.
• boolean enQueue(value) Inserts an element into the circular queue. Return true if the operation is successful.
• boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful.
• int Front() Gets the front item from the queue. If the queue is empty, return -1.
• int Rear() Gets the last item from the queue. If the queue is empty, return -1.
• boolean isEmpty() Checks whether the circular queue is empty or not.
• boolean isFull() Checks whether the circular queue is full or not.

Example 1:

Input: ["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"] [[3], [1], [2], [3], [4], [], [], [], [4], []] Output: [null, true, true, true, false, 3, true, true, true, 4]

Constraints:

• 1 <= k <= 1000
• 0 <= value <= 1000
• At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

Partition Equal Subset Sum

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

---

Examples

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

---

Constraints

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

---

Examples

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown: 5 -> 4 -> 11 -> 2

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There are two root-to-leaf paths: 1->2 (sum = 3) and 1->3 (sum = 4). Neither equals targetSum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false

---

Constraints

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

LFU Cache

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

• LFUCache(int capacity) Initializes the object with the capacity of the data structure.
• int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
• void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1. Any get or put operation on an existing key increments the use counter.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input: ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [1], [4, 4], [1], [3], [4]] Output: [null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Constraints:

• 1 <= capacity <= 10^4
• 0 <= key <= 10^5
• 0 <= value <= 10^9
• At most 2 * 10^5 calls will be made to and .

Write a Multi-Stage Dockerfile

You are tasked with creating a production-ready multi-stage Dockerfile for a Node.js TypeScript application. Multi-stage builds allow you to use multiple FROM statements in your Dockerfile, each starting a new build stage. You can selectively copy artifacts from one stage to another, leaving behind everything you don't need in the final image.

Problem

Given a configuration object describing an application, generate a complete multi-stage Dockerfile as a string. The Dockerfile must:

1. Build Stage: Install all dependencies (including devDependencies), compile TypeScript, and produce production-ready artifacts
2. Production Stage: Use a slim base image, copy only production dependencies and compiled code, and configure the container to run the application

---

Requirements

• Use node:20-alpine as the base image for both stages (unless overridden by config)
• The build stage should be named builder
• Install dependencies using npm ci (not npm install) for reproducible builds
• Copy only package.json and package-lock.json first (leverage Docker layer caching)
• Run the build command to compile TypeScript
• In the production stage, copy only node_modules (production) and compiled output from the builder
• Set the NODE_ENV environment variable to production
• Expose the specified port
• Use a non-root user for security
• Set the correct CMD to start the application

---

Examples

Example 1:

Input: {
  baseImage: "node:20-alpine",
  buildCmd: "npm run build",
  startCmd: "node dist/index.js",
  port: 3000
}

Output:
# Build stage
FROM node:20-alpine AS builder
WORKDIR /app
COPY package*.json ./
RUN npm ci
COPY . .
RUN npm run build

# Production stage
FROM node:20-alpine
WORKDIR /app
ENV NODE_ENV=production
COPY package*.json ./
RUN npm ci --only=production && npm cache clean --force
COPY --from=builder /app/dist ./dist
USER node
EXPOSE 3000
CMD ["node", "dist/index.js"]