Algorithm Complexity - Interview Questions

If you say, the complexity of Hashtable is O(1), then with the same logic, I would say, NP=P, and I am more accurate than you. If you don't know what is NP and P, and whether they are equal or not, then please read more about complexity and algorithms.

Read any research paper (not the textbook written for kids or by just finished graduates) on algorithms, when they talk about complexity, they always mention worst case complexity. Whenever they want to mention anything other than the worst case, they explicitly mention it.

Many people take the average case and say that the complexity of hashtable is O(1). In the same way, if we take the average no.of NP-complete problems and their average complexity, the complexity would be polynomial only. There are many NP-Complete problems, where 99% of the inputs can be solved by using polynomial algorithm. So, in average case NP=P. In this case, the average is much closer to the worst case than the Hashtable.

Exponential algorithms

Some times, people use exponential numbers in the solution, and think that the solution is linear or polynomial. The moment, one uses exponential number, the entire solution becomes exponential.

I know one interviewer who has one favorite problem. That problem has linear solution. If anyone answers that question, he changes that question little bit, which has the complexity of O(n^2). But, if we use an exponential number, then the problem looks like it is linear. Of course, the moment they use exponential number, the entire solution becomes exponential, but, he was not aware of that. He rejected many candidates who solved with O(n^2), and accepted those who solved with exponential numbers but looks like linear. The interviewer was dumber than the interviewees and he could not recognize people who are more talented than himself. [Unfortunately, smart people getting rejected by dumb people is very common in the software industry.]

Given a number n, what is the complexity of printing all the even numbers from 1 to n? Is it linear, polynomial or exponential?

Many people think that, it is linear. But, the fact is, it is exponential. The complexity of an algorithm is always with respect to the input size. If the input is the number n, then the input size is (log n) (with base 2) [It is the no.of bits required to represent n]. If the no.of bits in n is m, then, we need to count 2^m times, which is exponential to the input size m.

To understand in a simple way, if an algorithm is linear, whatever time it takes to give the input, the output would be given in the same proportion. If you spend one second to give the input, the result would be given within few seconds. Whereas, for exponential algorithms, as the input size increases, the time taken to give the output would increase exponentially, and even for average size input, the computation cannot be done within a life time. For example, printing all the numbers from one to 100,000,000,000,000,000 cannot be done in one life time. It can never be linear or polynomial.

Travelling Sales person's problem.

Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.

This is one problem which I disagreed with many people. There is a difference between theoretical version and practical version. In most of the books, there is a condition that each city should be visited exactly once. In reality, for a real sales person, that is not possible. For many places, the sales person has to visit more than once for optimized travel. If we put restriction that, they cannot visit a place more than once, then the total distance is not optimized for the real sales person. They have to take round trip to visit the places, and finally end up travelling more distance. Many people stress that, Hamiltonian Cycle is required for the travelling sales person's problem. It is required for the theoretical version, but not for the practical version.

Both the problems are NP-Hard. But, if we put the restriction of visiting each city exactly once, then the problem becomes even more harder, and even the approximation is also NP-Hard. Whereas for the practical version, there are good no.of approximate algorithms, and for many cases you may even get the optimum solution. That may be one reason, why more importance is given to visiting each city exactly once.

If you are taking interviews, and if you ask without having good knowledge, I am sure, you will miss very good candidates. I know many people, who would reject even the professors of IIT in their area of interest.

Courtesy: Abhiram G. Ranade, Ajit A Diwan, Sundar Vishwanathan

Tolstoy on Indian Independence

Tolstoy's observation on Indian Independence.

A commercial company enslaved a nation comprising two hundred million. Tell this to a man free from superstition and he would fail to grasp what those words mean.... Do not these figures make it clear that not the English, but the Indians, have enslaved themselves.

The same can be applied even now. People elect the politicians, and they only criticize them. The people enslaved themselves, and criticize the politicians who are honest in their dishonesty.

Source for Tolstoy's Observation: Gandhi - A Sublime Failure by S.S.Gill

Anna Hazare - Other Perspective

Almost everyone in India is strongly supporting Anna Hazare and his movement against corruption. Only Congress and Lok Satta Parties asked him to withdraw his fasting. Many people were inspired by him, and they did fasting or campaigning within their capacity. I feel his way of solving the problem is not scalable and may mislead the people and India.

Except Politicians everybody hates Politics

India is a democratic country, and all the Indian citizens get right to chose the people who can rule us. If we chose that option carefully, we don't need to do anything else. But, instead of choosing that option, he has chosen fasting. I would have been more happy, if he had come forward during the elections and asked everyone to vote for a good political party. If he thinks, there is no political party which is good, he should have started a political party.

Unfortunately, except the politicians and their families, everybody else hates politics. During the elections, ask any NGO or social worker for helping in your election, they would simply reject it unconditionally. During the elections time, all these 'so called' social workers sleep, and after that for five years, they try to do everything possible. They want the anti-corruption bill to be passed. They want the corrupted politicians (who were in the assembly/parliament for more than couple of decades) to be punished. They ask people to participate in the movements for developing the country, and the list is endless.

