Learn Algorithms

Many people are scared of the algorithmic questions they will face at their interviews. As we like to say in HiredInTech, practice makes perfect. That’s why we’ve prepared a section, which will guide you through the most fundamental algorithmic topics. For each topic we point you to insightful tutorials and suggest a number of problems to solve.

The suggested problems are taken from the TopCoder problem archive. In this course we show you how to quickly register and start using TopCoder’s arena for problem solving. It is recommended for practice by companies like Google and offers you a setup, which is very close to the real interview experience.

Below you can find the algorithmic topics that you need to cover in order to be well-prepared for your interviews. Each topic points you to one or more tutorials, which you have to read. In addition we have collected for you several problems, which you can try solving. Remember, practice is what makes you perfect. Finally, all problems have detailed solutions!

For each topic there is an optional list of problems taken from the famous book “Cracking the Coding Interview”. If you happen to have it, these questions will be a useful exercise, too.

Dynamic Programming

Dynamic programming is a very widely used technique. You may have even been applying it without knowing it. Its applications vary from very simple ones to more complicated cases. Nevertheless, many people wonder if they even need that for the interviews. Our experience shows that it is likely that you would get a problem requiring you to design a solution using dynamic programming. Overall, it is useful knowledge for many software engineers. Depending on what you work on it can come very handy sometimes.

  • Problem 1

    Statement: This is a very standard problem. Given a list of N ordered integers find the longest increasing subsequence in this list. Example: If the list is [16, 3, 5, 19, 10, 14, 12, 0, 15] one possible answer is the subsequence [3, 5, 10, 12, 15], another is [3, 5, 10, 14, 15].

    Try designing a solution, which will work efficiently for N <= 2,000. Can you think of a solution working fast enough for N <= 2,000,000? You can experiment by generating your own tests and running your solution against them.

    Solution: The straight forward solution, which will work for N <= 2,000 is to compute the longest subsequence ending at each number. Start by computing this from left to right. For each number X the answer can be obtained by looking at the numbers to the left of it. Any number to the left, which is smaller could be the previous one in a subsequence. Use the one, which has the longest subsequence ending with it. Extend this subsequence with X and this will be the answer for X. Can you answer why that works? What is the time and space complexity of this solution?

    There is a faster solution to this problem, which will work better for big cases where N <= 2,000,000. You can read about it here.

    Now a few problems selected from the TopCoder archive follow. Each problem can be solved using the TopCoder grader. If you don’t have an account there follow our step-by-step tutorial to easily set up your account and start submitting your solutions in the system. Each problem has a solution, which we provide a link to.

  • Problem 2 - Statement - Solution

  • Problem 3 - Statement - Solution

  • Problem 4 - Statement - Solution

If you would like to practice more you can either search for more problems on TopCoder from their archive page. You can also take a look at the book “Cracking the Coding Interview”. Here are some questions we have selected for you from this book: 9.2, 9.6, 9.8, 9.10

Sorting

Sorting is one of the fundamental topics. Nowadays, most programming languages have utilities, which allow us to sort items efficiently. So, in real life we rarely have to implement sorting. However, this topic is not just about pure sorting of items. Moreover, it is always helpful to have an idea about how these algorithms work and what to expect when we use them. This is why questions related to them can be expected at interviews.

A few problems selected from the TopCoder archive follow.

A harder TopCoder bonus problem - Statement - Solution

Some selected questions from “Cracking the Coding Interview” book: 11.1, 11.4, 11.7. The last one requires some knowledge in Dynamic Programming, too.

String problems

Engineers need to work with strings all the time. Imagine how much information in form of text is processed at companies like Google, Facebook, Microsoft. Such problems are popular at interviews and that’s why we have a separate section for them.

A few problems selected from the TopCoder archive follow.

Selected questions from “Cracking the Coding Interview” book: 11.2, 17.9, 18.8

Mathematics

Mathematics is a very wide topic. We have chosen a few area like prime numbers, factorization, numeric bases, GCD, a bit of geometry and others.

  • TopCoder Tutorial 1 - All of this except the section on complex numbers seems appropriate for interview preparation.
  • TopCoder Tutorial 2 - The topics up to and including the “Sieve of Eratosthenes” should be very useful

Here are three optional questions taken from “Cracking the Coding Interview” book: 7.7, 17.11, 18.2

Data Structures

Data structures are all around us. It is needless to say that a good engineer needs to be familiar at least with the basic ones. There is even this joke about Google interviews that everything there can be solved with a hash table. One of the reasons is that in their products they use such structures so much. You can definitely expect a question requiring some knowledge of data structures and the skills to implement them properly. In this section we will cover the most useful ones.

  • Problem 1

    This is a popular one. Design a data structure, which allows the regular heap operations of push and pop but can also return the median of all inserted elements with constant time (O(1)).

    Solution: You can try to use two heaps. One of them holds half the elements with the biggest one on top. The other heap holds the other half of the elements with the smallest one on top. The idea is to store the smaller elements in the first heap and the bigger ones in the second. This way you can make sure that the median element is at the top of one of the two heaps. We will leave to you to figure out the details.

  • Problem 2

    Write a program, which is given a long text and after that can very quickly answer questions of the type: “how many times is a given word seen in the text”. A proper question here would be: How big is the text? Let’s say that it will be no longer than 1GB. The incoming queries can be endless, you just have to answer them as quickly as possible. Each query consists of one word. What is the text like? Well, it contains words separated by spaces and other punctuation symbols.

    Solution: You could simply build a hash table, where the keys are words and the values are frequencies. It’s pretty easy to traverse the big text ones and build the whole hash table. After that use it to answer incoming queries.

    Another possibility that comes to mind is to use a trie built by using all the words in the big text. In the leafs of the trie you could store the frequencies. We leave to you to figure out how exactly to build the trie. What is the time and space complexity of building this data structure?

  • Problem 3 - Statement - Solution

Some problems from “Cracking the Coding Interview” book: 1.1, 2.1, 2.2, 2.4, 2.7, 3.2, 3.5, 3.6, 4.1. 4.5

Graphs

We end our algorithms chapter with graphs. One could model so many real-life entities with graphs. Think about the Facebook network, the relations between web pages in search engines or the Knowledge graph built by Google. Graphs are a powerful concept with endless applications and huge amounts of theory. However, you don’t need to be an expert to handle the interviews well. In this section we cover the most useful topics.

TopCoder Tutorial: Part 1, Part 2, Part 3

  • Problem 1

    Imagine that you are given a rectangular NxM grid with cells. There is a robot in a starting cell. The robot can pass through some of the cells while others are occupied and it cannot go through them. There is a cell where it must reach. Given the whole grid, the start and end cells, write a program, which determines if the robot can reach its goal.

    What about cases where N, M < 10,000. What about 10,000,000?

  • Problem 2 - Statement - Solution

  • Problem 3 - Statement - Solution

  • Problem 4 - Statement - Solution

Two optional problems from “Cracking the Coding Interview” book: 4.2, 10.5

What's next?

If you've carefully read and understood the tutorials above you now have a good theoretical preparation in terms of algorithms. Having solved the suggested problems makes you even more prepared since you've put your knowledge into practice. We recommend one more way to become even more confident at solving problems - the blitz rounds!

E-MAIL SUBSCRIPTION

Keep up-to-date with the latest interview questions and preparation tips and tricks delivered to you for free

 

E-MAIL SUBSCRIPTION

Close

Upload your CV

 
  •   Upload your CV
  •   Get referred
  •   Get hired