• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar

Pro Programming

Professional way of Programming: Learn C, C++, Java, Python, Dot Net, Android the professional way

  • Home
  • C MCQs
  • C/C++ Programs
  • Java Programs
  • C#
  • Python
  • MySQL
  • Topics
    • Arrays
    • Strings
    • Link Lists
    • Trees
    • Shapes
  • Projects
  • Articles
  • Games
You are here: Home / Archives for •   Stack Reversal – Recursion

•   Stack Reversal - Recursion

Co-ordinate Compression Multiple Choice Questions and Answers (MCQs)

Leave a Comment


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.



Source link

Filed Under: c programming Tagged With: •   Array-Recursion-Min-Max, •   Array-Recursion-Search - 1, •   Array-Recursion-Search - 2, •   Assembly Line Scheduling, •   Balanced Partition, •   Best First Search, •   Binary Search Iterative, •   Binary Tree Sort, •   Bipartite Graph, •   Bipartite Graphs Properties, •   Bogosort, •   Boolean Parenthesizations, •   Bottom Up Mergesort, •   Breadth First Search, •   Catalan Number, •   Chan's Algorithm, •   Closest Pair Problem, •   Co-ordinate Compression, •   Coin Change Problem, •   Comb Sort, •   Complete Bipartite Graph, •   Continuous Subarray - 1, •   Continuous Subarray - 2, •   Counting Sort, •   Decimal-Binary Conversion, •   Depth First Search, •   Dice Throw Problem, •   Digits Sum - Recursion, •   Dijkstra's Algorithm, •   Dynamic Programming, •   Edit Distance Problem, •   Eight Queens Problem, •   Euclid's Algorithm, •   Factorial using Recursion, •   Fibonacci Term, •   Fibonacci using Recursion, •   First-in First-out Algorithm, •   Fraction Knapsack Problem, •   GCD & LCM Recursion - 1, •   GCD & LCM Recursion - 2, •   Generating Combinations, •   Generating Partitions, •   Generating Permutations, •   Generating Subsets, •   Gnome Sort, •   Hamiltonian Path Problem, •   Hamming Code, •   Heapsort - 1, •   Heapsort - 2, •   Huffman Code, •   In-place Merge Sort, •   Inclusion Principle, •   Insertion Sort - 1, •   Insertion Sort - 2, •   Introsort, •   Jump Search, •   Kruskal's Algorithm, •   Linear Search Iterative, •   Linear Search Recursive, •   Linkedlist-Length-Recursion, •   Linkedlist-Recursion-Search, •   Lists-Recursion-Min-Max, •   Longest Subsequence, •   LSD Radix Sort, •   Matrix Multiplication, •   Max Bipartite Matching, •   Maximum Flow Problem, •   Minimum Cut, •   Minimum Number of Jumps, •   Minimum Spanning Tree, •   Monoalphabetic Cipher, •   Morse Code - 1, •   Morse Code - 2, •   N Queens Problem, •   Natural No's - Recursion, •   Non-recursive DFS, •   NP Complexity Classes, •   Number Power - Recursion, •   Odd-Even Sort, •   Optimal Page Replacement, •   Palindrome Min Insertions, •   Palindromic Subsequence, •   Pancake Sort, •   Permutation Sort, •   Polyalphabetic Cipher, •   Prim's Algorithm, •   Quick Search Algorithm, •   Quickhull, •   Quickselect, •   Quicksort - 1, •   Quicksort - 2, •   Quicksort - 3, •   Quicksort using Sampling, •   Rabin-Karp Algorithm, •   Rectangle Sum in 2D Matrix, •   Recursive Selection Sort, •   Rod Cutting, •   Selection Sort, •   Shell Sort - 1, •   Shell Sort - 2, •   Sleep Sort, •   Square Root Decomposition, •   Stable Marriage Problem, •   Stack Reversal - Recursion, •   Strassen's Algorithm, •   String Length - Recursion, •   String Reversal - Recursion, •   Timsort, •   Topological Sorting, •   Towers of Hanoi - Recursion, •   Uniform Binary Search, •   Vigenere Cipher, •   Wagner-Fischer Algorithm, 0 - 1 Knapsack Problem, 1000 C Questions & Answers, 1000 Hadoop Questions, 1000 Java Questions & Answers, 1000 Linux Questions & Answers, 1000 PHP Questions & Answers, 1000 Python Questions, About, About Us, Advanced C Training, Aeronautical, Aerospace, Agriculture, Algorithm & Programming Books, All Stream Best Books, All Stream Internships, All Stream Questions & Answers, Backtracking, Bangalore Training, BCA, Bellman–Ford Algorithm, Biotechnology, Bogosort Multiple Choice Questions and Answers (MCQs), Bottom-Up Mergesort Multiple Choice Questions and Answers (MCQs), Bubble Sort, Chemical, Chemical Engineering Books, Chemical Internships, Civil, Civil Engineering Books, Civil Internships, Cloud Computing Questions, Comb Sort Multiple Choice Questions and Answers (MCQs), Computer Science Books, Computer Science Internships, Computer Science Questions, Contact, Contact Us, Copyright, CS, Data Structures & Algorithms II – Questions and Answers, Data Structures & Algorithms Books, Developer Tracks, Developers Track, ECE, EE, EEE, Electrical Engineering Books, Electrical Internships, Electronics Engineering Books, Electronics Internships, Facebook, Fibonacci Search, Floyd Warshall Algorithm, GDB Assignment, here is complete set of 1000+ Multiple Choice Questions and Answers, Home, In-place Merge Sort Multiple Choice Questions and Answers (MCQs), Industrial Engineering Books, Industrial Internships, Instrumentation, Instrumentation Engg Books, Instrumentation Internships, Internship, Introsort Multiple Choice Questions and Answers (MCQs), IS, IT, IT Internships, Jobs, Kadane's Algorithm, Kernel Debugging, Kernel Programming, LinkedIn, Linux Device Drivers, Linux Driver Developer, Linux Fundamentals, Linux Kernel Developer, Linux Network Developer, Linux Threads, Linux-C Debugging, Live Training Photos, Manish, Manish Bhojasia, Marine, Matrix Chain Multiplication, MCA, Mechanical, Mechanical Engineering Books, Mechanical Internships, Mentoring, Mentoring Sessions, Metallurgical Engineering Books, Metallurgy, Mining, Network Programming, Next Page, Next Page - Square Root Decomposition Multiple Choice Questions and Answers (MCQs), Online Training, Operating System Questions and Answers, Permutation Sort Multiple Choice Questions and Answers (MCQs), Prev Page, Prev Page - Quickselect Multiple Choice Questions and Answers (MCQs), Privacy Policy, Programming, Quickhull Multiple Choice Questions and Answers (MCQs), Quickselect Multiple Choice Questions and Answers (MCQs), Quicksort using Random Sampling Multiple Choice Questions and Answers (MCQs), Recursion, SAN Developer, SAN I - Technology, SAN II - Admin, Sitemap, Software Productivity, Square Root Decomposition Multiple Choice Questions and Answers (MCQs), System Programming, Systems Internships, Terms, Test & Rank, Training, Twitter

Square Root Decomposition Multiple Choice Questions and Answers (MCQs)

Leave a Comment


This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Square Root Decomposition”.

1. What is the purpose of using square root decomposition?
a) to reduce the time complexity of a code
b) to increase the space complexity of a code
c) to reduce the space complexity of a code
d) to reduce the space and time complexity of a code
View Answer

Answer: a
Explanation: Square decomposition is mainly used in competitive programming to optimize code. It reduces the time complexity by a factor of √n.

2. By what factor time complexity is reduced when we apply square root decomposition to a code?
a) n
b) √n
c) n2
d) n-1/2
View Answer

Answer: b
Explanation: In square root decomposition a given array is decomposed into small parts each of size √n. This reduces the time complexity of the code by a factor of √n.

3. What will be the worst case time complexity of finding the sum of elements in a given range of (l,r) in an array of size n?
a) O(n)
b) O(l+r)
c) O(l-r)
d) O(r-l)
View Answer

Answer: a
Explanation: For a given array of size n we have to traverse all n elements in the worst case. In such a case l=0, r=n-1 so the time complexity will be O(n).

4. What will be the worst case time complexity of finding the sum of elements in a given range of (l,r) in an array of size n when we use square root optimization?
a) O(n)
b) O(l+r)
c) O(√n)
d) O(r-l)
View Answer

Answer: c
Explanation: When we use square root optimization we decompose the given array into √n chunks each of size √n. So after calculating the sum of each chunk individually, we require to iterate only 3*√n times to calculate the sum in the worst case.

5. Total how many iterations are required to find the sum of elements in a given range of (l,r) in an array of size n when we use square root optimization?
a) √n
b) 2*√n
c) 3*√n
d) n*√n
View Answer

