Given a node in binary tree - Check if left and right subtree are mirror of each other

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

Problem A binary tree is a mirror image of itself if its left and right subtrees are identical mirror images i.e., the binary tree is symmetrical. This is best explained with a few examples. Example 1 / \ 2 2 ```TRUE 1 / \ 2 2 \ 3 1 / \ 2 2 / \ / \ 4 3 3 4 1 / \ 2 2 / \ / \ [Read More]
Binary Tree  BT  kodeknight  Amazon 

Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1?

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

Problem Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1? Solution Method 1 - Using hashset on str2 and boolean array or hashset on str2 Break down the problem into two tasks. i) Finding the non-unique i.e. repeating elements in str 1. Hashing can be used for this purpose. ii) Finding if all the characters hashed in the first string are available in the second string. [Read More]
kodeknight  String  two-string  Amazon  Interview Question  unique 

Given a binary tree with extra field "next pointer" in node, populate the next pointer to the nodes inorder successor

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

Problem : Given a Binary tree where each node has an extra field (node * next), write a function that puts the inorder successor of that node in the next pointer. This is how our binary tree node looks like : struct node { int data; struct node\* left; struct node\* right; struct node\* next; } Initially, all next pointers have NULL values. Your function should fill these next pointers so that they point to inorder successor. [Read More]
inorder  Binary Tree  BT  kodeknight  Amazon  inorder successor  Inorder traversal 

Amazon Questions - Set 1

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

Write code to find Nth last node in a linked list. Solution Given a binary tree build a vertical sum array. Solution Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1? Solution Given two lists of strings return a list of strings that is an intersection of both of the lists. Analyze running time and space complexity. Give Test Case scenarios. [Read More]
kodeknight  Amazon  incomplete  Interview Question  interview-set 

Replace all spaces in a string with “%20″ in c-style string

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

Problem Write a C program that will replace all spaces with ‘%20′ Example Input: “Mr John Smith " Output: “Mr%20John%20Smith Solution The algorithm is as follows: Count the number of spaces during the first scan of the string. Parse the string again from the end and for each character: If a space is encountered, store “%20”. Else, store the character as it is in the newly shifted location. [Read More]
kodeknight  String  java-code  Amazon  spaces  calloc  replace  CrackingTheCodingInterview  malloc 

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