Essential code for lists and vectors in an interview

Lists are perhaps the fundamental data structure in code. There's virtually no program that doesn't use lists. Interviewers love asking questions that involve lists, either intentionally, or just because almost everything uses a list. To help you prepare for an interview, an keeping with our theme, I've created a list. It describes all the operations you should know how to perform on lists. This will make you comfortable when asked a question, and save you valuable time while coding.

Lists come in many forms, under the names "array", "vector", "queue", "stack" and more. In this article, we're looking at the general notion of a list: a collection of elements that have a specific order. Find the most general purpose list in your language and learn that one thoroughly.

Use this reference when preparing for an interview. Don't assume you can do each item, take the time and code it. You'd be surprised at how seemingly simple things can turn out hard, or how a momentary thought blip can derail you. Honestly, I don't think there's any language where I could sit down and do all of this from memory. Going into an interview, I need to prepare and freshen my knowledge. Making these operations part of your natural coding vocabulary helps tremendously when in a pressure situation.

Some languages implement lists as immutable data structures. However, the wording in this article assumes you're using a mutable list. You'll still need all these operations, but how your code structure will differ significantly. Focus on what is to be accomplished, rather than the specific wording.

Basics

If you jump between languages a lot, it's possible to have a blank on basic operations. This also happens when facing a blank screen, as opposed to existing source files. When you have nothing within view for reference, it's easy to forget simple syntax.

• Create a list: Your primary list should where all of the operations listed here are possible. There are specialty lists, but the most generic one is the best place to start.
• Add an element to the front or back: This is the primary way to get elements into the list. Back insertion almost always has a particular function, such as append or add. Front insertion often has a special function, but sometimes not.
• Pop element off front or back: This is the basic way to get elements out of the list.
• Forward iterate over elements: Stepping over the items in the list, from the first to the last, is the basic way of doing something with those items.
• Get the length of list: The syntax is different in virtually all languages; thus it's worthwhile to remind yourself.
• Test if empty: Most languages have a particular function, or syntax, to test if a list is empty. You can instead compare the length to zero, but knowing language specific functionality can often leave a good impression on the interviewer.

Location Based Operations

• Get item at location: Random access allows you to work with elements in the list in any order.
• Insert an item at location: Adding to the front or back is not enough, you need to know how to insert at an arbitrary position. In some languages, this is the only way to add at the front.
• Remove an item from location: Popping from the front or back is not enough, sometimes we need to remove from an arbitrary position.
• Replace/Assign item at location: Assigning an item is not the same as inserting. You replace the item with a new one, and the list length stays the same.

Sorting and searching

Searching and sorting are extremely common in interviews. You'll find that by knowing how to do this well, you'll use it a lot more than you expected.

• Find an item: Don't worry about it being efficient, just know how to find an item, matching a value, in a list.
• Find and remove an item: Like finding, but also remove that item.
• Find last matching item: Find usually starts from the front, but sometimes we want to start looking from the back of a list instead.
• Sort by natural order: The basic sort function will order a list by the natural ordering of the items. This is useful for fundamental types, like integers or strings, or for classes that define an order.
• Sort with custom comparator: A lot of algorithm questions require you to order a list with an arbitrary comparison.

Segment Manipulation

It's not enough to work with individual elements of a list. Often you'll want to work with segments, or slices, of lists. Knowing how to do this segment manipulation saves a lot of time and makes your code cleaner.

• Split the list at arbitrary location: Know how to make two lists from one.
• Multiple splits based on a match: Know how to create multiple lists by splitting on matching elements, such as a particular character.
• Clear the list: Remove all the elements from a list.
• Remove segment: Remove a range of elements from a list.
• Concatenate lists: Combine two lists into one by adding one to the end of the other.
• Insert list at location: Combine two lists into one by inserting the contents of one list into another.
• Get a sublist: Create a new list from a segment of an existing list. Be aware whether you're getting a view on the source list, or a true copy. If it's a view, also learn how to get a copy.

More Iteration

There are multiple ways to iterate over the items in a list. These can be done with basic for loops, but many languages offer extra features.

• Backward: Iterate over the items starting at the last and going towards the front.
• Partial segment iteration: Iterate only over a range of items in the list, that is, start in the middle and iterate an arbitrary number of items.
• Skipping elements: Iterate over every second or third element.

Creation

These patterns come up often enough that they often have custom syntax. You can always fall back to a for-loop and add items manually, but it consumes more of your time. Plus, using an advanced syntax can often demonstrate your language skills and impress the interviewer.

• Create from a static list of items: Given a known list of items, existing variables, create a list that contains them in a specific order.
• Create a range of numbers: Create a list of numbers ranging from a minimum to a maximum. This is a powerful ability when combined with the following data manipulation features.

Data Manipulation

Some languages have high-level data manipulation functions, others do not. If you don't know the specialized syntax, then at least know how to do the following using the basic operations.

• Mapping: Mapping calls a function for all elements in a list, either producing a new list or modifying in place.
• Filtering: Removes all elements matching a filter function, either generating a new list or modifying in place.
• Fold / Reduce: Combines all the elements in the list together, such as joining strings or summing the values.
• Zip: Combine two or more lists together by alternating the elements.

Advanced

The following are operations that come in handy if you've been given an algorithmic question. Many of those algorithms can be expressed as combinations of these operations or at least benefit from knowing this.

• Swap elements at two locations: There may or may not be a special syntax for this, but it comes up often enough to know either way.
• Reserve capacity: If your language offers lists with reserved capacity, you should know how to use it. Even if not exposed, you should know the difference between capacity and size.
• Replace content in a list: Instead of swapping out a list with a new one, can you update an existing list with entirely new content.
• Compare two lists: Determine if two lists contain the same items or comparable items.
• Search a sorted list: A sorted list can use binary search to find items. Many languages offer this as a standard library feature.
• Iterators: Know the difference between indexes and iterators. Be able to use a basic iterator manually, not just in a standard loop. Not all languages have iterators, in which case, learn how to use indexes as iterators.
• Multiple iterators at the same time: A lot of iteration syntax doesn't work when dealing with multiple lists. You need to know how to work with multiple lists at a time.

Now with strings

Knowing all of those operations will give you a significant boost during a coding interview. While I'm okay with people checking syntax during an interview, it costs valuable time. You want to make the part of your natural vocabulary. This will give you more time to dedicate to solving the actual problem. Additionally, the smoother this type of code flows from your fingertips, the stronger the impression you'll make on the interviewer.

Now, as a bonus, learn these same operations with strings, at least up to the "More iteration" section. If a language exposes a string the same way as a list, great! You don't need to learn more. Knowing how to do these operations with strings is primarily for interviews. Silly string questions are popular, even if they don't come up during daily coding. Indeed, a lot of the common ways to manipulate strings are wrong, but I digress and will get back to that.

While this list of operations may seem long, many of them share a common syntax. I've roughly ordered them from basics to advanced. Learning them in that order maximizes the usefulness for an interview, and for coding in general.

Now, learn them, and master that next interview. Be sure to let me know how it goes.

---

Do you want to learn more ways to become a great programmer? Read my book What is Programming?. I look at the People, the reason software exists, the code at the heart of that software, and you, the person behind the keyboard.