My software development journey
Given the in-order, and pre-order or post-order sequences of a binary tree, how do we construct a binary tree from them?Given only pre-order and post order traversals, we can not construct a unique binary tree from them.For example given In-order : {1, 2, 3, 4, 5, 6, 7, 8}Pre-order: {5, 3, 2, 1, 4, 8, 6,…
There are some gas stations arranged in a circle. Each of them has some amount of gas. We are also given the distances between all the consecutive stations. Assume that we have a vehicle with very large fuel tank(infinite) and one unit of gas is needed to cover one unit of distance, the problem is…
Given an array of positive and negative numbers, find the maximum sum of any sub sequence such that no two elements are contiguous.For example consider the array {3,-2, 1, 7}, maximum sum is 10 for {3,7}For {3,-2, 1, 0, -4, 2} it is 6 for {3,1,2}This problem can be efficiently solved in O(n) time using…
Given a string consisting of only 0s and 1s, How do we write a program to find the longest sub string with equal number of 0s and 1s in it? For example consider the string “01001”, the longest string with equal number of 0s and 1s is “1001”. Let us look at the solution approaches.Considering…
Given a string, how do we write a program to find the length of longest sub-string without any characters repeating in it. Let us call it a unique sub string. For example consider the string “program” the maximum length of a unique sub-string is 5 for the sub string “ogram”. A method by checking all…
Given an array of unique elements, Write a program to print all Pythagorean triples in it. A Pythagorean triple is a set of three numbers such that square of one number is the sum of squares of the other two. For example (3,4,5) is Pythagorean triple because 52 = 32 + 42 Consider the array {5, 6, 3,…
Given an a rooted n-ary tree represented as a parent id array, Write a program to find the depth of it. The depth of a tree is defined as the maximum length of the path from root to any leaf node. For example the following tree has a depth of 2 (for the path 0-2-4) It…
Given an array of numbers, how do we count the number of inversions in it? Suppose we are sorting an array of numbers in increasing order, an inversion is an ordered pair of indices (i,j) such that i < j and A[i] > A[j] . For example consider the array {3, 2, 1,…
Given a set of intervals, how do we find the maximum number of intervals overlapping at any point of time. For example let us consider the following intervals. { (0,2), (3, 7), (4,6), (7,8), (1,5) } The maximum number of intervals overlapped is 3 during (4,5). This can be asked in many forms in a…
Given a number expressed in base, exponent form (ab) where a is arbitrary big number For example contains 100 digits, We have to write a program to find the last digit in it’s expanded form. Eg: 45712 has a last digit of 1 Since the range of numbers is huge, it is impossible to expand…