Interview Questions

This category contains few tricky questions asked in interviews..

Reversing a Singly Linked List

Introduction Many people have asked me to explain the dynamics of how the reversing of a singly linked list works, when we do not have the liberty of creating a new linked list, may be due to limitation of memory. The Idea behind Reversing a Singly Linked List The idea is to iterate through the complete linked list and maintain three pointers as listed below: Pointer to the head of un reversed list headOfUnReversedLL. Pointer to the head of reversed list headOfReversedLL. Pointer to the node to be reversed nodeToReverse. In each iteration we follow the below four steps: The h...
Read More

Shortest Path Using Bellman Ford Algorithm

Introduction This post about Bellman Ford Algorithm is a continuation of the post Shortest Path Using Dijkstra's Algorithm. While learning about the Dijkstra's way, we learnt that it is really efficient an algorithm to find the single source shortest path in any graph provided it has no negative weight edges and no negative weight cycles. The running time of the Dijkstra's Algorithm is also promising, O(E +VlogV) depending on our choice of data structure to implement the required Priority Queue. Why Bellman Ford Algorithm? There can be scenarios where a graph may contain negative weight ...
Read More

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