Comments

Post a Comment

Popular posts from this blog

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

[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