Interview Questions

This category contains few tricky questions asked in interviews..

Shortest path in Binary Search Tree

Introduction Another interview question for the most interesting data structure called BST (Binary Search Tree). To know more about BSTs check my previous post. Problem Statement : Given a Binary Search Tree, keyed on positive integers. The task is to find the Shortest path in Binary Search Tree which adds up to the number K. If no such path exists, return a message accordingly. Understanding the problem A node in a binary search tree always has a higher key at its right child compared to its left child. There are many path running from the roots to the leaves. When we add up the key val...
Read More

Dynamic Programming – Longest Palindromic Sequence

[nextpage title="Introduction"] Palindromes are fascinating character sequences in a string. A palindrome is a string which reads the same when read from either of the ends. This post in particular talks about palindromic sub sequences. To know more about a sub sequence, please check my post on Longest Common Sub sequence. A palindromic sequence means a sequence of characters which is a palindrome. Now, we must understand it clearly that we are talking about a sub sequence and not a substring. Understanding the Longest Palindromic Subsequence problem better It is really easy to say if...
Read More

Binary Tree Linking Neighbors

Introduction Problem Statement : Given a regular binary tree with left, right and peer node pointers. The left and the right pointers are already populated. We need to make the peer pointer point to the next right neighbor on the same level. Understanding the problem Here is a diagram to explain what is needed. The red peer pointer points to the immediate right neighbor if the neighbor exists. Approach 1 The first solution which comes in mind is to do a custom, level order traversal as done in the post. And, in each iteration of the inner loop, just link each of the node to the next in ...
Read More

Matrix Transformation to make rows and columns zero

Introduction Another interview question about matrices. Matrices have been of great interest in programming and Linear Algebra and a matter of study for most of the programmers. The problem statement follows: "Given a matrix A of size M * N where M is the number of rows and N is the number of columns and each of its cell A[i][j] is populated with either zero or one. Transform the matrix such that if there exists a cell A[i][j] = 0 then the row i and column j is zero in the resultant matrix". You must not use extra space and try to solve it in lowest possible running time. Understanding...
Read More

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