Top 21 Arrays Interview Questions And Answers

Question 1

Name some characteristics of Array Data Structure

Accepted Answer

Arrays are: 
* **Finite (fixed-size)** - An array is finite because it contains only limited number of elements.
* **Order** -All the elements are stored one by one , in contiguous  location of computer memory in a linear order and fashion
* **Homogenous** - All  the elements of an array are of  same  data types only  and hence  it is termed as collection of homogenous

Question 2

Explain what is an Array?

Accepted Answer

An **array** is a collection of **homogeneous** (same type) data items stored in **contiguous memory** locations. For example if an array is of type “int”, it can only store integer elements and cannot allow the elements of other types such as double, float, char etc. The elements of an array are accessed by using an **index**. * O(1) * O(log n) * O(n) * O(n log n) * O(n²) * O(2ⁿ) * O(n!)

Question 3

What is time complexity of basic Array operations?

Accepted Answer

Array uses continuous memory locations (**space** complexity `O(n)`) to store the element so **retrieving** of any element will take `O(1)` time complexity (constant time by using index of the retrieved element). `O(1)` describes **inserting** at the end of the array. However, if you're inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is `O(n)` for arrays. End appending also discounts the case where you'd have to resize an array if it's full.

|Operation	|Average Case	|Worst Case
|-|-|-|
|Read	    | `O(1)`	        |`O(1)`
|Append       |`O(1)`            |`O(1)`
|Insert	   |`O(n)`	        |`O(n)`
|Delete	   |`O(n)`	        |`O(n)`
|Search	   |`O(n)`	        |`O(n)`

Question 4

What is a main difference between an Array and a Dictionary?

Accepted Answer

Arrays and dictionaries both store collections of data, but differ by _how they are accessed_. Arrays provide _random access_ of a sequential set of data. Dictionaries (or associative arrays) provide a _map_ from a _set of keys_ to a _set of values_. 
* Arrays store a set of objects (that can be accessed randomly)
* Dictionaries store pairs of objects
* Items in an array are accessed by position (_index_) (often a number) and hence have an order. 
* Items in a dictionary are accessed by _key_ and are unordered.

This makes array/lists more suitable when you have a group of objects in a set (prime numbers, colors, students, etc.). Dictionaries are better suited for showing relationships between a pair of objects.

Question 5

What are Dynamic Arrays?

Accepted Answer

A **dynamic array** is an array with a big improvement: _automatic resizing_.

One limitation of arrays is that they're _fixed_ size, meaning you need to specify the number of elements your array will hold ahead of time. A dynamic array expands as you add more elements. So you don't need to determine the size ahead of time.

Question 6

Name some advantages and disadvantages of Arrays

Accepted Answer

**Pros:**
* **Fast lookups**. Retrieving the element at a given index takes `O(1)` time, regardless of the length of the array.
* **Fast appends**. Adding a new element at the end of the array takes `O(1)` time.

**Cons:**
* **Fixed size**. You need to specify how many elements you're going to store in your array ahead of time.
* **Costly inserts and deletes**. You have to shift the other elements to fill in or close gaps, which takes worst-case `O(n)` time.

Question 7

How do Dynamic Arrays work?

Accepted Answer

A simple dynamic array can be constructed by _allocating an array of fixed-size_, typically _larger_ than the number of elements immediately required. The elements of the dynamic array are stored contiguously at the start of the underlying array, and the remaining positions towards the end of the underlying array are reserved, or unused. Elements can be added at the end of a dynamic array in constant time by using the reserved space until this space is completely consumed.

When all space is consumed, and an additional element is to be added, the underlying fixed-sized array needs to be increased in size. Typically resizing is expensive because you have to allocate a bigger array and copy over all of the elements from the array you have overgrow before we can finally append our item.

Dynamic arrays memory allocation is language specific. For example in C++ arrays are created on the stack, and have automatic storage duration -- you don't need to manually manage memory, but they get destroyed when the function they're in ends. They necessarily have a fixed size:

```js
int foo[10];
```

