KLA Corporation interview prep
10 practice questions on the topics candidates reported from KLA Corporation interviews, with answers. The questions are ours; each one links to the interview report that names its topic.
DSA 8
-
In this grid, 1 is land joined up, down, left and right. What is the area of the largest island?
1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 0 0 1- 4
- 5
- 6
- 3
Show the answer
B. 5
The top-left block has 4 cells; the right-hand group has the cells at (1,3), (1,4), (2,3), (2,4) and (3,4): 5. The lone 1 at the bottom has area 1. A DFS from each unvisited land cell counts the size as it goes.
This topic is named in a candidate’s interview report: Internship online assessment, 2021, on LeetCode.
-
How can you tell in O(n) time and O(1) space whether an array has indices i < j < k with a[i] < a[j] < a[k]?
- Sort the array and look at three neighbours
- Scan once, keeping the smallest value seen (first) and the smallest value that has something smaller before it (second); any element larger than second completes a triplet
- Check every triple of indices
- Use a hash set of all values
Show the answer
B. Scan once, keeping the smallest value seen (first) and the smallest value that has something smaller before it (second); any element larger than second completes a triplet
If x <= first, update first; else if x <= second, update second; else a triplet exists. first may later move past second, but second always proves some smaller value came before it.
This topic is named in a candidate’s interview report: Internship online assessment, 2021, on LeetCode.
-
A disjoint set union uses union by rank and path compression. What is the cost per operation?
- O(n) per operation
- O(log n) exactly
- Amortised O(alpha(n)), the inverse Ackermann function, which is at most 4 for any realistic n
- O(1) in the worst case for every single call
Show the answer
C. Amortised O(alpha(n)), the inverse Ackermann function, which is at most 4 for any realistic n
Path compression points nodes straight at their root as find walks up; union by rank keeps trees shallow. Together any sequence of m operations costs O(m alpha(n)), effectively linear.
This topic is named in a candidate’s interview report: Software engineer interview, Chennai, 2024, on LeetCode.
-
In [10, 20, 7] you may, 4 times, replace any element x with floor(x / 2). Always halving the current largest, what is the smallest sum you reach?
- 17
- 15
- 13
- 12
Show the answer
C. 13
20 becomes 10, then a 10 becomes 5, the other 10 becomes 5, and 7 becomes 3: 5 + 5 + 3 = 13. Halving the largest removes the most each time, and a max-heap finds it in O(log n), so k operations cost O(k log n).
This topic is named in a candidate’s interview report: Software engineer 2 interview, 2021, on LeetCode.
-
Stalls stand at positions 1, 2, 4, 8 and 9. Placing 3 cows, what is the largest possible minimum distance between any two of them?
- 2
- 1
- 4
- 3
Show the answer
D. 3
Binary search on the answer d: a greedy pass places a cow in the first stall and then in each stall at least d past the last cow. d = 3 fits (1, 4, 8); d = 4 places only two (1, 8). Feasibility is O(n), so the whole search is O(n log range) after sorting.
This topic is named in a candidate’s interview report: Software engineer 2 interview, 2021, on LeetCode.
-
A keyboard has four keys: A (types one A), Ctrl-A (select all), Ctrl-C (copy) and Ctrl-V (paste, appending the copied text). With 7 key presses, what is the most A's you can produce?
- 7
- 9
- 8
- 10
Show the answer
B. 9
Type A three times, then Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V: 3 + 3 + 3 = 9. In DP terms, best[n] is the larger of best[n-1] + 1 and best[j] * (n - j - 1) over a select-copy at j. Seven plain A's give only 7.
This topic is named in a candidate’s interview report: Software engineer 2 interview, 2021, on LeetCode.
-
An R x C matrix has every row sorted. You merge it into one sorted array with a min-heap that holds the next unread element of each row. What does that cost?
- O(R * C)
- O(R * C * log R)
- O(R * C * log(R * C))
- O(R + C)
Show the answer
B. O(R * C * log R)
Every one of the R * C elements is pushed and popped once, and the heap never holds more than R items, so each operation is O(log R). Sorting everything from scratch would be O(RC log RC). Columns being sorted too does not help this merge.
This topic is named in a candidate’s interview report: Software engineer 2 interview, 2021, on LeetCode.
-
Two keys hash to the same bucket of a hash table. Which is a standard way to handle it?
- Reject the second key
- Separate chaining (each bucket holds a list of entries) or open addressing (probe for another free slot)
- Overwrite the first key
- Double the size of every key
Show the answer
B. Separate chaining (each bucket holds a list of entries) or open addressing (probe for another free slot)
Collisions cannot be avoided, only made rare: a good hash spreads keys evenly, and resizing when the load factor passes a threshold (0.75 in Java's HashMap) keeps lookups near O(1). Java's HashMap chains, and turns a long chain into a balanced tree.
This topic is named in a candidate’s interview report: Software engineer 2 interview, 2021, on LeetCode.
C and C++ 1
-
How do lookups in std::map and std::unordered_map compare?
- map is O(1) and unordered_map is O(log n)
- Both are hash tables, O(1)
- map is a balanced tree, O(log n) and kept in key order; unordered_map is a hash table, O(1) on average
- Both are O(n), because they scan their keys
Show the answer
C. map is a balanced tree, O(log n) and kept in key order; unordered_map is a hash table, O(1) on average
std::map is usually a red-black tree, so lookups are O(log n) and iteration is in sorted order. std::unordered_map hashes the key, O(1) on average and O(n) in the worst case, with no useful order.
This topic is named in a candidate’s interview report: Software engineer 2 interview, 2021, on LeetCode.
Software engineering 1
-
In Kafka, how do several consumers share the work of one topic?
- Each message is copied to every consumer in the group
- The topic is split into partitions; within a consumer group each partition is read by exactly one consumer, so more partitions allow more parallel consumers
- Consumers take turns reading the whole topic
- Kafka allows only one consumer per topic
Show the answer
B. The topic is split into partitions; within a consumer group each partition is read by exactly one consumer, so more partitions allow more parallel consumers
Messages keep their order within a partition, and consumers record their offsets as they go. A different consumer group gets its own full copy of the stream.
This topic is named in a candidate’s interview report: Software engineer interview, Chennai, 2024, on LeetCode.