My software development journey
Anagram of a word is nothing but rearrangement of it’s letters to form another word.For example ‘listen’ is an anagram of ‘silent’ and ‘enlist’.We have to write a function to check if two given strings are anagrams are not. We can solve this problem in two different ways. The first way is to sort the…
Given an array, and a value K as input, we have to find a pair of elements such that their sum is K. There are multiple ways of solving this problem. We will discuss some of them in this post. Let us implement the function which prints the two values such that array[i] + array[j]…
Let us consider an array of size N contains numbers in the range [1,N]. We have to find if it has duplicates in linear time – O(n) and by using only constant extra space – O(1). Let us also have a restriction that we should traverse the array only once. Take a look at the following…
In this post we discuss how to efficiently implement a stack data structure with one additional operation getMin() along with push() and pop(). getMin() returns the minimum value in the stack. The trick here is to use another stack which stores the minimum values of the original stack. The top of Min-stack always contains the…
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…
Merge sort follows the divide and conquer approach. This is also a comparison based sorting algorithm like Bubble sort, selection sort and insertion sort etc. In this method we divide the array into two halves. We recursively sort these two parts and merge them into single array. Here the base case for recursion is just…
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…
How do you implement a stack using Queue? This is the exact reverse of the problem discussed in my earlier post. We have to use only Queue operations like enqueue(), dequeue() and size() operations to implement push() and pop() operations of the stack. This can be done using two queues. One queue acts as the…
Given a string as input, how do we find the first non-repeating character? We have to do this in linear time – O(n) and constant extra space- O(1) Assuming that the character set is ASCII, the number of characters possible are 256. This will differ if the string contains non-ASCII characters like Unicode. First we…