Q1: MaxHeap Insert (Heapify Result)

The array [15, 1, 13, 2, 6, 3, 19] is being sorted using heapsort. The max-heapify operation has just completed. What does the array look like now?

• [19, 13, 15, 2, 6, 1, 3]
• [19, 13, 15, 2, 3, 6, 1]
• [19, 6, 15, 1, 2, 3, 13]
• [19, 6, 15, 2, 1, 3, 13]

Explanation: Sift down from the root after replacing it with the largest leaf — the heap property settles to a left-biased layout where the second level is (13, 15) and the leaves preserve insertion order.

Q2: Topological Sort

Which of the following is/are valid topological orders for the graph below?

Edges: 2 → 8, 8 → 7, 8 → 4, 7 → 4, 4 → 9, 5 → 9.

• 245789
• 578249
• 527849
• 257849

Explanation: Any valid order must place 2 before 8, 8 before 7 and 4, 7 before 4, 4 and 5 before 9. 527849 and 257849 are both consistent with those constraints; the other two violate at least one edge.

Q3: Undirected Graph with n − 1 Edges

Given an undirected graph with n nodes and n − 1 edges. Which statement is correct?

• The shortest path between any two pairs of nodes will always be unique.
• There exists a connected component which is a tree.
• Both A and B
• None of the above

Explanation: n − 1 edges does not force connectivity (you can have a cycle plus an isolated node), so the graph isn't necessarily a single tree. But by pigeonhole / acyclic-component counting, at least one connected component is acyclic — i.e. a tree.

Q4: Time Complexity of Recursive Merge

What is the worst-case time complexity of the routine below (merge runs in O(n))?

def func1(arr, start, end):
    ans = 0
    if end > start:
        mid = (start + end) // 2
        ans += func1(arr, start, mid)
        ans += func1(arr, mid + 1, end)
        ans += merge(arr, start, mid, end)  # O(n)
    return ans

• O(n)
• O(log n)
• O(n²)
• O(n log n)

Explanation: This is the merge-sort recurrence T(n) = 2T(n/2) + O(n) → O(n log n) by the Master Theorem.

Implement a function to identify a user's location region based on their IP address.

IPv4 addresses are represented by four octets in the format "a.b.c.d" (e.g., "120.10.20.30"). These IPv4 addresses are classified into 5 different regions based on the first octet's value:

• 1: 0.0.0.0 – 127.255.255.255
• 2: 128.0.0.0 – 191.255.255.255
• 3: 192.0.0.0 – 223.255.255.255
• 4: 224.0.0.0 – 239.255.255.255
• 5: 240.0.0.0 – 255.255.255.255

Given a list of ip_addresses representing the validity of each address and classify it into one of the 5 regions. Return an array of integers representing the region index for each corresponding IP address. Invalid IP addresses should be represented as -1.

An IPv4 address is valid if:

• It contains exactly four octets separated by periods.
• Each octet is an integer between 0 and 255, inclusive.
• There are no leading zeros in any octet.

解法

每个 IP 按 . 切：4 段；每段纯数字；除单独的 "0" 外无前导零；值在 [0, 255]。再按首段所在范围映射到区域 1-5。单 IP O(n)。

def getRegions(ips):
    def region(ip):
        parts = ip.split('.')
        if len(parts) != 4: return -1
        for p in parts:
            if not p.isdigit(): return -1
            if len(p) > 1 and p[0] == '0': return -1
            v = int(p)
            if v < 0 or v > 255: return -1
        first = int(parts[0])
        if first <= 127: return 1
        if first <= 191: return 2
        if first <= 223: return 3
        if first <= 239: return 4
        return 5
    return [region(ip) for ip in ips]

class Solution {
    static int regionOf(String ip) {
        String[] parts = ip.split("\\.");
        if (parts.length != 4) return -1;
        int first = 0;
        for (int idx = 0; idx < 4; idx++) {
            String p = parts[idx];
            if (p.isEmpty() || (p.length() > 1 && p.charAt(0) == '0')) return -1;
            for (char c : p.toCharArray()) if (!Character.isDigit(c)) return -1;
            int v;
            try { v = Integer.parseInt(p); } catch (Exception e) { return -1; }
            if (v < 0 || v > 255) return -1;
            if (idx == 0) first = v;
        }
        if (first <= 127) return 1;
        if (first <= 191) return 2;
        if (first <= 223) return 3;
        if (first <= 239) return 4;
        return 5;
    }
    static int[] getRegions(String[] ips) {
        int[] out = new int[ips.length];
        for (int i = 0; i < ips.length; i++) out[i] = regionOf(ips[i]);
        return out;
    }
}

