Array List

Bài 1:

Implement methods ensureCapacity, add, size in template

class ArrayList representing the array list with type T with the initialized frame. The
description of each method is given in the code.

template <class T>

class ArrayList {

protected:

T* data; // dynamic array to store the list's items

int capacity; // size of the dynamic array

int count; // number of items stored in the array

public:

ArrayList(){capacity = 5; count = 0; data = new T[5];}

~ArrayList(){ delete[] data; }

void add(T e);

void add(int index, T e);

int size();

void ensureCapacity(int index);

};

template<class T>

void ArrayList<T>::ensureCapacity(int cap){

/*

if cap > capacity:

new_capacity = capacity * 1.5;

create new array with new_capacity

else: do nothing

*/

if (cap <= capacity) return;

int new_capacity = capacity * 1.5;

 if (new_capacity < cap) new_capacity = cap;

T* newData = new T[new_capacity];

for (int i = 0; i < count; i++) {

newData[i] = data[i];

delete[] data;

data = newData;

capacity = new_capacity;

template <class T>

void ArrayList<T>::add(T e) {

/* Insert an element into the end of the array. */

this->ensureCapacity(this->count + 1);

this->data[count++] = e;

template<class T>

void ArrayList<T>::add(int index, T e) {

/*

Insert an element into the array at given index.

if index is invalid:

throw std::out_of_range("the input index is out of range!");

*/

if (index < 0 || index > count) {

throw std::out_of_range("the input index is out of range!");

ensureCapacity(count + 1);

for (int i = count; i > index; i--) {

data[i] = data[i - 1];

}
 data[index] = e;

count++;

template<class T>

int ArrayList<T>::size() {

/* Return the length (size) of the array */

return count;

Bài 2: Implement methods removeAt, removeItem, clear in template

class ArrayList representing the singly linked list with type T with the initialized
frame. The description of each method is given in the code.

template <class T>

class ArrayList {

protected:
T* data; // dynamic array to store the list's items
int capacity; // size of the dynamic array
int count; // number of items stored in the array

public:
ArrayList(){capacity = 5; count = 0; data = new T[5];}
~ArrayList(){ delete[] data; }

void add(T e);

void add(int index, T e);
int size();
bool empty();
void clear();
T get(int index);
void set(int index, T e);
int indexOf(T item);
bool contains(T item);
T removeAt(int index);
bool removeItem(T item);

void ensureCapacity(int index);

};

template<class T>
T ArrayList<T>::removeAt(int index){

/*

Remove element at index and return removed value

if index is invalid:

throw std::out_of_range("index is out of range");

*/

if(index < 0 || index >= count)

throw std::out_of_range("index is out of range");

T removed = data[index];

// shift left

for (int i = index; i < count - 1; i++) {

data[i] = data[i + 1];

count--;

return removed;

template<class T>

bool ArrayList<T>::removeItem(T item){

/* Remove the first apperance of item in array and return true, otherwise return false
*/

for (int i = 0; i < count; i++){

if (data[i] == item) {

removeAt(i);

return true;

return false;

template<class T>

void ArrayList<T>::clear(){

/*
 Delete array if array is not NULL

Create new array with: size = 0, capacity = 5

*/

if (data != nullptr) {

delete[] data;

capacity = 5;

count = 0;

data = new T[capacity];

Bài 3: Implement methods Get, set, clear, empty, indexOf, contains in template
class ArrayList representing the array list with type T with the initialized
frame. The description of each method is given in the code.

template <class T>

class ArrayList {

protected:

T* data; // dynamic array to store the list's items

int capacity; // size of the dynamic array

int count; // number of items stored in the array

public:

ArrayList(){capacity = 5; count = 0; data = new T[5];}

~ArrayList(){ delete[] data; }

void add(T e);

void add(int index, T e);
int size();
bool empty();
void clear(); //remove data and set the list to the initial condition
T get(int index); //get the element at the index, if the index is out of
range, "throw std::out_of_range("index is out of range");"

void set(int index, T e); //set the index position in the list with the value e
int indexOf(T item); //get the first index of item in the list, else return -1
bool contains(T item); //check if the item is in the list
T removeAt(int index);
bool removeItem(T item);

};
Notice: You just have to implement the methods: set, get, clear, empty,
indexOf, contains. Other methods have been implemented already.

template<class T>

T ArrayList<T>::get(int index) {

if (index < 0 || index >= count) {

throw std::out_of_range("Index is out of range");

return data[index];

template<class T>

void ArrayList<T>::set(int index, T e) {

if (index < 0 || index >= count) {

throw std::out_of_range("Index is out of range");

data[index] = e;

template<class T>

void ArrayList<T>::clear() {

delete[] data;

capacity = 5;

count = 0;

data = new T[capacity];

template<class T>

bool ArrayList<T>::empty() {

return count == 0;

template<class T>
int ArrayList<T>::indexOf(T item) {

for (int i = 0; i < count; i++) {

if (data[i] == item) return i;

return -1;

template<class T>

bool ArrayList<T>::contains(T item) {

return indexOf(item) != -1;

Bài 4:

Given an array of integers nums and a two-dimension array of

integers operations.

Each operation in operations is represented in the form {L, R, X}. When

applying an operation, all elements with index in range [L, R] (include L and R)
increase by X.

Your task is to implement a function with following prototype:

vector<int> updateArrayPerRange(vector<int>& nums, vector<vector<int>>&

operations);

The function returns the array after applying all operation in operations.

vector<int> updateArrayPerRange(vector<int>& nums, vector<vector<int>>&

operations) {

// STUDENT ANSWER

int n = [Link]();

vector<int> diff(n + 1, 0);

for (auto& op : operations) {

int L = op[0], R = op[1], X = op[2];

diff[L] += X;

if (R + 1 < n) diff[R + 1] -= X;
 }

int add = 0;

for (int i = 0; i < n; i++) {

add += diff[i];

nums[i] += add;

return nums;

Bài 5: Given an array of integers.

Your task is to implement a function with the following prototype:

bool consecutiveOnes(vector<int>& nums);

The function returns if all the 1s appear consecutively in nums. If nums does
not contain any elements, please return true

Note:

- The iostream and vector libraries have been included and namespace std are
being used. No other libraries are allowed.

- You can write helper functions.

- Do not use global variables in your code.

bool consecutiveOnes(vector<int>& nums) {

// STUDENT ANSWER

if ([Link]()) return true;

bool seenOne = false;

bool endedBlock = false;

for (int x : nums) {

if (x == 1) {

if (endedBlock) return false;

seenOne = true;
 } else {

if (seenOne) endedBlock = true;

return true;

Bài 6: The prices of all cars of a car shop have been saved as an array called N.
Each element of the array N is the price of each car in shop. A person, with the
amount of money k want to buy as much cars as possible.

Request: Implement function

buyCar(int* nums, int length, int k);

Where nums is the array N, length is the size of this array and k is the amount
of money the person has. Find the maximum cars this person can buy with his
money, and return that number.

Example:

nums=[90, 30, 20, 40, 50]; k=90;

The result is 3, he can buy the cars having index 1, 2, 3 (first index is 0).

Note: The library iostream, 'algorithm' and using namespace std have been
used. You can add other functions but you are not allowed to add other
libraries.

int buyCar(int* nums, int length, int k) {

sort(nums, nums + length);

int sum = 0, count = 0;

for (int i = 0; i < length; i++)

if (sum + nums[i] <= k)

sum += nums[i];

count++;
 }

else

break;

return count;

Bài 7:

Given an array of integers.

Your task is to implement a function with following prototype:

int equalSumIndex(vector<int>& nums);

The function returns the smallest index i such that the sum of the numbers to
the left of i is equal to the sum of the numbers to the right.

If no such index exists, return -1.

Note:

- The iostream and vector libraries have been included and namespace std is
being used. No other libraries are allowed.

- You can write helper functions.

int equalSumIndex(vector<int>& nums) {

// STUDENT ANSWER

int total = 0;

for (int n : nums)

total += n;

int leftSum = 0;

for (int i = 0; i < (int)[Link](); i++)

int rightSum = total - leftSum - nums[i];

if (leftSum == rightSum)
 return i;

leftSum += nums[i];

return -1;

Bài 8:

Given an array of strings.

Your task is to implement a function with following prototype:

int longestSublist(vector<string>& words);

The function returns the length of the longest subarray where all words share
the same first letter.

Note:

- The iostream and vector libraries have been included and namespace std is
being used. No other libraries are allowed.

- You can write helper functions

int longestSublist(vector<string>& words)

if ([Link]())

return 0;

int maxLen = 1;

int currentLen = 1;

for (int i = 1; i < (int)[Link](); i++)

if (!words[i].empty() && !words[i - 1].empty() &&

words[i][0] == words[i - 1][0])

currentLen++;

}
 else

currentLen = 1;

if (currentLen > maxLen)

maxLen = currentLen;

return maxLen;

Singlylinked List

Bài 1: Implement methods add, size in template class SLinkedList (which

implements List ADT) representing the singly linked list with type T with the initialized
frame. The description of each method is given in the code.

template <class T>

void SLinkedList<T>::add(const T& e) {

/* Insert an element into the end of the list. */

Node* tmp = new Node(e);

if (head == NULL) {

head = tail = tmp;

}else {

tail->next = tmp;

tail = tmp;

count++;

template<class T>

void SLinkedList<T>::add(int index, const T& e) {

 /* Insert an element into the list at given index. */

if(index <0 || index > count)

throw std::out_of_range("The index is out of range!");

if (index == count)

return this->add(e);

if (index == 0){

Node* tmp = new Node(e);

tmp->next = this->head;

this->head = tmp;

this->count++;

}else {

Node* tmp = new Node(e);

Node* prev = this->head;

for (int i = 0; i < index - 1; i++){

prev = prev->next;

tmp->next = prev->next;

prev->next = tmp;

this->count++;

template<class T>

int SLinkedList<T>::size() {

/* Return the length (size) of list */

return count;

}
Bài 2: Implement methods get, set, empty, indexOf, contains in template
class SLinkedList (which implements List ADT) representing the singly linked list
with type T with the initialized frame. The description of each method is given in the
code.

template<class T>

T SLinkedList<T>::get(int index) {

/* Give the data of the element at given index in the list. */

if (index < 0 || index >= count)

throw std::out_of_range("The index is out of range!");

Node* cur = head;

for (int i = 0; i < index; i++) {

cur = cur->next;

return cur->data;

template <class T>

void SLinkedList<T>::set(int index, const T& e) {

/* Assign new value for element at given index in the list */

if (index < 0 || index >= count)

throw std::out_of_range("The index is out of range!");

Node* cur = head;

for (int i = 0; i < index; i++) {

cur = cur->next;

cur->data = e;

template<class T>

bool SLinkedList<T>::empty() {

/* Check if the list is empty or not. */

 return count == 0;

template<class T>

int SLinkedList<T>::indexOf(const T& item) {

/* Return the first index wheter item appears in list, otherwise return -1 */

Node* cur = head;

int idx = 0;

while (cur != NULL) {

if (cur->data == item) return idx;

cur = cur->next;

idx++;

return -1;

template<class T>

bool SLinkedList<T>::contains(const T& item) {

/* Check if item appears in the list */

return indexOf(item) != -1;

Bài 3: Implement methods removeAt, removeItem, clear in template

class SLinkedList (which implements List ADT) representing the singly linked list
with type T with the initialized frame. The description of each method is given in the
code.

template <class T>

T SLinkedList<T>::removeAt(int index)

if (index < 0 || index >= count)

throw std::out_of_range("The index is out of range!");

Node* temp = head;

T removedData;
 // Case 1: remove head

if (index == 0)

removedData = head->data;

head = head->next;

delete temp;

count--;

if (count == 0)

tail = nullptr;

return removedData;

// Case 2: remove at middle or tail

Node* prev = nullptr;

for (int i = 0; i < index; i++)

prev = temp;

temp = temp->next;

removedData = temp->data;

prev->next = temp->next;

if (temp == tail)

tail = prev;

delete temp;

count--;

return removedData;

template <class T>

bool SLinkedList<T>::removeItem(const T& item)

if (head == nullptr)

return false;

Node* temp = head;

Node* prev = nullptr;

if (temp->data == item)

head = head->next;

delete temp;

count--;

if (count == 0)

tail = nullptr;

return true;

while (temp != nullptr)

if (temp->data == item)

prev->next = temp->next;

if (temp == tail)

tail = prev;

delete temp;

count--;

return true;

prev = temp;

temp = temp->next;
 }

return false;

template <class T>

void SLinkedList<T>::clear()

Node* current = head;

while (current != nullptr)

Node* nextNode = current->next;

delete current;

current = nextNode;

head = nullptr;

tail = nullptr;

count = 0;

Bài 4: Class LLNode representing a node of singly linked lists is declared as below:

class LLNode {

public:

int val;

LLNode* next;

LLNode(); // Constructor: val = 0, next = nullptr

LLNode(int val, LLNode* next); // Constructor with customized data

Given a singly linked list head node.

Your task is to implement a function with following prototype:

LLNode* reverseLinkedList(LLNode* head);

The function returns head node of the reversed singly linked list.

LLNode* reverseLinkedList(LLNode* head) {

 // STUDENT ANSWER

LLNode* prev = nullptr;

LLNode* curr = head;

LLNode* next = nullptr;

while (curr != nullptr)

next = curr->next;

curr->next = prev;

prev = curr;

curr = next;

return prev;

Bài 5: Class LLNode is used to store a node in a singly linked list, described on the
following:

class LLNode {

public:

int val;

LLNode* next;

LLNode();

LLNode(int val, LLNode* next);

Where val is the value of node, next is the pointer to the next node.

Request: Implement function:

LLNode* addLinkedList(LLNode* l0, LLNode* l1);

Where l0, l1 are two linked lists represented positive integers, each node is a digit, the
head is the least significant digit (the value of each node is between 0 and 9, the length
of each linked list is between 0 and 100000). This function returns the linked list
representing the sum of the two integers.

Example:

Given l0 = [2, 3] (representing 32) and l1 = [1, 8] (representing 81). The result would
be l0 = [3, 1, 1] (representing 32 + 81 = 113).

Note:
In this exercise, the libraries iostream, string, cstring, climits, utility, vector,
list, stack, queue, map, unordered_map, set, unordered_set, functional, algorithm has
been included and namespace std are used. You can write helper functions and classes.
Importing other libraries is allowed, but not encouraged, and may result in unexpected
errors.

LLNode* addLinkedList(LLNode* l0, LLNode* l1) {

// STUDENT ANSWER

LLNode* dummy = new LLNode(0, nullptr);

LLNode* curr = dummy;

int carry = 0;

while (l0 != nullptr || l1 != nullptr || carry != 0) {

int x = (l0 != nullptr) ? l0->val : 0;

int y = (l1 != nullptr) ? l1->val : 0;

int sum = x + y + carry;

carry = sum / 10;

curr->next = new LLNode(sum % 10, nullptr);

curr = curr->next;

if (l0 != nullptr) l0 = l0->next;

if (l1 != nullptr) l1 = l1->next;

LLNode* result = dummy->next;

delete dummy;

return result;

Bài 6: Class LLNode representing a node of singly linked lists is declared as below:

class LLNode {

public:
 int val;

LLNode* next;

LLNode(); // Constructor: val = 0, next = nullptr

LLNode(int val, LLNode* next); // Constructor with customized data

Given a singly linked list head node and a integer k.

Your task is to implement a function with following prototype:

LLNode* rotateLinkedList(LLNode* head, int k);

The function returns head node of the rotated singly linked list obtained after rotate the
linked list to the right by k places.

LLNode* rotateLinkedList(LLNode* head, int k) {

// STUDENT ANSWER

if (head == nullptr || head->next == nullptr || k == 0)

return head;

int length = 1;

LLNode* tail = head;

while (tail->next != nullptr) {

tail = tail->next;

length++;

k = k % length;

if (k == 0)

return head;

tail->next = head;
 int stepsToNewTail = length - k - 1;

LLNode* newTail = head;

for (int i = 0; i < stepsToNewTail; i++)

newTail = newTail->next;

LLNode* newHead = newTail->next;

newTail->next = nullptr;

return newHead;

Bài 7:

lass LinkedList is used to represent single linked list, described as the

following:

class LinkedList {
public:
class Node;
private:
Node* head;
Node* tail;
int size;
public:
class Node {
private:
int value;
Node* next;
friend class LinkedList;
public:
Node() {
this->next = NULL;
}
Node(Node* node) {
this->value = node->value;
this->next = node->next;
}
Node(int value, Node* next = NULL) {
this->value = value;
this->next = next;
}
};
LinkedList(): head(NULL), tail(NULL), size(0) {};
void partition(int k);
};
In this class; head, tail and size are the pointers of the first element, the last
element and size of linked list.

Request: Implement function

void LinkedList::partition(int k)

void LinkedList::partition(int k) {

if (head == NULL || head->next == NULL)

return;

Node *lessHead = NULL, *lessTail = NULL;

Node *equalHead = NULL, *equalTail = NULL;

Node *greaterHead = NULL, *greaterTail = NULL;

Node* curr = head;

while (curr != NULL) {

Node* nextNode = curr->next;

curr->next = NULL;

if (curr->value < k) {

if (!lessHead) lessHead = lessTail = curr;

else {

lessTail->next = curr;

lessTail = curr;

} else if (curr->value == k) {

if (!equalHead) equalHead = equalTail = curr;

else {

equalTail->next = curr;

equalTail = curr;

} else {

if (!greaterHead) greaterHead = greaterTail = curr;

 else {

greaterTail->next = curr;

greaterTail = curr;

curr = nextNode;

Node* newHead = NULL;

Node* newTail = NULL;

if (lessHead) {

newHead = lessHead;

newTail = lessTail;

if (equalHead) {

if (!newHead) newHead = equalHead;

else newTail->next = equalHead;

newTail = equalTail;

if (greaterHead) {

if (!newHead) newHead = greaterHead;

else newTail->next = greaterHead;

newTail = greaterTail;

head = newHead;

tail = newTail;

if (tail) tail->next = NULL;

}
Bài 8:

Polynomials is an important application of arrays and linked lists. A polynomial

is composed of different terms where each of them holds a coefficient and an
exponent. A polynomial p(x) is the expression in variable x which is in the form
(anxn + an-1xn-1 + .... + a1x+ a0), where an, an-1, ...., a0 fall in the category of real
numbers and 'n' is the non-negative integer, which is called the degree of
polynomial.

Example: 10x2 + 26x, here 10 and 26 are coefficients and 2, 1 is its exponential value.

Points to keep in Mind while working with Polynomials:

- The sign of each coefficient and exponent is stored within the coefficient and the
exponent itself.
- The storage allocation for each term in the polynomial must be done in descending
order of their exponent.

In this question, complete SLinkedList class is included (Check the IList documentation
under Lab 1 for details on the class and its methods). You should use this class to
complete your Polynomial class with initialized frame as following. This task is implement
insertTerm to insert a term into a polynomial.

void Polynomial::insertTerm(const Term& term) {

// STUDENT ANSWER

if ([Link] == 0)

return;

for (int i = 0; i < terms->size(); i++) {

Term curr = terms->get(i);

if ([Link] == [Link]) {

[Link] += [Link];

if ([Link] == 0) {

terms->removeAt(i);

} else {

terms->set(i, curr);

}
 return;

if ([Link] > [Link]) {

terms->add(i, term);

return;

terms->add(term);

void Polynomial::insertTerm(double coeff, int exp) {

// STUDENT ANSWER

Term t(coeff, exp);

insertTerm(t);