May 282017

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

May 122017

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}

Continue reading »

May 042017

Given two sorted arrays of size m and n respectively. Also given an empty third array of size (m+n). write code to merge the two arrays and store the result in the third array.

          a = {1, 4, 5, 9}
          b = {0, 2, 3, 7, 15, 29}
          c = {0, 1, 2, 3, 4, 5, 7, 9, 15, 29}

Continue reading »

May 032017

The structure of Node of a Binary Tree and Doubly linked list are same.

struct Node
   int data;
   Node* left;
   Node* right; 

 Structure of Node of a Binary Tree    

struct Node
   int data;
   Node* previous;
   Node* next; 

  Structure of Node of a Doubly linked list

If we treat left pointer as previous and right pointer as next, we can use the Node of a Binary Tree to represent node of a Doubly linked list or vice-versa.

Given a binary tree, modify the pointers in each node of the tree so that they represent a Doubly linked. Order of the nodes in DLL should be same as that in the in-order traversal.

If the Input Binary tree is as below

Binary Search Tree

then the function should modify pointers in the nodes, as shown below and return the head pointer.

Doubly Linked List
Continue reading »

May 012017

String matching is a big research area and there are many data structure (eg. B-Tree, HashMap, Set) that help indexing of strings. There are also many algorithms used for string matching (like KMP, etc.)

The major application of Trie data structure is in storing a dictionary (Collection of strings) such the searching for a word in dictionary become O(k) time operation where k is the number of characters in the word. Continue reading »

Apr 262017

Given a Binary tree, write code to find the length of longest path such that value of node in that path are consecutive and in decreasing order. For example is the tree is

Then output should be: 3 because path (5, 4, 3) has all nodes in consecutively decreasing order.

Note that Path <5, 6, 7> are also consecutive, but they are not in decreasing order, hence not considered. Continue reading »