Katkat
Back

Solve classic array, graph, and parsing problems

TeslaSoftware Engineer · HR Screen
MediumSoftware EngineerHR ScreenCoding & Algorithms

Last updated

This multi-part question evaluates algorithmic problem-solving and data-structure competency, covering expression parsing, array and sequence manipulation, sorting-based counting, interval merging, graph traversal/union-find, in-place rearrangement, hashing for set operations, and DAG/topological ordering within the Coding & Algorithms domain.

Implement and analyze solutions to the following independent tasks:

  1. Expression evaluator: Given a string s of digits, '+', '-', '*', '/', and spaces representing a non-negative integer expression with no parentheses, return its integer value. Division truncates toward zero. Aim for O(n) time using a single pass and O( 1)–O(n) extra space.
  2. Count triangle triplets: Given an array of positive integers, count triplets (i<j<k) that can form a non-degenerate triangle. Target O(n^
  3. after sorting.
  4. Merge ranges: Given a list of closed intervals [l, r], merge all intervals that overlap or touch and return the merged, sorted list.
  5. Count land clusters: Given an m×n grid of '1' (land) and '0' (water), count the number of 4-directionally connected land clusters. Use DFS, BFS, or Union-Find.
  6. Smallest missing positive: Given an unsorted integer array, return the smallest missing positive integer in O(n) time and O(
  7. extra space by rearranging in place.
  8. Maximum subarray sum: Given an integer array, return the maximum possible sum of a non-empty contiguous subarray. Also return the subarray boundaries if asked.
  9. Single-transaction stock profit: Given daily prices, compute the maximum profit from one buy and one sell (buy before sell). Return 0 if no profit is possible.
  10. Longest consecutive run: Given an unsorted array of integers, return the length of the longest sequence of consecutive integers. Achieve average O(n) time using hashing.
  11. Course completion feasibility: Given numCourses and prerequisite pairs (a, b) meaning b must precede a, determine whether all courses can be finished. If feasible, return any valid ordering. Handle up to 1e5 nodes and edges efficiently.