Month: September 2017

Interview Basics: Static vs. Dynamic Arrays

Interview Basics: Static vs. Dynamic Arrays

Arrays are one of the most basic data structures in computer science. But they form the basis of some difficult technical interview questions! So no matter where you are in your programming career, you need to be very familiar with arrays and how to use them. Read on to review the basics of static and dynamic arrays, then watch our video to get clear on the differences between them. And once you’re ready to solve some array-based technical interview questions on your own, head to Interview Practice. You’ll be able to practice solving array interview questions that have been asked at Google, LinkedIn, Apple, Uber, and Palantir. 

First Things First

Whatever programming language you choose use in an interview, make sure you know its array methods very well. Like, forwards and backwards well. Interviewers will definitely be judging you on this! If you don’t know something basic like this in the language you’ve chosen to interview with, they’ll question how well you know that language at all… Not to mention how well you can program, period. So spend some time with your language’s documentation to make sure that you’ve got a handle on its basic and advanced array methods.

Arrays

The simplest definition of an array is that it’s a data structure that contains a group of elements. In interviews, you’ll get a lot of questions about static arrays, which are the most basic implementation of this data structure. You’ll also get questions about dynamic arrays. We’re going to focus on static and dynamic arrays in this article. (You’ll also get questions about multidimensional arrays in technical interviews, which we’re going to cover in an upcoming article.)

Static Arrays

The most basic implementation of an array is a static array. A static array is a random-access data structure with a fixed size. You have to declare its size when you first initialize it. To add or remove elements from a static array, you have to create a new appropriately-sized contiguous chunk of memory. Then you have to copy the elements that you want to keep into this new array.

The good: The item lookup by index for static arrays is really quick (O(1)), and they have a very low memory footprint.

The bad: Adding elements to or deleting elements from the array is an O(n) operation, where n is the number of elements in the array. Searching the array for a particular element is also O(n). Arrays don’t allow for the quick rearrangement of their elements.

Dynamic Arrays

A dynamic array is a random-access, variable-sized list data structure that elements can be added to or removed from. They’re basically like static arrays, but with the addition of space that’s reserved for adding more elements. When dealing with a dynamic array, there are two important factors to consider. There’s the logical size of the array (the number of elements being used by the array’s contents) and its physical size (the size of the underlying array). The physical size is counted in either the number of elements the array has room for, or the number of bytes used. In a technical interview, you should use a dynamic array if you know you’ll need to add or delete information.

The good: On average, it’s quick to insert elements to the end of the dynamic array. And item lookup by index is O(1).

The bad: They don’t allow for the quick rearrangement of their elements. And they have inconsistent runtimes for adding elements to the array, so they’re not good for real-time systems.

Diving Deeper

Now that you’re clear on the basics of static and dynamic arrays, watch this video for a deeper dive on the differences between the two.

Bonus Array Joke

  1. Why did the programmer leave his job?
  2. Because he didn’t get arrays.

(Get it? Arrays, “a raise”! Stop groaning. It’s a great joke.)

Interview Basics: Reverse a Linked List

Interview Basics: Reverse a Linked List

Reversing a linked list is a very common task in technical interviews. That’s why we devote a whole section of Interview Practice to them! Being able to solve this question easily is a great way to demonstrate to an interviewer that you’re a capable, competent programmer. Let’s discuss two different ways of reversing the direction of a linked list: recursively and iteratively.Linked list refresher

A linked list can be modeled by Node objects, where each node stores a value and a next pointer to the next node in the list. The last node in the list points to NULL, to indicate that you’ve reached the end of the list. You access the linked list by having access to a head pointer at the beginning of the list.

Basic Linked List
A basic linked list

You need to apply a function reverse(head) that does two things:

  1. Reverses the direction of the arrows, changing the structure of the linked list, and
  2. Returns a pointer to the new beginning of the list.

So all the nodes will stay in place in memory, and only the direction of the pointers will change.

Linked List Reversed
What we want to get

You probably wouldn’t implement a linked list this way in an actual program. There might be a lot of different references to the linked list before you reverse it.

Linked List Multiple References
A linked list with multiple references

If you call reverse(head1), you would update head1. But all the other pointers would then be stuck at the end of the linked list, and only head1 would be a good head pointer.

Linked List Reversing With Multiple References
Only head1 was reversed

To get around this, you could make a LinkedList class, or a sentinel head that external references could point to that contains the pointer to the beginning of the linked list. Then you could safely update this reference without breaking any external references.

Linked List with Sentinel Head
A linked list with a sentinel head

But so that we can focus on just the core algorithm, the solutions in this video use a simple version of the linked list.

Why is reversing a linked list tricky?

Linked lists are designed to be easy to traverse in the forward direction, and once a node passes a particular point there is no way of going back to it. If you were in a position where reversing order was something you needed to do often, then a linked list would be a poor choice of data structure and you’d be better off choosing something else.

So this isn’t a problem that you’d really ever encounter on the job. In technical interviews, though, this kind of question is asked as a way of assessing how well you can perform tricky manipulations. That’s why sometimes the problems that interviewers ask can feel kind of artificial.

In this video, I demonstrate two different approaches to reversing a linked list: a recursive one, and an iterative one.

The code