10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
Trạng thái Đã xong
Bắt đầu vào lúc Chủ Nhật, 20 tháng 10 2024, 1:08 AM
Kết thúc lúc Thứ Ba, 22 tháng 10 2024, 5:39 PM
Thời gian thực 2 Các ngày 16 giờ
hiện
Điểm 7,00/7,00
Điểm 10,00 trên 10,00 (100%)
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 1/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
Câu hỏi 1
Đúng
Đạt điểm 1,00 trên 1,00
Implement all methods in class Queue with template type T. The description of each method is written as comment in
frame code.
#ifndef QUEUE_H
#define QUEUE_H
#include "DLinkedList.h"
template<class T>
class Queue {
protected:
DLinkedList<T> list;
public:
Queue() {}
void push(T item) ;
T pop() ;
T top() ;
bool empty() ;
int size() ;
void clear() ;
};
#endif /* QUEUE_H */
You can use all methods in class DLinkedList without implementing them again. The description of class DLinkedList is written as
comment in frame code.
template <class T>
class DLinkedList
{
public:
class Node; //forward declaration
protected:
Node* head;
Node* tail;
int count;
public:
DLinkedList() ;
~DLinkedList();
void add(const T& e);
void add(int index, const T& e);
T removeAt(int index);
bool removeItem(const T& removeItem);
bool empty();
int size();
void clear();
T get(int index);
void set(int index, const T& e);
int indexOf(const T& item);
bool contains(const T& item);
};
For example:
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 2/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
Test Result
Queue<int> queue;
assert(queue.empty());
assert(queue.size() == 0);
Answer: (penalty regime: 0 %)
Reset answer
1 ▼ void push(T item) {
2 // TODO: Push new element into the end of the queue
3 list.add(item);
4 }
5
6 ▼ T pop() {
7 // TODO: Remove an element in the head of the queue
8
9 return list.removeAt(0);
10
11 }
12
13 ▼ T top() {
14 // TODO: Get value of the element in the head of the queue
15 return list.get(0);
16 }
17
18 ▼ bool empty() {
19 // TODO: Determine if the queue is empty
20 return list.empty();
21 }
22
23 ▼ int size() {
24 // TODO: Get the size of the queue
25 return list.size();
26 }
27
28 ▼ void clear() {
29 // TODO: Clear all elements of the queue
30 list.clear();
31 }
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 3/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
Passed all tests!
Đúng
Marks for this submission: 1,00/1,00.
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 4/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
Câu hỏi 2
Đúng
Đạt điểm 1,00 trên 1,00
Given an array of integers.
Your task is to implement a function with following prototype:
int sumOfMaxSubarray(vector<int>& nums, int k);
The function returns the sum of the maximum value of every consecutive subarray of nums with fixed length k.
Note:
- The iostream, vector, queue and deque libraries have been included and namespace std is being used. No other libraries are
allowed.
- You can write helper functions and classes.
For example:
Test Result
vector<int> nums {1, 2, 4, 3, 6}; 14
int k = 3;
cout << sumOfMaxSubarray(nums, k);
Answer: (penalty regime: 0 %)
Reset answer
1 ▼ int sumOfMaxSubarray(vector<int>& nums, int k) {
2 // STUDENT ANSWER
3 int sum = 0;
4 int n = nums.size();
5 deque<int> q;
6 ▼ for(int i = 0; i < n; i++){
7 ▼ while(!q.empty() && q.back() < i - k + 1){
8 q.pop_back();
9 }
10 ▼ while(!q.empty() && nums[q.front()] <= nums[i]){
11 q.pop_front();
12 }
13 q.push_front(i);
14 if(i >= k - 1) sum += nums[q.back()];
15 }
16 return sum;
17 }
Test Expected Got
vector<int> nums {1, 2, 4, 3, 6}; 14 14
int k = 3;
cout << sumOfMaxSubarray(nums, k);
vector<int> nums {8016}; 8016 8016
int k = 1;
cout << sumOfMaxSubarray(nums, k);
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 5/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
Passed all tests!
Đúng
Marks for this submission: 1,00/1,00.
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 6/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
Câu hỏi 3
Đúng
Đạt điểm 1,00 trên 1,00
Research queue which is implemented in C library at: http://www.cplusplus.com/reference/queue/queue/. You can use library
queue in c++ for this question.
Using queue, complete function void bfs(vector<vector<int>> graph, int start) to traverse all the nodes of the graph from
given start node using Breadth First Search algorithm and data structure queue, and print the order of visited nodes.
You can use below liberaries in this question.
#include <iostream>
#include <vector>
#include <queue>
For example:
Test Result
int init_graph[10][10] = { {0, 1, 1, 0, 1, 0, 1, 0, 1, 0}, 0 1 2 4 6 8 3 7 5 9
{0, 0, 1, 1, 0, 0, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 1, 1, 0, 1, 1},
{1, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
{1, 0, 1, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 1, 1, 0, 1, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 0, 0, 0, 1, 0} };
int n = 10;
vector<vector<int>> graph(n, vector<int>());
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (init_graph[i][j]) graph[i].push_back(j);
}
}
bfs(graph, 0);
Answer: (penalty regime: 0 %)
Reset answer
1 ▼ void bfs(vector<vector<int>> graph, int start) {
2 queue<int> q;
3 int n = graph.size();
4 vector<bool> visited(n, false);
5 visited[start] = true;
6 q.push(start);
7 ▼ while(!q.empty()){
8 int curr = q.front();
9 q.pop();
10 cout << curr << " ";
11
12 ▼ for(int i : graph[curr]){
13 ▼ if(!visited[i]) {
14 visited[i] = true;
15 q.push(i);
16 }
17 }
18 }
19 }
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 7/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
Passed all tests!
Đúng
Marks for this submission: 1,00/1,00.
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 8/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
Câu hỏi 4
Đúng
Đạt điểm 1,00 trên 1,00
Research queue which is implemented in C library at http://www.cplusplus.com/reference/queue/queue/. You can use
library queue in c++ for this question.
Using queue, complete function bool isBipartite(vector<vector<int>> graph) to determine if a graph is bipartite or not (the
graph can be disconnected). In caat https://en.wikipedia.org/wiki/Bipartite_graph.
You can use below liberaries in this question.
#include <iostream>
#include <vector>
#include <queue>
For example:
Test Result
int G[6][6] = { {0, 1, 0, 0, 0, 1}, Yes
{1, 0, 1, 0, 0, 0},
{0, 1, 0, 1, 0, 0},
{0, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 1, 0} };
int n = 6;
vector<vector<int>> graph(n, vector<int>());
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (G[i][j]) graph[i].push_back(j);
}
}
isBipartite(graph) ? cout << "Yes" : cout << "No";
Answer: (penalty regime: 0 %)
Reset answer
1 ▼ bool isBipartite(vector<vector<int>> graph) {
2 int n = graph.size();
3 vector<int> color(n, -1);
4 queue<int> q;
5
6▼ for(int i = 0; i < n; i++){
7▼ if(color[i] == -1) {
8 color[i] = 0;
9 q.push(i);
10 ▼ while(!q.empty()){
11 int u = q.front();
12 q.pop();
13 ▼ for(auto &v : graph[u]){
14 ▼ if(color[v] == -1){
15 color[v] = 1 - color[u];
16 q.push(v);
17 }
18 else if(color[v] == color[u]) return false;
19 }
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 9/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
19 }
20 }
21 }
22 }
23 return true;
24 }
Passed all tests!
Đúng
Marks for this submission: 1,00/1,00.
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 10/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
Câu hỏi 5
Đúng
Đạt điểm 1,00 trên 1,00
Given a n*m grid where each cell in the grid can have a value of 0, 1 or 2, which has the following meaning:
1. Empty cell
2. This cell contains a fresh apple
3. This cell contains a rotten apple
After 1 second, the cell with rotten apple will rot all fresh apples in all the cells adjacent to it (i.e the cells (x+1, y), (x-1, y), (x,
y+1), (x, y-1))
Determine the minimum time (in seconds) required to rot all apples. If this cannot be done, return -1.
Note: iostream, vector, and queue are already included.
Constraint:
1 <= n, m <= 500
Hint: Have you ever heard about breadth-first-search?
Example 1:
Input: grid = {{2,2,0,1}}
Output: -1
Explanation:
The grid is
2201
The apple at (0, 3) cannot be rotten
Example 2:
Input: grid = {{0,1,2},{0,1,2},{2,1,1}}
Output: 1
Explanation:
The grid is
012
012
211
Apples at positions (0,2), (1,2), (2,0)
will rot apples at (0,1), (1,1), (2,2) and (2,1) after 1 second.
For example:
Test Input Result
int rows, cols; 1 4 -1
cin >> rows >> cols; 2 2 0 1
vector<vector<int>> grid(rows, vector<int>(cols));
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) cin >> grid[i][j];
}
cout << secondsToBeRotten(grid);
int rows, cols; 3 3 1
cin >> rows >> cols; 0 1 2
vector<vector<int>> grid(rows, vector<int>(cols)); 0 1 2
for(int i = 0; i < rows; i++) { 2 1 1
for(int j = 0; j < cols; j++) cin >> grid[i][j];
}
cout << secondsToBeRotten(grid);
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 11/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
Answer: (penalty regime: 0 %)
Reset answer
1 // iostream, vector and queue are included
2 // Hint: use breadth-first-search
3
4 ▼ int secondsToBeRotten(vector<vector<int>>& grid) {
5 if(grid.empty()) return 0;
6 int m = grid.size(), n = grid[0].size(), days = 0, tot = 0, cnt = 0;
7 queue<pair<int, int>> rotten;
8 ▼ for(int i = 0; i < m; ++i){
9 ▼ for(int j = 0; j < n; ++j){
10 if(grid[i][j] != 0) tot++;
11 if(grid[i][j] == 2) rotten.push({i, j});
12 }
13 }
14
15 int dx[4] = {0, 0, 1, -1};
16 int dy[4] = {1, -1, 0, 0};
17
18 ▼ while(!rotten.empty()){
19 int k = rotten.size();
20 cnt += k;
21 ▼ while(k--){
22 int x = rotten.front().first, y = rotten.front().second;
23 rotten.pop();
24 ▼ for(int i = 0; i < 4; ++i){
25 int nx = x + dx[i], ny = y + dy[i];
26 if(nx < 0 || ny < 0 || nx >= m || ny >= n || grid[nx][ny] != 1) continue;
27 grid[nx][ny] = 2;
28 rotten.push({nx, ny});
29 }
30 }
31 if(!rotten.empty()) days++;
32 }
33
34 return tot == cnt ? days : -1;
35 }
Test Input Expected Got
int rows, cols; 1 4 -1 -1
cin >> rows >> cols; 2 2 0 1
vector<vector<int>> grid(rows, vector<int>(cols));
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) cin >> grid[i][j];
}
cout << secondsToBeRotten(grid);
int rows, cols; 3 3 1 1
cin >> rows >> cols; 0 1 2
vector<vector<int>> grid(rows, vector<int>(cols)); 0 1 2
for(int i = 0; i < rows; i++) { 2 1 1
for(int j = 0; j < cols; j++) cin >> grid[i][j];
}
cout << secondsToBeRotten(grid);
Passed all tests!
Đúng
Marks for this submission: 1,00/1,00.
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 12/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 13/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
Câu hỏi 6
Đúng
Đạt điểm 1,00 trên 1,00
[Eng] Given a queue of integers of even length, rearrange the elements by interleaving the first half of the queue with the
second half of the queue.
Your task is to implement interleaveQueue function.
stack and queue are included.
[Vie] Cho 1 hàng đợi có số lượng phần tử là số chẵn, sắp xếp lại các phần tử theo quy tắc xen kẽ phần tử ở nửa đầu và
nửa sau của hàng đợi.
Sinh viên cần hiện thực hàm interleaveQueue.
Thư viện stack và queue đã được thêm vào.
For example:
Test Input Result
queue<int> q; 4 1 3 2 4
int n; cin >> n; 1 2 3 4
for (int i = 0; i < n; i++){
int element; cin >> element;
q.push(element);
}
interleaveQueue(q);
while (!q.empty()){
cout << q.front() << ' ';
q.pop();
}
queue<int> q; 6 2 8 4 10 6 12
int n; cin >> n; 2 4 6 8 10 12
for (int i = 0; i < n; i++){
int element; cin >> element;
q.push(element);
}
interleaveQueue(q);
while (!q.empty()){
cout << q.front() << ' ';
q.pop();
}
Answer: (penalty regime: 0 %)
Reset answer
1 ▼ void interleaveQueue(queue<int>& q){
2 if(q.size() % 2 != 0) return;
3 stack<int> s;
4 int halfSize = q.size() / 2;
5
6 ▼ for (int i = 0; i < halfSize; i++) {
7 s.push(q.front());
8 q.pop();
9 }
10
11 ▼ while (!s.empty()) {
12 q.push(s.top());
13 s.pop();
14 }
15
16 ▼ for (int i = 0; i < halfSize; i++) {
17 q.push(q.front());
18 q.pop();
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 14/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
q p p();
19 }
20
21 ▼ for (int i = 0; i < halfSize; i++) {
22 s.push(q.front());
23 q.pop();
24 }
25
26 ▼ while (!s.empty()) {
27 q.push(s.top());
28 s.pop();
29 q.push(q.front());
30 q.pop();
31 }
32 }
Test Input Expected Got
queue<int> q; 4 1 3 2 4 1 3 2 4
int n; cin >> n; 1 2 3 4
for (int i = 0; i < n; i++){
int element; cin >> element;
q.push(element);
}
interleaveQueue(q);
while (!q.empty()){
cout << q.front() << ' ';
q.pop();
}
queue<int> q; 6 2 8 4 10 6 12 2 8 4 10 6 12
int n; cin >> n; 2 4 6 8 10 12
for (int i = 0; i < n; i++){
int element; cin >> element;
q.push(element);
}
interleaveQueue(q);
while (!q.empty()){
cout << q.front() << ' ';
q.pop();
}
Passed all tests!
Đúng
Marks for this submission: 1,00/1,00.
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 15/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
Câu hỏi 7
Đúng
Đạt điểm 1,00 trên 1,00
A nice number is a positive integer that contains only 2's and 5's.
Some nice numbers are: 2, 5, 22, 25, 52, 55, ...
Number 2 is the first nice number.
Given an integer N, return the Nth nice number.
Note: iostream, vector, queue are already included for you.
Constraint:
1 <= n <= 10^6
Example 1:
Input:
n=5
Output:
52
Explanation:
The sequence of nice numbers is 2, 5, 22, 25, 52, 55, ...
The 5th number in this sequence is 52
Example 2:
Input:
n = 10000
Output:
2255522252225
For example:
Test Input Result
int n; 5 52
cin >> n;
cout << nthNiceNumber(n) << endl;
int n; 10000 2255522252225
cin >> n;
cout << nthNiceNumber(n) << endl;
Answer: (penalty regime: 0, 0, 0, 5, 10, ... %)
Reset answer
1 // iostream, vector and queue are included
2 // You can write helper methods
3
4 ▼ long long nthNiceNumber(int n) {
5 queue<long long> q;
6 q.push(2); // init the stack with 2 and 5
7 q.push(5);
8
9 int nE = 2;
10 while (nE < n)
11 ▼ {
12 q.push(q.front() * 10 + 2);
13 nE++;
14
15 if (nE == n) break;
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 16/17
10/22/24, 5:39 PM Queue: Xem lại lần làm thử | BK-LMS
15 if (nE == n) break;
16
17 q.push(q.front() * 10 + 5);
18 nE++;
19
20 q.pop();
21 }
22 int size = q.size();
23 while (size-- > 1) q.pop();
24 return q.front();
25 }
Test Input Expected Got
int n; 5 52 52
cin >> n;
cout << nthNiceNumber(n) << endl;
int n; 10000 2255522252225 2255522252225
cin >> n;
cout << nthNiceNumber(n) << endl;
Passed all tests!
Đúng
Marks for this submission: 1,00/1,00.
https://lms.hcmut.edu.vn/mod/quiz/review.php?attempt=4596338&cmid=445607 17/17
