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 

Arrays Index

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

Rotated array How to rotate an array? Rotated sorted array Find the minimum element in the rotated sorted array. Find the rotation count in rotated sorted array Find Nth largest element in the rotated sorted array Search an element in the sorted rotated array  Sorted Infinite Arrays Searching the element in sorted infinite array of integers Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 . [Read More]
kodeknight  Page