Arrays, Strings and Hashing Interview Questions for Data Structures and Algorithms

Show answer

A static array has a fixed size set at creation, such as int[] in Java, and offers O(1) index access with contiguous memory. A dynamic array such as Java ArrayList or Python list grows automatically by allocating a larger block and copying elements, giving amortised O(1) append. Both have O(n) insertion or deletion in the middle because elements must shift. Dynamic arrays trade a little memory for flexibility.

What is the two pointer technique and when is it used?

Show answer

Two pointers move through an array or string, often from both ends or at different speeds, to avoid nested loops. On a sorted array you can find a pair with a given sum in O(n) by moving left or right depending on the current sum. It is also used for reversing, removing duplicates in place, merging sorted arrays, palindrome checks and partitioning. It usually needs sorted data or a monotonic condition.

Strings are immutable in Java and Python. How does that affect algorithm complexity?

Show answer

Every modification creates a new string, so building a string by concatenation inside a loop can copy characters repeatedly and become O(n squared). Use StringBuilder in Java or collect parts in a list and call join in Python, which is O(n) overall. Immutability also makes strings safe as hash map keys and lets runtimes cache their hash codes, which is why they are good dictionary keys.

What is the difference between a subarray, a subsequence and a substring?

Show answer

A subarray is a contiguous part of an array, and an array of n elements has n times n plus 1 over 2 of them. A substring is the same idea for strings. A subsequence keeps the original order but may skip elements, so there are 2 to the power n of them. This matters for choosing techniques: sliding window and prefix sums suit subarrays, while subsequence problems often need dynamic programming.

How would you check whether two strings are anagrams, and what changes if input can contain any Unicode characters?

Show answer

For lowercase English letters, compare character counts using an array of 26 integers in O(n) time and O(1) space; sorting both strings also works in O(n log n). With arbitrary Unicode, use a hash map of counts instead of a fixed array. I would also clarify whether case and spaces matter and whether to normalise accented characters, since visually identical text can have different code point sequences.

Solve two sum: return the indices of two numbers that add up to the target.

Show answer

def two_sum(nums, target): seen = {} # value -> index for i, x in enumerate(nums): need = target - x if need in seen: return [seen[need], i] seen[x] = i return [] # two_sum([2, 7, 11, 15], 9) -> [0, 1] # O(n) time, O(n) space; sorting + two pointers gives O(1) space but loses indices

Implement Kadane's algorithm for the maximum subarray sum.

Show answer

def max_subarray(nums): best = current = nums[0] for x in nums[1:]: current = max(x, current + x) # extend or start fresh best = max(best, current) return best # max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) -> 6 (subarray 4, -1, 2, 1)

Check whether a string is a palindrome, ignoring case and non-alphanumeric characters.

Show answer

// Java static boolean isPalindrome(String s) { int i = 0, j = s.length() - 1; while (i < j) { char a = s.charAt(i), b = s.charAt(j); if (!Character.isLetterOrDigit(a)) { i++; continue; } if (!Character.isLetterOrDigit(b)) { j--; continue; } if (Character.toLowerCase(a) != Character.toLowerCase(b)) return false; i++; j--; } return true; } // Two pointers, O(n) time, O(1) space.

Describe a time you got stuck during a coding interview or contest. How did you recover?

Show answer

Situation: in an online round I could not find an efficient approach for a subarray problem. Task: still score well under time pressure. Action: I first submitted a correct brute-force solution for partial marks, then wrote out small examples and noticed the prefix sums pattern, which led to an O(n) solution with a hash map. Result: I solved it with ten minutes left and learned to secure a working solution before optimising.

Explain the sliding window technique with fixed and variable windows.

Show answer

A sliding window keeps a contiguous range and updates its result incrementally instead of recomputing. A fixed window of size k, such as the maximum sum of k consecutive elements, adds the new element and removes the old one each step in O(n). A variable window grows the right end and shrinks the left end while a condition is violated, as in the longest substring without repeating characters. Both turn O(n squared) into O(n).

What are prefix sums and what problems do they solve?

Show answer

A prefix sum array stores pre[i] as the sum of the first i elements, built in O(n). The sum of any range from l to r is then pre[r+1] minus pre[l] in O(1). Combined with a hash map of prefix sums, it counts subarrays with sum k in O(n). 2D prefix sums answer rectangle sum queries on grids, and difference arrays apply many range updates efficiently.

How does a hash table work, and how are collisions handled?

Show answer

A hash table computes a hash of the key and maps it to a bucket index, giving average O(1) insert, lookup and delete. A collision happens when two keys map to the same bucket. Separate chaining stores a list or tree in each bucket, which Java HashMap uses and converts to a tree after 8 entries. Open addressing probes other slots, which Python dict uses. Tables resize when the load factor grows too high.

What is Kadane's algorithm?

Show answer

