My software development journey
Given a set of numbers, how do we generate its power set? For example for the set {1,2} the power set is given below. { {}, {1}, {2}, {1,2} } A power set is nothing but all the possible subsets of a given set. If a set contains N elements, it’s power set contains 2N…
The following function is simply based on recursion mechanism. We write a function printReverse(). Initially we call this function by passing a pointer to the first character of the string. We keep calling this function recursively by incrementing the pointer until we reach the null character (End of the string). If we reach null, the…
Given an array of 0s and 1s, how do we sort them? After sorting all the 0s appear before all the 1s.For example the array [0,1,0,1,1,0,0,0,1,1] becomes [0,0,0,0,0,1,1,1,1,1]Let us look at two approaches to solve this problem. The first one is based on bucket sort and the second is more intelligent.Method#1:We can take two counts…
Given an array numbers, how do we write a function checkDuplicates() which returns true if the array has at least one element repeated; returns false if all the elements are unique. We discuss three different implementations of this function with various time and space complexities. Method-1: Naive approach This approach checks every possible pair in…
Quick sort is a comparison based sorting algorithm. Like Merge sort, this also follows divide and conquer algorithmic pattern. Quick sort works as follows. A random element from the array is chosen as a pivot element. A pivot element is a special element which divides the array into left part and right part. All the…
Given two strings, How do we delete all the characters in the first string which are present in the second string? Find the character set of the string. Create a Boolean array of size equal to the character set size. If the character set is ASCII, the size is 256. This array will be indexed…
Pattern matching algorithms are very important in computer science. In this post we will discuss the simplest algorithm for pattern matching. Given some text and a pattern, we have to find where in the text, the pattern is found. In this brute-force algorithm, we start matching the pattern from the beginning of the text. If…
Given a single linked list, how do you find the middle of the list?One simple method is to traverse through the list twice once to find it’s length, and second to navigate to the middle of the list by traversing length/2 nodes. Even though this method runs in O(n) time, there is still a chance…
In simple words, Recursion is nothing but a function calling itself. How can we solve this problem using recursion? Initially pass the entire string as input to the function. Basically a pointer to the first character is passed. This function examines the next character; if it is not null, it calls itself by advancing the pointer…
Given an array of positive integers, all numbers occur even number of times, except one which occurs odd number of times. How do you find the number in O(n) time and O(1) space? You can find a similar question in interviews which is infact a specific problem of the above category. An array contains 2n+1…