Unfortunately, even Anna Hazare does not have good opinion about politics and politicians. He is against politics and politicians. He thinks that most of the politicians are bad (Initially, he said all politicians are bad) and does not want to meet them. If they are bad, why the people had voted for them in the first place? If we chose a corrupted person, he would do corruption. Politicians are honest in their dishonesty. We are doing wrong thing by voting for a corrupted person, and then we are fighting on the streets to punish that person. This kind of things done only by people who do not have any work or mind.

Spend one day in voting for a correct person, and you can take rest for five years. But, all these active people sleep on the voting day and fight for the next five years.

Voting bad people during election and then sitting on Dharna afterwards is much like not studying during exam and pleading professor for grace marks. - chanchal_p

Do we need a separate act for people's representatives

If atleast 20% of the voters take little interest, then we don't need any acts for people's representatives. Except sons and daughters of the senior politicians, almost everyone starts at a small level and gradually they become ministers. Those who come to politics without much background start their career as a corporator, councilor or surpanch. After that, they rise to Chairman/Mayor, then to MLA, then to Minister of State, then to Cabinet Minister and then to Chief Minister.

If the politician is doing corruption at any level, and if the voters immediately refuse him/her, do not vote him/her again in his/her life time, then nobody would do corruption. A corporator knows that, if he/she does corruption, he/she will never become even an MLA, no need to speak of Minister. So, if they want higher post, they have to be sincere. It may be very unlikely that, a person is sincere for 20 years, and suddenly becomes corrupt. Even if there are politicians like that, still, the average net profits that they would get across all those politicians would be negligible. Because, not every candidate wins in the election continuously, and even among those who won, not everyone becomes minister. So, if anyone is trying to be sincere for 20 years and then want to do corruption, country won't lose that much because of them.

Hysteria will not end corruption

If NGO types want to make laws, let them get elected to the Lok Sabha or else go back to activities that are genuinely non-governmental. Making laws is the right of government, no matter how ineffective or corrupt the government may be. This appears to have been forgotten in the mass hysterics of last week. It is time to remember.

Does Fasting Help?

In Manipur, there is a lady Chanu Sharmila, who has been fasting for the last 10 years for human rights in Manipur. She has been in hospital for the last 10 years. Till now, nobody cared about her.

Misuse of Fasting

1.5 years back, one politician (mis)used fasting, and almost everyone in that state had to suffer like anything, and that state lost everything for 6 months, starting from IPL to new software companies.

If people start using fasting for everything, then there will be more misuses, and it is definitely loss for the country.

Only Politics Can Change People's Life

Government can do a lot to the people and it cannot be replaced by even the biggest billionaires of the world. What can be done by a Prime Minister in two weeks is a no match with the donation made by Bill Gates or Warren Buffett.

http://blog.tnsatish.com/2009/03/why-jayaprakash-narayan-came-to.html

Are we sincere?
http://manchupallakee.blogspot.com/2011/04/blog-post.html (It is in Telugu)

"I Don't Like Anyone" Option While Voting

I see many people asking for the option of "I don't like anyone" while voting in the elections. But, that option is not required. If all the candidates are bad, then by voting for the person who is least bad will change the entire system automatically.

Most of the people sees the candidates from the major parties (which can form the government), and if their candidates are bad, then they say, everybody is bad, and they need option of "I don't like anyone". In almost all the elections, there are many good candidates contesting either from small parties or as Independents. If they get atleast 1000 votes in an assembly election, that would give lot of encouragement for them, and they would continue to contest in the elections to change the system.

Right now, many uneducated people are very hesitant to vote for the candidate who may lose. If they cannot vote for the winner, they feel like as if they lost their prestige. The educated people, instead of asking for this option, and if they vote for the good candidate, and if he/she gets good no.of votes, then even the uneducated people also change. They would change by seeing the no.of votes that a small candidate gets, and that would effect all the big parties, and very soon, the small candidate wins in the election.

In Andhra Pradesh, if anyone asks for this option, I would see him/her like a fool only. If they want to improve the system, they should vote for Lok Satta Party.

Related Posts:
Vote for Party or Vote for Candidate

Allowing Investments Of Short Duration

Let's suppose, without any external investment, we are earning some amount every month. If we get some extra investment, then our income increases. One external organization is ready to invest for certain unspecified duration. As long as they keep the investment with us, we get extra income. Once, they withdraw the investment, we will fall back to the original income that we were receiving.

In this case, should we allow the external organization to invest in our organization or not?

Ask any communist, they would reject this idea without any second thought, and clearly says, no external organization should invest in our organization. For that, they show the proofs.

The graph would be something like below.

Any disturbances in the external organization would lead to the drops like B to C. There are many incidents like this. We don't want to suffer because of their disturbances.

But, if we step back, and look at the complete graph, it would look like something below.

F is the point where, the external organization invested money. Because of their investment only, we started getting more money. Once they withdraw the money, then our position will not fall back to the previous place, but, it would be little better than our previous position because of the extra income that we received during their period they invested. But, the typical communists do not see the whole picture, but, just sees the period where it is fallen, and criticize capitalists in all possible ways.

You’ll never meet a rich person who has never lost money. If you never want lose money, then you will never become rich.