Zupee Interview Questions

Background: In Zupee's gaming platform, we need to visualize areas and communities that are connected. This graph-based problem helps us understand clusters of connected resources.
Problem statement: You are given a grid of 1s (land) and 0s (water). Write a function to count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Function/class signature:

• def num_islands(grid: List[List[str]]) -> int:

Example 1:
Input:
grid = [['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']]
Output: 3
Explanation: There are three islands.Example 2:
Input:
grid = [['1','1','1','1','0'],
['0','1','0','0','0'],
['1','1','0','1','1']]
Output: 1
Explanation: There is one island.Constraints:

• 1 <= grid.length <= 300


• 1 <= grid[i].length <= 300


• Each grid[i][j] is either 0 or 1.

Background: Zupee relies on accurate analytics which sometimes requires parsing location data represented as a grid. Efficiently counting distinct land masses (islands) in a grid is crucial for geographic data processing.
Problem statement: Given a 2D grid of '1's (land) and '0's (water), implement a function to count the number of distinct islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Two islands are considered different if they have different shapes.
Function/class signature:

• def numIslands(grid: List[List[str]]) -> int:

Example 1:

• Input: [['1','1','0','0','0'], ['1','0','0','1','0'], ['0','0','0','0'], ['0','0','1','1','1']]


• Output: 3


• Explanation: Three distinct islands are present in the grid.

Example 2:

• Input: [['1','0','0','1'], ['0','0','0','0'], ['1','0','1','1']]


• Output: 3


• Explanation: The input contains three separate islands.

Constraints:

• The grid dimensions can be up to 100 x 100.


• Each grid element is either '1' or '0'.


• At least one element will be present in the grid.

Background: Zupee often works with various data to generate insights about user behavior. Understanding connected components in datasets can be crucial for determining user groupings, especially in competition scenarios. This problem will help in identifying unique groups of connected users in a hypothetical community map.
Problem statement: Given a 2D grid representing a map where 1 represents land and 0 represents water, count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.
Function/class signature:

• def num_islands(grid: List[List[str]]) -> int:

Example 1:
Input: [['1','1','1','1','0'], ['1','1','0','1','0'], ['0','0','0','0','0'], ['0','1','1','0','1']]
Output: 3
Explanation: There are three islands in the provided grid layout.
Example 2:
Input: [['1','1','0','0','0'], ['0','1','0','0','1'], ['0','0','0','1','1']]
Output: 4
Constraints:

• 1 <= grid.length, grid[i].length <= 300


• All grid[i] are either '0' or '1'.

Background: Zupee's gaming platform often involves managing various game regions represented in a grid. Understanding how to navigate and count these regions is essential for features related to territorial games and bonuses.
Problem statement: Given a 2D grid representing a map where 1 represents land and 0 represents water, write a function that returns the number of islands (connected components of 1's) in the grid. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Function/class signature:

• def numIslands(grid: List[List[str]]) -> int:

Example 1:

• Input: grid = [["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"]]


• Output: 3


• Explanation: There are three islands in the grid represented by the 1s.

Example 2:

• Input: grid = [["1","1","1","1","0"], ["1","0","0","1","0"], ["1","1","0","0","0"]]


• Output: 1


• Explanation: There is one large island in this configuration.

Constraints:

• 1 <= grid.length <= 300


• 1 <= grid[0].length <= 300


• Each grid cell is "0" or "1".


• The grid is not empty.

Background: Zupee operates in the online gaming industry, where players often purchase in-game items using virtual currency. Efficiently managing currency combinations to provide change for transactions is crucial for a seamless user experience.
Problem statement: You are given an array of integers coins, representing different denominations of coins available, and an integer amount representing the total amount of money to make change for. Your task is to compute the number of different ways to make change for that amount using the available coins. Return the number of combinations that make up that amount. The same combination of coins can be used in different orders but should only be counted once (e.g., [1, 2] is the same as [2, 1]).
Function/class signature:

• def change(amount: int, coins: List[int]) -> int:

Example 1:
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: There are four ways to make change: [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [5].
Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: There are no ways to make change for amount 3 with only a 2.
Constraints:

• 0 <= amount <= 5000


• 1 <= coins.length <= 300


• 1 <= coins[i] <= 5000

Background: Zupee's gaming environment often involves managing many islands represented in a grid format, where each cell is either land or water. Their system needs an efficient way to determine the number of distinct islands formed by connected land cells for dynamic game scenarios.
Problem statement: Given a 2D grid of 1s (land) and 0s (water), write a function that returns the number of islands (connected 1s).
Each cell can connect with its adjacent cells in four directions (up, down, left, right).
Function/class signature:

• def numIslands(grid: List[List[str]]) -> int:

Example 1:

• Input: grid = [['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]


• Output: 3


• Explanation: The grid has three islands.

Example 2:

• Input: grid = [['1','1','1','1','0'], ['0','1','0','0','0'], ['1','1','0','1','1']]


• Output: 2


• Explanation: The grid has two islands.

Constraints:

• 1 <= grid.length, grid[i].length <= 300


• grid[i][j] is '0' or '1'.