Interview Questions

This category contains few tricky questions asked in interviews..

Find Pair of Numbers in Array with a Given Sum

Problem Definition This problem has appeared in many interviews as well as the qualifying round of Google Code Jam in the past. There are various versions of the problem. To list a few: Find Pair of Numbers in Array with a Given Sum - The array is unsorted and contains a given range of numbers bounded by min and max. Find Pair of Numbers in Array with a Given Sum - The array is sorted and contains a given range of numbers bounded by min and max. Find Pair of Numbers in Array with a Given Sum - The array contains unique numbers only. In all the above versions, we have to return the ...
Read More

Further Reading for Minimum Spanning Tree

Introduction This is a supplement to the posts for Minimum Spanning Tree and their Analysis. Check out the other related articles in the following section. Further Reading for Minimum Spanning Tree This section is meant to be read in conjunction to the post Minimum Spanning Tree - Prim's Algorithm The minimum spanning tree of a Graph is the union of minimum spanning trees of its connected components. This is a very important observation and it must be discussed in length and breadth because this will help us design our algorithm for MST in a better way. Why is it so important to underst...
Read More

Minimum Spanning Tree Prim’s Algorithm

Introduction What is the minimum length of the network cable we require if we have to connect 100 computing machines in a building distributed across multiple floors? How do I guarantee that there can be no other minimum length possible than what I derive? Why is it even important to find the minimum length? The history of the problem You can read the classic problem solved by MST Applications of Minimum Spanning Tree Defining Spanning Trees A spanning tree is always defined for a weighted Graph G(V,E) where the weights are positive. This means that all the edges carry some positive we...
Read More

Shortest Path using Dijkstra’s Algorithm

Introduction This is the third post in the Graph Traversals – Online Classes. After learning how to move through a graph, we might be interested in learning more. One interesting problem is determining the shortest path between two vertices of a graph. The problem can be extended and defined in many other forms. I prefer to call it "minimizing the cost". For e.g. When we measure the cost in terms of the distances between vertices, it can be called as the Shortest Path. When we measure the cost in terms of the money spent between vertices, it can be called as the Cheapest Path. Whe...
Read More

Depth First Traversal

Introduction This is the second post in the Graph Traversals – Online Classes. I Recommend you to look at the first post Breadth First Traversal as it contains more explanation and details and I will keep this post smaller just around the depth first concept. Depth First Traversal The Idea In this traversal, we choose a start vertex and keep moving forward along the length of the graph until there is no undiscovered vertex in that path. Once reaching a dead end, we back track to all the visited vertices and check if we have any vertex which has an adjacent undiscovered vertex. We kee...
Read More

Make anagrams from two Strings

Problem Statement Given two strings, find the total number of characters we need to delete from these strings to make them anagrams of each other. Understanding Anagrams Anagrams are defined with respect to a given string of characters (not necessarily characters in the English Alphabet) but a wider set of characters may be. Given two strings A and B, if the number of time each character occurs in both the string is exactly same, we say A and B are anagrams. However, the order in which the character appears may be different and doesn't matter. For example A = axbbxxcecdeedda B = abacb...
Read More

Matrix Rotation and Matrix Transpose

Problem Definition – Matrix Rotation (by 90, 180, 270 degrees) This is a very famous interview question and has been asked numerous times. We are trying to solve the problem of matrix rotations where the inputs are as follows: A matrix of dimension M * N A number from the set (90, 180, ,270) by which we need to rotate the matrix. For simplicity we will consider a matrix to be a 2 dimensional array of integers. What does it mean to rotate a matrix? This can only be explained by nice diagrams. Just for a formal definition, I would say that matrix rotation is a structural re-arrangeme...
Read More