I have been doing technical interviews for around 8 years, and it is not easy to find great candidates, probably because great candidates last very little in the market, however time after time I deal with candidates that, unfortunately, are not able to cover certain basics, lets go through them.

## 1-Big-oh notation, time and space complexity.

Being able to determine when it is worth to optimize an algorithm is absolutely fundamental, I have seen codes where collections of 100 elements were sorted because a search will be performed once or twice… that says a lot about developers.

Also, it is important to understand how bad or how well out algorithm will do as a function of the size of the input. An image is worth more than words, so here is the fundamental picture to keep in mind.

Anybody doing an interview should have that picture really clear in their heads. The reason? lets go through a simple question: lets say you have 1 million numbers, unsorted, and you will need to search whether or not a given number is in your million numbers, such operation is to be repeated 100 times. Is it worth sorting your 1 million numbers or not?

It is a simple question, and it should have a simple and definite answer, however without the help of the big-oh notation and some knowledge about the running time of sorting and searching algorithms, it is impossible to answer it.

However, with the help of big-oh one can answer this question very effectively.

Doing a sequential search will take linear time, that is \(O(n)\)

Doing a binary search will take log time, that is \(O(log(n))\) but in order to perform a binary search we first need to sort. Sorting takes \(O(n*log(n))\) now, in our case we are specifically dealing with \(log_2(10^6)\) which is approximately 20 as \(2^{20} \simeq 10^6\)

This means that

- Using a binary search will take around 20 operations (worst case) to find a number
- Using a sequential search will take 1 million operations (worst case) to find a number
- The cost of preparing our numbers to be able to perform binary searches is 20 million operations

Now, lets ask ourselves the question again. Is it worth sorting 1 million numbers if we are going to search 100 times within them? The answer is yes, as our initial cost is 20 million operations, but after that, the cost of a binary search is almost none, while a sequential search will take 1 million operations each time.

## 2-Basic data structures.

The simple data structure is an array, but everyone should be familiar with stacks, queues, linked lists, hash tables, trees, graphs and possibly also sets and heaps.

Furthermore, I expect people to be able to implement any of the structures mentioned above. Sure, you will NEVER implement those in real life, but I think it is an interesting exercise to be able to implement those by yourself. I tend to ask people how to implement a simple Stack, and some people really struggle to do so, I would never ask anybody to implement a full hashtable, but I will certainly expect them to be able to do so if a hash function is provided to them.

Being familiar with data structures is key for being able to solve problems, here comes an example: Imagine you are given all the correct works of the English dictionary, how could you implement a spell checker that will not only inform the user if the work they type is correct, but also provide them suggestions in the case the wrote an incorrect work?

Most people will initially resort to a hashtable, however there is a problem with hashtables: they only help you with exact searches, if you type “helo” there is no way to let the user know that maybe he wanted to type “hello” or “hell”. How would you do that? The solution is a trie, a type of tree where each level contains each of the letter of the alphabet, if a particular node is a word, then it will contain a flag indicating so, again lets illustrate this with a picture.

This is a simple yet interesting example on how a problem that might seem very complex at first could be effectively solved using the right structure. Most people operate with linked lists, sets and hashtables pretty much every day, however trees, graphs and other structures might not be used so often but they are incredibly powerful in certain situations. As a software engineer it is your job to know your tools, and data structures are pretty much tools 101 here.

## 3-Basic data types.

What should you know about floating point numbers and monetary calculations? they are no-no, and for good reasons. Due to the internals of how floating point numbers are stored, they cannot represent fractions accurately, the loss of precision is not too terrible for scientific calculations, but it can be really bad for monetary calculations (or any other calculations where precision is critical). As an example a simple piece of python code (the same problem will occur in java)

1 2 3 4 5 |
millis = 0.001 total = 0 for i in range(1000): total += millis print(total) |

Now, the expected output of that calculation should be 1, right? well, not really, the actual result is

1 |
1.0000000000000007 |

So, if that happens after only 1000 operations, imagine what floating point numbers could do to multiplications and divisions. And then imagine what would happen if those multiplications and division involve money (currency conversion, tax calculations, margins…) Again, it is your job as a IT professional to know this and use the proper tools. Most languages provide mechanisms to deal with this problem, do you know them?

## 4-Basic object orientation understanding.

Becoming an expert on object oriented programming takes years, even I struggle sometime to find the right abstractions, it is a never ending process but, when done correctly, object oriented programming can solve many problems, as it allows us to work with abstractions rather than low level details.

Can you clearly explain what is polymorphism? without resorting to an example? could you explain it to your mum? that is the level you should be able to provide in an interview.

Do you fully understand inheritance and composition? Have you realize that inheritance can actually break encapsulation (if done wrong)?

I am surprised, quite often I ask candidates about information hiding and most of them are able to explain the mechanisms that languages like java provide for such technique (private, protected, public…) however when asked “why would you ever want to make something private? can you give me an example?” many people actually struggle, furthermore, many people will simply answer that you make attributes private and then provide getters and setters.

You need to understand how information hiding allows you to keep the internal state of the object separated from the outside world, you should be aware of the consequences of not doing so, and you should be able to clearly and confidently explain that.

This concludes the first part of this story.

Happy coding.