How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Flexport.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Flexport during technical interviews.

Solve Two Robbery Optimization Variants | Flexport Coding Question

Q: Solve Two Robbery Optimization Variants

This question evaluates competence in dynamic programming for linear optimization and recursion/tree DP for hierarchical structures, as well as the ability to reason about the correctness of greedy heuristics.

Solve Two Robbery Optimization Variants

Company: Flexport

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are asked to solve two related optimization problems. ### Part 1: Linear street You are given an array `values`, where `values[i]` is the amount of money in the `i`-th house on a straight street. If you rob two adjacent houses, an alarm is triggered. Return the maximum amount of money you can rob. Implement: ```text maxLinearRobbery(values: int[]) -> int ``` Requirements: - `0 <= values.length <= 100000` - `0 <= values[i] <= 10^9` - The algorithm should run in `O(n)` time. - Be prepared to discuss whether a simple greedy strategy is correct. If you propose a greedy rule, justify it or provide a counterexample. Example: ```text values = [2, 7, 9, 3, 1] output = 12 ``` Explanation: Rob houses with values `2`, `9`, and `1`. ### Part 2: Tree-shaped neighborhood You are given the root of a binary tree. Each node represents a house and contains a non-negative amount of money. If you rob a node, you cannot rob either of its direct children. Return the maximum amount of money you can rob from the tree. Use the following node definition: ```text class TreeNode: value: int left: TreeNode | null right: TreeNode | null ``` Implement: ```text maxTreeRobbery(root: TreeNode | null) -> int ``` Requirements: - The tree may contain up to `100000` nodes. - `0 <= node.value <= 10^9` - The algorithm should visit each node a constant number of times. Example: ```text Input tree: 3 / \ 2 3 \ \ 3 1 output = 7 ``` Explanation: Rob the root with value `3`, the left-right grandchild with value `3`, and the right-right grandchild with value `1`.

Quick Answer: This question evaluates competence in dynamic programming for linear optimization and recursion/tree DP for hierarchical structures, as well as the ability to reason about the correctness of greedy heuristics.

Part 1: Linear Street Robbery Optimization

You are given a list values where values[i] is the amount of money in the i-th house on a straight street. You may rob any subset of houses, but you cannot rob two adjacent houses because that triggers an alarm. Return the maximum total amount of money you can rob.

Constraints

0 <= len(values) <= 100000
0 <= values[i] <= 10^9
The answer may exceed a 32-bit signed integer.
The algorithm should run in O(n) time.

Examples

Input: ([],)

Expected Output: 0

Explanation: There are no houses to rob.

Input: ([5],)

Expected Output: 5

Explanation: With one house, the best choice is to rob it.

Input: ([2, 7, 9, 3, 1],)

Expected Output: 12

Explanation: Rob houses with values 2, 9, and 1.

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

Expected Output: 4

Explanation: Rob the first and last houses. This is also a counterexample to some simple greedy pair strategies.

Input: ([1000000000, 0, 1000000000, 0, 1000000000],)

Expected Output: 3000000000

Explanation: Rob houses at indices 0, 2, and 4. The result exceeds 32-bit integer range.

Hints

For each house, consider two choices: rob it and combine with the best answer ending two houses earlier, or skip it and keep the previous best.
A simple local greedy rule can fail. For example, choosing the larger house from each adjacent pair does not always produce a globally optimal subset.

Part 2: Tree-Shaped Neighborhood Robbery Optimization

You are given a binary tree where each node represents a house containing a non-negative amount of money. If you rob a node, you cannot rob either of its direct children. Return the maximum amount of money you can rob from the tree. For this standalone problem, the tree is passed as a level-order list. The value -1 represents a missing child, and all real node values are non-negative.

Constraints

0 <= number of real tree nodes <= 100000
0 <= node value <= 10^9
-1 is reserved only as the missing-node sentinel and is never a real node value.
The serialized input is a valid level-order representation.
Each real node should be processed only a constant number of times.

Examples

Input: ([],)

Expected Output: 0

Explanation: An empty tree contains no money.

Input: ([10],)

Expected Output: 10

Explanation: With one node, robbing it is optimal.

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

Expected Output: 7

Explanation: Rob the root with value 3, the left-right grandchild with value 3, and the right-right grandchild with value 1.

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

Expected Output: 7

Explanation: This is a skewed tree. Rob the node with value 4 and the grandchild with value 3.

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

Expected Output: 32

Explanation: Rob the root and all four grandchildren for a total of 10 + 10 + 10 + 1 + 1 = 32.

Hints

For every node, compute two values: the best total if this node is robbed, and the best total if this node is skipped.
If a node is robbed, its children must be skipped. If a node is skipped, each child may independently be robbed or skipped.

Quick Overview

This question evaluates competence in dynamic programming for linear optimization and recursion/tree DP for hierarchical structures, as well as the ability to reason about the correctness of greedy heuristics.