Given a binary search tree with 2 nodes swapped find number of pairs not following BST properties

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Given a binary search tree with 2 nodes swapped, give the number of nodes not following bst property. Follow up - Fix the BST, in the next post. Example Consider the BST: Following is the correct BST 10 / \\ 5 20 / \\ 2 8 Now we swap 8 and 20, and BST is changed. Input Tree: 10 / \\ 5 8 / \\ 2 20 In the above tree, nodes 20 and 8 must be swapped to fix the tree. [Read More]
inorder  Inorder traversal  bank-bazaar  binary-search-tree  BST  count 

Program to count leaf nodes in a binary tree

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Count leaf nodes in a binary tree Solution Method 1 - Recursive Here is the logic: If node is NULL then return 0. Else If left and right child nodes are NULL return 1. Else recursively calculate leaf count of the tree using below formula. Leaf count of a tree = Leaf count of left subtree + Leaf count of right subtree Here is the recursive solution: [Read More]
Binary Tree  BT  kodeknight  count 

Count the number of 2s between 0 and n

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

Problem Write a method to count the number of 2s between 0 and n. Example Input Range : between 0-20, Output : 3 (i.e 2, 12 , 20)) Solution We need recursion. The number n can be broken down into a couple of ranges. The number of 2’s of numbers in each range is independent of each other. For example, 3345 can be broken into [0, 3000] and (3000, 3345]. [Read More]
kodeknight  hard  CrackingTheCodingInterview  count 

Count the number of digits in the number

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

Problem Given the integer, find the number of digits in the integer. Solution Method 1 - Brute force using loop Keep dividing the number, until it is 0. This will give us the count of number. Java code public static int getSize(long number) { int count = 0; while (number > 0) { count += 1; number = (number / 10); } return count; } Method 2 - Convert to string [Read More]
kodeknight  divide and conquer  count 

Count the number of calls of put() and get() for a map in Java

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

Problem Suppose you are using a map in your program, how would you count the number of times the program calls the put() and get() functions? Solution Method 1 - Implement the map interface with static count field One simple solution is to put count variables for get() and put() methods and, whenever they are called, increment the count. We can also achieve this by extending the existing library map and overriding the get() and put() functions. [Read More]
kodeknight  CrackingTheCodingInterview  count  java 

Number of unique elements in sorted array with repeated elements

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

Problem Find the number of unique elements in sorted array with repeated elements. Follow up - How can you do it without using extra space Example Input = [1,1,1, 2] Output = 2 i.e. 1 and 2. Example for follow up Input = [1,1,2] Output = 2 Solution It’s not really possible to know in constant time how many unique items are in a collection, even if the collection is sorted, unless you only allow one instance of the item in the collection at any given time. [Read More]
kodeknight  duplicate  count  sorted-array  java 

Count total set bits in all numbers from 1 to n

 Posted on March 23, 2014  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n. Examples Input: n = 3 Output: 4 Input: n = 6 Output: 9 Input: n = 7 Output: 12 Input: n = 8 Output: 13 Solutions Method 1 - Simple - Count bits in individual number upto n A simple solution is to run a loop from 1 to n and sum the count of set bits in all numbers from 1 to n. [Read More]
kodeknight  bits  count 

Count number of bits to be flipped to convert A to B

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

Problem You are given two numbers A and B. Write a function to determine the number of bits need to be flipped to convert integer A to integer B. Example Input: 73, 21 Output: 4 Representing numbers in bits : A = 1001001 B = 0010101 C = \* \*\*\* C = 4 Solution Method 1 - Counting the bits set after XORing 2 numbers 1. Calculate XOR of A and B. [Read More]
kodeknight  CrackingTheCodingInterview  bits  count  xor 

Find the rotation count in rotated sorted array

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

**Question : **Find the minimum element in the rotated sorted array. So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Solution This can be solved in linear time and logarithmic time. If we notice the above array, we see the array has been rotated 2 times, which is also the index of smallest element in the array. [Read More]
ArraySearch  kodeknight  recursion  array  rotated array  count  min  sorted-array