Multiply a number by a power of two using bit left shift

 Posted on January 17, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Remember the bit shift operation? « and »? Well if we left shift a number, we are multiplying that number by a power of two. For example, 1 = 0001. If we left shift it by 1, we’ll have 1 « 1 = 0010 = 2 = 1 * 2^1. If we left shift it by 2, we’ll have 1 « 2 = 0100 = 4 = 1 * 2^2. Thus, the general formula is: [Read More]
kodeknight  bits 

Find largest Binary Search Tree in a Binary Tree

 Posted on January 17, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Find the largest Binary Search Tree in a given Binary Tree.

…Solution will be posted soon.

Update : Solution

Traverse the tree. From each node to the parent, return the following
set of values.

  1. If BST, size of the current BST or -1 if the tree is not.
  2. Minval & Maxval of the subtree and maxbstsize seen so far (
    probably using references)

So in each node check the following:

kodeknight  Amazon  incomplete 

Convert Binary tree to Binary Search Tree conversion in place

 Posted on January 17, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

http://stackoverflow.com/questions/5468015/convert-binary-tree-to-binary-search-tree-inplace-using-c

http://stackoverflow.com/questions/2577098/how-to-convert-a-binary-tree-to-binary-search-tree-in-place-i-e-we-cannot-use

http://www.geeksforgeeks.org/binary-tree-to-binary-search-tree-conversion/

conversion  kodeknight  Amazon  incomplete 

Given a stream of characters, find the kth non-repeated character at any given time.

 Posted on January 17, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Solution: - Use an array of size 256, and update the count of each characters as arrives - Use another array of same size, to keep track of order of the characters appeared in the stream, update this stream only if count of that character is 0 in the first array before updating. When you need to find the kth non-repeating character, start traversing the second array and get the count, You can get the kth character whose count is 1 in the first array [Read More]
kodeknight  Amazon 

Find all the pythagorean triplets in an array of integer

 Posted on January 17, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Given an array a of n integers find all possible Pythagorean triplets from the array. A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. this formula is derived from Pythagoras theorem: _“For every right angle triangle with side lengths a, b, and c=> a_2 + b2 = c2“. Solution: Conceptually it is similar to Find Non duplicate pairs that sum to S and 3 SUM problem [Read More]
kodeknight  2Sum  pythagorean triplet  Amazon 

3 sum problem

 Posted on January 17, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem Statement: Problem Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = 0.  Making more generic:  Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = T. Solution Brute force approach is of O(n^3) but we can solve it in O(n^2) by using the approach in 2 sum problem approach. [Read More]
kodeknight  2Sum  array  CrackingTheCodingInterview 

Maximum value in a Sliding Window

 Posted on November 12, 2013  (Last modified on August 7, 2020)  |  11 minutes  |  Kinshuk Chandra

Problem Statement Question: A long array A[] is given to you. There is a sliding window of size w, which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Example: The array is [1 3 -1 -3 5 3 6 7], and w is 3. Window position Max \--------------- ----- \[1 3 -1\] -3 5 3 6 7 3 1 \[3 -1 -3\] 5 3 6 7 3 1 3 \[-1 -3 5\] 3 6 7 5 1 3 -1 \[-3 5 3\] 6 7 5 1 3 -1 -3 \[5 3 6\] 7 6 1 3 -1 -3 5 \[3 6 7\] 7 Input: A long array A[], and a window width w [Read More]
max  Algorithms  kodeknight  queue  deque  Amazon  PriorityQueue  facebook  stack  window