Introduction
This is made in regard to crack Placement who specifically asks problems on DSA. It is made in align with C++ language as majorly people use this and its also offers advantage and wide support with resources and cpp coding community.
It will include basic introduction to arrays to advanced topics with questions to practice. And if you follow this you can start feeling confidence in your problem-solving skills that eventually helps you to crack placement.
You can share your suggestions with us by commenting below, we sure look forward to them, and help us to make best course with your support. This page will update daily as we go deeper into this, make sure you bookmark this.(alert-passed)
Data Structures
Data structures are a way of organizing and storing data in a way that makes it efficient to access and manipulate. They can be classified into two types: primitive and non-primitive.
- Primitive data structures are the most basic type of data structures. They store data of a single type, such as integers, characters, or floating-point numbers. Examples of primitive data structures include integers, characters, floats, and Booleans.
- Non-primitive data structures are more complex than primitive data structures. They can store data of multiple types, and they can be used to represent more complex data structures, such as linked lists, trees, and graphs. Examples of non-primitive data structures include arrays, lists, stacks, and queues.
1D Arrays
A 1D array in C++ is a collection of elements of the same type that are stored in a single, linear sequence. The elements of a 1D array are accessed by their index, which is a number that indicates the position of the element in the array.
For example, the following code defines a 1D array called numbers that stores 5 integers:
int numbers[5];(code-box)
The index of the first element in the array is 0, the index of the second element is 1, and so on. To access the element at a specific index, you can use the [] operator. For example, the following code will print the value of the element at index 2 of the numbers array:
int value = numbers[2];(code-box)
1D arrays are a very versatile data structure, and they can be used to store a variety of data. For example, you could use a 1D array to store the scores of a group of students, the names of a list of employees, or the coordinates of a set of points.
Problem 1: Write a program that reads 10 integers from the user and prints the sum of the even numbers.
Solution:
#include <iostream>
using namespace std;
int main() {
int numbers[10];
int sum = 0;
for (int i = 0; i < 10; i++) {
cin >> numbers[i];
if (numbers[i] % 2 == 0) {
sum += numbers[i];
}
}
cout << "The sum of the even numbers is " << sum << endl;
return 0;
}(code-box)
Problem 2: Write a program that reads 10 integers from the user and prints the largest and smallest numbers.
Solution:
#include <iostream>
using namespace std;
int main() {
int numbers[10];
int largest = numbers[0];
int smallest = numbers[0];
for (int i = 1; i < 10; i++) {
cin >> numbers[i];
if (numbers[i] > largest) {
largest = numbers[i];
}
if (numbers[i] < smallest) {
smallest = numbers[i];
}
}
cout << "The largest number is " << largest << endl;
cout << "The smallest number is " << smallest << endl;
return 0;
}(code-box)
Problem 3: Write a program that reads 10 integers from the user and prints the second largest number.
Solution:
#include <iostream>
using namespace std;
int main() {
int numbers[10];
int largest = numbers[0];
int second_largest = numbers[1];
for (int i = 2; i < 10; i++) {
cin >> numbers[i];
if (numbers[i] > largest) {
second_largest = largest;
largest = numbers[i];
} else if (numbers[i] > second_largest) {
second_largest = numbers[i];
}
}
cout << "The second largest number is " << second_largest << endl;
return 0;
}(code-box)
Explanation:
This problem is a bit more challenging than the previous two problems, because it requires us to keep track of the two largest numbers in the array. We can do this by initializing two variables, largest and second_largest, to the first two elements in the array. Then, we can iterate through the rest of the array, and if we find a number that is larger than largest, we update largest to be that number. If we find a number that is larger than second_largest, but not larger than largest, we update second_largest to be that number.
At the end of the loop, we will have largest set to the largest number in the array, and second_largest set to the second largest number. We can then print the value of second_largest to the console.
2D Arrays
A 2D array is a data structure that stores data in a two-dimensional table. Each element in the array is stored at a specific row and column location. The rows and columns of a 2D array are often referred to as dimensions.
For example, a 2D array with 3 rows and 4 columns would have a total of 12 elements. The first element would be stored at row 0, column 0, the second element would be stored at row 0, column 1, and so on.
2D arrays are often used to store data that is naturally organized in a tabular format. For example, you could use a 2D array to store a chessboard, a spreadsheet, or a map.
Declaration of 2D arrays
The declaration of a 2D array in C++ is similar to the declaration of a 1D array. The only difference is that the declaration must specify the number of rows and columns in the array.
For example, the following code declares a 2D array called numbers with 3 rows and 4 columns:
int numbers[3][4];
Accessing elements in 2D arrays
The elements in a 2D array are accessed using two indices: the row index and the column index. The row index specifies the row of the element, and the column index specifies the column of the element.
For example, the following code prints the value of the element at row 1, column 2 of the numbers array:
int value = numbers[1][2];(code-box)
Memory representation of 2D arrays
2D arrays are stored in memory in a row-major order. This means that the elements in a row are stored contiguously in memory, and the rows are stored one after the other.
For example, the following diagram shows the memory representation of a 2D array with 3 rows and 4 columns:
Row 0: [0, 1, 2, 3]
Row 1: [4, 5, 6, 7]
Row 2: [8, 9, 10, 11](code-box)
Advantages of 2D arrays
2D arrays have several advantages over other data structures, such as linked lists and trees.
- It is easy to understand and use.
- 2D arrays are efficient for storing data that is naturally organized in a tabular format.
- 2D arrays can be used to represent a wide variety of data, such as chessboards, spreadsheets, and maps.
Disadvantages of 2D arrays
2D arrays also have some disadvantages, such as:
- 2D arrays can be inefficient for storing data that is not naturally organized in a tabular format.
- 2D arrays can be difficult to iterate over, especially if the rows and columns are not of equal length.
Problem1 : Write a program that reads a 2D array of integers from the user and prints the sum of all the elements in the array.
Solution:
#include <iostream>
using namespace std;
int main() {
int numbers[3][4];
int sum = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
cin >> numbers[i][j];
sum += numbers[i][j];
}
}
cout << "The sum of all the elements in the array is " << sum << endl;
return 0;
}(code-box)
Explanation:
This code first declares a 2D array called numbers with 3 rows and 4 columns. Then, it iterates through the array, adding the value of each element to the running sum. Finally, it prints the value of the running sum to the console.
Linked List
A linked list is a data structure that stores data in a linear order, but the elements are not stored in contiguous memory locations. Instead, each element (called a node) contains a pointer to the next element in the list. The first element in the list is called the head, and the last element is called the tail.
Linked lists are a dynamic data structure, which means that they can grow or shrink as needed. This makes them a good choice for applications where the size of the data set is not known in advance.
Here is an example of a linked list in C++:
struct Node {
int data;
Node* next;
};(code-box)
This defines a struct called Node. Each Node has two members: data and next. data stores the data for the node, and next is a pointer to the next node in the list.
Node* head = nullptr;(code-box)
This declares a Node pointer called head. The head pointer points to the first node in the list.
void addNode(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* currentNode = head;
while (currentNode->next != nullptr) {
currentNode = currentNode->next;
}
currentNode->next = newNode;
}
}(code-box)
This function adds a new node to the linked list. The function takes an int as input, which is the data for the new node. The function first creates a new Node object, and then sets the data and next members of the new node.
If the head pointer is nullptr, then the new node is the first node in the list. Otherwise, the function finds the last node in the list, and then sets the next member of the last node to the new node.
void printList() {
Node* currentNode = head;
while (currentNode != nullptr) {
std::cout << currentNode->data << std::endl;
currentNode = currentNode->next;
}
}(code-box)
This function prints the contents of the linked list. The function starts at the head node, and then iterates through the list, printing the data for each node. The function stops iterating when the currentNode pointer is nullptr, which indicates that the end of the list has been reached.
Comment Below, How are you feeling with this?(alert-success)
