**DOWNLOAD FREE PDF** **<<CLICK HERE>>**

## Co-ordinate Compression Multiple choice Questions and Answers (MCQs)

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

What is co-ordinate compression?

process of reassigning co-ordinates to remove gaps | |

inserting gaps in a co-ordinate system | |

removing redundant co-ordinates | |

adding extra gaps |

Question 1 Explanation:

Co-ordinate compression is the process of reassigning co-ordinates in order to remove gaps. This helps in improving efficiency of a solution.

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

What is the need for co-ordinate compression?

for improving time complexity | |

for improving space complexity | |

for improving both time and space complexity | |

for making code simpler |

Question 2 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.

Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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; }

4 3 0 1 2 | |

1 2 3 4 5 | |

5 4 1 2 3 | |

0 1 2 3 4 |

Question 3 Explanation:

The given code converts the elements of the input array. They are replaced with their respective position number in the sorted array.

Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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; }

O(n) | |

O(n log n) | |

O(n ^{2}) | |

O(log n) |

Question 4 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.

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

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; }

O(1) | |

O(n) | |

O(log n) | |

O(n log n) |

Question 5 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.

There are 5 questions to complete.