Interview Questions

This category contains few tricky questions asked in interviews..

Inorder Predecessor of node in Binary Tree Using Parent Pointer

Introduction This is the seventh article in the Tree Traversals - Online Classes. This article presents ways to find out inorder predecessor of node in binary tree. As we have already read about the Inorder Successor it wont take much effort to understand the predecessor. Definition - Inorder Predecessor of node in Binary Tree If a node K is called the inorder predecessor of node N then N must be visited immediately after K in a inorder traversal of the tree. Below is a more formal definition of Inorder Predecessor: If the node has a left sub-tree, then inorder predecessor is the ...
Read More

Inorder Successor of node in Binary Tree Using Parent Pointer

Introduction This is the sixth article in the Tree Traversals - Online Classes. This article presents ways to find out inorder successor of node in binary tree. Before we jump into the code it would be good to correctly define the meaning of the problem. Definition - Inorder Successor of node in Binary Tree If a node K is called the inorder successor of node N then K must be visited immediately after N in a inorder traversal of the tree. Below is a more formal definition of Inorder Successor: If the node has a right sub-tree, then inorder successor is the left most node of the rig...
Read More

Arrays are permutation of each other

Problem Definition – Arrays are permutation of each other The problem definition goes as follows: Given two arrays of equal length, find out if the elements of one array is the permutation of the elements of another array. Of course the constraint is to solve it in constant space and linear time. Which means that the running time should be O(N) and auxiliary space required should be O(1). Approach There may be several thoughts which seem to work but eventually they will fail at one or the other ways. Here are few interesting ways which may not work for all the conditions: XORing the ...
Read More

Dutch Flag Problem

Problem Definition - Dutch Flag Problem The dutch flag looks like the below image. The problem "Dutch Flag Problem" derives its name from the arrangement of colors in the flag. The actual problem definition goes like this: Given an array of balls of three colors ( Red, White and Blue). The balls are kept in random positions in the array. We need to develop a mechanism which can arrange the balls in groups (based on colors). Below is the image of a possible input and the expected output. The balls of different colors in the above image are randomly distributed in the input where...
Read More

Shift Zeroes To Right

Problem Definition - Shift Zeroes To Right We are trying to solve a problem at hand in which we are given an array of zeroes and positive integers. We need to Shift Zeroes To Right and positive integers to the left without disturbing the relative order of the positive integers. Approach I try to solve the problem in a simple way, you may find a similar problem on the web, here is a approach which solves this problem in O(N) time using constant auxiliary space (may be one or two extra variables). The first thing which comes in mind can be traversing the array and swapping zeroes with the ...
Read More

Tree Diameter

Introduction This is the fifth article in the Tree Traversals - Online Classes. A very interesting problem is to find the diameter of a tree. The challenge is not in coding the algorithm but in understanding the meaning of the problem. We will try to define the problem so that visualizing the solution becomes easy. Defining the problem - Tree Diameter Few confusions about the diameter must be avoided before we start. The tree diameter is always the distance between two leaf nodes The diameter may or may not pass through the root. The diameter can also lie on one of the two sides,...
Read More

Spiral Traversal

Spiral Traversal or Zigzag Traversal in a Tree. This is the fourth article in the Tree Traversals - Online Classes. Recently I wrote an article on Level Order Tree Traversal. Another problem on the same lines is to traverse the tree in a zigzag manner. That is also termed as spiral traversal. This question has been asked in many companies during the interview process. Although it is not very specific problem, if you understand the idea behind traversing a tree in breadth first manner, then you can easily solve this. Please read further for more understanding. Defining the problem L...
Read More