Interview Questions

This category contains few tricky questions asked in interviews..

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...

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. ...

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...