Given a text and a pattern. Replace all the occurrences of the pattern in the text by another given string. For Example: If text = “aabaabab” and pattern = “ab”. Then after replacing pattern in the text by “abc” the output should be “aabcaabcabc”. The trivial solution would be to do a brute-force search of […]
Category Archives: Algorithms
Given a string, rearrange characters of the string such that no duplicate characters are adjacent to each other. For example, Input: aaabc Output: abaca Input: aa Output: No valid output Input: aaaabc Output: No valid output How can we achieve this rearrangement? The very first idea that may pop up is to count the frequency […]
From wiki, Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959, with his work published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or […]
Given an array of stock prices, where the increasing indexes of the array signify the increase in time. Return a good time to buy and sell such that profit is maximized. Suppose we are given an array of n integers representing stock prices on a single day. We want to find a pair (buyDay, sellDay), […]
Given two big integers represented as strings, Multiplication them and return the production as string. For example, given a=2343324 and b=232232 then retiurn c = a*b = 23433242334323342 * 23223233232434324 = 544195652122144709711313995190808 We can see that the problem is trivial if we had given two small integers. But as the numbers can be really big […]
Given n, print numbers from zero to n sequentially using two threads such that one thread prints only odds and other prints only evens. This is a simple classical thread synchronization problem. Before moving to the solution I would like revise basic process, thread, and synchronization/concurrency concepts. Some of the figures in this article are […]
Given a positive number. Find all unique combinations of factors that constitute the number. Note that we are not asking for only prime factors but any factors including primes. For example, given number n=12 can be factorize into 12 * 1, 6 * 2, 4 * 3, 3 * 2 * 2. Note that for […]
Given an integer N, find all the prime numbers less than in sorted order. A trivial solution would be to loop through all numbers from 2 to N and check if a number is prime or not. How can we check if a number is prime ? Note that a number is a prime if […]
Implement pow(x,y) in logarithm time The problem would be straightforward if we are allowed to do it in O(n) time as we can simply multiple x by itself y times. But how to do it in log time? The problem description itself is telling us how to implement it in log time. If we need […]
Given a set of characters. Find the power set or super set of the set. For example, S={a,b,c}, then powerSet = {{}, {a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c}}. For a set of n elements there are 2^n elements on the super set including the empty set. The brute-force method would be to find all […]