Activity 7
Q1 Given a string, find the first non-repeating character and return it. If all characters repeat, return None.
Input: "aabbcddce"
Output: "e"
Q2 Given an array of integers, find the length of the longest increasing subsequence. A subsequence is a sequence
derived from the array without changing the relative order of elements Time complexity O(nlog(n))
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Q3 Given an array, rotate it to the right by k steps, where k is a non-negative integer. You must do this in-place
without using extra space for another array.
Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: [5, 6, 7, 1, 2, 3, 4]
Q4 Given a string, find the length of the longest substring without repeating characters in O(n) time complexity
Input: "abcabcbb"
Output: 3
Hint: Each character is processed at most twice (once when expanding and once when shifting l).
Q5 You have a warehouse database storing item information:
The warehouse has a maximum weight capacity W. You need to maximize the total value stored in the warehouse,
considering the item quantities available.
Steps:
1. Fetch item details from the database.
2. Use a greedy approach to pick items with the highest value per weight first, without exceeding weight W.
3. Return the total value of the items that can be stored.
Input: W = 7
Output: Maximum value stored = 40
Q6 Given a string, find the minimum number of deletions required to make it a palindrome.
Input: "agbcba"
Output: 1
Concepts you should use:
● Dynamic Programming (LCS Variation): Compute the Longest Palindromic Subsequence (LPS) using LCS
of s and s[::-1].
● Greedy Strategy: The answer is len(s) - LPS(s).
● Time Complexity: O(n²) DP Table, O(n²) Space Optimization Possible
Q7 Given n items with weights and values, and a maximum weight W, find the maximum value that can be obtained.
Additionally, some items must be picked together (grouped constraints).
Input:
items = [(weight=2, value=4), (weight=3, value=5), (weight=1, value=3)]
groups = [{0, 2}] # If item 0 is picked, item 2 must also be picked
W=5
Output: 7
Concepts you should use:
● Standard 0/1 Knapsack DP: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] +
value[i]).
● Handling Groups:
○ Instead of iterating over individual items, iterate over groups of items.
○ If picking one item in a group, ensure all required items are also picked.
● Time Complexity: O(nW) DP, with additional O(n²) Group Constraints Handling.
Q8 Given an array and window size k, return the maximum in each sliding window.
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Concepts you should use:
● Naïve O(nk) Approach: Iterate over every window (brute force).
● Optimized O(n) Approach: Use a Deque (Doubly-ended queue).
○ Maintain a deque of indices where the front always has the largest element in the window.
○ Remove indices that go out of the window (i-k).
○ Only keep useful elements (remove smaller ones from the back).
● Time Complexity: O(n) using Deque, since each element is processed at most twice.
Q9 Given a weighted, directed graph, find the shortest path from a source node to all other nodes. However, each
edge weight can be dynamically updated based on previous decisions (similar to knapsack).
Input:
Graph:
0 → (1, 4), (2, 1)
1 → (3, 1)
2 → (1, 2), (3, 5)
3 → (4, 3)
Output: Shortest path from node 0 to all nodes
Concepts Used:
● Graph Traversal: Use Dijkstra’s Algorithm for shortest paths.
● Dynamic Weights: If an edge (u → v, w) is used, a greedy penalty may be applied (like Knapsack weight
update).
● DP Transition: Maintain a dp[node] array where dp[v] = min(dp[v], dp[u] + weight).
● Time Complexity: O((V+E) log V) using Priority Queue (Min-Heap).
Q 10 You are given a directed weighted graph representing a network of cities. Each city has:
1. Cost of Building a Hub (build_cost[i]) – If you establish a hub in a city, you must pay this cost.
2. Revenue (revenue[i]) – Each city generates a fixed revenue per unit time if a hub is established.
3. Roads (edges[i][j] = cost_ij) – A directed edge represents the cost to build a road from city i to j.
4. Dependency (dependency[i]) – A city i can only be activated if at least k other cities are already
activated.
Your goal is to maximize profit over T time units, where:
● Profit = (Sum of Revenue from active cities × T) - (Total Construction Cost of hubs and roads)
● A city must be connected to the central node (City 0) via roads to be considered "active."
● You must decide which cities to activate and which roads to build under the given constraints.
Constraints
● 1 ≤ N ≤ 10⁵ (100,000 Cities)
● 1 ≤ M ≤ 10⁵ (100,000 Roads)
● 1 ≤ T ≤ 10⁶ (1 Million Time Units)
● 0 ≤ build_cost[i] ≤ 10⁶
● 0 ≤ revenue[i] ≤ 10⁶
● 0 ≤ cost_ij ≤ 10⁶
● Each city must be connected to the central hub (City 0) before activation.
● Dependencies have an upper limit: dependency[i] ≤ 3 to prevent deep dependency chains.
Input:
N = 5, M = 6, T = 10
build_cost = [5, 10, 20, 15, 25]
revenue = [5, 8, 15, 10, 20]
edges = [
(0, 1, 3),
(1, 2, 5),
(1, 3, 2),
(2, 4, 7),
(3, 4, 4)
dependency = [0, 1, 2, 1, 1] # City 4 needs at least 1 city active
Output:
Maximum Profit: 65
Cities Activated: [0, 1, 3, 4]
