Invert a Binary Tree

What makes this question special is this tweet.

He questions the interview process, I am with him. But whatever it is, it is.

Question : Invert a binary tree. Return the root of the inverted tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9
    
    to
   
     4
   /   \
  7     2
 / \   / \
9   6 3   1

 I would request you to change tabs or minimize your browser and give a good 30-40 minutes before seeing the solution.

Solution :-
As you can see in the example, all nodes have their siblings inverted or swapped! So we can recursively swap siblings for every node. But we cannot do it in one function, hence using another function to do the recursion work is required.

void inv(TreeNode* root){
    if(root==NULL)
        return;

    swap(root->left, root->right);

    inv(root->left);
    inv(root->right);
}

TreeNode* Solution::invertTree(TreeNode* root) {
    inv(root);
    return root;
}


The Time Complexity : O(n)
, since each node is visited once. Here n is the number of nodes.
The Space Complexity : O(h), as this many function calls will be put on the stack in the worst case, here h is the height of the binary tree. h ∈ O(n)

The full working code is available at Github, you can star the repository to get updates. I am also maintaining an Interview-Question-Wiki, kindly star and contribute. You can also follow this blog for more such posts. Comment in your queries, report bugs, discuss!:)

Data structures and algorithms practice resources

Data Structure and Algorithms resource guide.

bryanttunbutr

Here are the sites I have experience with and my thoughts

  • LeetCode is excellent because there are many problems and explanations. Furthermore the problems without explanations have answers and commented solutions in the discussion boards. It is the best online judge in my (limited) experience.
  • Code Wars is fun and great for learning a specific language and its features, i.e. JavaScript. But I did not find it as valuable for algorithms.
  • Cracking the Coding Interview has many questions and detailed answers in Java.
  • Data Structures and Algorithms Made Easy in Java is excellent. Sure there are many, many, many typos. But it has so many code samples for each of the data structures, explanations from worse (brute force) to best (optimized) along with advantages and disadvantages of the many possible solutions.

An honorable mention goes to Free Code Camp. The first time I ever had fun solving code challenges…

View original post 35 more words

Compare Versions

 

Given two strings which represent different version releases of a software, print -1, 1 or 0 depending on the order of the releases.

If version1 was released after version2 print 1,
If version1 was released before version2 print -1,
otherwise print 0.

Assumptions granted : Strings may only contain digits and the ‘.'(dot) character and must contain atleast 1 character.

The ‘.’ character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:
0.1 < 1.1 < 1.2 < 1.13 < 1.13.4

version number such as 1, 01, 1.0 are equivalent.

I would request you to change tabs or minimize your browser and give a good 30-40 minutes before seeing the solution.

This is a basic implementation based question, the only thing to take care about is the sequence of 0’s that may crept in after a dot.

WordPress is not rendering the code properly so kindly check out the code here on github.

Time Complexity   : O(n), where n is the sum of the lengths of the 2 versions.
Space Complexity  : O(n), where n is the sum of the lengths of the 2 versions.

It can also be done with the space complexity of O(1), with the help of substr function, left as an exercise. 

You can follow this blog for more such posts. Comment in your queries, report bugs, discuss! 🙂

Step by step Kaggle competition tutorial

A clean and concise guide to Data Science.

Datanice

Kaggle is a Data Science community where thousands of Data Scientists compete to solve complex data problems.

In this article we are going to see how to go through a Kaggle competition step by step.

The contest explored here is the San Francisco Crime Classification contest. The goal is to classify a crime occurrence knowing the time and place it happened.

Screenshot from 2016-04-10 10:06:15.png

View original post 916 more words

3. Reverse Bits

Question : Write a program that takes a 64-bit word, output the reverse of that word.
I would urge you to minimize the window and try to solve this question on your own first.

 

Method – 1 Brute Force Solution
Simply apply the bitswap method we used earlier on all the extreme bits.

int bitSwap(int num, int i, int j){
	if( ( ( num>>i ) & 1 ) != ( ( num>>j ) & 1 ) ){
		int bitMask = (1<<i) | (1<<j);
		num ^=bitMask;
	}
	return num;
}

int reverseBits(int num){
	if(num!=0){
		int noOfBits=log2(num)+1;
		for(int i=0, j=noOfBits-1; i<j ; i++,j--){
			num=bitSwap(num,i,j);
		}
	}
	return num;
}

Time Complexity : O(k), where k is the number of bits in the number.
Space Complexity : O(1).

Method -2 Cache!
Just like the parity bit solution we can cache the solution of smaller bits (say 16) and combine the results.

void precompute (void){
	for (int i=0;i<=int(pow(2,(sizeOfInt/4))-1);i++){
		Table[i]=reverseBits(i);
	//	cout<<i<<' '<<Table[i]<<endl;
	}

	return ;
}
int reverseBitsUsingTable(int reverseOf, int wordSize, int bitMask){
	if(reverseOf<(1<<sizeOfInt/4))
		return Table[reverseOf];

	if(reverseOf<(1<<2*sizeOfInt/4)) 		return  Table[(reverseOf >> (wordSize))&bitMask] |
		Table[(reverseOf & bitMask)]<<(wordSize);

	if(reverseOf<(1<<3*sizeOfInt/4)) 		return Table[(reverseOf >> (2*wordSize))&bitMask] |
		Table[(reverseOf >> (wordSize))&bitMask]<<(wordSize) |
		Table[(reverseOf & bitMask)]<<(2*wordSize); 	return  Table[((reverseOf >> (3*wordSize)))&bitMask] |
	Table[(reverseOf >> (2*wordSize))&bitMask]<<(wordSize) | 	Table[(reverseOf >> (wordSize))&bitMask]<<(2*wordSize) |
	Table[(reverseOf & bitMask)]<<(3*wordSize);

}

The Time Complexity : O(n/L + 2^L), where n is the number of bits in the word and L is the width of the word for which we cache the results. 2^L time will be taken to prepare the table, if L is known beforehand we can remove it from the notation, as we only talk about the growth of function in Big-Oh Notation.
The Space Complexity : O(2^L), only a constant amount of extra space required.

The full working code is available at Github, you can star the repository to get updates. You can also follow this blog for more such posts. Comment in your queries, report bugs, discuss!:)

Standard Template Library : An Introduction

What is the Standard Template Library(STL) ?
The Standard Template Library (STL) is a software library for the C++ programming language. It provides four components called containers, iterators, algorithms and functional. STL library lies in the std namespace.

Why do we need to use the STL?
1. There is no use in inventing a wheel that has been in presence for decades.
2. STL in C++ provides humongous number of ready-made common classes, such as containers that can be used in any built and user defined type, that supports elementary operations like (such as copying and assignment).
*You should know how to write these data structures yourself. This knowledge will help you choose the best STL data structure required for your need.

Containers :
Containers are objects that store data. Inbuilt implementations of various abstract data types are available in STL.

The container manages the storage space that is allocated for its elements and provides member functions to access them, either directly or through iterators (objects with similar properties to pointers).

Most containers have at least several member functions in common, and share functionalities. Which container is the best for the particular application depends not only on the offered functionality, but also on its efficiency for different workloads.

Header file :- In most of the cases, header files of the container have their name of the of form, <containerName>. For instance the header files of vector, stack, deque are <vector>, <stack>, <deque> respectively.

Iterators :
An iterator is any object that, pointing to some element in a range of elements (such as an array or a container), has the ability to iterate through the elements of that range using a set of operators (with at least the increment (++) and dereference (*) operators).

Header file :- <iterator>
There are 5 types of iterators :-
InputIterator 
OutputIterator
ForwardIterator
BidirectionalIterator
RandomIterator.

Algorithms :
The algorithms library defines functions for a variety of purposes (e.g. searching, sorting, counting, manipulating) that operate on ranges of elements. Note that a range is defined as [first, last) where last refers to the element past the last element to inspect or modify. The exhaustive list of functions available in algorithm can be read from cplusplus reference.

Header file :- <algorithm>

Functional :
Functional provides a set of predefined class templates for function objects, including operations for arithmetic, comparisons, and logic.

Header file :- <functional>

So now that you are aware of the basic STL terminology in the coming posts we will go through the features of the most commonly used containers one by one. Don’t forget to subscribe, love, code and discuss. 🙂

Numbers and recipes at Codenmath.com

A much awaited day, a long lost dream, finally comes to life with codenmath.com, a wish I had for 9 years now; has awaken only to become a reality. At last a place where I can share all my knowledge, of whatever I have. A belly that has been so full of words will finally get some peace.

I would be sharing my views on numbers, scripts, programs, movies and maybe eh humans! To start of, my favorite number is 28, the only number known to mankind that can be represented as a sum of first few prime numbers(2,3,5,7,11), first few composite numbers(4,6,8,10) and as the sum of its own proper factors(1,2,4,7,14). Fascinating.

Behold! fasten your seat-belts for the ride that is about to come! Also let us know your favorite number. 🙂