Arrays, Strings and Lookup Tables (with some essential math)
* Can you efficiently find two elements of an array with maximum difference between them? (Inefficient method is easy!)
* Can you compress a given String with Run Length Encoding? (This one is way easier than it sounds!)
With fast lookup and overwrites, Arrays (Numeric and Character) are probably the most widely used of all data-structures. That’s why they are also a popular interview question. A Lookup Table is one of the most useful usage of an array, and probably also the most popular variant of Array-based interview questions.
Problems in this section, will deal with numeric arrays, character arrays (strings) and 2D arrays. We will also mutilate strings in many possible ways. There will also be some difficult questions in this section, like building a regex matcher.
Some problems here may use Hash Tables, but we won’t delve much into how to create hash-functions. Hash functions, once set, often don’t need to be changed in practice and also make a less popular interview question.
Problems in this section will also cover basic math (e.g. prime numbers, arithmetic, Matrices, Fibonacci etc.).
Linked Lists, Stacks and Queues
* How do we build an LRU Cache? (Linked List is the most usual way an LRU Cache is implemented)
* Can you implement a stack such that getMinimum() is an O(1) operation?
In the modern days of application programming, most of us don’t have to deal with Linked Lists directly (they are abstracted as libraries). but they are still fairly common in low-level software where you need granular control e.g. software that deals with processing of voice and video data.
They make a good programming question, also because the knowledge of linked lists proves that you are familiar with basic memory management, and that you can properly deal with an ordered list of values.
However intimidating they may be, there are not too many variants of Linked List related problems. We’ll cover those in this section.
Stacks and Queues are special cases of Linked Lists. We’ll first go over all the basic operations of these structures. Then we will delve into some frequent applications of Stacks and Queues e.g. Traversing trees.
* Can you compute the Lowest Common Ancestor of two nodes in a Binary Search Tree? (This problem has important applications!)
Binary Trees are the most intuitive for representing hierarchical data. While we’ll do a couple of problems relating to Binary Trees, we’ll focus most of our attention to the more popular interview-variant: Binary Search Trees (BST).
Arrays are expensive for insertion and deletion when the data needs to remain sorted. That’s where BSTs shine. We’ll go over various methods of traversing a BST, and some common applications.
We’ll touch on less-frequently asked tree-types, viz. Red/Black Trees, AVL Trees, B-Trees. While these are very important data-structures, they are used in highly specific problems.
* Can you calculate the shortest path between two nodes on a graph?
Graphs are recently becoming popular as an interview question. That’s because of the advent of a lot of interest-based networks viz. Twitter, Facebook, Quora etc. Interest networks are often represented as Graphs in the backend.
Other useful data-structures
Heaps, Tries, Suffix Trees, Interval Trees: These are data-structures that are used for specific problems. They are less common in interviews (except maybe Heaps and Tries), but we’ll still go over them, just in case.
Big-Oh! Pun intended.
In programming, nearly everything is about how you manage state. That is to say, nothing influences an algorithm like the choice of a data-structure does. As we go thru different data-structures, we’ll also pick algorithms appropriate to access that data-structure. Algorithms will span sorting, searching, traversing, and transforming data-structures in a number of different ways. We’ll also practice with recursive and iterative forms. And of course, after every problem, we’ll analyze its complexity with Big-Oh notation.
We’ll explicitly devote some time to internalizing sorting algorithms. QuickSort and MergeSort (small and large data-sets) should become muscle memory to you!
DP is a very efficient technique to solve some common and complex problems. However, it is not as simple as our professors made it sound. We’ll practice several DP problems, until you realize the crux of the technique.
* Two egg problem, anyone?
They are annoying, but thankfully the trend is fading away. We’ll take some popular ones.
Dust off your mutexes and protect your critical sections. We’ll do short problems in that space. Read-write lock anyone?
In Internet scale companies, we also apply the same principles on Distributed System resource contention problems.
Large Scale System Design
* How do you design a URL shortening service?
As the world is getting more and more online for everything we do, most web companies nowadays struggle with unprecedented amount of traffic and myriad of use-cases. Building systems that can handle thousands of requests per hour, or store Gigabytes per second, across geographically spread locations using multitude of servers in the cloud, is becoming routine. Companies hence love it when they can find someone who understands and appreciates those challenges.
We’ll go over some fundamental problems in this space from some very experienced practitioners in the area. These are often open-ended discussions with white-boarded patterns. A good source of problems is highscalability.com.
Depending on interest, we may have to hold more than one session for this section.
Object Oriented Design
In the world of Application programming, the skill of turning a real-world scenario into classes and objects, is very vital. While there are established Design Patterns to deal with most such problems, interviews often look for a skill that comes even before that: translating real-world objects into Classes in code. We’ll review popular problems in this space and write code.
Towards the end of this section, we will also discuss and code some popular Design Patterns.
Believe it or not, but answering Behavioral Questions properly is equally, if not more, important than answering technical questions. A solid behavioral interview can make the interviewer/committee ignore mistakes made in the technical questions. They are open-ended questions, with no definite answers. But there are a lot of bad answers and only a few good answers. We’ll go over good standard behavioral questions and their pitfalls.
(*Curriculum is subject to change and evolve. Who wants a stagnant curriculum anyway?)