Q1:
void interleaveQueue(queue<int>& q)
{
queue<int> queue1;
queue<int> queue2;
int size = q.size();
int halfSize = size / 2;
for (int i = 0; i < halfSize; i++)
{
queue1.push(q.front());
q.pop();
}
for (int i = 0; i < halfSize; i++)
{
queue2.push(q.front());
q.pop();
}
for (int i = 0; i < halfSize; i++)
{
q.push(queue1.front());
queue1.pop();
q.push(queue2.front());
queue2.pop();
}
Q2:
bool isBipartite(vector<vector<int>> graph)
{
int n = graph.size();
std::vector<int> color(n, -1);
std::queue<int> q;
for (int i = 0; i < n; i++) {
if (color[i] == -1) {
color[i] = 0;
q.push(i);
while (!q.empty()) {
int curr = q.front();
q.pop();
for (int neighbor : graph[curr]) {
if (color[neighbor] == -1) {
color[neighbor] = 1 - color[curr];
q.push(neighbor);
} else if (color[neighbor] == color[curr]) {
return false;
}
}
}
}
}
return true;
}
Q3:
void bfs(vector<vector<int>> graph, int start)
{
int n = graph.size();
std::vector<bool> visited(n, false);
std::queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty())
{
int current = q.front();
q.pop();
std::cout << current << " ";
for (int neighbor : graph[current])
{
if (!visited[neighbor])
{
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
Q4:
void push(T item)
{
list.add(item);
}
T pop()
{
if (empty())
{
throw std::out_of_range("Queue is empty");
}
T frontItem = list.get(0);
list.removeAt(0);
return frontItem;
T top()
{
if (empty())
{
throw std::out_of_range("Queue is empty");
}
return list.get(0);
}
bool empty()
{
return list.empty();
int size()
{
return list.size();
}
void clear()
{
list.clear();
}
Q5:
long long nthNiceNumber(int n)
{
int i = 0;
std::vector<long long> niceNumbers;
niceNumbers.push_back(2);
niceNumbers.push_back(5);
if (n == 1)
{
return niceNumbers[0];
}
if (n == 2)
{
return niceNumbers[1];
}
int count = 2;
while (count < n)
{
niceNumbers.push_back(niceNumbers[i] * 10 + 2);
niceNumbers.push_back(niceNumbers[i] * 10 + 5);
count += 2;
i++;
return niceNumbers[n - 1];
}
Q6:
int secondsToBeRotten(vector<vector<int>>& grid)
{
int rows = grid.size();
int cols = grid[0].size();
int freshApples = 0;
int minutes = 0;
std::queue<std::pair<int, int>> rottenApples;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (grid[i][j] == 1)
{
freshApples++;
}
else if (grid[i][j] == 2)
{
rottenApples.push({i, j});
}
}
}
if (freshApples == 0)
{
return 0;
}
std::vector<std::pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -
1}};
while (!rottenApples.empty())
{
int size = rottenApples.size();
bool hasRotten = false;
for (int i = 0; i < size; i++)
{
int x = rottenApples.front().first;
int y = rottenApples.front().second;
rottenApples.pop();
for (const auto& direction : directions) {
int newX = x + direction.first;
int newY = y + direction.second;
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols &&
grid[newX][newY] == 1)
{
grid[newX][newY] = 2;
rottenApples.push({newX, newY});
freshApples--;
hasRotten = true;
}
}
}
if (hasRotten)
{
minutes++;
}
}
if (freshApples > 0)
{
return -1;
}
return minutes;
}
Q7:
int sumOfMaxSubarray(vector<int>& nums, int k)
{
std::deque<int> dq;
int sum = 0;
for (int i = 0; i < nums.size(); i++)
{
while (!dq.empty() && dq.front() <= i - k)
{
dq.pop_front();
}
while (!dq.empty() && nums[dq.back()] < nums[i])
{
dq.pop_back();
}
dq.push_back(i);
if (i >= k - 1)
{
sum += nums[dq.front()];
}
}
return sum;
}
