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