Introduction
This post is an enhancement over one of the previous posts where the task was to find if a given string C is an interleaving of strings A and B. To know more about the problem description, please visit the previous post
Solution
The previous solution is a iterative solution which requires lot of space. Here we will discuss a recursive solution. Hopefully with small code foot print. Before we jump into the code, let us understand the idea behind the solution.
Here are the example Strings A, B and C
A -> abcd
B -> ade
C -> abadcde
The recursive algorithm...

Read More
# Interview Questions

This category contains few tricky questions asked in interviews..

## Count Word Frequency in Stream

Introduction
Continuing our discussions on Tries, here is another practical problem which is used in many text processing scenarios. Counting word frequency in stream translates to a scenario where you are given a list of words (dictionary). Now, there is an infinite stream of characters coming in. Your task is to print the frequency of words appearing in the stream.
To know more about the basics of building a Trie, please visit my previous post
Example Problem for counting word frequency in stream
Let us say we have a dictionary which contains the following words
aca
cat
hell...

Read More
## Rotating an Array by a fixed distance

Problem Statement
Another question which is favorite among interviewers is rotating an array by a fixed distance. Before understanding how can we do that, it is important to understand what it means to rotate an array. Given an array of length N, rotation by a fixed distance K means shifting each element to the right by K indices. The indices of course are computed in a rotational manner such that if the new index of the element goes beyond the array boundaries, it can be wrapped to the beginning of the array.
Here is an example of input and output.
The problem seems very easy until s...

Read More
## Find the Point of Rotation in Sorted Array

Problem Statement
You are given a sorted array. However, there is a problem. Someone just rotated the sorted array by K spaces and we do not know the value of K.
Write a program to find the value of K by which the array is rotated. As the array has millions of numbers, it would be good to have a solution which takes minimal time.
Approach to Find the Point of Rotation
Brute Force
Let us try out my favorite approach, the Brute Force Method. It is quite simple, below are the steps:
Start traversing the array from the beginning
There will be a index in the array where the value sto...

Read More
## Find the maximum possible profit

Problem Statement
Given an array of stock prices per share for a given share over a time period. Calculate the maximum possible profit per share one could have made . Here we do not consider short selling as an option. The trader must have purchased the stocks before selling it.
The problem statement is a real world definition of the problem called maximum positive difference.
For the above two arrays, here are the maximum profit per share one could have made:
A : 18.0 (difference between 21 and 3)
B : 13.0 (difference between 19 and 6)
What is Maximum Positive Difference?
...

Read More