Algorithms – Ritambhara Technologies – Coding Interview Preparations

Check if a Tree is Almost Complete Binary Tree

Sep 092017

Algorithms Tags:Binary Tree 9 Responses »

Given a pointer to the root node of the tree, write code to find if it is an Almost Complete Binary Tree or not?

A Binary Tree of depth d is Almost Complete iff:

The tree is Complete Binary Tree (All nodes) till level (d-1).
At level d, (i.e the last level), if a Node is present, then all the Nodes to the left of that node should also be present.

For example, the left tree below is NOT an Almost Complete Binary Tree but the right tree is an Almost Complete Binary Tree

    NOT Almost Complete           Almost Complete Binary Tree
   --------------------           ---------------------------
          _ A _           |             _ A _
        /       \         |           /       \
       B         C        |          B         C
     /   \     /   \      |        /   \     /   \
    D     E    F    G     |       D     E    F    G
   / \        / \         |      / \ 
  H   I      J   K        |     H   I

The left tree is not almost complete because in the last level, the nodes left to Node-J are missing (children of Node-E).
Continue reading »

Separate Chaining: Hashing collision handling technique

Aug 042017

Algorithms Tags:hashing No Responses »

It is almost impossible to design a generic hash system without collision. In case of collision, it need to be handled. There are multiple ways of handling collision. Separate chaining is one of such techniques.

Check if two node are siblings in a binary tree

Aug 012017

Algorithms Tags:Binary Tree No Responses »

Given a binary tree and two values. Find if these values appear in sibling nodes in the tree. For example, if tree is

Then 2 and 6 are siblings but 6 and 9 are not siblings (they are cousin nodes).

Check duplicate parenthesis in an expression

Jun 292017

Algorithms Tags:Array, Stack, String No Responses »

A valid mathematical expression can also have duplicate parenthesis as shown below:

((a+b))
(((a+(b)))+(c+d))

Write code to find if an expression has duplicate parenthesis. You may assume that expression does not have any white spaces. Continue reading »

Next greater element

Jun 282017

Algorithms Tags:Array No Responses »

Print Next Greater Element for every element in the array. The Next greater Element of element x is first greater element on its right side.

Elements for which no greater element exist, next greater element is -1.

Example:
- For any array, rightmost element always has next greater element as -1.
- All elements of an array sorted in decreasing order have next greater element as -1.
- For input array {5, 9, 1, 15}, the next greater elements of each element are as follows.
{9, 15, 15, -1}
- For input array {20, 17, 15, 10}, the next greater elements are {-1, -1, -1, -1}

Adjacency matrix implementation of Graph data structure

Jun 102017

Algorithms Tags:Graph No Responses »

Binary tree is a specialization of Graph data structure. Node in a Graph is called a Vertex and the connection between two vertices is called an Edge.

If we use this terminology, A Binary tree edge is only from a parent to its (at the most two) children. In Graph, any vertex (Node) can connect to any vertex and there is no limit on the number of vertices that a vertex can connect to. The connection can be uni-directional (as in Binary trees) or bi-directional. When connections are uni-directional the edge is called directed edge and graph is called directed graph. When connections are bi-directional, edge is called un-directed edge and graph is called undirected graph. Because of these connections, there is no hierarchy among the vertices of a Graph. Continue reading »

Recursive implementation of Insertion Sort

May 282017

Algorithms Tags:Array; Sorting, Recursion, Sorting No Responses »

We discussed Insertion sort in detail earlier. This post shows the recursive implementation of Insertion Sort. Continue reading »

Count frequency of a number in a sorted array

May 262017

Algorithms Tags:Binary Search, Divide-n-Conquer No Responses »

Given a sorted array of numbers and a number x, count the number of occurrences of x in the array.
Input:

int arr[] = {1, 3, 3, 4, 4 ,5, 5, 5, 7, 8, 8};	int x = 5;
Output:
3

Counting Sort

May 172017

Algorithms Tags:Array; Sorting No Responses »

It is used when there are few unique elements in an array. Counting sort takes O(n+k) time in the worst case, where n is number of elements and all the elements are in the range 1 to k (both inclusive). Continue reading »

Add sum of all previous elements in array (DPFCI_1.2)

May 122017

Algorithms Tags:Book Solution, Dynamic Programming for Coding Interviews 2 Responses »

This question is from exercise in my book Dynamic Programming for Coding Interviews (Question: 1.2, Page-5)

Question: Given an array, arr of integers, write a recursive function that add sum of all the previous numbers to each index of the array. For example, if the input array is

{1, 2, 3, 4, 5, 6}

then your function should update the array to

{1, 3, 6, 10, 15, 21}

Older Entries