Pinterest

Implement a MedianFinder class for streaming integers.

Class Methods:

MedianFinder()      // Initialize
addNum(int num)     // Add number
findMedian()        // Get current median

Examples:

1. Add 2, 3: findMedian() → 2.5

2. Add 1, 3: findMedian() → 1.0 findMedian() → 2.0

Implement binary search for prefix matching in sorted string array.

Function:

findFirstWithPrefix(arr: string[], prefix: string): number

Examples:

1. arr = ["ab", "app", "apple", "bbb"], prefix = "ap" Output: 1 (first match: "app")

2. arr = ["ab", "app", "apple", "bbb"], prefix = "aP" Output: -1 (case sensitive, no match)

Calculate maximum number of fully visible pins on screen.

Requirements:

• Two columns (L/R)
• Non-overlapping pins
• Screen length constraint

Example: Input:

• Pins: [(1,4,"L"), (2,3,"R"), (4,8,"R"), (6,9,"L")]
• Screen length: 5

Output: 2 (maximum visible pins)

Part 1: Count and Say Given a digit string s, implement countAndSay(s) by splitting into minimal substrings with unique digits.

Example 1:

Input: countAndSay('1')
Output: '11' (one '1')

Input: countAndSay("3322251")
Output: "23321511" (two '3's, three '2's, one '5', one '1')

Part 2: Reverse Count and Say Implement reverse_count_and_say(s) to find all possible strings that would generate s as their count-and-say sequence.

Example:

Input: reverse_count_and_say('123')
Output: ['23', '333333333333']
Explanation:
- countAndSay('23') = '123' (one '2', one '3')
- countAndSay('333333333333') = '123' (twelve '3's)

Design a system to track store capacity and reservations. Return available capacity for each time interval.

Input Parameters:

• Store hours (open/close time)
• Total capacity
• List of existing reservations

Example 1:

Store Hours: 8 AM - 9 PM
Capacity: 5
Reservations: [{
  start: "9:00 AM",
  end: "9:30 AM",
  size: 3
}]

Output:
8:00 AM - 9:00 AM: 5
9:00 AM - 9:30 AM: 2
9:30 AM - 9:00 PM: 5

Example 2:

Store Hours: 8 AM - 9 PM
Capacity: 5
Reservations: [
  {
    start: "9:00 AM",
    end: "9:30 AM",
    size: 3
  },
  {
    start: "9:15 AM",
    end: "9:45 AM",
    size: 2
  }
]

Output:
8:00 AM - 9:00 AM: 5
9:00 AM - 9:15 AM: 2
9:15 AM - 9:30 AM: 0
9:30 AM - 9:45 AM: 3
9:45 AM - 9:00 PM: 5

Requirements:

• Handle overlapping reservations
• Track capacity accurately
• Return all time intervals
• Support variable reservation sizes