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

[25] Search an element in a sorted and infinite array - Interview Problem

Image
https://www.geeksforgeeks.org/find-position-element-sorted-array-infinite-numbers/ Understanding the Problem Problem Description:  You are given a sorted and infinite array A[] and an element K. You need to search for the element K in the array. If found, return the index of the element, else return -1. For Example : Input: A[] = {1,3,5,8,12,13,17,19,28,39,103,123,140,2040,…}, K = 17 Output: 6 Input: A[] = {10,20,25,30,67,93,159,192,350,1230,1341,4533,…}, K = 23 Output: -1 Possible questions to ask the interviewer:- What is the meaning of infinite array ? ( Ans : We don't know the upper bound of the array) How big can the resultant index be? ( Ans:  Ignore the integer overflow problem, we just want to check your logic, let us assume integer overflow won’t occur) Brute force and Efficient solutions We will be discussing three solutions for this problem:- Brute Force approach : Using linear Search Increment by a constant value and using binary search...
Read more