Print binary representation of a decimal number
Posted on March 21, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
intPart »= 1; this is fr wat?
Unknown - Jul 6, 2014
intPart »= 1; this is fr wat?
Hi Chaitrali, sorry for the delayed response. This means division by 2.
In general, bit_arg»shift_arg shifts bits to of bit_arg shift_arg places to the right – equivalent to integer division by 2^shift_arg
Print binary representation of a decimal number
Posted on March 21, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem
Given a (decimal – e.g. 3.72) number that is passed in as a string, print the binary representation. If the number can not be represented accurately in binary, print “ERROR”.
Solution
This is equivalent to implement toBinaryString() method built in Java API.
Lets think about the IEEE-754 standard. In a 32-bit machine, the 1st bit is for sign, 2nd – 9th digits are for exponent and the rest are for mantissa.
[Read More]You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes Create an algorithm to decide if T2 is a subtree of T1
Posted on March 21, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes Create an algorithm to decide if T2 is a subtree of T1
Solution
Method 1 - Brute force
Traverse T1. If the current node is equal to the root node of T2, traverse both of the trees (T2 and the current subtree of T1) at the same time. Compare the current node.
[Read More]Print all paths in a binary tree which sum up to a value
Posted on March 21, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem
You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree – it does not have to start at the root.
Example
Consider a tree below:
10 / \\ 7 15 / \\ / \\ 8 9 11 1 input value = 16
[Read More]Set all bits of a number in a range equal to another number
Posted on March 21, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem
You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j).
**Example **
Consider the integer N, where we want to fit in M between bits i and j of N.
Input: N = 10000000000, M = 10101, i = 2, j = 6 Output: N = 10001010100
[Read More]Add arithmetic operators to make 3 1 3 6 = 8 true
Posted on March 21, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem: Add arithmetic operators (plus, minus, times, divide) to make the following expression true: 3 1 3 6 = 8. You can use any parentheses you’d like.
Solution: Method 1 - Hit and try
This is what I can think of : we can first see 3+1+3+6 =13 No Multiplying is not solution either (3+1+3)/6 No 48/6 = 8 but 48 cannot be made by 3 1 3.
[Read More]Add two numbers without using arithmetic operators
Posted on March 19, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
Write a function Add() that returns sum of two integers. The function should not use any of the arithmetic operators (+, ++, –, -, .. etc).
Solution
We can get carry by &(and) operator and bit by ^ (xor) operator. We have already seen, how we can use bit-wise operators to replace arithmetic operators i.e. implement arithmetic operators using bitwise operators.
Method 1 - Iterative method
int Add(int x, int y) { // Iterate till there is no carry while (y !
[Read More]Convert sorted array to Balanced BST
Posted on February 26, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.
Examples
Input: 1 2 3 4 5 6 7 Output: 4 / \\ 3 6 / \\ / \\ 3 4 6 7 Solutions ** Method 1 - Take the array’s middle element and insert it recursively**
Pick up the middle element of the array Set it as the root Recursively build up left and right subtrees with lower and higher halves of the array Here is the code in java:
[Read More]Determine if a small tree T2 is the subtree of a huge tree T1
Posted on February 13, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
Solution
Method 1 - Traversing through T1 and finding subtree at each node, if T1’s node = T2.root
Here’s what we will do:
Traverse T1. If the current node is equal to the root node of T2, traverse both of the trees (T2 and the current subtree of T1) at the same time.
[Read More]Create linked lists of all the nodes at each depth for a BST
Posted on February 10, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists)
Example
So a binary tree such as :
(1) / \\ / \\ (2) (3) / \\ / \\ (4) (5) (6) (7) Will return linked lists:
(1) => NULL (2) => (3) => NULL (4) => (5) => (6) => (7) => NULL Solution
[Read More]