Interview Experience | On Campus - Aug 2025

Interview rounds

Round

Hard

Online Coding Test

Duration90 minutes

Interview date7 Aug 2025

Coding problem4

The online assessment was 90 minutes long, conducted on the DoSelect platform with proctoring enabled to ensure fairness. It consisted of 4 challenging DSA problems, all of which were hard-level. The environment was serious and focused, as every participant was aware of the difficulty level and the limited time available.

1. Minimum Cost to Reach Destination in Time

Hard

0/120

Asked in company

You are given a country of 'n' cities, a series of bi-directional roads, and a list of passing fees for each city. The journey starts at city 0 and must end at city n-1 within a given maxTime.

The details are as follows:

The roads are given as a 2D array edges, where edges[i] = [u, v, time] represents a road between city u and v that takes time minutes to travel.

The cost of visiting any city is given in the passingFees array.

The total cost of a journey is the sum of the passing fees of all unique cities visited, including the start and end cities.

The total time of a journey is the sum of the travel times of all roads used.

Your task is to find the path from city 0 to city n-1 that has the minimum possible cost, while ensuring the total time does not exceed maxTime. If no such path exists, return -1.

Problem approach

Step 1: Modelled it as a constrained shortest path on an expanded state space. A state is (node u, totalLatency t). The priority queue key is the total toll so far.

Step 2: Initialization: push (1,0) with cost = toll[1].

Step 3: Pop the lowest-toll state; if we’ve already seen a cheaper toll for (u,t), skip.

Step 4: Relax every edge (u,v,w): if t+w ≤ maxL, push (v, t+w) with newCost = curCost + toll[v].

Step 5: Prune dominated states: for each node, if we already achieved latency t′ ≤ t with toll ≤ newCost, skip pushing.

Step 6: Answer = min over t≤maxL of best[n][t]; if none exists, return −1.
(Think “Dijkstra on (node,time) with domination pruning”, exactly how LC-1928 is solved.)

Try solving now

2. Cherry Pickup

Hard

0/120

Asked in company

You are given an 'n' x 'n' grid where each cell contains one of three values:

0: An empty cell you can pass through.

1: A cell with a cherry you can pick up. After you pick it, the cell becomes empty (0).

-1: A thorn that blocks your path.

Your task is to find the maximum number of cherries you can collect by completing a round trip, following these rules:

1) Forward Trip: Start at (0, 0) and travel to (n-1, n-1) by moving only right or down.

2) Return Trip: From (n-1, n-1), travel back to (0, 0) by moving only left or up.

3) You can only move through cells that are not thorns (-1).

4) If there is no valid path for either the forward or return trip, you can collect 0 cherries.

Problem approach

Step 1: Observed the two trips can be modeled as two people walking from (0,0) to (n−1,m−1) simultaneously in k steps (0..n+m−2), each moving right or down.

Step 2: DP state: dp[k][r1][r2] = max value after k moves when walkers are at (r1,c1=k−r1) and (r2,c2=k−r2). If any cell is blocked, state = −∞.

Step 3: Transition from four predecessors at step k−1: (r1−1,r2−1), (r1−1,r2), (r1,r2−1), (r1,r2). Add grid[r1][c1] + grid[r2][c2] (but if same cell, add once).

Step 4: Initialize dp[0][0][0] = grid[0][0] if not blocked.

Step 5: Result = max(0, dp[n+m−2][n−1][n−1]); if it’s −∞, return 0.
(Time O((n+m)·n·n), space can be rolled to O(n²).)

Try solving now

3. Optimal Character Rearrangement

Easy

0/40

Asked in company

You are given a string s. Your task is to rearrange the characters of s to create a new string, srearranged, such that the number of positions where s[i] != srearranged[i] is maximized.

You need to return this maximum possible number of mismatched positions.

Problem approach

Step 1: Count frequencies; let n = |s| and maxf = max character frequency.

Step 2: By pigeonhole principle, at least max(0, 2·maxf − n) positions must match (a majority letter can’t be fully displaced).

Step 3: Therefore the maximum mismatches = n − minimal matches = min(n, 2·(n − maxf)).

(Constructive idea if needed) Sort indices by character blocks and rotate one block by maxf positions; then greedily swap any residual matches.
This gives O(n) counting + O(n log σ) or O(n) construction, and matches examples (e.g., if maxf ≤ ⌊n/2⌋, answer = n).

Try solving now

4. Huffman Coding with Unequal Letter Costs

Ninja

0/200

Asked in company

You are given a set of 'n' symbols, each with a given probability of occurrence. Your task is to devise a prefix-free binary code for these symbols using an alphabet {‘A’, ‘B’}.

However, the transmission time for the letters in the alphabet is unequal:

Transmitting 'A' takes 1 unit of time.

Transmitting 'B' takes 2 units of time.

