Quick Overview

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.

Solve classic array, graph, and parsing problems

Company: Tesla

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: HR Screen

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^ 2) after sorting. 3) Merge ranges: Given a list of closed intervals [l, r], merge all intervals that overlap or touch and return the merged, sorted list. 4) 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. 5) Smallest missing positive: Given an unsorted integer array, return the smallest missing positive integer in O(n) time and O( 1) extra space by rearranging in place. 6) 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. 7) 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. 8) 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. 9) 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.

Quick Answer: 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.

Part 1: Expression Evaluator

Given a valid expression string s containing non-negative integers, spaces, and the operators +, -, *, and / with no parentheses, compute its integer value. Multiplication and division have higher precedence than addition and subtraction. Division must truncate toward zero.

Constraints

  • 1 <= len(s) <= 10^5
  • s contains digits, spaces, and the operators +, -, *, /
  • The expression is valid and all intermediate results fit in a signed 32-bit integer

Examples

Input: ('3+2*2',)

Expected Output: 7

Explanation: Multiplication happens before addition: 3 + (2 * 2) = 7.

Input: (' 3/2 ',)

Expected Output: 1

Explanation: 3 / 2 truncates toward zero, so the result is 1.

Hints

  1. When you reach a new operator, you have finished reading the previous number.
  2. Keep a running total for completed + and - terms, and a separate last term for * and / precedence.

Part 2: Count Triangle Triplets

Given an array of positive integers nums, count how many index triplets (i < j < k) can form a non-degenerate triangle. Three lengths a, b, c form a triangle if the sum of the two smaller sides is greater than the largest side.

Constraints

  • 0 <= len(nums) <= 2000
  • 1 <= nums[i] <= 10^4
  • An O(n^2) solution after sorting is expected

Examples

Input: ([2, 2, 3, 4],)

Expected Output: 3

Explanation: The valid index triplets are (0,1,2), (0,2,3), and (1,2,3).

Input: ([4, 2, 3, 4],)

Expected Output: 4

Explanation: After sorting to [2,3,4,4], the four valid triplets are formed by indices (0,1,2), (0,1,3), (0,2,3), and (1,2,3).

Hints

  1. After sorting, if nums[i] + nums[j] > nums[k], then every index from i to j - 1 paired with j will also work for that k.
  2. Try fixing the largest side first and use two pointers for the other two sides.

Part 3: Merge Ranges

Given a list of closed intervals [l, r], merge all intervals that overlap or touch at an endpoint, then return the merged intervals sorted by start value. For example, [1,4] and [4,5] should be merged into [1,5].

Constraints

  • 0 <= len(intervals) <= 10^5
  • -10^9 <= l <= r <= 10^9
  • Intervals are closed and merging should include endpoint touching

Examples

Input: ([[1,3],[2,6],[8,10],[15,18]],)

Expected Output: [[1,6],[8,10],[15,18]]

Explanation: [1,3] and [2,6] overlap, so they merge into [1,6]. The other intervals do not connect.

Input: ([[1,4],[4,5]],)

Expected Output: [[1,5]]

Explanation: These intervals touch at endpoint 4, so they must be merged.

Hints

  1. Sorting by interval start lets you process intervals from left to right.
  2. Compare each interval only with the last merged interval.

Part 4: Count Land Clusters

You are given an m x n grid of characters where '1' means land and '0' means water. Count how many land clusters exist, where cells are connected only in the 4 main directions: up, down, left, and right.

Constraints

  • 0 <= m, n <= 300
  • grid[r][c] is either '1' or '0'
  • An O(m * n) traversal is expected

Examples

Input: ([['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']],)

Expected Output: 3

Explanation: There are three separate groups of land: the top-left block, the single land cell in the middle, and the bottom-right pair.

Input: ([],)

Expected Output: 0

Explanation: An empty grid contains no land clusters.

Hints

  1. Every time you find an unvisited land cell, start a DFS or BFS and mark the whole component.
  2. Be careful not to count the same land cell more than once.

Part 5: Smallest Missing Positive

Given an unsorted integer array nums, return the smallest missing positive integer. Your algorithm should run in O(n) time and use O(1) extra space by rearranging elements in place.

Constraints

  • 0 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • A linear-time, constant-extra-space solution is expected

