Katkat
Back

Implement array and tree traversal tasks

MicrosoftSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize an array-based trading algorithm using a greedy approach and your mastery of level-order tree traversal to extract a specific view of a binary tree.

Part 1: Maximum Profit

Given an array prices where prices[i] is the price of a given stock on the i-th day, design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times), but you must sell the stock before you buy again.

Example

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 3.
             Total profit = 4 + 3 = 7.

Part 2: Binary Tree Right Side View

Given the root of a binary tree, imagine yourself standing on the right side of the tree. Return the values of the nodes you can see ordered from top to bottom.

Example

Input: root = [1, 2, 3, null, 5, null, 4]
Output: [1, 3, 4]

Constraints

  • The number of nodes in the tree is in the range [0, 100].
  • The prices array length is in the range [1, 3 * 10^4].
  • Prices are integers between 0 and 10^4.

Interface

def maxProfit(prices: list[int]) -> int:
    pass

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rightSideView(root: TreeNode) -> list[int]:
    pass

Hints

Hint 1

For the stock problem, focus on accumulating every positive difference between consecutive days since you can trade as often as you like.

Hint 2

For the right-side view, consider using Breadth-First Search (BFS) to traverse level by level, capturing the last node in each level.

Hint 3

Alternatively, for the tree problem, a Depth-First Search (DFS) can work if you traverse the right child before the left and record only the first node visited at each depth level.

Follow-up questions

  • How would your stock profit solution change if there were a mandatory 'cooldown' period of one day after selling a stock?
  • Can you solve the tree right-side view problem using recursion instead of an explicit queue?
  • What are the space complexity implications if the binary tree is highly unbalanced (e.g., a linked list structure)?