Solve common search/parse/graph frequency tasks
Overview
This multi-part question evaluates algorithmic problem-solving skills across searching and sorting variants, rotated-array search, nested string decoding, graph connectivity, and frequency analysis, testing familiarity with binary-search techniques, pivoted-array search logic, stack/recursion-based parsing, graph traversal/union-find concepts, and counting/top-k strategies in the Coding & Algorithms domain. It is commonly asked in technical interviews because it probes time and space complexity reasoning and implementation efficiency, emphasizing practical application of conceptual algorithmic understanding rather than purely theoretical knowledge.
You are given several independent coding tasks. For each task, write a function that returns the required output.
1) Find insertion index in a sorted array
Input: a non-decreasing integer array nums and an integer target.
Output: the smallest index i such that inserting target at index i keeps nums sorted. If target already exists, return the index of the first occurrence where it could be placed.
Constraints (typical): 1 ≤ len(nums) ≤ 1e5.
2) Search in a rotated sorted array
A strictly increasing array was rotated at an unknown pivot (e.g., [4,5,6,7,0,1,2]).
Input: integer array nums (no duplicates) and integer target.
Output: the index of target in nums, or -1 if not found.
Constraints (typical): 1 ≤ len(nums) ≤ 1e5.
3) Decode an encoded string
An encoded string follows the pattern k[encoded_string] where k is a positive integer indicating repetition count. Encodings may be nested.
Examples:
-
"3[a]2[bc]" → "aaabcbc" -
"3[a2[c]]" → "accaccacc"
Input: string s containing digits, letters, and brackets [].
Output: the decoded string.
Constraints (typical): length of s up to 1e5 (decoded output may be larger).
4) Count connected components from an adjacency matrix
You are given an n x n adjacency matrix M for an undirected graph with n nodes, where M[i][j] = 1 means an edge exists between i and j (and M[i][i] = 1).
Input: M.
Output: the number of connected components in the graph.
Constraints (typical): 1 ≤ n ≤ 2000.
5) Return the k most frequent elements
Input: integer array nums and integer k.
Output: any ordering of the k elements with highest frequency in nums.
Constraints (typical): 1 ≤ len(nums) ≤ 1e5, 1 ≤ k ≤ (# of distinct elements).
Notes: Discuss time/space complexity tradeoffs. For problems (1) and (2), aim for O(log n) time. For (4) and (5), aim for near-linear time in input size when feasible.