Introduction
The topological ordering for graphs get many applications where the nature of the problem is ordered sequential processing. Few of the problems in this category are as follows:
Dynamic Linking/Loading of programs while building and execution.
Deciding the pre-requisites in a course structure.
Job Scheduling in Processors or Assembly Line Processing.
Building an Alien Dictionary from given words.
There are many more but I am sure you got the idea. When we say topological ordering of graph, we are necessarily talking about the ordering of the vertices of the graph.
Un...

Read More
# Amazon Interview

## Left Hand Projection of a Tree

Introduction
Another interesting interview question, this question has many forms. One of the form is print the left hand projection of a tree or right hand projection of a tree or so on. Also, this problem can be specialized for a binary tree, ternary tree or n-ary tree, it really doesn't matter, the concept is the same.
We will just try and print the left hand projection and I will add a note on how to print the right had project and you can try that yourself.
Understanding the problem - Left Hand Projection of a Tree
Let us consider the below tree for our problem statement.
What is...

Read More
## Filling Wine Glasses Interview Question

Introduction
This is another interesting interview question and took me sometime to think for an answer. The problem statement goes as follow:
"There are wine glasses stacked such that the top level has one glass, the second level has two glasses, the third one has three glasses and so on.
Imaging that the levels are deep enough. Each of the glass in the stack has volume u. Now given a jug of volume V full of wine such that V >= u, find the lowest level where wine can reach."
Analyzing the problem statement
Here is a supporting image for the problem statement.
Now I pick up the ju...

Read More
## Student Enrollment Interview Question

Introduction
This is another interview question which I find interesting. The problem statement goes as follow:
"Its the beginning of a new academic year and I am a teacher of Data Structures and Algorithm subject. Many students with distinct roll numbers want to enroll for the class. After sometime few students wanted to opt out from the enrollment because they found some other subject much more interesting. Now, I also have a teaching assistant who can ask me the roll number of a student who is still enrolled into my class. It is not mandatory to tell him a different roll number every ti...

Read More
## Polynomial Operations

Introduction
This is a famous interview question where it is asked to write program for simple arithmetic polynomial operations. The operation may include adding, subtracting and multiplication of two polynomials (mostly in one variable).
For those who want to refresh their knowledge of polynomials, I would include a section below:
Understanding Polynomials
Polynomials are mathematical expressions of the form a1xnym + a2xn-1ym-1+ . . . + akxn-ky + . . . + anx + an+1.
The above polynomial is said to be a polynomial in two variables (x and y).
a1xn + a2xn-1 + a3xn-2 + . . . + an-1x + ...

Read More
## 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
## 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