ARRAYS 101: The brief summary for Interviews

Everything you need to know about arrays before a technical interview.

Photo by sigmund on Unsplash

Hello, tech geeks. If you have an upcoming interview and need to brush up on basic array concepts, you’ve come to the perfect place. I made some notes on every topic of data structures with python language when preparing for my interviews a while back, and I’m here to share them with you. Let’s get started!

What is an ARRAY?

An array is a data structure primarily for storing multiple data items with a similar data type. Here, items are stored or allocated at adjacent memory locations. And, these locations are referred to as elements of the array.

The total number of elements in an array is called the length of array and the reference that we use to access its position is called an index of the array. In an array, these 2 things i.e. element and index of an element are the most important concept. The more you play around with these 2 things in the array problems, the more your logic of array gets stronger. Lastly, array is the most commonly asked data structure during interviews.

Why do we need arrays?

• Arrays assist us to maintain a huge set of data under a single variable name to avoid confusion that might come when using several variables.
• Additionally, it is better at swiftly and efficiently processing multiple values and also allows random access to elements.
• Lastly, compared to other data structures, arrays make it simpler to perform operations like searching and sorting values too.

Syntax of ARRAY:

In most programming languages, there are three primary things that are used when declaring an array. They are as follows:

1. Array name — used to make it simple to refer to the collection of items.
2. Data type — used for data integrity and type checking.
3. Elements

//In C++ language:
int interest[3] = {100,250,400}

//In Java language:
int[] interest = new int[]{100,250,400};

However, arrays are not the same as lists in Python. So it has a separate module called array for dealing with arrays, which we must import before we begin working on it. So, for declaring an array in python:

1. Array name — An identifier for specifying its name
2. Module — Python has a particular module called “array” that we must import before we can use it.
3. Method — The array module includes an initialisation method. It requires two arguments (type code and elements).
4. Type code — Specifies the data type
5. Elements.

#In Python language:
import array
interest = array.array('i',[100,250,400])

Finally, we can access any specific array value by just using its syntax. It is very quick and simple.

#Syntax:
arrayName[index]

Example:

interest[1]

#Output: 250

Operations in Arrays:

In arrays, there are five operations that can be performed. In other programming languages, such as C++ and Java, we must write programs to execute such operations; however, in Python, the array module includes separate functions for executing such array operations.

1. Insert: Here, we can insert one or more items into the array at the start, end, or any given index. It takes two arguments, index and value.

#Syntax
arrayName.insert(index,value)

2. Delete: For deletion, we can delete an item from an array by its value. Here, this method accepts only one argument, i.e. value. After execution, array items are re-arranged and indices are re-assigned.

#Syntax
arrayName.remove(value)

3. Search: This method is non-destructive i.e. it has no effect on the array values. In this case, we can search an item in the array by its value. As a result, this method only accepts one argument, value.

#Syntax
arrayName.index(value)

4. Update: This method works similarly to the insertion operation, except that we are replacing an existing value at the given index with a new one. This method accepts the same two arguments as insert.

#Syntax
arrayName.update(index,value)

5. Traverse: We can traverse a python array by using loops.

#Syntax
import array
interest = array.array('i',[100,250,400])
for x in interest:
  print(x)

Output:

100
250
400

Common terms to know for array problems:

1. Sub-array: It is a range of contiguous values within an array.

#Example:
arr = array.array('i',[2,3,4,6,8,1])
#Here, [2,3,4] is a subarray but, [2,4,6] is not a subarray.
#It needs to be contiguous.

2. Sub-sequence: It is a sequence which we can be derived from a given sequence by deleting some or no elements without changing the order of the remaining elements.

#Example:
arr = array.array('i',[2,3,4,6,8,1])
#Here, [2,4,6] is a subsequence but, [2,6,4] is not a subsequence.
#It needs to be in the specific given order.

Advantages of arrays:

1. Storing multiple elements of the same type under a single variable name.
2. Faster in accessing elements: As long as, we have the index, we can access elements quickly unlike a linked list where we need to traverse the whole from the head.

Disadvantages of arrays:

1. Addition and removal of elements into/from any middle position of the array is very slow, as we have to shift all the elements to accommodate the new element.

Time Complexity of the operations:

From techinterviewhandbook

Techniques used in most of the array problems:

1. Sliding Window: Sliding Window is a computational technique that tries to replace nested loops with a single loop, reducing the time complexity. Here, two pointers usually move in the same direction and will never overtake each other. It mostly works in most subarray/substring problems.

Practice questions:

Longest Substring Without Repeating Characters - LeetCode

Minimum Window Substring - LeetCode

2. Two Pointers: Two pointers is a general version of the sliding window, where the pointers can cross each other and can be on different arrays too.

Practice Questions:

Sort Colors - LeetCode

Palindromic Substrings - LeetCode

3. Traversing from right: Sometimes, it is better to traverse the array from the right instead of the left which we conventionally do.

Practice Questions:

Daily Temperatures - LeetCode

Number of Visible People in a Queue - LeetCode

4. Sorting array: Mostly in binary search problems, we need to sort the array.

Practice Questions:

Non-overlapping Intervals - LeetCode

Merge Intervals - LeetCode

5. Pre-computation: It is used where summation and multiplication of subarray are involved, using hashing, etc.

Practice Questions:

Product of Array Except Self - LeetCode

Minimum Size Subarray Sum - LeetCode

Books recommendation for data structures and algorithms:

1. Data Structures And Algorithms Made Easy: Data Structures And Algorithmic Puzzles

2. Data Structures and Algorithms Made Easy in JAVA: Data Structure and Algorithmic Puzzles

3. Hands-On Data Structures and Algorithms with Python_second Edition

Data Structures And Algorithms Made Easy: Data Structures And Algorithmic Puzzles

Hands-On Data Structures and Algorithms with Python_second Edition: Write complex and powerful code…

Data Structures and Algorithms Made Easy in JAVA: Data Structure and Algorithmic Puzzles