DSA for MAANG Interviews
Arrays and Strings
Arrays: The Building Blocks
Think of an array as a row of numbered boxes, all sitting next to each other. Each box can hold one item, and all items must be of the same type, like integers or characters. Because the boxes are in a neat, numbered line, you can instantly jump to any box just by knowing its number, or index. This makes accessing data in an array very fast.
In most programming languages, indexing starts at 0. So, in an array with 10 items, the first item is at index 0, and the last is at index 9. This might feel odd at first, but it's a fundamental convention in computer science.
// A simple array of integers in Java
int[] numbers = {10, 20, 30, 40, 50};
// Access the first element (at index 0)
int first = numbers[0]; // first is 10
// Access the third element (at index 2)
int third = numbers[2]; // third is 30
The main properties of an array are its fixed size and the requirement that all elements are the same data type. Once you create an array to hold, say, five integers, you can't just decide to make it hold six, or start putting text in it. This rigidity is what makes them simple and efficient.
Working with Arrays
The most common thing to do with an array is to visit each element in order. This is called traversal. You might do this to print every item, sum them up, or find a specific value.
// Traversing an array in Python to print each number
numbers = [10, 20, 30, 40, 50]
for number in numbers:
print(number)
What about adding or removing elements? Since an array's size is fixed, this gets a bit tricky. To "insert" an element into a full array, you'd typically need to create a new, larger array, copy everything over, and then add the new item. Deleting an item might mean shifting all subsequent elements one spot to the left to fill the gap.
These operations can be slow, especially for large arrays. This is a key trade-off: arrays offer fast access but slower modifications.
Arrays excel at storing and reading data. They are less ideal when you need to frequently add or remove elements.
Sometimes, one row of boxes isn't enough. A two-dimensional array, or matrix, is like a grid or a spreadsheet. It's an array of arrays. You access elements using two indices: one for the row and one for the column.
// A 2D array (3 rows, 4 columns) in C++
int matrix[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
// Access the element in the 2nd row, 3rd column
// (row index 1, column index 2)
int element = matrix[1][2]; // element is 7
Strings: Arrays of Characters
A string is just a sequence of characters. In many languages, strings are implemented under the hood as arrays of characters. This means a lot of what you know about arrays applies to strings, too. You can access individual characters using an index, and you can traverse a string from beginning to end.
However, strings usually come with a set of powerful, built-in functions that make them easier to work with than plain arrays. Here are a few common operations.
| Operation | Description | Example (Python) |
|---|---|---|
| Concatenation | Joining two strings together. | 'hello' + ' ' + 'world' |
| Substring | Extracting a piece of a string. | 'computer'[0:4] returns 'comp' |
| Search | Finding if a smaller string exists inside a larger one. | 'world' in 'hello world' returns True |
One final, important point about strings is character encoding. A computer only understands numbers, so every character needs a numeric code. Early systems used ASCII, which covered English letters, numbers, and basic symbols. But what about characters like 'é', 'ñ', or '你好'?
Unicode is a modern standard that aims to provide a unique number for every character, no matter the language or platform. UTF-8 is the most common Unicode encoding on the web. You don't always have to think about it, but it's good to know that this system is what allows software to handle text from all over the world.
Let's check your understanding of these fundamental structures.
What is the primary trade-off when using arrays?
In a standard array with 25 elements, the first element is at index 0 and the last element is located at which index?
Arrays and strings are the foundation for more complex data structures. Mastering how to access and manipulate them is a critical first step in solving programming challenges.