Solve four OA string/array/matrix/graph tasks
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Take-home Project
Quick Answer: This multi-part prompt evaluates proficiency in core programming competencies: string parsing and character classification, simulation/greedy processing of linear movement and arrays, matrix manipulation including row/column operations and rotations, and undirected graph path reconstruction.
Part 1: Absolute Difference Between Uppercase and Lowercase Counts
Constraints
- 0 <= len(s) <= 10^5
- s may contain any ASCII characters
- Only characters in 'A'..'Z' and 'a'..'z' should be counted
Examples
Input: ("",)
Expected Output: 0
Explanation: Empty string: both counts are 0.
Input: ("aA",)
Expected Output: 0
Explanation: One uppercase and one lowercase letter.
Input: ("Hello, WORLD!",)
Expected Output: 2
Explanation: Uppercase = 6 (H, WORLD), lowercase = 4 (ello), so answer is 2.
Input: ("1234!?",)
Expected Output: 0
Explanation: There are no letters.
Input: ("z",)
Expected Output: 1
Explanation: Uppercase = 0, lowercase = 1.
Hints
- Scan the string once and maintain two counters.
- Compare each character directly against the uppercase and lowercase ASCII ranges.
Part 2: Scooter-Walking Trip Total Ridden Distance
Constraints
- 1 <= target <= 10^9
- 0 <= len(scooters) <= 2 * 10^5
- 0 <= scooters[i] <= 10^9
- Scooter positions may be unsorted and may contain duplicates
Examples
Input: (25, [5, 15])
Expected Output: 20
Explanation: Ride from 5 to 15 (10 units), then from 15 to 25 (10 units).
Input: (23, [12, 2, 20])
Expected Output: 20
Explanation: Walk to 2, ride to 12; ride from 12 to 22; then walk the last 1 unit.
Input: (8, [0, 3, 20])
Expected Output: 8
Explanation: A scooter is available at position 0, so you can ride directly to target.
Input: (10, [])
Expected Output: 0
Explanation: No scooters exist, so the whole trip is walking.
Input: (10, [10])
Expected Output: 0
Explanation: You walk to position 10 and have already reached target, so the ridden distance is 0.
Hints
- Since your position only moves forward, sorting the scooter positions is very helpful.
- After sorting, use a pointer to find the first scooter that is not behind your current position.
Part 3: Apply Sequential Operations to a Matrix
Constraints
- 1 <= number of rows, number of columns <= 200
- 0 <= len(operations) <= 1000
- All indices in operations are valid at the moment the operation is applied
- Matrix values are integers
Examples
Input: ([[1, 2], [3, 4]], [['SWAP_ROW', 0, 1], ['SWAP_COL', 0, 1]])
Expected Output: [[4, 3], [2, 1]]
Explanation: First swap the rows, then swap the two columns.
Input: ([[1, 2, 3], [4, 5, 6]], [['REVERSE_ROW', 1], ['REVERSE_COL', 0]])
Expected Output: [[6, 2, 3], [1, 5, 4]]
Explanation: Row 1 becomes [6,5,4], then column 0 is reversed.
Input: ([[1, 2, 3], [4, 5, 6]], [['ROTATE_CW']])
Expected Output: [[4, 1], [5, 2], [6, 3]]
Explanation: The 2x3 matrix becomes a 3x2 matrix after rotation.
Input: ([[1, 2], [3, 4], [5, 6]], [['ROTATE_CW'], ['SWAP_ROW', 0, 1], ['SWAP_COL', 0, 1]])
Expected Output: [[4, 6, 2], [3, 5, 1]]
Explanation: This checks that later row and column indices are interpreted after rotation.
Input: ([[7]], [['ROTATE_CW'], ['REVERSE_ROW', 0], ['REVERSE_COL', 0]])
Expected Output: [[7]]
Explanation: A 1x1 matrix stays unchanged under all valid operations.
Hints
- Most operations can be simulated directly on the matrix.
- A 90-degree clockwise rotation can be built by reversing the row order and then transposing.
Part 4: Reconstruct a Travel Path from Unordered Adjacent Photos
Constraints
- 2 <= n <= 2 * 10^5, where n is the number of locations in the path
- len(photos) = n - 1
- Each photo is a pair of integers [a, b]
- The graph formed by the pairs is guaranteed to be a simple path
Examples
Input: ([[1, 2], [3, 2], [4, 3]],)
Expected Output: [1, 2, 3, 4]
Explanation: The path is 1-2-3-4, and 1 is the smaller endpoint.
Input: ([[5, 4], [2, 3], [4, 3]],)
Expected Output: [2, 3, 4, 5]
Explanation: The same path can be read in reverse, but we start from the smaller endpoint 2.
Input: ([[-1, 0], [1, 0], [1, 2]],)
Expected Output: [-1, 0, 1, 2]
Explanation: The path uses negative and positive labels.
Input: ([[10, 20]],)
Expected Output: [10, 20]
Explanation: With one photo, the path contains exactly two locations.
Input: ([[7, 8], [5, 6], [6, 7]],)
Expected Output: [5, 6, 7, 8]
Explanation: The photos are unordered, but the underlying graph is still a simple path.
Hints
- In a path graph, the two endpoints are exactly the nodes with degree 1.
- Once you start from an endpoint, keep moving to the neighbor that is not the previous node.