2. Swap bits

Question : Given a number and 2 indices return the number after swapping bits present at those indices.

Method-1 : Brute-Force
We can swap bits by following the given steps :-
1. Using bitmasks to extract the ith and jth bits.
2. Save the extracted bits to some local variables.
3. Write the jth  bit to the ith position and vice-versa.

int bitSwapBruteForce(int x, int i, int j){
	int temp1= ((x & (1<<i)) !=0);
	int temp2= ((x & (1<<j)) !=0);
	x = temp1==1 ? (x | ( temp1<<j) ) : (x & ~(1<<j));
	x = temp2==1 ? (x | ( temp2<<i) ) : (x & ~(1<<i));
	return x;
}

The Time Complexity : O(1), only a constant amount of operations are required.
The Space Complexity : O(1), only a constant amount of extra space required.

Method-2 : Oh! Its beauty.
Since a bit can take only two values we can do better, lets swap only when bits differ. We’ll use the magical XOR once again.


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

As ith and jth bits of num differ, only 1 of them would be 1, resulting in bitMask having only one 1 in its bit representation. Now the XOR would swap the bits with help of bitMask.

For num=(1110)2, i=0, j=2;
bitMask=(1)2 | (100)2 = (101)2
num = (1110)2 XOR (0101)2 = (1011)2

The Time Complexity : O(1), only a constant amount of operations are required.
The Space Complexity : O(1), 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!:)

Advertisements

1. Parity of a Word

Question : Compute the parity of a 64-bit word.
Parity of a number refers to whether it contains an odd or an even number of 1’s in its binary representation. The parity of a number is 1 if it contains odd number of 1’s, else 0.

Method-1 : Brute Force
We can iteratively test the value of each bit while tracking the number of 1’s seen so far.

int Parity (long x){
	int result=0;
	while(x){
		result+=(x&1);
		x>>1;
	}
	return result%2;
}

 

The Time Complexity : O(n), where n is the number of bits in the word.
The Space Complexity : O(1), only a constant amount of extra space required.

Method-2 : A better Approach
We can apply the method that is used to compute the number of 1’s in the bit representation of a number.

int Parity (int x){
	int result=0;
	while(x){
		x=x&(x-1); // removes the lowest set bit.
		result^=1;
	}
	return result;
}

x-1 contains last set bit of x as unset, hence there AND unsets that bit.
The Time Complexity : O(k), where k is the number of SET bits.
The Space Complexity : O(1), only a constant amount of extra space is required.

Method-3: CACHE!
The original question asks us the compute the parity of a 64 bit number, previous methods are sufficiently fast to compute parity for such numbers, though if the computation has to take place for many numbers it is a better idea to cache our solutions and use them when required. Caching 2^64(9223372036854775808) numbers? Ah! does not look like a good idea. Better we can cache answers to first 2^16 numbers and then compute solution for larger numbers by combining the solutions of smaller segments. For a 64 bit number we’ll break the number into 4 segments of 16 bits. We’ll use the table to compute parities of all the 4 segments and then XOR the values to compute the final answer.

void precompute (void){
	for (int i=0;i<=int(pow(2,(sizeOfInt/4))-1);i++){
		Table[i]=parity(i);
		//cout<<i<<' '<<Table[i]<<endl; Uncomment this to check for yourself
	}
	return ;
}

 

int parityAns( int ParityOf, int BitMask, int wordSize){
	return ( Table [ParityOf>>( 3 * wordSize)]
	^ Table[( ParityOf >>  ( 2 * wordSize ) ) & BitMask]
	^ Table[( ParityOf >> ( wordSize ) ) & BitMask]
	^ Table[ ParityOf & BitMask] );
}


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.

Method-4 The Final Blow
We can use the property of XOR to compute the parity.
say X consists of 4 bits(a,b,c,d), we ran the following steps on it.

X =        a     b     c     d
X=X^X>>1 = a    a^b   b^c   c^d
X=X^X>>2 = a    a^b  a^b^c a^b^c^d

The last bit contains the parity which we can extract by ANDing X with 1.

int parity(int ParityOf){
	int factorOfShift = sizeOfInt/2;
	while(factorOfShift){
		ParityOf^=(ParityOf>>factorOfShift);
		factorOfShift=factorOfShift/2;
	}
	return ParityOf & 0x1;
}

The Time Complexity : O(log n), where n is the number of bits in the word.
The Space Complexity : O(1), only a constant amount of extra space required.

Also we can combine the last 2 methods, the full working code to which 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! 🙂

A series on Programming Interview Questions

I have decided to write complete solutions and analysis of the questions that are frequently asked in programming interviews at major tech. companies for the position of Software Engineer/Software Engineering Intern.

This series will contain exhaustive list of solutions for all the problems posed in The Elements Of Programming Interviews, I will also maintain a Github repository for all the codes. They can be accessed directly using this EPI link.

pyDelhi Conference- An Affair with Python

Hey folks,
Did you just lose out on an opportunity to be a part of the pyDelhi conference? Come let’s have a look at it through my lens.

March 5th, 2016 was a much awaited day for me as I attended my first developer’s conference, the Pydelhi Conference. It took place in JNU amidst the beautiful lush green, state of the art campus

After registration formalities we got jet-black tees, with the Python logo over it, a pad and a pen to take away home.

The conference began with Anuvrat giving us the first snack of the day, the internet access ID and password.

It all started with a keynote by Kiran Jonnalagadda, the co-founder of Hasgeek, he talked about how python, savetheinternet campaign and politics are inter-related. It was a great 40 minute absorbing talk along with an intensive discussion on the philosophical and industrial aspects of development.

After this talk, simultaneously 3 talks/workshops started to take place in different rooms. Hence we had options to choose, the first divergence led us to Vagrant and Ansible.

Next in the line up for us was Jaidev Deshpande. I have just started reading about machine learning and data mining so this was one of the talks I was looking forward to. He told us about some good practices to follow while cleaning and validating data. He also told us about his project ‘Pysemantic‘, a data validation model.

The theme of data analysis continued with a workshop on ‘Deep Learning in NLP’, where Rishabh Shukla, made us acquainted with the Theano library used for deep learning. A good discussion went on about the freely available datasets.

Lastly, Manoj Pandey told us about data scraping and his experience with the various web scraping libraries such as Scrapy, BeautifulSoup used.

This conference gave us a great opportunity to interact with some of the most amazing minds working in the field. Be it Manu Gupta, a research scholar at MIT labs or an experienced beast in Gora Mohanty, everyone was up for long chats and exchange of ideas seemed like the only trading currency. This event not only deepened my love for python but also motivated me to take this community one step further. Looking forward to the bigger stage, Pycon India conference 2k16.

Learning the Bootstrap Framework

I would suggest you to go through the following resources in order to get yourself acquainted with Bootstrap

Read this StackOverFlow entry of the question “What is bootstrap”.

Microsoft: DEV203x Introduction to Bootstrap :- This course is extremely beginner friendly, Christopher Harrison would walk you through all the basic elements of the framework like Page Layout, Forms etc.

Halen Stevens “Bootstrap: You’re Doing It Wrong” :- This blog post highlights some of the best practices that you should follow in order to produce beautiful websites.

Lastly, you can always access the Official Bootstrap documentation to know more about it’s features.

List of resources to learn HTML/CSS

These are some of the best resources I found, read them in the sequential order.

Wikipedia’s entry of HTML and CSS :- Read what these words mean, their applications in the real world.

CodeCademy’s HTML/CSS track :- Hands down, it is the best way anyone could get comfortable with the basic structure and syntices.

Shay Howe’s Tutorials :- Though this may come as a little overwhelming, this is by far the best series for diving deeper into front end development. Go slow, take your time.

If you don’t understand much from Shay Howe’s Tutorials, you can use W3CSchools and TutorialsPoint (HTML, CSS).

At this stage you are ready to create some cool project of yours, go design a webpage, imitate one!

My take on Web Development

Having participated for few months in coding contests, I felt a need to switch, to learn a skill which would help me in bringing a difference to the lives of people. After giving a lot of thought to both Mobile App and Web Development, I went with the latter.

There are currently 3 billion people who have access to the INTERNET, it is almost 40% of the World’s total population, hence web is the closest you can get to the remotest of beings. If you can produce a web app that eases the lives of the people, the impact could be global. It’s fascinating, the power of INTERNET, without losing the place you are seated on, you can contribute to the development of your favorite programming language, the only prerequisite is a will to learn, with the help of the World Wide Web, millions of people, use MOOC to enhance their skills, daily. Websites like Github, LinkedIn act as  breeding platforms for the technologies of tomorrow. If you have useful content on your website, you’ll get the audience.

Tons of connections, a higher degree of satisfaction and a way to become a part of a project that could make lives of billions better, if that’s what you are looking for, Web Development is a great choice.