Basic Data structure questions

Comments

Post a Comment

Popular posts from this blog

[GE][First Method]Find smallest permutation of given number

Smallest number by rearranging digits of a given number Find the Smallest number (Not leading Zeros) which can be obtained by rearranging the digits of given number. Examples: Input: n = 846903 Output: 304689 Input: n = 55010 Output: 10055 Steps to find the smallest number. Count the frequency of each digit in the number. Place the smallest digit (except 0) at the left most of required number. and decrement the frequency of that digit by 1. Place all remaining digits in ascending order from left to right. This solution is based on  counting sort . // C++ program for finding smallest number // from digits of given number #include<iostream> using namespace std;     // function to find the smallest number int smallest( int num) {      // initialize frequency of each digit to Zero      int freq[10] = {0};          // count frequency of e...
Read more

[23] Find top k (or most frequent) numbers in a stream

Given an array of n numbers. Your task is to read numbers from the array and keep at-most K numbers at the top (According to their decreasing frequency) every time a new number is read. We basically need to print top k numbers sorted by frequency when input stream has included k distinct elements, else need to print all distinct elements sorted by frequency. Examples: Input :  arr[] = {5, 2, 1, 3, 2}              k = 4 Output : 5 2 5 1 2 5 1 2 3 5 2 1 3 5 Input  : arr[] = {5, 2, 1, 3, 4}              k = 4 Output : 5 2 5 1 2 5 1 2 3 5 1 2 3 4 Expected time complexity is O(n * k) Given an array of n numbers. Your task is to read numbers from the array and keep at-most K numbers at the top (According to their decreasing frequency) every time a new number is read. We basically need to print top k numbers sorted by frequency when input stream has included k distinct elements, else need to print all...
Read more

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