Kadane's algorithm finds the maximum sum contiguous subarray in O(n) time and O(1) space. At each element it decides whether to extend the current subarray or start fresh: current = max(x, current + x), and best = max(best, current). The insight is that a negative running sum never helps a future subarray. For an all-negative array it correctly returns the largest single element when initialised with the first value.

What is the load factor of a hash table and why does it matter?

Show answer

Load factor is the number of stored entries divided by the number of buckets. As it rises, collisions increase and operations slow down. Java HashMap resizes when the load factor passes 0.75, doubling buckets and rehashing every entry, which costs O(n) occasionally but keeps operations O(1) amortised. If you know the final size, set the initial capacity to avoid repeated resizing in performance-sensitive code.

What is the Dutch National Flag algorithm?

Show answer

It sorts an array of three distinct values, such as 0, 1 and 2, in one pass with O(1) space. It keeps three pointers: low, mid and high. If arr[mid] is 0, swap it with arr[low] and advance both; if 1, advance mid; if 2, swap it with arr[high] and decrease high without advancing mid. It runs in O(n) and is the basis of three-way partitioning in quicksort.

An array of size 100000 must answer 100000 queries asking for the sum between two indices. What approach would you use?

Show answer

Recomputing each sum is O(n) per query, about 10 to the power 10 operations in total, which is too slow. Since the array does not change, I would build a prefix sum array once in O(n) and answer each query in O(1) as pre[r+1] minus pre[l], giving O(n plus q) overall. If the array also receives updates, I would switch to a Fenwick tree or segment tree for O(log n) updates and queries.

Your brute-force solution for the longest substring without repeating characters is O(n cubed). How would you improve it?

Show answer

I would use a variable sliding window. Keep a map from character to its last index and a left pointer. Move the right pointer through the string; when the current character was seen at an index at or after left, move left to that index plus one. Update the best length at each step. Each character is processed a constant number of times, giving O(n) time and O(alphabet size) space.

You must merge two sorted arrays where the first array has enough empty space at the end for the second. How would you do it in place?

Show answer

Merging from the front would overwrite unread elements, so merge from the back. Use three pointers: the last real element of the first array, the last element of the second, and the last slot of the first array. Repeatedly place the larger of the two candidates at the write position and move pointers left. When the second array is exhausted, the rest is already in place. This takes O(m plus n) time and O(1) space.

Find the length of the longest substring without repeating characters.

Show answer

def length_of_longest_substring(s): last = {} # char -> last index seen left = best = 0 for right, ch in enumerate(s): if ch in last and last[ch] >= left: left = last[ch] + 1 last[ch] = right best = max(best, right - left + 1) return best # 'abcabcbb' -> 3, 'bbbbb' -> 1, 'pwwkew' -> 3; O(n) time

Rotate an array to the right by k steps in place.

Show answer

def rotate(nums, k): n = len(nums) k %= n def reverse(l, r): while l < r: nums[l], nums[r] = nums[r], nums[l] l += 1 r -= 1 reverse(0, n - 1) # reverse all reverse(0, k - 1) # reverse first k reverse(k, n - 1) # reverse the rest # [1,2,3,4,5,6,7], k=3 -> [5,6,7,1,2,3,4]; O(n) time, O(1) space

Tell me about a time you used the right data structure to solve a real problem in a project or job.

Show answer

Situation: in my internship, a duplicate-detection script for customer records took hours because it compared every pair. Task: make it run within the nightly window. Action: I normalised names and phone numbers into a key and grouped records in a hash map, comparing only records within the same group. Result: runtime dropped from four hours to six minutes, and my mentor asked me to present the approach to the team.

How do the KMP and Rabin-Karp string matching algorithms work?

Show answer

Naive matching is O(n times m). KMP precomputes a longest prefix-suffix array for the pattern, so after a mismatch it shifts the pattern without re-reading text characters, giving O(n plus m) worst case. Rabin-Karp computes a rolling hash of each text window and compares characters only when hashes match, averaging O(n plus m) and extending well to multiple patterns, but collisions can make the worst case O(n times m).

You have a 100 GB file of integers and only 4 GB of RAM. How would you find the duplicates?

Show answer

The data does not fit in memory, so I would partition it. Read the file in streaming fashion and write each number to one of, say, 50 bucket files based on hash of the number modulo 50, so equal numbers land in the same bucket. Each bucket of about 2 GB fits in memory, where a hash set finds duplicates. Alternatively use external merge sort and scan adjacent values. A Bloom filter can pre-screen candidates.

A hash map lookup in your service suddenly becomes very slow under certain traffic. What could cause it?

Show answer

If many keys produce the same hash, they pile into a few buckets and operations degrade toward O(n). This can come from a poor custom hashCode, such as returning a constant or using only one field, or from attackers sending crafted keys. Fixes include a better hash function combining all fields, randomised hashing, which Python uses for strings, and tree-based buckets as in Java 8 HashMap, which caps the worst case at O(log n).

Return an array where each element is the product of all other elements, without using division.