Question 1:
There is a cleaning robot which is cleaning a rectangular grid of size N x M, represented by array R consisting of N strings. Rows are numbered from 0 to N-1 (from top to bottom) and columns are numbered from 0 to M-1 (from left to right).
The robot starts cleaning in the top-left corner, facing rightwards. It moves in a straight line for as long as it can, in other words, while there is an unoccupied grid square ahead of it. When it cannot move forward, it rotates 90 degrees clockwise and tries to move forward again until it encounters another obstacle, and so on. Dots in the array (".") represent empty squares and "X"s represent occupied squares (ones the robot cannot move through). Each square that the robot occupied at least once is considered clean. The robot moves indefinitely.
Write a function:
class Solution { public int solution (string[] R); }
that, given an array R consisting of N strings, each of length M. representing the grid, returns the number of clean squares.
Examples:
Given A = ["...Χ..", "....XX", "....."], your function should return 6.
The robot starts at (0,0), facing rightwards, and moves to (0,2), where it turns due to the obstacle at (0,3). Then it goes down from (0,2) to (1,2), where it changes direction again due to another obstacle. Next it goes left from (1, 2) to (1,0), where it turns once because of the grid boundary, then it moves once and turns once more, which makes it stand again at position (0,0) facing rightwards, just as at the beginning, which means it will now repeat the loop indefinitely. The total number of cleaned squares is 6.
Question 2:
You are given two tables describing theater plays and reservations for these plays in specific theaters.
create table plays (
id integer not null,
title varchar(40) not null,
writer varchar(40) not null,
unique(id)
);
create table reservations (
id integer not null,
play_id integer hot null,
number_of_tickets integer not null,
theater varchar(40) not null,
unique (id)
);
Write an SQL query that counts the total number of tickets reserved for each play. The table of results should contain three columns: id (id of play), title (title of play) and reserved_tickets (total number of reserved tickets for play). Rows should be ordered by decreasing reserved_tickets. In the case of a tie, rows should be sorted by increasing id of play.
int solution(vector<string> &R)
{
// Get the dimensions of the grid
int N = R.size(); // Number of rows
int M = R[0].size(); // Number of columns
// Initialize a 3D vector to keep track of visited squares.
// Now, 3rd dimension will represent 4 directions (0: right, 1: down, 2: left, 3: up) to which movement is already performed
vector<vector<vector<bool>>> visited(N, vector<vector<bool>>(M, vector<bool>(4, false)));
// Initialize the robot's position and direction
int x = 0; // Row index
int y = 0; // Column index
int d = 0; // Direction (0: right, 1: down, 2: left, 3: up)
// Define the offsets for moving in each direction
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
// Loop until the robot stops moving
while (true)
{
// Try to move forward in the current direction
int nx = x + dx[d];
int ny = y + dy[d];
// check if the current direction from the cell has already been visited or not
if (visited[x][y][d])
{
// if yes then even if we move forward, we will get same result as it is in a loop
break;
}
else
{
// Mark the current square with direction tried as visited
visited[x][y][d] = true;
// Check if the next square is valid and unoccupied
if (nx >= 0 && nx < N && ny >= 0 && ny < M && R[nx][ny] == '.')
{
// Move to the next square
x = nx;
y = ny;
}
else
{
// Rotate 90 degrees clockwise
d = (d + 1) % 4;
}
}
}
// Initialize the number of clean squares to zero
int clean = 0;
// Now get count of unique cells cleaned by robot
// we can check this by iterating over visited 3D array where in each cell we will check if any 4 directions has true set
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (visited[i][j][0] || visited[i][j][1] || visited[i][j][2] || visited[i][j][3])
clean++;
}
}
return clean;
}Q2
SELECT plays.id, plays.title, SUM(reservations.number_of_tickets) AS reserved_tickets
FROM plays
JOIN reservations ON plays.id = reservations.play_id
GROUP BY plays.id, plays.title
ORDER BY reserved_tickets DESC, plays.id;