Your goal is to find an optimal set of codes that minimizes the total expected transmission time. The expected time is calculated as the sum over all symbols of (symbolprobability * timeofitscode).

A prefix-free code is one where no symbol's code is a prefix of another symbol's code.

Problem approach

Step 1: Framed it as building an optimal binary prefix tree where left edges (‘A’) cost 1 and right edges (‘B’) cost 2; leaves correspond to symbols, minimizing Σ p[i]·(sum of edge costs on its root→leaf path).

Step 2: Used the standard unequal-letter-cost approach: compute target code “lengths” via a Shannon-like bound using the generalized Kraft inequality. For costs {1,2}, the base φ solves φ⁻¹ + φ⁻² = 1 ⇒ φ = (1+√5)/2. Set preliminary lengths ℓᵢ ≈ ⌈log_φ(1/pᵢ)⌉.

Step 3: Applied a package-merge / DP adjustment so that the multiset {ℓᵢ} satisfies the Kraft constraint for costs {1,2}, then assigned canonical codes by growing the A/B tree (no code is a prefix of another; if any code is exactly “A”, all others must begin with ‘B’).

Step 4: Verified on examples (e.g., p = [0.5, 0.3, 0.2]) we can emit {A, BA, BB} or {B, AA, AB}—both achieve the same optimal expected time.

Try solving now

Round

Hard

Face to Face

Duration60 minutes

Interview date8 Aug 2025

Coding problem2

The interview happened in the afternoon in a calm and focused environment. The interviewer was friendly, gave hints when needed, and wanted clear, optimized answers. The round was about one hour long with two hard coding problems. I fully solved the first problem using both recursion and an iterative method. For the second problem, I explained my approach but didn’t get time to write the full code.

1. The Binary Tree Lineage

Easy

0/40

Asked in company

In a distant galaxy, a species' lineage is tracked using an infinite binary tree. The gender of each individual is determined by a simple set of genetic rules:

The ancestor at the root of the tree (level 1) is a Male ('M').

If a parent is a Male ('M'), their left child is a Male ('M') and their right child is a Female ('F').

If a parent is a Female ('F'), their left child is a Female ('F') and their right child is a Male ('M').

You are given n (a level in the tree, 1-indexed) and k (a position within that level, 1-indexed from left to right). Your task is to determine the gender of the individual at that specific position.

Problem approach

Step 1: Saw that it followed a repeated pattern that could be solved using recursion.
Step 2: Wrote a recursive solution to find the parent’s value from the previous row.
Step 3: Also wrote an iterative version to avoid too many recursive calls.

Try solving now

2. Drone's Journey

Hard

0/120

Asked in company

You are tasked with programming a delivery drone to navigate an N x M grid. The grid contains different types of cells:

'S': The drone's starting position.

'P': The package pickup location.

'D': The delivery destination.

'.': Empty space, free to travel through.

'#': An obstacle, which cannot be entered.

The drone must complete a journey in two parts:

First, it must travel from its start 'S' to the pickup location 'P'.

Then, it must travel from the pickup location 'P' to the delivery destination 'D'.

The drone's movement capabilities change after it picks up the package:

Without the package (S to P): The drone can move one step at a time to any adjacent cell (up, down, left, or right).

With the package (P to D): The drone is heavier and can only move down or right.

Your task is to find the minimum total number of steps required for the entire journey (S -> P -> D).

Try solving now

Round

Hard

Face to Face

Duration60 minutes

Interview date8 Aug 2025

Coding problem2

This round was in the afternoon in a serious and focused environment. The interviewer was polite but expected very strong problem-solving skills. The questions were extremely hard. I could only explain the approach for the first problem and couldn’t solve the second. The round lasted about one hour.

1. Coin Collector's Quest

Hard

0/120

Asked in company

You are given an undirected tree with 'n' nodes, labeled 0 to n-1. Each node is represented by a value in a coins array:

1: The node contains a coin.

0: The node does not contain a coin.

You start your journey at any node you choose. To collect all the coins in the tree, you must visit every node that has a coin. Moving from a node to an adjacent node costs 1 operation.

Your task is to find the minimum total number of operations (edge traversals) required to visit all nodes containing coins. You do not need to return to your starting node.

Problem approach

Step 1: Understood that the tree structure and distances mattered.
Step 2: Planned to remove extra edges and trim leaves without coins to reduce the search space.
Step 3: Thought of using BFS or DFS to count only the required paths.
Step 4: Could explain the logic to the interviewer but couldn’t finish coding due to time.

Try solving now

2. Box Annihilation

Hard

0/120

Asked in company

You are given a list of N boxes, each represented by a positive integer indicating its color.

You can remove boxes in a series of rounds. In each round, you can choose a contiguous group of k boxes of the same color. Removing this group gives you k * k points. After removal, the boxes to the left and right of the removed group (if any) become adjacent.

