Meta interview prep

DSAMedium

You merge n sorted arrays of k elements each into one sorted array, using a min-heap that holds the smallest unused element of each array. What is the time complexity?

1. O(nk log n)
2. O(nk log nk)
3. O(nk)
4. O(n^2 k)

This topic is named in a candidate’s interview report: New grad onsite, 2022, on LeetCode.

DSAMedium

The sorted array [4, 5, 6, 7, 0, 1, 2] has been rotated. A modified binary search looks for 0. Why can binary search still work, and how fast is it?

1. At every step at least one half of the range is sorted, which tells you which half can hold the target; O(log n)
2. You must scan for the rotation point, so it is O(n) at best
3. The array must be sorted again first, so it takes O(n log n)
4. It only works when the array has not been rotated

This topic is named in a candidate’s interview report: SDE on-campus interview, 2019, on Code360.

DSAMedium

Kadane's algorithm finds the maximum sum of a contiguous subarray. For [-2, 1, -3, 4, -1, 2, 1, -5, 4], what is that sum and which indices does it cover?

1. 6, indices 3 to 6
2. 7, indices 3 to 8
3. 5, indices 0 to 6
4. 4, index 3 only

This topic is named in a candidate’s interview report: Software engineer interview, 2018, on Code360.

DSAMedium

A disjoint set union uses union by rank and path compression. What is the cost per operation?

1. O(n) per operation
2. O(log n) exactly
3. Amortised O(alpha(n)), the inverse Ackermann function, which is at most 4 for any realistic n
4. O(1) in the worst case for every single call

This topic is named in a candidate’s interview report: SDE on-campus interview, 2021, on Code360.

DSAMedium

How do you find the first and last positions of a target in a sorted array with duplicates in O(log n)?

1. Binary search once, then walk left and right from the match
2. Two binary searches: one that keeps going left after a match (lower bound) and one that keeps going right (upper bound)
3. Scan the array from both ends
4. Hash every value to its positions

This topic is named in a candidate’s interview report: New grad onsite, 2022, on LeetCode.

DSAMedium

Buildings stand in a row with heights [4, 2, 3, 1], and the ocean is to the right. A building has a view if every building to its right is shorter. Which indices have a view?

1. [0, 2, 3]
2. [3]
3. [0, 1, 2, 3]
4. [0, 3]

This topic is named in a candidate’s interview report: New grad onsite, 2022, on LeetCode.

DSAMedium

What is the length of the longest strictly increasing subsequence of [10, 9, 2, 5, 3, 7, 101, 18]?

1. 3
2. 5
3. 4
4. 2

This topic is named in a candidate’s interview report: SDE on-campus interview, 2019, on Code360.

DSAEasy

You remove the 2nd node from the end of 1 -> 2 -> 3 -> 4 -> 5 in one pass with two pointers. What is the list after?

1. 1 -> 2 -> 3 -> 5
2. 1 -> 2 -> 4 -> 5
3. 1 -> 3 -> 4 -> 5
4. 1 -> 2 -> 3 -> 4

This topic is named in a candidate’s interview report: Business technology analyst interview, 2022, on Code360.

DSAMedium

Merging the overlapping intervals among [1, 3], [2, 6], [8, 10] and [15, 18] leaves how many intervals?

1. 4
2. 3
3. 2
4. 1

This topic is named in a candidate’s interview report: SDE on-campus interview, 2019, on Code360.

DSAMedium

Which pair of traversals pins down one binary tree when all keys are distinct?

1. Preorder and postorder
2. Inorder together with preorder (or with postorder)
3. Preorder alone
4. Level order alone

This topic is named in a candidate’s interview report: SDE on-campus interview, 2021, on Code360.

DSAMedium

In the grid below, 2 is a rotten orange, 1 a fresh one and 0 empty. Each minute, fresh oranges next to a rotten one (up, down, left, right) rot. How many minutes until none are fresh? Rows: [2, 1, 1], [1, 1, 0], [0, 1, 1].

1. 3
2. 4
3. 5
4. Never

This topic is named in a candidate’s interview report: Business technology analyst interview, 2022, on Code360.

PythonMedium

What does this print?

def ok(s, skip=True):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            if not skip:
                return False
            return ok(s[i + 1:j + 1], False) or ok(s[i:j], False)
        i, j = i + 1, j - 1
    return True

print(ok("abca"), ok("abc"))

1. True True
2. False False
3. False True
4. True False

This topic is named in a candidate’s interview report: New grad onsite, 2022, on LeetCode.