int regionOf(const string& ip) {
 vector<string> parts;
 string cur;
 for (char c : ip) {
 if (c == '.') { parts.push_back(cur); cur.clear(); }
 else cur += c;
 }
 parts.push_back(cur);
 if (parts.size() != 4) return -1;
 int first = 0;
 for (int idx = 0; idx < 4; ++idx) {
 auto& p = parts[idx];
 if (p.empty() || (p.size() > 1 && p[0] == '0')) return -1;
 for (char c : p) if (!isdigit(c)) return -1;
 int v = stoi(p);
 if (v < 0 || v > 255) return -1;
 if (idx == 0) first = v;
 }
 if (first <= 127) return 1;
 if (first <= 191) return 2;
 if (first <= 223) return 3;
 if (first <= 239) return 4;
 return 5;
}

vector<int> getRegions(vector<string>& ips) {
 vector<int> out;
 for (auto& ip : ips) out.push_back(regionOf(ip));
 return out;
}

Given start_year and end_year, return names of all series that started in start_year or earlier and ended in end_year or earlier. If end_year == -1, the show must still be in production. Return list sorted alphabetically.

解法

分页拉 API；每个剧用正则从 runtime_of_series 抽 4 位年份。结尾的 - 后无年份表示仍在播。end_year == -1 时只保留在播剧，否则要求有限的结束年 ≤ end_year。复杂度 O(total_records)。

import requests, re

def showsInProduction(start_year, end_year):
    matched = []
    page = 1
    while True:
        r = requests.get(f'https://jsonmock.hackerrank.com/api/tvseries?page={page}').json()
        for show in r['data']:
            runtime = show['runtime_of_series']
            years = re.findall(r'\d{4}', runtime)
            if not years: continue
            sy = int(years[0])
            ey = int(years[1]) if len(years) > 1 else None
            still_running = ey is None and '-' in runtime
            if sy > start_year: continue
            if end_year == -1:
                if not still_running: continue
            else:
                if still_running: continue
                if ey is None or ey > end_year: continue
            matched.append(show['name'])
        if page >= r['total_pages']: break
        page += 1
    return sorted(matched)

A network security administrator has identified a rogue signal originating from coordinates (xl, yl) that illuminates nodes within a radius R. The network is represented as a rectangular grid with bottom-left (x1, y1) and top-right (x2, y2). A point (x, y) is fully illuminated if its distance from the beacon's center ≤ R.

Determine how many grid nodes are completely illuminated.

There are n processes to be executed, and the ith process has a size of processSize[i], where 1 ≤ i ≤ n. Also, there are m processors of different size capacity. The capacity of the ith processor is capacity[i] ( 1 ≤ i ≤ m ). A processor can process a task of size less than or equal to its capacity in 1 second, but it cannot execute processes whose size is greater than its capacity. A processor can execute multiple processes one after the other, but needs to pause for 1 second after completing its current one. Multiple processors can work on different processes simultaneously. Find the minimum time to execute all the processes or return -1 if there is no way to execute all the processes. Function Description Complete the function findMinimumTime in the editor. findMinimumTime has the following parameters:

• 1. int[] processSize: an array of integers representing the sizes of processes
• 2. int[] capacity: an array of integers representing the capacities of processors Returns int: the minimum time to execute all the processes or -1 if it is not possible

Example 1

Input:

processSize = [2, 5, 3]
capacity = [6, 2, 4]

Output:

1

Explanation: The optimal way to assign processes is to give:

• The first processor the second process
• The second processor the first process
• The third processor the third process All of them complete their processes in 1 second. Therefore, the minimum time required is 1 second.

Example 2

Input:

processSize = [1, 2, 3, 4, 6]
capacity = [4, 1, 4]

Output:

3

Explanation: Assign the second and third process to the first processor. It completes the first process in 1 second, then pauses for another second before completing the third process in 1 second This test case was added on 2025-03-23.

Example 3

Input:

processSize = [2, 5, 8]
capacity = [6, 7, 4]

Output:

-1

Explanation: No processor has the required capacity to process the third process (size = 8), so there is no way to process them all. This test case was added on 2025-03-23.

A server network is represented as a tree of g_nodes servers indexed from 1 to g_nodes and g_nodes - 1 edges where the ith edges connect the servers g_from[i] and g_to[i]. The transfer time between any two connected servers is 1 unit. Given the graph g, find the maximum time taken to transfer the data between any two servers in the system. Function Description Complete the function maximumTimeRequiredToTransferData in the editor. maximumTimeRequiredToTransferData has the following parameters:

• int g_nodes: the number of servers
• int[] g_from: an array of integers representing the starting server of each edge
• int[] g_to: an array of integers representing the ending server of each edge Returns int: the maximum time required to transfer data between any two servers

Example 1

Input:

g_nodes = 3
g_from = [1, 2]
g_to = [2, 3]

Output:

2

Explanation: The maximum time required to transfer data from 1 to 3 that takes 2 units of time. Hence, the answer is 2.

Example 2

Input:

g_nodes = 5
g_from = [1, 1, 1, 5]
g_to = [5, 3, 2, 4]

Output:

3

Explanation: :)

Example 3

Input:

g_nodes = 7
g_from = [4, 4, 2, 1, 2]
g_to = [2, 7, 5, 6, 3]

Output:

4

Explanation: Then sample output in the source is indeed 4..it's just been cut out in the ss..