Basic Data structure questions

Comments

Post a Comment

Popular posts from this blog

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Subset Sum Problem | DP-25 Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum. Example: Input:  set[] = {3, 34, 4, 12, 5, 2}, sum = 9 Output:  True  //There is a subset (4, 5) with sum 9. // A recursive solution for subset sum problem #include <stdio.h>     // Returns true if there is a subset of set[] with sun equal to given sum bool isSubsetSum( int set[], int n, int sum) {     // Base Cases     if (sum == 0)       return true ;     if (n == 0 && sum != 0)       return false ;         // If last element is greater than sum, then ignore it     if (set[n-1] > sum)       return isSubsetSum(set, n-1, sum);         /* else, check if sum...
Read more

[17 Feb 2020] Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side.

Find the nearest smaller numbers on left side in an array Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side. Examples: Input:  arr[] = {1, 6, 4, 10, 2, 5} Output:         {_, 1, 1,  4, 1, 2} First element ('1') has no element on left side. For 6, there is only one smaller element on left side '1'. For 10, there are three smaller elements on left side (1, 6 and 4), nearest among the three elements is 4. Input: arr[] = {1, 3, 0, 2, 5} Output:        {_, 1, _, 0, 2} Expected time complexity is O(n). // C++ implementation of efficient algorithm to find // smaller element on left side #include <iostream> #include <stack> using namespace std;   // Prints smaller elements on left side of every element void printPrevSmaller(int arr[], int n) {     // Create an empty stack     stack<int> S;   ...
Read more

[15 Feb 2020] Remove duplicates from a string in O(1) extra space

Remove duplicates from a string in O(1) extra space Given a string  str  of lowercase characters, the task is to remove duplicates and return a resultant string without modifying the order of characters in the original string. Examples: Input: str = "geeksforgeeks" Output: geksfor Input: str = "characters" Output: chartes Approach:  The idea is to use bits of a  counter  variable to mark the presence of a character in the string. To mark the presence of ‘a’ set 0th bit as 1, for ‘b’ set 1st bit as 1 and so on. If the corresponding bit of character present in the original string is set to 0, it means it is the first occurrence of that character, hence set its corresponding bit as 1 and keep on including the current character in the resultant string. // C++ implementation of above approach #include <bits/stdc++.h> #include <string> using namespace std;     // Function to remove duplicates string remove...
Read more