Prepare Yourself for a Coding Interview with Data Structures in Python

Learn Basic Data Structures
Practical Approach - 1

In Computer Science, graduates and programmers are applying for programming and software development roles at startups and big organizations like Google, Amazon, Microsoft many more. As a graduate, it's expected from you to have strong knowledge of both basic data structures like Array, Linked List, Stack, Queue, Binary Tree, Hash Table, and advanced data structures like Binary Heap, Buffer, etc. It does not matter whether your a java developer or a web developer.

In this article, I will share the basic concepts of frequently asked Data Structures and Algorithms in the interviews along with some questions based on that data structure. (Solutions will be available only in python3)

Prerequisites:- At least familiar with coding.

Let's start with What is Data Structure?

Data Structures is a collection of data values that are stored and organized in such a way that it allows for efficient access and modification.

Some of the uses of Data Structures:

• It provides data efficiency for uses such as large databases and internet indexing services.
• Hash Tables are usually used for implementing compilers.
• It can be used to store and retrieve information from both the main memory and secondary memory

Note: Efficient Data Structures are key to designing efficient Algorithms.

You might be thinking What is the difference between Data Structure and Algorithms?

Data Structure is about organizing and managing data effectively such that we can perform specific operations efficiently.
The Algorithm is a step-by-step procedure to be followed to reach the desired output. Steps in an algorithm can use one or more data structure(s) to solve a problem.

Some examples of Data Structures:

• Linear Data Structure: Array, Linked List, Stack, Queue.
• Hierarchical Data Structure: Tree, Heap, Trie.
• Other Data Structures: Graph, Hash, Matrix.

Some examples of Algorithms:

• Sorting Algorithms: Quick Sort, Merge Sort, Radix sort, etc.
• Searching Algorithms: Binary Search, Linear Search, etc.
• Shortest Path Algorithms: Dijkstra's algorithm, Floyd–Warshall algorithm, etc.

Let's now look at some of the most frequently asked Data Structures and Algorithms:

1. Array

An array is a collection of elements stored at the contiguous memory locations. It stores a fixed-size sequential collection of the same type.

An array is the most fundamental data structure and it is one of the favorite topics of the interviewer. You may hear a lot of questions about an array in technical interviews.

The benefit of an array is that it takes O(1) to search elements if you know the index of the element. But adding and removing the element from an array is quite not efficient because you can not change the size of an array once it is created.

But by default python doesn't have an array it has a list. Lists are similar to a dynamic array. To use array in python you'll need to import data structure (array) from array module or NumPy package. The list can store different types of data, as it's a default in python it is a part of python's syntax.

Let's see How the array stores data in memory?:

As shown in the above figure,
Meaning that given an array identifier of arr which is assigned the values [3, 4, 5, 7, 8, 9], in order to access the 5 the element, you would use the index 2 to lookup the value: arr[2]. We generally use 64-bit integers are shown in the second figure.

The compiler remembers the address of the first byte of an array only. In fact, the address of the first byte is considered as the memory address for the entire array.

Implementation of an Array and Python's default List:

Some operation that can be performed on the array:

append(value)	To insert an element to the end of an array
insert(i,value)	To insert an element at a given position
extend(arr)	To extend more than one value to an array
remove(value)	To remove the first equivalent element to value
pop() and pop(i)	To remove the last element of an array and element at index i
index(value)	To find an index of a given value
count(value)	To count the occurrence of the value
reverse()	To reverse array

Now let's implement these functions:

Here is the list of some of the popular array-based coding interview questions:

1. Reverse an array in place? (Solution)
2. Remove duplicate from an array in place? (Solution)
3. Find duplicate numbers from an array if it contains duplicates? (Solution)
4. Sort an integer array in place using the QuickSort algorithm? (Solution)
5. Find missing numbers from the integer array? (Solution)
6. Finding all pairs of integer array whose sum is equal to the given number? (Solution)
7. Check if values in array form a valid mountain. (Problem with Solution)
8. Find a maximum and minimum number from the unsorted integer array? (Solution)
9. Search for an element in a rotated sorted array. (Problem with Solution)
10. Finding the peak element from an array. (Problem with Solution)

2. String

The string is not a Data Structure but it is a data type and often implemented as an array data structure (of words) that stores a sequence of the element.

A Series of characters is known as String.

If you know how to solve array-based questions then it might be easy to solve string programming questions as well.

In Python, a string is a sequence of Unicode Characters. However, python does not support character data type, python considers a single character as a string having a length 1.

As shown in the above figure, Square brackets are used to access and manipulate the elements of the string. 

Let's see String in action:

Here is the list of some of the popular string coding interview questions:

1. Remove all blank spaces from a string? (Solution)
2. Print duplicate characters from a string? (Solution)
3. Check if two strings are an anagram of each other? (Solution)
4. Check if a string is a palindrome? (Solution)
5. Count the occurrence of a given character in a string? (Solution) 
6. Find all the permutation of a string? (Solution)
7. Check if two strings are rotation of each other? (Solution)
8. Find the length of the longest substring without repeating character? (Problem with Solution)
9. Convert given string into integer like atoi()? (Problem with Solution)
10. How to reverse a word in a sentence without using any library? (Solution)