Answer: c
Explanation: After calculating the sum of each chunk individually we require to iterate only 3*√n times to calculate the sum in the worst case. It is because two of the √n factors consider the worst case time complexity of summing elements in the first and last block. Whereas the third √n considers the factor of summing the √n chunks.

6. What will be the time complexity of update query operation in an array of size n when we use square root optimization?
a) O(√n)
b) O(n)
c) O(1)
d) O(n2)
View Answer

Answer:c
Explanation: The time complexity of query operation remains the same in both square root optimized code and non optimized code. We simply find the chunk in which the update requires to be performed and then add the new updated value at the desired index.

7. Square root decomposition technique is only applicable when the number of indices in an array is a perfect square.
a) true
b) false
View Answer

Answer: b
Explanation: Square root decomposition technique can be applied to an array with any number of indices. It does not require this number to be a perfect square.

8. What will be the worst case time complexity of code to find sum in given query range (l,r) in an array of size n with q number of such queries?
a) O(n)
b) O(q)
c) O(n*q)
d) O(n+q)
View Answer

Answer: c
Explanation: For finding the result of one query the worst case time complexity will be n. So for q queries the time complexity will be O(q*n). This can be reduced by using square root optimization.

9. What will be the worst case time complexity of code to find sum in given query range (l,r) in an array of size n with q number of such queries when we apply MO’s algorithm?
a) O(n*q)
b) O(n)
c) O((q+n)√n)
d) O(q*√n)
View Answer

Answer: c
Explanation: Mo’s algorithm requires O(q*√n) + O(n*√n) time for processing all the queries. It is better than the naive solution where O(n*q) time is required.

10. Mo’s algorithm can only be used for problems where the query can be calculated from the result of the previous query.
a) true
b) false
View Answer

Answer: a
Explanation: Mo’s algorithm uses the result of the previous query in order to compute the result of the given query. It cannot be implemented where such a scenario is not possible.

11. What will be the time complexity of the code to find a minimum element from an array of size n and uses square root decomposition(exclude pre processing time)?
a) O(√n)
b) O(n)
c) O(1)
d) O(n2)
View Answer

Answer: a
Explanation: For finding the minimum element in a given array of size n using square root decomposition we first divide the array into √n chunks and calculate the result for them individually. So for a given query, the result of middle blocks has to be calculated along with the extreme elements. This takes O(√n) time in the worst case.

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.



Source link

