Concepts For Coding Interviews | Algorithms and Data Structures
3 min read
I spent the last months figuring out how to improve my coding interview skills. In this post, I’ll be sharing the insights and tips I gained along the way.
Many of the concepts tested in coding interviews are not what you usually use at work. thus you most likely need to freshen up your memory on solving this kind of question.
This is why I decide to make a list of the most common concepts you will need for the next round of coding interviews.
This is not all the concept you will need to be aware of. this is a list of the most tested concepts from my experience.
- Graph & Tree Traversal It's almost guaranteed you will be asked about graph traversal in the coding interview process. it's not a question if you will be asked but when? you will be asked about it.
You need to practice very well Depth-First-Search and Breadth-First-Search. How to handle cyclic graphs?
- Two Pointers Technique This is one of the rare occasions the CS people named something clearly, as it is exactly as it sounds. It's the use of two different pointers (usually to keep track of array or string indices) to solve a problem involving said indices with the benefit of saving time and space.
This can be used to figure out the frequency or sum of subarrays. also sometimes very useful with linked-lists
Recursion A solid understanding of recursion is super useful. Recursion can make so many problems much easier to solve. Traversing a tree recursively is trivial it's literally a couple of lines of code and we are done compare this to the iterative version. The recursive solution is much much easier to implement and many other problems work this way. Making recursion a super useful tool to learn and practice very well.
Binary Search Chances are binary-search was the first algorithm you learned about. However, you need to be comfortable writing a correct implementation of it. It's unlikely you will get asked about binary-search but it comes up a lot as a step to solve a problem.
Linked Lists Linked lists problems are very common and although they conceptually are very easy problems but implementing them and keep track of all these pointers requires some practice.
One of the best to practice this skill is to get comfortable with reversing a linked list. as reversing a linked list forces you to be familiar with most manipulation you will need to do on a linked list and it's a fairly common question to get asked.
- Suffix tree (the fancy trie!) A suffix tree is a compressed trie containing all the suffixes of the given text. this really cool data structure to know as it helps with many string problems. when you are searching for a pattern or trying to figure out if a string is part of another string.
Dynamic programming This is not so common, but it gets asked on the harder coding interviews so it's a good idea to get a lot of practice on it. the best thing you can do is to focus on the most famous patterns of this problem like Longest/Shortest Common Subsequence. 0–1 Knapsack problem. Rod Cutting. Longest Increasing Subsequence problem. You can learn about all the popular problems here Top 10 Dynamic Programming Problems
Sorting algorithms It's so common to have sorting as part of the solution. the two most of them are quick sort & merge sort.
- Min&Max Heap A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Since a heap is a complete binary tree, a heap with N nodes has log N height. It is useful to remove the highest or lowest priority element. It is typically represented as an array. There are two types of Heaps in the data structure.
A min-heap will be ordered to have the min first & A Max-heap will be ordered by larger values first.