Ace the Java Coding Interview

Complexity plays an important role in coding. Users may experience a decline with an increase in complexity. This is why questions related to complexity are an important part of programming interviews. This module is a complete guide to the complexity of different data structures. It starts with the concepts and formulas related to complexity. Then, we'll solve different problems with different complexities. At the end of this module, we'll look at some interview questions related to code complexity, as well as a cheat sheet that will help us with the interview questions.

Big-O Notation

Are all decision problems in the complexity class NP?

Are all decision problems in the complexity class NP?

Can optimization problems be in NP?

Travelling salesman problem is defined as a salesman planning to visit a bunch of cities to sell his merchandise. The salesman wants to cut costs and needs to follow a route which allows him to visit every city but at the same time is the shortest route among all possible routes. Is this problem in NP-complete?

Travelling salesman problem is defined as a salesman planning to visit a bunch of cities to sell his merchandise. The salesman wants to cut costs and needs to follow a route which allows him to visit every city but at the same time is the shortest route among all possible routes. Is this problem in NP-complete?

If P=NP is proven, will integer factorization be still in complexity class NP-intermediate? 

If P=NP is proven, will integer factorization be still in complexity class NP-intermediate?

NP-complete problems can't be solved at all?

NP-complete problems can’t be solved at all?

Questions to test understanding of P/NP problems.

Complexity Problems

Conclusion

Problem Set 6