Question-1
You are monitoring the building density in a district of houses. The district is represented as a number line, where each house is located at some integer along the line. Imagine that some of the houses are gradually being destroyed over time. You are given houses, an array of integers representing the initial locations of all houses in the district. You are also given queries, an array of integers representing the locations of the houses which will be destroyed, sorted by the order in which they are destroyed. After each house is destroyed, your task is to find the number of house segments remaining within the district. House segments are defined as one or more adjacent houses which do not have neighbors on either side. Return an array of integers representing the number of house segments after each house from queries is destroyed.
NOTE: It's guaranteed that all houses are in distinct locations. The locations of all houses in queries are present in houses, and also distinct.
Example:-
For houses = [1, 2, 3, 6, 7, 9] and queries [6, 3, 7, 2, 9, 1], the output should be solution(houses, queries) [3, 3, 2, 2, 1, 0]. Initially, there are 6 houses in the district at positions 1, 2, 3, 6, 7, and 9, which form three house segments: [1, 2, 3] and [9]. Let's consider what happens after each step in queries [6.7],
• After queries [0] = 6 the house at location 6 is removed, and the remaining houses are in three segments: [1, 2, 3], [7], and [9], so the output is 3.
• After queries [1] = 3 , the house at location 3 is removed, and the remaining houses are still in three segments: [1, 2], [7], and [9], so the output is also overline 3 .
• After queries [2] = 7 the house at location 7 is removed, and the remaining houses are now in two segments: [1, 2] and [9], so the output is 2.
• After queries [3] = 2 the house at location 2 is removed, and the remaining houses are still in two segments: [1] and [9], so the output is 2.
• After queries [4] = 9 , only one house in position 1 remains, which can only be in one segment, so the output is 1.
• After queries [5] = 1 , there are no more houses in the district, so the output is o.
Altogether, the final answer is [3, 3, 2, 2, 1, 0].
All test cases passed succesfully
def solution(houses, queries):
house_set = set(houses)
segments = 0
prev = None
for house in sorted(houses):
if prev is None or house != prev + 1:
segments += 1
prev = house
results = []
for q in queries:
house_set.remove(q)
left_neighbor = q - 1
right_neighbor = q + 1
if left_neighbor not in house_set and right_neighbor not in house_set:
segments -= 1
elif left_neighbor in house_set and right_neighbor in house_set:
segments += 1
results.append(segments)
return results
Question-2
Imagine you are given a board of cells, each containing a bubble of a specific color (as shown below). Neighboring cells of the bubble are defined as adjacent cells (on either the same row or column as the given cell) which have a common side with the given cell. For example, the neighboring cells for each of the Cells A, B, and c are highlighted in corresponding color in the picture below. Our task is to perform a bubble explosion on the board. A bubble explosion is defined by the following rules:
A bubble within any given cell is eligible to explode if it has the same color as bubbles in at least 2 neighboring cells.
• All eligible bubbles and bubbles of the same color in neighboring cells are marked for explosion.
All marked bubbles explode at the same time. Exploded bubbles are removed from the board, resulting in empty cells.
• After all exploded bubbles are removed, remaining bubbles in cells above the empty cells drop down to fill all empty cells.
You are given an initial board of cells bubbles a multidimensional array of integers representing cells containing bubbles of various colors. Return the ward state after a bubble explosion. The output should be a multidimensional array of integers with the same size as bubbles, but replacing all empty cells ithout bubbles) with 0
Note: You are not expected to provide the most optimal solution, but a solution with time complexity not worse than o(bubbles. length bbles[0].lengtir) will fit within the execution time limit.
All test cases passed succesfully
def solution(bubbles):
rows, cols = len(bubbles), len(bubbles[0])
marked_for_explosion = [[False] * cols for _ in range(rows)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def within_bounds(r, c):
return 0 <= r < rows and 0 <= c < cols
for r in range(rows):
for c in range(cols):
color = bubbles[r][c]
if color == 0:
continue
count = 0
for dr, dc in directions:
nr, nc = r + dr, c + dc
if within_bounds(nr, nc) and bubbles[nr][nc] == color:
count += 1
if count >= 2:
stack = [(r, c)]
while stack:
x, y = stack.pop()
if not marked_for_explosion[x][y]:
marked_for_explosion[x][y] = True
for dr, dc in directions:
nx, ny = x + dr, y + dc
if within_bounds(nx, ny) and bubbles[nx][ny] == color:
stack.append((nx, ny))
for r in range(rows):
for c in range(cols):
if marked_for_explosion[r][c]:
bubbles[r][c] = 0
for c in range(cols):
empty_row = rows - 1
for r in range(rows - 1, -1, -1):
if bubbles[r][c] != 0:
bubbles[empty_row][c] = bubbles[r][c]
if empty_row != r:
bubbles[r][c] = 0
empty_row -= 1
return bubbles
There were 2 more questions but I don't remember it