Examples

Input: ([1, 2, 0],)

Expected Output: 3

Explanation: The values 1 and 2 are present, so the smallest missing positive is 3.

Input: ([3, 4, -1, 1],)

Expected Output: 2

Explanation: After placing valid values in their correct indices, 1 is present but 2 is missing.

Hints

  1. If the array length is n, the answer must be in the range 1 to n + 1.
  2. Try placing each value x in index x - 1 whenever 1 <= x <= n.

Part 6: Maximum Subarray Sum

Given an integer array nums, find the maximum possible sum of a non-empty contiguous subarray. Return a tuple of the form (max_sum, start_index, end_index), where start_index and end_index are inclusive. If multiple optimal subarrays exist, return the one with the smallest start index; if still tied, the smallest end index.

Constraints

  • 1 <= len(nums) <= 2 * 10^5
  • -10^9 <= nums[i] <= 10^9
  • An O(n) solution is expected

Examples

Input: ([-2, 1, -3, 4, -1, 2, 1, -5, 4],)

Expected Output: (6, 3, 6)

Explanation: The best subarray is [4, -1, 2, 1] with sum 6.

Input: ([1],)

Expected Output: (1, 0, 0)

Explanation: Edge case: a single element must be the answer.

Hints

  1. For each position, decide whether it is better to extend the current subarray or start a new one there.
  2. Track the start index whenever you reset the running sum.

Part 7: Single-Transaction Stock Profit

Given a list prices where prices[i] is the stock price on day i, compute the maximum profit possible using at most one buy and one sell, with the buy occurring before the sell. Return 0 if no profit is possible.

Constraints

  • 0 <= len(prices) <= 2 * 10^5
  • 0 <= prices[i] <= 10^9
  • An O(n) one-pass solution is expected

Examples

Input: ([7,1,5,3,6,4],)

Expected Output: 5

Explanation: Buy at price 1 on day 1 and sell at price 6 on day 4 for a profit of 5.

Input: ([7,6,4,3,1],)

Expected Output: 0

Explanation: Prices only decrease, so no profitable transaction is possible.

Hints

  1. As you scan left to right, remember the lowest price seen so far.
  2. At each day, ask what profit you would make if you sold today.

Part 8: Longest Consecutive Run

Given an unsorted integer array nums, return the length of the longest sequence of consecutive integers. The algorithm should run in average O(n) time using hashing.

Constraints

  • 0 <= len(nums) <= 2 * 10^5
  • -10^9 <= nums[i] <= 10^9
  • An average O(n) solution is expected

Examples

Input: ([100, 4, 200, 1, 3, 2],)

Expected Output: 4

Explanation: The longest consecutive run is [1, 2, 3, 4], which has length 4.

Input: ([0, 3, 7, 2, 5, 8, 4, 6, 0, 1],)

Expected Output: 9

Explanation: The longest consecutive run is [0, 1, 2, 3, 4, 5, 6, 7, 8], which has length 9.

Hints

  1. A number starts a sequence only if the previous number is not present.
  2. Using a set lets you check whether neighbors exist in average O(1) time.

Part 9: Course Completion Feasibility

There are numCourses labeled from 0 to numCourses - 1 and a list of prerequisite pairs [a, b] meaning course b must be completed before course a. Determine whether all courses can be finished. Return a tuple (can_finish, order), where can_finish is a boolean and order is a valid course ordering if one exists, otherwise an empty list. To make results deterministic, return the lexicographically smallest valid order among currently available zero-indegree courses.

Constraints

  • 1 <= numCourses <= 10^5
  • 0 <= len(prerequisites) <= 10^5
  • 0 <= a, b < numCourses

Examples

Input: (2, [[1, 0]])

Expected Output: (True, [0, 1])

Explanation: Course 0 has no prerequisites, so take it first. Then course 1 becomes available.

Input: (4, [[1, 0], [2, 0], [3, 1], [3, 2]])

Expected Output: (True, [0, 1, 2, 3])

Explanation: After taking course 0, both 1 and 2 are available. Choose 1 first because it is smaller, then 2, then 3.

Hints

  1. Think of courses as a directed graph and prerequisites as edges.
  2. If you repeatedly remove zero-indegree nodes and cannot process all nodes, a cycle exists.

Loading coding console...