Amazon SDE Intern OA – Round 1 Questions (Need Approach Help)

Hi everyone,

I recently appeared for an Amazon SDE Intern Online Assessment and was able to solve the first question, but I got stuck on the second one.

---

Question 1: Feasible Indices After Prefix/Suffix Reduction

📄 Problem Statement

You are given an integer array arr of size n, where all elements are distinct.

You can perform the following operations any number of times:

1. Choose a non-empty prefix of the array and delete all elements except the minimum element of that prefix.
2. Choose a non-empty suffix of the array and delete all elements except the maximum element of that suffix.

After each operation, the remaining elements are concatenated to form a new array.

---

Task

An index i is called feasible if it is possible to reduce the array to a single element [arr[i]] using the above operations.

Return a binary string of length n where:

• 1 → feasible index
• 0 → not feasible

---

Constraints

• 1 ≤ n ≤ 2 × 10^5
• 1 ≤ arr[i] ≤ 10^6
• All elements are distinct

---

Example

Input:
arr = [1, 3, 2, 5, 4]

Output:
10011

---

🧠 Approach Idea (High-Level)

• Prefix operation → keeps minimum
• Suffix operation → keeps maximum
• So an element survives if:
  • It behaves like a prefix minimum, OR
  • It behaves like a suffix maximum

Efficient approach uses:

• Prefix minimum tracking
• Suffix maximum tracking

---

🤔 Need Approach Help

Question 2: Secure Maximum Deliveries

---

📄 Problem Statement

You are given:

• An array deliveryLogs of size n, where each value represents deliveries in a log
• An even integer k representing number of warehouses

---

📦 Storage Rules

1. Each warehouse stores deliveries from only one log
2. A log can be split across multiple warehouses
3. Deliveries from different logs cannot be mixed

After storing:

• The largest k/2 warehouses are compromised ❌
• The remaining k/2 warehouses are safe ✅

---

Task

Return the maximum number of deliveries that can be stored safely.

---

Constraints

• 1 ≤ n ≤ 1000
• 2 ≤ k ≤ 1000
• k is even
• 0 ≤ deliveryLogs[i] ≤ 1000

---

Example 1

Input:
deliveryLogs = [3, 5, 9, 6]
k = 4

Output:
9

---

Example 2

Input:
deliveryLogs = [6]
k = 2

Output:
3

It Feels Difficult

Looking For Guidance Could someone please guide me on: What is the correct intuition for this problem?

---

🚀 Interview Reflection

• Solving Q1 ✔️
• Struggling in Q2 ❗

---

**Good progress — Continue learnig... ** Thanks in advance!