Arrays created with operator `new[]` have _dynamic_ storage duration and are stored on the heap (technically the "free store"). They can have any size, but you need to allocate and free them yourself since they're not part of the stack frame:

```js
int* foo = new int[10];
delete[] foo;
```

Question 8

What does Sparse Array mean?

Accepted Answer

A **sparse array** is an array of data in which many elements have a value of zero. This is in contrast to a dense array, where most of the elements have non-zero values or are “full” of numbers.

```sh
0	3	5	0	0	0	0	9	0	0
```

For example consider representing a very large 2D matrix of values, where most of the values are 0. The most straightforward representation would be a very large two dimensional array of integers. This straightforward approach has a few limitations however. If the matrix we are reperesenting is very large, it requires a large quantity of memory to store, even if the number of non-zero elements is small. A better way of representing a sparse martrix would be to only store the values that are non-zero, in such a way that iterating through the rows or columns of non-empty elements is relatively fast.

Question 9

Compare Array based vs Linked List stack implementations

Accepted Answer

The following implementations are most common: * Stack backed by a **singly-linked list**. Because a singly-linked list supports O(1) time prepend and delete-first, the cost to push or pop into a linked-list-backed stack is also O(1) worst-case. However, each new element added requires a new allocation, and allocations can be expensive compared to other operations. The _locality_ of the linked list is not as good as the locality of the dynamic array since there is no guarantee that the linked list cells will be stored contiguously in memory. * Stack backed by a **dynamic array**. Pushing onto the stack can be implemented by appending a new element to the dynamic array, which takes **amortised** O(1) time and worst-case O(n) time. Popping from the stack can be implemented by just removing the last element, which runs in worst-case O(1) (or amortised O(1) if you want to try to reclaim unused space). In other words, the most common implementation has best-case O(1) push and pop, worst-case O(n) push and O(1) pop, and amortised O(1) push and O(1) pop.

Question 10

What is an Associative Array?

Accepted Answer

In computer science, an **associative array**, map, symbol table, or **dictionary** is an abstract data type composed of a collection of [key, value] pairs, such that each possible key appears at most once in the collection. Associative array can be implemented as:
* Hash table
* Self-balancing binary search tree
* Unbalanced binary search tree
* Association list

Top 21 Arrays Interview Questions

Explain what is an Array?

Name some characteristics of Array Data Structure

How do Dynamic Arrays work?

What are Dynamic Arrays?

What is a main difference between an Array and a Dictionary?

Name some advantages and disadvantages of Arrays

What is time complexity of basic Array operations?

How exactly indexing works in Arrays?

What is the advantage of Heaps over Sorted Arrays?

What are time complexities of sorted array operations?

What are advantages of Sorted Arrays?

What is an Associative Array?

Compare Array based vs Linked List stack implementations

When to use a Linked List over an Array/Array List?

What does Sparse Array mean?

What defines the dimensionality of an Array?

How would you compare Dynamic Arrays with Linked Lists and vice versa?

Why is the complexity of fetching from an Array be `O(1)`?

Check for balanced parentheses in linear time using constant space

How to merge two sorted Arrays into a Sorted Array?

How to implement 3 Stacks with one Array?

Top 21 Arrays Interview Questions

Explain what is an Array?

Name some characteristics of Array Data Structure

How do Dynamic Arrays work?

What are Dynamic Arrays?

What is a main difference between an Array and a Dictionary?

Name some advantages and disadvantages of Arrays

What is time complexity of basic Array operations?

How exactly indexing works in Arrays?

What is the advantage of Heaps over Sorted Arrays?

What are time complexities of sorted array operations?

What are advantages of Sorted Arrays?

What is an Associative Array?

Compare Array based vs Linked List stack implementations

When to use a Linked List over an Array/Array List?

What does Sparse Array mean?

What defines the dimensionality of an Array?

How would you compare Dynamic Arrays with Linked Lists and vice versa?

Why is the complexity of fetching from an Array be O(1)?

Check for balanced parentheses in linear time using constant space

How to merge two sorted Arrays into a Sorted Array?

How to implement 3 Stacks with one Array?

Why is the complexity of fetching from an Array be `O(1)`?