This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Co-ordinate Compression”.
1. What is co-ordinate compression?
a) process of reassigning co-ordinates to remove gaps
b) inserting gaps in a co-ordinate system
c) removing redundant co-ordinates
d) adding extra gaps
View Answer
Answer: a
Explanation: Co-ordinate compression is the process of reassigning co-ordinates in order to remove gaps. This helps in improving efficiency of a solution.
2. What is the need for co-ordinate compression?
a) for improving time complexity
b) for improving space complexity
c) for improving both time and space complexity
d) for making code simpler
View Answer
Answer: c
Explanation:Co-ordinate compression is the process of reassigning co-ordinates in order to remove gaps. This helps in improving both time and space complexity of a solution.
3. What is the output for the following code?
#include <bits/stdc++.h> using namespace std; void convert(int a[], int n) { vector <pair<int, int> > vec; for (int i = 0; i < n; i++) vec.push_back(make_pair(a[i], i)); sort(vec.begin(), vec.end()); for (int i=0; i<n; i++) a[vec[i].second] = i; } void printArr(int a[], int n) { for (int i=0; i<n; i++) cout << a[i] << " "; } int main() { int arr[] = {10,8,2,5,7}; int n = sizeof(arr)/sizeof(arr[0]); convert(arr , n); printArr(arr, n); return 0; }
a) 4 3 0 1 2
b) 1 2 3 4 5
c) 5 4 1 2 3
d) 0 1 2 3 4
View Answer
Answer: a
Explanation: The given code converts the elements of the input array. They are replaced with their respective position number in the sorted array.
4. What will be the time complexity of given code?
#include <bits/stdc++.h> using namespace std; void convert(int a[], int n) { vector <pair<int, int> > vec; for (int i = 0; i < n; i++) vec.push_back(make_pair(a[i], i)); sort(vec.begin(), vec.end()); for (int i=0; i<n; i++) a[vec[i].second] = i; } void printArr(int a[], int n) { for (int i=0; i<n; i++) cout << a[i] << " "; } int main() { int arr[] = {10,8,2,5,7}; int n = sizeof(arr)/sizeof(arr[0]); convert(arr , n); printArr(arr, n); return 0; }
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Answer: b
Explanation: The time complexity of the given code will be governed by the time complexity of the sorting algorithm used. As this code uses in built sorting of C++ so it will take O(n log n) time.
5. What is the auxiliary space complexity of the given code?
#include <bits/stdc++.h> using namespace std; void convert(int a[], int n) { vector <pair<int, int> > vec; for (int i = 0; i < n; i++) vec.push_back(make_pair(a[i], i)); sort(vec.begin(), vec.end()); for (int i=0; i<n; i++) a[vec[i].second] = i; } void printArr(int a[], int n) { for (int i=0; i<n; i++) cout << a[i] << " "; } int main() { int arr[] = {10,8,2,5,7}; int n = sizeof(arr)/sizeof(arr[0]); convert(arr , n); printArr(arr, n); return 0; }
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer
Answer: b
Explanation: The given code uses an auxiliary space of O(n). It is used by a vector which pairs each element of the array with their respective index number of the original array.
6. What will be the output of the following code?
#include <bits/stdc++.h> using namespace std; void convert(int arr[], int n) { int temp[n]; memcpy(temp, arr, n*sizeof(int)); sort(temp, temp + n); unordered_map<int, int> map; int sort_index = 0; for (int i = 0; i < n; i++) map[temp[i]] = sort_index++; for (int i = 0; i < n; i++) arr[i] = map[arr[i]]; } void printArr(int arr[], int n) { for (int i=0; i<n; i++) cout << arr[i] << " "; } int main() { int arr[] = {3,5,2,4}; int n = sizeof(arr)/sizeof(arr[0]); convert(arr , n); printArr(arr, n); return 0; }
a) 0 2 3 4
b) 1 3 0 2
c) 2 4 1 3
d) 1 2 3 4
View Answer
Answer: b
Explanation: The given code converts the elements of input array. They are replaced with their respective position number in the sorted array.
7. What is the time complexity of the following code?
#include <bits/stdc++.h> using namespace std; void convert(int arr[], int n) { int temp[n]; memcpy(temp, arr, n*sizeof(int)); sort(temp, temp + n); unordered_map<int, int> map; int sort_index = 0; for (int i = 0; i < n; i++) map[temp[i]] = sort_index++; for (int i = 0; i < n; i++) arr[i] = map[arr[i]]; } void printArr(int arr[], int n) { for (int i=0; i<n; i++) cout << arr[i] << " "; } int main() { int arr[] = {10, 20, 15, 12, 11, 50}; int n = sizeof(arr)/sizeof(arr[0]); convert(arr , n); printArr(arr, n); return 0; }
a) O(n)
b) O(1)
c) O(n log n)
d) O(n2)
View Answer
Answer: c
Explanation: The time complexity of the given code will be governed by the time complexity of the sorting algorithm used. As this code uses inbuilt sorting of C++ so it will take O(n log n) time.
8. What will be the auxiliary space complexity of the following code?
a) O(n)
b) O(1)
c) O(log n)
d) O(n log n)
View Answer
Answer: a
Explanation: The given code uses an auxiliary space of O(n). It is used by a vector which pairs each element of the array with their respective index number of the original array.
9. Co-ordinate compression reduces the number of squares in a graph.
a) true
b) false
View Answer
Answer: a
Explanation: The idea behind co-ordinate compression is to reduce the number of squares in a graph by converting them into rectangles of viable size. This reduces the time complexity of traversal.
10. Co-ordinate compression can only be applied in a co-ordinate system problem
a) true
b) false
View Answer
Answer: b
Explanation: Co-ordinate compression technique can be applied where such optimization is suitable. It does not require to co-ordinate system problem only.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.