Most Popular Data Structures Interview Questions For Software Developers in 2023 — Part 2 Answers
Data Structures Are a Fundamental Topic in Computer Science And Are Frequently Asked About in Interviews, Regardless Of The Specific Tech Role.
Part One with a full list of questions is here.
So let us continue…
Hashing
- Describe how a hash table works.
The hash table stores data in key-value pairs. Each key is associated with one value. Keys are unique identifiers. The essence of a hash table is to provide quick and efficient data retrieval based on key-value pairs.
Advantages:
- Efficient Data Retrieval: O(1) average time complexity for lookups, insertions, and deletions.
- Direct Access: Data is accessed directly through keys, making retrievals fast.
Disadvantages:
- Space Complexity: Hash tables consume more memory due to the storage of keys and values.
- Collision Handling: Requires additional logic and can be complex depending on the method used.
Hash tables are highly efficient in terms of data retrieval and are particularly useful in scenarios where quick lookup, insertion, and deletion of data are required.
2. How do you handle collisions in a hash table?
Collisions in a hash table occur when two or more keys hash to the same index in the array. Handling these collisions is critical for the efficiency and accuracy of the hash table. There are several methods to handle collisions, with the most common being separate chaining and open addressing.
In separate chaining, each bucket of the hash table’s array contains a linked list (or another type of secondary data structure like a binary search tree). When a collision occurs, the new key-value pair is added to the end of the list in the corresponding bucket.
- Insertion: If two keys hash to the same index, they are stored in a list at that index.
- Lookup: To find an item, you hash the key and then search through the list at the corresponding index.
- Deletion: To delete an item, hash the key to find the list and then traverse the list to remove the item.
The advantages of separate chaining are — simple to implement, less sensitive to hash function quality, and can accommodate more elements than there are slots in the hash table.
Separate chaining’s performance can degrade if the lists become too long.
In open addressing, all key-value pairs are stored within the array itself. When a collision occurs, the hash table searches for the next empty slot according to a predefined sequence. The most common strategies in open addressing are linear probing, quadratic probing, and double hashing.
- Linear Probing — When a collision occurs, the hash table checks the next slot linearly until an empty slot is found. This can lead to clustering, where a group of adjacent slots gets filled up, leading to longer search times.
- Quadratic Probing — Instead of searching linearly, quadratic probing uses a quadratic function to calculate the interval between probes. This reduces clustering compared to linear probing.
- Double Hashing — Two different hash functions are used. The second hash function is used to determine the interval between probes after a collision. This method also helps in reducing clustering.
The advantages of open addressing are that all data is stored in the array, no extra space for pointers or nodes is required, and better cache performance.
Open addressing performance can degrade as the load factor increases.
Recursion and Dynamic Programming*
*Recursion is a method of solving problems where a function calls itself as a subroutine. In essence, a recursive function solves a problem by solving smaller instances of the same problem. Dynamic Programming is an optimization technique used to solve complex problems by breaking them down into simpler sub-problems and storing the results of these sub-problems to avoid redundant computations. Recursion is a technique, while dynamic programming is a method built on top of recursion. Recursion can lead to redundant calculations and higher time complexity in cases of overlapping sub-problems, whereas dynamic programming eliminates these redundancies by storing previous results.
- Implement the Fibonacci series using recursion and Dynamic Programming:
Implementing the Fibonacci series using both recursion and dynamic programming are classic examples of how a problem can be solved in multiple ways in programming, each with its own set of trade-offs.
- Using recursion:
public static int fibonacciRecursive(int n) {
if (n <= 1) {
return n;
}
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}- Using DP (Dynamic Programming):
private static Map<Integer, Integer> memo = new HashMap<>();
public static int fibonacciDP(int n) {
if (n <= 1) {
return n;
}
// Check if the value is already computed
if (memo.containsKey(n)) {
return memo.get(n);
}
int result = fibonacciDP(n - 1) + fibonacciDP(n - 2);
// Memoize the result
memo.put(n, result);
return result;
}In the dynamic programming version, a HashMap is used for memoization, which stores the Fibonacci numbers as they are calculated. Whenever a Fibonacci number is requested, the method first checks if it is in the map. If not, it calculates and stores it in the map.
This approach significantly reduces the number of recursive calls, especially for large values of n.
For large n, the dynamic programming approach is much more efficient.
2. How do you find the nth stair using step 1, 2, or 3 in a staircase problem?
public class Staircase {
public static int findWaysToClimb(int n) {
if (n == 0 || n == 1) return 1;
if (n == 2) return 2;
int[] ways = new int[n + 1];
ways[0] = 1;
ways[1] = 1;
ways[2] = 2;
for (int i = 3; i <= n; i++) {
ways[i] = ways[i - 1] + ways[i - 2] + ways[i - 3];
}
return ways[n];
}
public static void main(String[] args) {
int n = 4;
System.out.println("Number of ways to climb " + n + " steps: " + findWaysToClimb(n));
}
}
Output: Number of ways to climb 4 steps: 7
3. Explain the concept of memoization.
Memoization is a technique used in computer programming to optimize the execution time of a function by storing the results of expensive function calls and reusing them when the same inputs occur again.
- When a function is called, the result is stored in a data structure (such as an array or a hash map) with its parameters as the key.
- On subsequent calls with the same parameters, the function first checks the data structure. If the result is already stored, it is returned immediately without recomputing.
- This significantly reduces the number of calculations, especially in recursive algorithms where the same calculations are often repeated.
Memoization is a technique closely associated with dynamic programming, but they are not quite the same thing.
Memoization is a part of dynamic programming (specifically, the top-down approach). While all memoization can be considered a form of dynamic programming, not all dynamic programming uses memoization (as some use the bottom-up approach). There are two key approaches to dynamic programming:
- Top-Down Approach (Memoization) — This is essentially recursion with memoization. The problem is broken down into subproblems which are solved independently, and their solutions are stored for future reference.
- Bottom-Up Approach (Tabulation) — This approach involves systematically solving the problem, and building up the solution by solving all related subproblems first, typically using iteration. It starts with the simplest subproblems and uses their solutions to construct solutions to larger subproblems.
public class FibonacciMemoization {
private static long[] memo;
public static long fib(int n) {
if (memo[n] != -1) {
return memo[n];
}
if (n <= 1) {
return n;
} else {
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
}
public static void main(String[] args) {
int n = 30; // Example input
memo = new long[n + 1];
java.util.Arrays.fill(memo, -1);
System.out.println("Fibonacci of " + n + " is: " + fib(n));
}
}Time Complexity:
- Pure Recursion — Exponential (O(2^n)), because it recomputes the same subproblems multiple times.
- Recursion with Memoization — Linear (O(n)), as each subproblem is computed only once.
Space Complexity:
- Pure Recursion — O(n) due to the depth of the recursive call stack.
- Recursion with Memoization — O(n) for the recursive call stack and O(n) for the memoization array, but still considered O(n) overall.
Sorting and Searching
- The binary search algorithm
The binary search algorithm is an efficient method for finding an item in a sorted array. This algorithm repeatedly divides in half the portion of the list that could contain the item, until you’ve narrowed the possible locations to just one.
Here’s how the binary search algorithm works:
Define two variables to keep track of the current search range within the array. Typically, these are called start and end, initially set to the first and last indices of the array, respectively. In each iteration, find the middle element of the current search range. The middle element can be found as mid = start + (end - start) / 2. This prevents overflow issues that might arise from simply using (start + end) / 2. Compare the target value with the value at the mid index.
If the target value is equal to the middle element, you’ve found the item, and the search can be terminated. If the target value is less than the middle element, adjust the end to mid - 1. If the target value is greater than the middle element, adjust the start to mid + 1. Repeat the process with the new start and end values until the start exceeds end, indicating that the target is not in the array, or until the target is found.
public class BinarySearch {
public static int binarySearch(int[] array, int target) {
int start = 0;
int end = array.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (array[mid] == target) {
// Target found at index mid
return mid;
} else if (array[mid] < target) {
// Target is in the right half
start = mid + 1;
} else {
// Target is in the left half
end = mid - 1;
}
}
// Target is not in the array
return -1;
}
public static void main(String[] args) {
int[] numbers = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
int target = 23;
int result = binarySearch(numbers, target);
if (result == -1) {
System.out.println("Element not present in the array.");
} else {
System.out.println("Element found at index: " + result);
}
}
}
2. The quicksort algorithm
Quicksort is a highly efficient sorting algorithm that uses a divide-and-conquer approach. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
This is done by initializing two index variables, often named low and high, at the start and end of the array (excluding the pivot). Repeatedly move low and high closer together and swap elements if needed, so that elements lower than the pivot end up on the left and elements higher than the pivot end up on the right.
public class QuickSort {
public static void quickSort(int[] arr, int begin, int end) {
if (begin < end) {
int partitionIndex = partition(arr, begin, end);
quickSort(arr, begin, partitionIndex - 1); // Sort left subarray
quickSort(arr, partitionIndex + 1, end); // Sort right subarray
}
}
private static int partition(int[] arr, int begin, int end) {
int pivot = arr[end];
int i = (begin - 1);
for (int j = begin; j < end; j++) {
if (arr[j] <= pivot) {
i++;
int swapTemp = arr[i];
arr[i] = arr[j];
arr[j] = swapTemp;
}
}
int swapTemp = arr[i + 1];
arr[i + 1] = arr[end];
arr[end] = swapTemp;
return i + 1;
}
public static void main(String[] args) {
int[] array = { 9, -3, 5, 2, 6, 8, -6, 1, 3 };
quickSort(array, 0, array.length - 1);
System.out.println("Sorted array: " + Arrays.toString(array));
}
}Time Complexity:
- Average and Best Case: O(n log n)
- Worst Case: O(n²), which occurs when the smallest or largest element is always chosen as the pivot. However, this is rare in practice, especially with a good choice of pivot.
Space Complexity: O(log n) due to recursion. Quicksort is an in-place sort (it doesn’t require extra space).
Quicksort is often faster in practice than other O(n log n) algorithms like mergesort or heapsort.
3. The first non-repeated character in a string
To find the first non-repeated character in a string, we can use a two-pass approach. In the first pass, we count the frequency of each character, and in the second pass, we identify the first character that has a frequency of one.
import java.util.HashMap;
public class FirstNonRepeatedCharacter {
public static char findFirstNonRepeatedChar(String str) {
HashMap<Character, Integer> charCountMap = new HashMap<>();
// First pass: build the character count map
for (char c : str.toCharArray()) {
charCountMap.put(c, charCountMap.getOrDefault(c, 0) + 1);
}
// Second pass: find the first non-repeating character
for (char c : str.toCharArray()) {
if (charCountMap.get(c) == 1) {
return c;
}
}
// Return a default value if no non-repeating character is found
return Character.MIN_VALUE; // Or you can throw an exception if needed
}
public static void main(String[] args) {
String str = "aabbcddeff";
char result = findFirstNonRepeatedChar(str);
if (result != Character.MIN_VALUE) {
System.out.println("The first non-repeated character is: " + result);
} else {
System.out.println("There are no non-repeated characters in the string.");
}
}
}This program will return the first character in the string str that does not repeat. If there are no non-repeating characters, it returns a default value, which in this case is Character.MIN_VALUE.
Time Complexity: O(n), where n is the length of the string. The algorithm iterates over the string twice: once to build the frequency map and once to find the non-repeated character.
Space Complexity: O(min(n, k)), where k is the number of distinct characters in the string. The space complexity is due to the additional HashMap used to store character frequencies. In the worst-case scenario (all characters are unique), the space complexity can be O(n).
Part three coming soon…
Stay tuned and thank you for reading this article!
For more articles like this, 👉 Subscribe.
I also wrote these interesting articles here:
Applying S-O-L-I-D Principles to Flutter Development
Clean Code Principles — A Guidelines To Writing Better, Greener Code
Code Less Create More How Declarative Programming Paradigm Shapes Modern Mobile Development
Extracting Dominant Image Colors In Flutter
Exploring Android Framework and Flutter Framework-Similarities and Differences
