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
# Interview Questions

This category contains few tricky questions asked in interviews..

## 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
## Finding Missing Number in an Increasing Sequence

Problem Statement
You are given an array which contains an increasing sequence of numbers from 1 to N. There is one number missing in the sequence. The task at hand is find the missing number in minimum running time.
Input: An array A of numbers in increasing order, with one number missing.
Output: The missing integer
Constraint: The sequence is strictly increasing. The algorithm should finish in minimum time.
Approach for Finding Missing Number
At first, it looks like a simple problem which can be solved in O(N) time. Indeed it is. Here are the steps:
Start traversing from the...

Read More
## Data Structure for Efficient Search

Problem Statement
Given one million 10 digit unique integers, design an efficient data structure which has lowest time complexity for searches. You are given ample amount of space and the time for building the data structure and populating it is not judged.
The only criteria is to offer efficient searches.
Thought Process for Efficient Search
The numbers are 10 digit unique integers and we need a data structure which can offer search in near constant time. The problem is similar to finding if a word exists in a dictionary. Its just that the Strings are replaced by the 10 digit numbers.
...

Read More
## Maximum Element Sliding Window

A very interesting problem indeed! Often asked in Interviews in various forms and we will discuss one of these forms here in this post.
Problem Statement - Maximum Element Sliding Window
Given a stream or array of elements (preferably integers). Find the elements with maximum value in a window of length K where the window slides by one step to the right every time.
What is a Sliding Window?
Given an array A, a sliding window of length K is a range of fixed size K in the array such that the range slides to the right by one index. Here is a diagram to explain how sliding window will look...

Read More
## The Pitfalls of Singleton Design Pattern

Yes! its true that a Singleton object is the loneliest construct in Programming. :) Let us keep the humor aside and listen to this interesting story.
Last time we had a fun story while understanding the Factory Method Design Pattern. This time let us have a story from one of our software developers Manish. He wants to create this wonderful application.
An awesome application
This application uses the socket connections heavily and has to write data over the network. Manish wrote a code which works great. Every time he wants to use the connection he creates one and starts using it. In no ...

Read More