Filed Under: c programming Tagged With: •   Array-Recursion-Min-Max, •   Array-Recursion-Search - 1, •   Array-Recursion-Search - 2, •   Assembly Line Scheduling, •   Balanced Partition, •   Best First Search, •   Binary Search Iterative, •   Binary Tree Sort, •   Bipartite Graph, •   Bipartite Graphs Properties, •   Bogosort, •   Boolean Parenthesizations, •   Bottom Up Mergesort, •   Breadth First Search, •   Catalan Number, •   Chan's Algorithm, •   Closest Pair Problem, •   Co-ordinate Compression, •   Coin Change Problem, •   Comb Sort, •   Complete Bipartite Graph, •   Continuous Subarray - 1, •   Continuous Subarray - 2, •   Counting Sort, •   Decimal-Binary Conversion, •   Depth First Search, •   Dice Throw Problem, •   Digits Sum - Recursion, •   Dijkstra's Algorithm, •   Dynamic Programming, •   Edit Distance Problem, •   Eight Queens Problem, •   Euclid's Algorithm, •   Factorial using Recursion, •   Fibonacci Term, •   Fibonacci using Recursion, •   First-in First-out Algorithm, •   Fraction Knapsack Problem, •   GCD & LCM Recursion - 1, •   GCD & LCM Recursion - 2, •   Generating Combinations, •   Generating Partitions, •   Generating Permutations, •   Generating Subsets, •   Gnome Sort, •   Hamiltonian Path Problem, •   Hamming Code, •   Heapsort - 1, •   Heapsort - 2, •   Huffman Code, •   In-place Merge Sort, •   Inclusion Principle, •   Insertion Sort - 1, •   Insertion Sort - 2, •   Introsort, •   Jump Search, •   Kruskal's Algorithm, •   Linear Search Iterative, •   Linear Search Recursive, •   Linkedlist-Length-Recursion, •   Linkedlist-Recursion-Search, •   Lists-Recursion-Min-Max, •   Longest Subsequence, •   LSD Radix Sort, •   Matrix Multiplication, •   Max Bipartite Matching, •   Maximum Flow Problem, •   Minimum Cut, •   Minimum Number of Jumps, •   Minimum Spanning Tree, •   Monoalphabetic Cipher, •   Morse Code - 1, •   Morse Code - 2, •   N Queens Problem, •   Natural No's - Recursion, •   Non-recursive DFS, •   NP Complexity Classes, •   Number Power - Recursion, •   Odd-Even Sort, •   Optimal Page Replacement, •   Palindrome Min Insertions, •   Palindromic Subsequence, •   Pancake Sort, •   Permutation Sort, •   Polyalphabetic Cipher, •   Prim's Algorithm, •   Quick Search Algorithm, •   Quickhull, •   Quickselect, •   Quicksort - 1, •   Quicksort - 2, •   Quicksort - 3, •   Quicksort using Sampling, •   Rabin-Karp Algorithm, •   Rectangle Sum in 2D Matrix, •   Recursive Selection Sort, •   Rod Cutting, •   Selection Sort, •   Shell Sort - 1, •   Shell Sort - 2, •   Sleep Sort, •   Square Root Decomposition, •   Stable Marriage Problem, •   Stack Reversal - Recursion, •   Strassen's Algorithm, •   String Length - Recursion, •   String Reversal - Recursion, •   Timsort, •   Topological Sorting, •   Towers of Hanoi - Recursion, •   Uniform Binary Search, •   Vigenere Cipher, •   Wagner-Fischer Algorithm, 0 - 1 Knapsack Problem, 1000 C Questions & Answers, 1000 Hadoop Questions, 1000 Java Questions & Answers, 1000 Linux Questions & Answers, 1000 PHP Questions & Answers, 1000 Python Questions, About, About Us, Advanced C Training, Aeronautical, Aerospace, Agriculture, Algorithm & Programming Books, All Stream Best Books, All Stream Internships, All Stream Questions & Answers, Backtracking, Bangalore Training, BCA, Bellman–Ford Algorithm, Biotechnology, Bubble Sort, C Program to find the Lowest Common Ancestor of a given Binary Search Tree, C Programming Examples on Arrays, C Programming Examples on Combinatorial Problems & Algorithms, C Programming Examples on Numerical Problems & Algorithms, C# Programming Examples on LINQ, Chemical, Chemical Engineering Books, Chemical Internships, Civil, Civil Engineering Books, Civil Internships, Cloud Computing Questions, Co-ordinate Compression Multiple Choice Questions and Answers (MCQs), Computer Science Books, Computer Science Internships, Computer Science Questions, Contact, Contact Us, Copyright, CS, Data Structures & Algorithms Books, Database Management System Questions and Answers, Developer Tracks, Developers Track, ECE, EE, EEE, Electrical Engineering Books, Electrical Internships, Electronics Engineering Books, Electronics Internships, Facebook, Fibonacci Search, Floyd Warshall Algorithm, GDB Assignment, here is complete set of 1000+ Multiple Choice Questions and Answers, Home, Industrial Engineering Books, Industrial Internships, Instrumentation, Instrumentation Engg Books, Instrumentation Internships, Internship, IS, IT, IT Internships, Java Programming Examples on Arrays, Java Programming Examples on Numerical Problems & Algorithms, Jobs, Kadane's Algorithm, Kernel Debugging, Kernel Programming, LinkedIn, Linux Device Drivers, Linux Driver Developer, Linux Fundamentals, Linux Kernel Developer, Linux Network Developer, Linux Threads, Linux-C Debugging, Live Training Photos, Manish, Manish Bhojasia, Marine, Matrix Chain Multiplication, MCA, Mechanical, Mechanical Engineering Books, Mechanical Internships, Mentoring, Mentoring Sessions, Metallurgical Engineering Books, Metallurgy, Mining, Network Programming, Online Training, Prev Page, Prev Page - Co-ordinate Compression Multiple Choice Questions and Answers (MCQs), Privacy Policy, Programming, Python Programming Examples on Trees, RDBMS Questions and Answers, Recursion, SAN Developer, SAN I - Technology, SAN II - Admin, Sitemap, Software Productivity, System Programming, Systems Internships, Terms, Test & Rank, Training, Twitter

Primary Sidebar

Recent Posts

  • Engineering Chemistry Questions and Answers – Application of Colloids
  • MongoDB Beginners Tutorial
  • 10 Projects That Every Developer Should Lay Their Hands-On
  • Engineering Chemistry Questions and Answers – Detergents
  • What is Blockchain? How the Blockchain Network Actually Works?
  • Privacy Policy
  • About
  • Contact US

© 2019 ProProgramming
 Privacy Policy About Contact Us