PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick 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.

  • medium
  • PayPal
  • Coding & Algorithms
  • Software Engineer

Solve common search/parse/graph frequency tasks

Company: PayPal

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: 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.

Part 1: Find Insertion Index in a Sorted Array

Given a non-decreasing integer array nums and an integer target, return the smallest index i such that inserting target at index i keeps the array sorted. If target already appears multiple times, return the first position where it could be inserted.

Constraints

  • 1 <= len(nums) <= 100000
  • nums is sorted in non-decreasing order
  • -10^9 <= nums[i], target <= 10^9

Examples

Input: ([1, 3, 5, 6], 5)

Expected Output: 2

Explanation: Target already exists at index 2, and that is the first valid insertion position.

Input: ([1, 3, 5, 6], 2)

Expected Output: 1

Explanation: Inserting 2 at index 1 keeps the array sorted.

Input: ([1, 3, 5, 6], 7)

Expected Output: 4

Explanation: All elements are smaller than 7, so it goes at the end.

Input: ([1, 3, 3, 3, 5], 3)

Expected Output: 1

Explanation: The first valid position for 3 is before the existing 3s.

Input: ([10], 5)

Expected Output: 0

Explanation: Edge case: single-element array where target belongs before the only element.

Hints

  1. This is a classic lower-bound search: look for the first index where nums[i] is greater than or equal to target.
  2. A binary search over the index range [0, len(nums)] gives O(log n) time.

Part 2: Search in a Rotated Sorted Array

A strictly increasing array has been rotated at an unknown pivot. Given the rotated array nums with no duplicates and an integer target, return the index of target if it exists, otherwise return -1.

Constraints

  • 1 <= len(nums) <= 100000
  • All values in nums are distinct
  • -10^9 <= nums[i], target <= 10^9

Examples

Input: ([4, 5, 6, 7, 0, 1, 2], 0)

Expected Output: 4

Explanation: The target 0 appears at index 4.

Input: ([4, 5, 6, 7, 0, 1, 2], 3)

Expected Output: -1

Explanation: The target does not exist in the array.

Input: ([1], 0)

Expected Output: -1

Explanation: Edge case: single-element array where the target is absent.

Input: ([1], 1)

Expected Output: 0

Explanation: Edge case: single-element array where the target is present.

Input: ([6, 7, 1, 2, 3, 4, 5], 4)

Expected Output: 5

Explanation: The array is rotated, but 4 is still found by modified binary search.

Hints

  1. At every step of binary search, one half of the array is still normally sorted.
  2. Compare target against the sorted half to decide which side can be discarded.

Part 3: Decode an Encoded String

An encoded string uses the pattern k[encoded_string], where k is a positive integer telling how many times to repeat the substring inside brackets. Encodings can be nested. Decode and return the full string.

Constraints

  • 1 <= len(s) <= 100000
  • s contains digits, letters, '[' and ']'
  • The encoding is valid and brackets are balanced

Examples

Input: "3[a]2[bc]"

Expected Output: "aaabcbc"

Explanation: Repeat 'a' three times and 'bc' two times, then concatenate.

Input: "3[a2[c]]"

Expected Output: "accaccacc"

Explanation: The inner block '2[c]' becomes 'cc', so the outer block becomes 'acc' repeated 3 times.

Input: "2[abc]3[cd]ef"

Expected Output: "abcabccdcdcdef"

Explanation: Decode each block and keep the trailing letters 'ef'.

Input: "abc"

Expected Output: "abc"

Explanation: Edge case: no brackets, so the string stays the same.

Input: "10[a]"

Expected Output: "aaaaaaaaaa"

Explanation: Edge case for a multi-digit repeat count.

Hints

  1. A stack is useful when you enter and leave bracketed sections.
  2. Remember that repeat counts can have multiple digits, such as 10[a].

Part 4: Count Connected Components from an Adjacency Matrix

You are given an n x n adjacency matrix M for an undirected graph, where M[i][j] == 1 means there is an edge between node i and node j. Return the number of connected components in the graph.

Constraints

  • 1 <= n <= 2000, where n = len(M)
  • M is an n x n matrix
  • M[i][j] == M[j][i] for all valid i, j
  • M[i][i] == 1 for all valid i

Examples

Input: [[1, 1, 0], [1, 1, 0], [0, 0, 1]]

Expected Output: 2

Explanation: Nodes 0 and 1 form one component, and node 2 is alone.

Input: [[1, 0, 0], [0, 1, 0], [0, 0, 1]]

Expected Output: 3

Explanation: No off-diagonal edges exist, so every node is its own component.

Input: [[1, 1, 1], [1, 1, 1], [1, 1, 1]]

Expected Output: 1

Explanation: Every node is reachable from every other node.

Input: [[1]]

Expected Output: 1

Explanation: Edge case: a graph with one node has one connected component.

Hints

  1. Each unvisited node can start a BFS or DFS that marks an entire connected component.
  2. With an adjacency matrix, scanning neighbors of one node takes O(n), so O(n^2) is acceptable because the input itself has n^2 entries.

Part 5: Return the K Most Frequent Elements

Given an integer array nums and an integer k, return the k distinct elements with the highest frequencies. For this version, to make the output deterministic, return the result ordered by descending frequency; if two elements have the same frequency, place the smaller element first.

Constraints

  • 1 <= len(nums) <= 100000
  • 1 <= k <= number of distinct elements in nums
  • -10^9 <= nums[i] <= 10^9

Examples

Input: ([1, 1, 1, 2, 2, 3], 2)

Expected Output: [1, 2]

Explanation: 1 appears 3 times, 2 appears 2 times, and 3 appears once.

Input: ([4, 4, 4, 6, 6, 2, 2], 2)

Expected Output: [4, 2]

Explanation: 4 has frequency 3; 2 and 6 both have frequency 2, so 2 comes before 6 by tie-break rule.

Input: ([5], 1)

Expected Output: [5]

Explanation: Edge case: single-element array.

Input: ([1, 2, 3, 4], 2)

Expected Output: [1, 2]

Explanation: All numbers appear once, so the smallest values come first by tie-break rule.

Input: ([7, 7, 8, 8, 9, 9, 9], 1)

Expected Output: [9]

Explanation: 9 has the highest frequency.

Hints

  1. First count frequencies of all values, then group values by frequency.
  2. A bucket array indexed by frequency can avoid sorting all elements by count.
Last updated: Apr 21, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Minimize a String Using Allowed Swaps - PayPal (medium)
  • Compute variance of a list in Python - PayPal (easy)
  • Explain list vs tuple in Python - PayPal (easy)
  • Explain differences between Python list and tuple - PayPal (hard)
  • Compute Variance from a Python List - PayPal (hard)