Close

## Forming the nth binary sequence

A binary sequence contains 0 and 1 only S.No  Binary sequence——————–1     02     13     004     015     10…Given a number k, we have to design an algorithm to print kth binary sequence. Initial approach (not efficient): Starting from the sequence 0, this algorithm iterates k times. To get the next sequence, in each iteration we do the following. check the last…

## Building a binary tree using inorder and post/pre order traversals

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,…

## Gas station problem

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…

## Maximum sum of a subsequence with no contiguous elements

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…

## Longest substring with equal number of 0s and 1s

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…

## Longest substring with unique characters

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…