Your goal is to find the maximum possible total score you can achieve by removing all the boxes.

Problem approach

Tip 1: Recognized this as a dynamic programming problem with overlapping subproblems.
Tip 2: Considered using a 3D DP approach (index range + extra boxes count).

Try solving now

SDE - Intern

Interview preparation journey

Are you ready for your Dream Job?

Interview rounds

1. Minimum Cost to Reach Destination in Time

You are given a country of 'n' cities, a series of bi-directional roads, and a list of passing fees for each city. The journey starts at city 0 and must end at city n-1 within a given maxTime.

The details are as follows:

The roads are given as a 2D array edges, where edges[i] = [u, v, time] represents a road between city u and v that takes time minutes to travel.

The cost of visiting any city is given in the passingFees array.

The total cost of a journey is the sum of the passing fees of all unique cities visited, including the start and end cities.

The total time of a journey is the sum of the travel times of all roads used.

Your task is to find the path from city 0 to city n-1 that has the minimum possible cost, while ensuring the total time does not exceed maxTime. If no such path exists, return -1.

2. Cherry Pickup

You are given an 'n' x 'n' grid where each cell contains one of three values:

0: An empty cell you can pass through.

1: A cell with a cherry you can pick up. After you pick it, the cell becomes empty (0).

-1: A thorn that blocks your path.

Your task is to find the maximum number of cherries you can collect by completing a round trip, following these rules:

1) Forward Trip: Start at (0, 0) and travel to (n-1, n-1) by moving only right or down.

2) Return Trip: From (n-1, n-1), travel back to (0, 0) by moving only left or up.

3) You can only move through cells that are not thorns (-1).

4) If there is no valid path for either the forward or return trip, you can collect 0 cherries.

3. Optimal Character Rearrangement

You are given a string s. Your task is to rearrange the characters of s to create a new string, srearranged, such that the number of positions where s[i] != srearranged[i] is maximized.

You need to return this maximum possible number of mismatched positions.

4. Huffman Coding with Unequal Letter Costs

You are given a set of 'n' symbols, each with a given probability of occurrence. Your task is to devise a prefix-free binary code for these symbols using an alphabet {‘A’, ‘B’}.

However, the transmission time for the letters in the alphabet is unequal:

Transmitting 'A' takes 1 unit of time.

Transmitting 'B' takes 2 units of time.

Your goal is to find an optimal set of codes that minimizes the total expected transmission time. The expected time is calculated as the sum over all symbols of (symbolprobability * timeofitscode).

A prefix-free code is one where no symbol's code is a prefix of another symbol's code.

1. The Binary Tree Lineage

In a distant galaxy, a species' lineage is tracked using an infinite binary tree. The gender of each individual is determined by a simple set of genetic rules:

The ancestor at the root of the tree (level 1) is a Male ('M').

If a parent is a Male ('M'), their left child is a Male ('M') and their right child is a Female ('F').

If a parent is a Female ('F'), their left child is a Female ('F') and their right child is a Male ('M').

You are given n (a level in the tree, 1-indexed) and k (a position within that level, 1-indexed from left to right). Your task is to determine the gender of the individual at that specific position.

2. Drone's Journey

You are tasked with programming a delivery drone to navigate an N x M grid. The grid contains different types of cells:

'S': The drone's starting position.

'P': The package pickup location.

'D': The delivery destination.

'.': Empty space, free to travel through.

'#': An obstacle, which cannot be entered.

The drone must complete a journey in two parts:

First, it must travel from its start 'S' to the pickup location 'P'.

Then, it must travel from the pickup location 'P' to the delivery destination 'D'.

The drone's movement capabilities change after it picks up the package:

Without the package (S to P): The drone can move one step at a time to any adjacent cell (up, down, left, or right).

With the package (P to D): The drone is heavier and can only move down or right.

Your task is to find the minimum total number of steps required for the entire journey (S -> P -> D).

1. Coin Collector's Quest

You are given an undirected tree with 'n' nodes, labeled 0 to n-1. Each node is represented by a value in a coins array:

1: The node contains a coin.

0: The node does not contain a coin.

You start your journey at any node you choose. To collect all the coins in the tree, you must visit every node that has a coin. Moving from a node to an adjacent node costs 1 operation.

Your task is to find the minimum total number of operations (edge traversals) required to visit all nodes containing coins. You do not need to return to your starting node.

2. Box Annihilation

You are given a list of N boxes, each represented by a positive integer indicating its color.

You can remove boxes in a series of rounds. In each round, you can choose a contiguous group of k boxes of the same color. Removing this group gives you k * k points. After removal, the boxes to the left and right of the removed group (if any) become adjacent.

Your goal is to find the maximum possible total score you can achieve by removing all the boxes.