Panda Guru LogoPanda
Guru

Meesho OA 2025

Round 1

Questions:

Problem 1:
Count number of unique ways to get a total of N using numbers m, any number of times, also mod needs to be taken. Classic DP problem.
Constraints: N*m < 10^6;
Mock solution:

dp[0] = 1; for(int i = 0; i <= Total; ++i) { for(int j = 1; j <= m; ++j) { (dp[i] += dp[i - j]) %= mod; // i >= j } }

Problem 2:
A tree is given, with every node containing a non-negative value and a value m. We need to count the number of paths in the vertical direction such that the sum of nodes in the vertical direction modulo m is zero.
Constraints: nodes < 10^6; nodes_val < 10^9; m < 10^5;
Mock approach:
Maintain a hashmap of prefix sum during the DFS. Any vertical path's sum can be deduced as (pre[i] - pre[j]) % m = 0 which is equivalent to pre[i] == pre[j].


Problem 3:
A grid is given with a start and end node, we have to find the minimum number of jumps from start to end. There are blocks, we can jump in all 4 directions. Also, there is a constraint on the jump: