Hedge Funds v/s Mutual Funds

funds.jpg

Recent efforts by the Indian government to weed out black money from the economy and increase the tax base have called for a paradigm shift in the way people in India choose to save their money. The pumping out of cash from the economy has brought the citizen to a point where he is considering alternative investment options to save his money. This has led to an increase in the number of people who are now investing in the securities and derivative market. With a boom in the stock market over the past year, people are now more inclined to invest in securities, while carefully trying to avoid losses. It is the success of these markets that Long term capital gain tax found its way into the Budget announcement in February this year.


What are Hedge Funds and Mutual Funds?
Hedge funds and Mutual Funds are investment funds made by the fund management companies. The aim of these is to generate profits by investing in more than single entity i.e. through a diversified portfolio.

How do they work?
Investment from different parties gets pooled into a single portfolio. Both (Hedge Funds and Mutual Funds) of these play the stock, invest in land, real estate, currencies and derivatives in order to have high capital gains. They decide upon different investment options with the will of maximising the profits and create a single portfolio out of it.

What are the differences between Hedge Funds and Mutual Funds?
ELIGIBILITY
Hedge Funds are regulated by SEBI and are registered under SEBI, Alternative Investment Funds Regulation 2012. A Hedge Fund should have a minimum corpus of Rs. 20 Crores and minimum investment of Rs 1 Crore by each investor or member of the fund.
Whereas, Mutual Funds are regulated under Securities and Exchange Board of India (Mutual Funds) Regulations, 1996. A firm interested in opening Mutual Funds must register as trusts under the Indian Trusts Act, 1882 and set up a separate Asset Management Company, with the net worth of the parent company / AMC be amounting to at-least Rs 5 Crores.

AUTONOMY
Hedge Funds may at times be only available to a list of high profiled businesses and individuals. They are entrusted with total autonomy and are are allowed to take key decisions at all times. This luxury is not available to the Mutual Fund investors. Owing to the low budget nature of their clients, they are required to be more cautious.

LIQUIDITY
When it comes to liquidity, hedge funds are somewhat stricter. One cannot withdraw their shares whenever they want to. There is a lockup period, during which one cannot withdraw their stake. In the case of mutual funds, one can withdraw their funds whenever they want to.


In the light of recent developments in the Indian securities ecosystem, hedge funds and mutual funds serve as lucrative investment options for corporates and public alike.

 

Advertisements

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!:)

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.