Jun 282017

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.

- 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}

Continue reading »

Jun 102017

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 »

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 »