250+ TOP MCQs on Co-ordinate Compression and Answers

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) 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

Answer: a
Clarification: 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

Answer: c
Clarification: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  
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

Answer: a
Clarification: 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  
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)

Answer: b
Clarification: 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  
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)
Answer: b
Clarification: 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  
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

Answer: b
Clarification: 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  
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)
Answer: c
Clarification: 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?

#include  
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(log n)
d) O(n log n)

Answer: a
Clarification: 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
Clarification: 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
Clarification: Co-ordinate compression technique can be applied where such optimization is suitable. It does not require to co-ordinate system problem only.

Leave a Reply

Your email address will not be published. Required fields are marked *