Data Structures
Data Structures are among the most important topics to know both when creating actual software and on interviews. You should know the basics of how common data structures work and the pros & cons of using a particular one. Interviewers may also ask you to implement a basic data structure for use in a problem, even if you wouldn't usually do that when actually programming.
Basic Data Structures
If you need a refresher, check these reviews of what Data Structures are and Nodes and Lists. Then make sure you can deal with LinkedLists, a topic often covered on interviews, even if in real life you'll usually use Dynamic Arrays.
LinkedLists are just a list of Nodes that point to each other, while Dynamic Arrays use arrays internally and resize when needed. LinkedLists are generally slower (since they take longer to reach a specific index) but they are faster for certain operations (when you already have the Node being modified).
Interviews usually deal with singly-linked lists, which can only be traversed in one direction, but be aware of doubly-linked lists, which allow traversal in both directions.
Stacks and Queues are often useful for solving interview challenges so make sure you know when to use them. They can be implemented by adding wrapper push
and pop
methods around an internal LinkedList. For practice, check out the Stack and Queue Challenges, and check that you can solve these challenges in linear time:
Maps Sets and Hashes
A large number of problems can be solved in linear time (or at least optimally) with a HashTable. Make sure you know how to use it! You should also know the basics of how it works since that can be asked in an interview. The key idea of a HashTable is to use some kind of hash function (such as a simple mod
) to convert an item's data into a location in an array.
Review using Sets and Maps, how a HashTable works, and examples of programs you can create using HashSets and HashMaps.
Note: Technically, the most common data structures are Arrays and Strings, but they are part the basics of programming and and were covered in the previous page.