Basic Data structure questions

Comments

Post a Comment

Popular posts from this blog

Which data structure is used in redo-undo feature?

Explanation:  Stack data structure is most suitable to implement redo-undo feature. This is because the stack is implemented with LIFO(last in first out) order which is equivalent to redo-undo feature i.e. the last re-do is undo first. Consider a situation where a client receives packets from a server. There may be differences in speed of the client and the server. Which data structure is best suited for synchronization? (A)  Circular Linked List (B)  Queue (C)  Stack (D)  Priority Queue Answer:   (B) Explanation:  Since packets need to be processed in First In First Out order, a queue can be used for synchronization. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. o Delection of the smallest element o Insertion of an element if it is not already present in the set Which of the following data structur...
Read more

Print all subsets of given size of a set

Generate all possible subset of size  r  of given array with distinct elements. Examples: Input : arr[] = {1, 2, 3, 4} r = 2 Output : 1 2 1 3 1 4 2 3 2 4 3 4 Input : arr[] = {10, 20, 30, 40, 50} r = 3 Output : 10 20 30 10 20 40 10 20 50 10 30 40 10 30 50 10 40 50 20 30 40 20 30 50 20 40 50 30 40 50 The idea here is similar to  Subset Sum Problem . We one by one consider every element of input array, and recur for two cases: 1) The element is included in current combination (We put the element in data[] and increment next available index in data[]) 2) The element is excluded in current combination (We do not put the element and do not change index) When number of elements in data[] become equal to r (size of a combination), we print it. This method is mainly based on  Pascal’s Identity , i...
Read more

[02 Feb 2020] Given an array of N distinct elements, find the minimum number of swaps required to sort the array.

Given an array of N distinct elements, find the minimum number of swaps required to sort the array. #include<bits/stdc++.h> using namespace std; // Function to find minimum swaps to // sort an array int findMinSwap(int arr[] , int n) {     // Declare a vector of pair        vector<pair<int,int>> vec(n);         for(int i=0;i<n;i++)     {         vec[i].first=arr[i];         vec[i].second=i;     }     // Sort the vector w.r.t the first     // element of pair     sort(vec.begin(),vec.end());     int ans=0,c=0,j;     for(int i=0;i<n;i++)     {          // If the element is already placed         // correct, then continue         if(vec[i].second==i)             continue; ...
Read more