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.
245789578249527849257849
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 ansO(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)