You can also find all 100 answers here ๐ Devinterview.io - Data Structures
In-place reversal modifies the original array without extra space.
Here is a general-purpose implementation:
Here is the Python code:
def reverse_array(arr):
start, end = 0, len(arr) - 1
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start, end = start + 1, end - 1
my_array = [1, 2, 3, 4, 5]
print("Original Array:", my_array)
reverse_array(my_array)
print("Reversed Array:", my_array)
Let me put the two fundamental type of lists, Arrays and Linked Lists, into perspective.
- Array: Employs sequential memory storage and each element has a unique index.
- Linked List: Elements are scattered in memory and accessed sequentially via references (pointers).
- Array: Typically requires a single, contiguous memory block.
- Linked List: Memory allocations are dynamic and non-contiguous.
Operation | Array | Linked List |
---|---|---|
Access |
|
|
Bulk Insertion |
|
|
Deletion |
|
-
Arrays are preferable when:
- There's a need for direct or random access such as in lookup tables.
- The data will remain relatively unchanged, and performance in accessing elements takes precedence over frequent insertions or deletions.
-
Linked Lists are more suitable when:
- Frequent insertions and deletions are expected, especially in the middle.
- The exact size of the list isn't known in advance, and you want the memory to be used flexibly.
- The primary operations are sequential, such as iteration from the beginning to the end.
Here is the Python code:
# Define array
my_array = [10, 20, 30, 40, 50]
# Access element by index
print(my_array[2]) # Output: 30
# Bulk insertion at the beginning
my_array = [5, 6, 7] + my_array
print(my_array) # Output: [5, 6, 7, 10, 20, 30, 40, 50]
# Deletion from the middle
del my_array[4]
print(my_array) # Output: [5, 6, 7, 10, 30, 40, 50]
# Define linked list nodes (in reality, you'd have a LinkedList class)
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Create linked list
head = Node(10)
node1 = Node(20)
node2 = Node(30)
head.next = node1
node1.next = node2
# Bulk insertion at the beginning
new_node1 = Node(5)
new_node2 = Node(6)
new_node3 = Node(7)
new_node3.next = head
head = new_node1
new_node1.next = new_node2
print_nodes(head) # Output: 5, 6, 7, 10, 20, 30
# Deletion from the middle
new_node1.next = new_node3
# Now, just print_nodes(head) will output: 5, 6, 7, 20, 30
Checking for duplicates in an array without additional space is a common challenge with solutions using hash functions, sorting, and mathematical calculations.
The code checks for duplicates based on numerical repetition.
-
Time Complexity:
$O(n^2)$ -
Space Complexity:
$O(1)$
Here is the Python code:
def has_duplicates(arr):
n = len(arr)
for i in range(n):
for j in range(i+1, n):
if arr[i] == arr[j]:
return True
return False
arr = [1, 2, 3, 4, 3]
print(has_duplicates(arr)) # Output: True
This method involves sorting the array using a comparison-based sorting algorithm like Quick Sort. If two adjacent elements are the same, then the array has duplicates.
-
Time Complexity: Best/Worst:
$O(n \log n)$ -
Space Complexity:
$O(1)$ or$O(n)$ depending on sorting algorithm
Here is the Python code:
def has_duplicates_sorted(arr):
arr.sort()
n = len(arr)
for i in range(n - 1):
if arr[i] == arr[i+1]:
return True
return False
arr = [1, 2, 3, 4, 3]
print(has_duplicates_sorted(arr)) # Output: True
For this method, the sum of numbers in the array is calculated. Mathematically, if no duplicates are present, the sum of consecutive natural numbers can be calculated to compare against the actual sum.
If
Here is the Python code:
def has_duplicates_math(arr):
array_sum = sum(arr)
n = len(arr)
expected_sum = (n * (n-1)) // 2 # Sum of first (n-1) natural numbers
return array_sum - expected_sum != 0
arr = [1, 2, 3, 4, 5, 5]
print(has_duplicates_math(arr)) # Output: True
Let's look at the high-level strategy behind binary search and then walk through a step-by-step example.
- Divide & Conquer: Begin with the entire sorted array and refine the search range in each step.
- Comparison: Use the middle element to determine the next search range.
- Repetition: Continue dividing the array until the target is found or the search range is empty.
Let's consider the following array with the target value of 17
:
[1, 3, 6, 7, 9, 12, 15, 17, 20, 21]
-
Initial Pointers: We start with the whole array.
[1, 3, 6, 7, 9, 12, 15, 17, 20, 21] ^ ^ Low High Middle: (Low + High) / 2 = 5
This identifies the
Middle
number as12
. -
Comparison: Since the
Middle
number is less than the target17
, we can discard the left portion of the array.[15, 17, 20, 21] ^ ^ Low High
-
Updated Pointers: We now have a reduced array to search.
Middle = 7 ^ ^ Low High
-
Final Comparison:
Since theMiddle
number is now the target,17
, the search is successfully concluded.
Rotating a 2D array by
-
Transpose: Swap each element
$A[i][j]$ with its counterpart$A[j][i]$ -
Reverse Rows (for
$90^\circ$ CW) or Columns (for$90^\circ$ CCW)
-
Time Complexity: Both steps run in
$O(n^2)$ time. -
Space Complexity: Since we do an in-place rotation, it's
$O(1)$ .
Here is the Python code:
def rotate_2d_clockwise(matrix):
n = len(matrix)
# Transpose
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Reverse Rows
for i in range(n):
for j in range(n//2):
matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]
return matrix
def rotate_matrix_ccw(matrix):
n = len(matrix)
# Transpose
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Reverse Columns
for i in range(n):
for j in range(n//2):
matrix[j][i], matrix[n-j-1][i] = matrix[n-j-1][i], matrix[j][i]
return matrix
# Test
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(rotate_2d_clockwise(matrix))
# Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
You can compress a string following the count of each character. For example, "aabbccc" becomes "a2b2c3".
The python code for this algorithm is:
def compress_string(input_string):
# Initialize
current_char = input_string[0]
char_count = 1
output = current_char
# Iterate through the string
for char in input_string[1:]:
# If the character matches the current one, increment count
if char == current_char:
char_count += 1
else: # Append the count to the output and reset for the new character
output += str(char_count) + char
current_char = char
char_count = 1
# Append the last character's count
output += str(char_count)
# If the compressed string is shorter than the original string, return it
return output if len(output) < len(input_string) else input_string
This algorithm has a time complexity of
The space complexity is
Let's look at what is an Array Slice and how it's implemented in some programming languages.
An array slice is a view on an existing array that acts as a smaller array. The slice references a continuous section of the original array which allows for efficient data access and manipulation.
Array slices are commonly used in languages like Python, Rust, and Go.
- Read: Access elements in the slice.
- Write: Modify elements within the slice.
- Grow/Shrink: Resize the slice, often DWARF amortized.
- Iteration: Iterate over the elements in the slice.
A slice typically contains:
- A pointer to the start of the slice.
- The length of the slice (the number of elements in the slice).
- The capacity of the slice (the maximum number of elements that the slice can hold).
- No Copy Overhead: Slices don't duplicate the underlying data; they're just references. This makes them efficient and memory-friendly.
- Flexibility: Slices can adapt as the array changes in size.
- Safety: Languages like Rust use slices for enforcing safety measures, preventing out-of-bounds access and memory issues.
-
Python: Uses list slicing, with syntax like
my_list[2:5]
. This creates a new list. -
Go Lang: Employs slices extensively and is perhaps the most slice-oriented language out there.
-
Rust: Similar to Go, it's a language heavily focused on memory safety, and slices are fundamental in that regard.
Here is the Python code:
original_list = [1, 2, 3, 4, 5]
my_slice = original_list[1:4] # Creates a new list: [2, 3, 4]
Here is the Rust code:
let original_vec = vec![1, 2, 3, 4, 5];
let my_slice = &original_vec[1..4]; // References a slice: [2, 3, 4]
And here is the Go code:
originalArray := [5]int{1, 2, 3, 4, 5}
mySlice := originalArray[1:4] // References the originalArray from index 1 to 3
Both array insertions and deletions have a time complexity of
-
Beginning:
$O(n)$ if array full;$1$ for shifting. -
Middle:
$O(n)$ to make room and insert. -
End:
$O(1)$ on average for appending.
-
Beginning:
$O(n)$ due to re-arrangement often needed. -
Middle:
$O(n)$ as it involves shifting. -
End:
$O(1)$ for most cases, but$O(n)$ when dynamic resizing is required.
Merging two sorted arrays into a new sorted array can be accomplished through a variety of well-established techniques.
-
Using Additional Space:
- Create a new array and add elements from both arrays using two pointers, then return the merged list.
- Time Complexity:
$O(n + m)$ - where$n$ and$m$ are the number of elements in each array. This approach is simple and intuitive.
-
Using a Min Heap:
- Select the smallest element from both arrays using a min-heap and insert it into the new array.
- Time Complexity:
$O((n + m) \log (n + m))$ - Space Complexity:
$O(n + m)$ - Heap might contain all the elements. - This approach is useful when the arrays are too large to fit in memory.
-
In-Place Merge:
- Implement a merge similar to the one used in Merge Sort, directly within the input array.
- Time Complexity:
$O(n \cdot m)$ - where$n$ and$m$ are the number of elements in each array. - In-Place Merging becomes inefficient as the number of insertions increases.
-
Using Binary Search:
- Keep dividing the larger array into two parts and using binary search to find the correct position for elements in the smaller array.
- Time Complexity:
$O(m \log n)$
-
Two-Pointer Technique:
- Initialize two pointers, one for each array, and compare them to determine the next element in the merged array.
- Time Complexity:
$O(n + m)$
To find the
-
Idea: Partition the array using a pivot (similar to quicksort) and divide into subarrays until the partitioning index is the
$k^{\text{th}}$ largest element. -
Time Complexity:
- Worst-case:
$O(n^2)$ - This occurs when we're faced with the least optimized scenario, reducing$n$ by only one element for each stitch step. - Average-case:
$O(n)$ - Average performance is fast, making the expected time complexity linear.
- Worst-case:
-
Code Example: Python
import random def quickselect(arr, k): if arr: pivot = random.choice(arr) left = [x for x in arr if x < pivot] right = [x for x in arr if x > pivot] equal = [x for x in arr if x == pivot] if k < len(left): return quickselect(left, k) elif k < len(left) + len(equal): return pivot else: return quickselect(right, k - len(left) - len(equal))
- Build a max-heap
$O(n)$ - This takes linear time, making$O(n) + O(k \log n) = O(n + k \log n)$ . - Extract the max element
$k$ times (each time re-heapifying the remaining elements).
import heapq
def kth_largest_heap(arr, k):
if k > len(arr): return None
neg_nums = [-i for i in arr]
heapq.heapify(neg_nums)
k_largest = [heapq.heappop(neg_nums) for _ in range(k)]
return -k_largest[-1]
Singly linked lists and doubly linked lists differ in how they manage node-to-node relationships.
-
Singly Linked List: Each node points to the next node.
-
Doubly Linked List: Both previous and next nodes are pointed to.
-
Access Direction: Singly linked lists facilitate one-way traversal, while doubly linked lists support bi-directional traversal.
-
Head and Tail Movements: Singly linked lists only operate on the head, while doubly linked lists can manipulate the head and tail.
-
Backward Traversal Efficiency: Due to their structure, singly linked lists may be less efficient for backward traversal.
-
Memory Requirement: Doubly linked lists use more memory as each node carries an extra pointer.
Here is the Java code:
public class SinglyLinkedList {
private static class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head;
public void insertFirst(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
public void display() {
Node current = head;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
}
Here is the Java code:
public class DoublyLinkedList {
private static class Node {
private int data;
private Node previous;
private Node next;
public Node(int data) {
this.data = data;
this.previous = null;
this.next = null;
}
}
private Node head;
private Node tail;
public void insertFirst(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
} else {
head.previous = newNode;
newNode.next = head;
head = newNode;
}
}
public void display() {
Node current = head;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
public void displayBackward() {
Node current = tail;
while (current != null) {
System.out.println(current.data);
current = current.previous;
}
}
}
Cycle detection in a linked list is a fundamental algorithm that uses pointers to identify if a linked list has a repeating sequence.
Floyd's algorithm utilizes two pointers:
- The "tortoise" moves one step each iteration.
- The "hare" moves two steps.
If the linked list does not have a cycle, the hare either reaches the end (or null) before the tortoise, or vice versa. However, if there is a cycle, the two pointers are guaranteed to meet inside the cycle.
- Initialize both pointers to the start of the linked list.
- Move the tortoise one step and the hare two steps.
- Continuously advance the pointers in their respective steps:
- If the tortoise reaches the hare (a collision point), return such a point.
- If either pointer reaches the end (null), conclude there is no cycle.
-
Time Complexity:
$O(n)$ where$n$ is the number of nodes in the linked list, due to each pointer visiting each node only once. -
Space Complexity:
$O(1)$ as the algorithm uses only a constant amount of extra space.
Here is the Python code:
def has_cycle(head):
tortoise = head
hare = head
while hare and hare.next:
tortoise = tortoise.next
hare = hare.next.next
if tortoise == hare:
return True
return False
Let's look at the major operations you can perform on a singly linked list and their associated time complexities:
-
Head: Constant time:
$O(1)$ . -
Tail:
$O(n)$ without a tail pointer, but constant with a tail pointer. -
Middle or k-th Element:
$\frac{n}{2}$ is around the middle node; getting k-th element requires$O(k)$ .
-
Unordered: May require scanning the entire list. Worst case:
$O(n)$ . - Ordered: You can stop as soon as the value exceeds what you're looking for.
-
Head:
$O(1)$ -
Tail:
$O(1)$ with a tail pointer, otherwise$O(n)$ . -
Middle:
$O(1)$ with tail pointer and finding position in$O(1)$ time; otherwise, it's$O(n)$ .
-
Head:
$O(1)$ -
Tail:
$O(n)$ because you must find the node before the tail for pointer reversal with a single pass. -
Middle:
$O(n)$ since you need to find the node before the one to be deleted.
- Naive: Requires a full traversal. Every addition or removal requires this traversal.
- Keep Count: Maintain a separate counter, updating it with each addition or removal.
Here is the Python code:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def append(self, data): # O(n) without tail pointer
new_node = Node(data)
if not self.head:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def delete(self, data): # O(n) only if element is not at head
current_node = self.head
if current_node.data == data:
self.head = current_node.next
current_node = None
return
while current_node:
if current_node.data == data:
break
prev = current_node
current_node = current_node.next
if current_node is None:
return
prev.next = current_node.next
current_node = None
def get_middle(self): # O(n)
slow, fast = self.head, self.head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def get_kth(self, k): # O(k)
current_node, count = self.head, 0
while current_node:
count += 1
if count == k:
return current_node
current_node = current_node.next
return None
# Other methods: display, length, etc.
In-Place Algorithms modify data structures with a constant amount of extra working space
A Singly Linked List presents a straightforward example of an in-place data structure, well-suited for in-place reversal algorithms.
The reversal algorithm just needs to update each node's next
reference so that they point to the previous node. A few key steps achieve this:
- Initialize: Keep track of the three key nodes:
previous
,current
, andnext
. - Reverse Links: Update each node to instead point to the previous one in line.
- Move Pointers: Shift
previous
,current
, andnext
nodes by one position for the next iteration.
This process proceeds iteratively until current
reaches the end, i.e., NULL
.
-
Time Complexity: The algorithm exhibits a linear time complexity of
$O(n)$ as it visits each node once. -
Space Complexity: As the algorithm operates in-place, only a constant amount of extra space (for nodes pointers) is required:
$O(1)$ .
Here is the Python code:
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def reverse_inplace(self):
previous = None
current = self.head
while current:
next_node = current.next
current.next = previous
previous = current
current = next_node
self.head = previous
def display(self):
elements = []
current = self.head
while current:
elements.append(current.data)
current = current.next
print(" -> ".join(str(data) for data in elements))
# Populate the linked list
llist = LinkedList()
values = [4, 2, 8, 3, 1, 9]
for value in values:
llist.append(value)
# Display original
print("Original Linked List:")
llist.display()
# Reverse in-place and display
llist.reverse_inplace()
print("\nAfter Reversal:")
llist.display()
Finding the middle element of a linked list is a common problem with several efficient approaches, such as the two-pointer (or "runner") technique.
The two-pointer technique uses two pointers, often named slow
and fast
, to traverse the list. While fast
moves two positions at a time, slow
trails behind, covering a single position per move. When fast
reaches the end, slow
will be standing on the middle element.
Given the linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
The pointers will traverse as follows:
- (1)
slow
: 1;fast
: 2 - (2)
slow
: 2;fast
: 4 - (3)
slow
: 3;fast
: 6 - (4)
slow
: 4;fast
: end
At (4), the slow
pointer has reached the middle point.
-
Time Complexity:
$O(N)$ -- For every N nodes, we check each node once. -
Space Complexity:
$O(1)$ -- We only use pointers; no extra data structures are involved.
Here is the Python implementation:
def find_middle_node(head):
if not head:
return None
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow