UKG interview questions & answers

11 real UKG interview questions with full model answers — Coding. Drawn from the same verified bank ChannelPulse drills from (11 UKG questions in total).

CodingEasyUKGSoftware Engineer

1. Valid Word (LeetCode)

Model answer

The task

Decide whether a string is a valid word: it must have at least three characters, contain only English letters or digits, and include at least one vowel and one consonant.

Key idea

Scan the string once, rejecting any character that is not an ASCII letter or digit. During the scan, track whether a vowel and a consonant have appeared; digits satisfy neither condition.

Approach

  1. Return False if the string is shorter than three characters.
  2. Initialize flags for whether a vowel and a consonant have been seen.
  3. For each character, check that it is an ASCII letter or digit.
  4. For letters, update the appropriate flag, ignoring case.
  5. Return True only if both flags are set.
class Solution:
    def isValid(self, word: str) -> bool:
        if len(word) < 3:
            return False

        vowels = set("aeiou")
        has_vowel = False
        has_consonant = False

        for char in word:
            is_ascii_letter = (
                "a" <= char <= "z" or "A" <= char <= "Z"
            )
            is_ascii_digit = "0" <= char <= "9"

            if not is_ascii_letter and not is_ascii_digit:
                return False

            if is_ascii_letter:
                if char.lower() in vowels:
                    has_vowel = True
                else:
                    has_consonant = True

        return has_vowel and has_consonant

Complexity:

  • Time: O(n), where n is the length of the string.
  • Space: O(1), since the vowel set and tracking flags have fixed size.

Common follow-ups

  • How would you handle Unicode letters? Define the permitted character categories explicitly, then use Unicode-aware classification.
  • Can you stop early? Yes, once both letter types have appeared, any remaining characters need only be checked for validity.
  • What if the vowel set changes? Store the allowed vowels in a configurable set and use the same scan.
CodingEasyUKGSoftware Engineer

2. Two Sum (LeetCode)

Model answer

The task

Given a list of integers and a target, return the indices of two distinct elements whose values add up to the target. The usual version guarantees a valid pair.

Key idea

As we scan the list, store each value’s index in a hash table. For the current value, check whether its needed complement has already appeared; this finds a pair in one pass.

Approach

  1. Create a dictionary mapping previously seen values to their indices.
  2. For each element, compute the complement needed to reach the target.
  3. If that complement is in the dictionary, return its stored index and the current index.
  4. Otherwise, store the current value and index, then continue.
from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Map each value already visited to its index.
        seen = {}

        for index, value in enumerate(nums):
            complement = target - value

            # A match must come from an earlier, distinct element.
            if complement in seen:
                return [seen[complement], index]

            seen[value] = index

        # The standard problem guarantees a solution.
        raise ValueError("No two elements sum to the target")

Complexity:

  • Time: O(n), where n is the number of elements; each lookup and insertion is O(1) on average.
  • Space: O(n), for the dictionary of values seen so far.

Common follow-ups

  • What if there may be multiple valid pairs? Return the first pair found, or keep searching and collect pairs according to the required output rules.
  • What if the input is sorted? Use two pointers from opposite ends for O(1) extra space; preserve original indices if those are required.
  • What if values repeat? The dictionary stores indices, and checking before insertion ensures the current element is not paired with itself.
CodingEasyUKGSoftware Engineer

3. Valid Palindrome (LeetCode)

Model answer

The task

Determine whether a string reads the same forward and backward after disregarding characters that are not letters or digits and treating uppercase and lowercase as equivalent.

Key idea

Compare characters from both ends, skipping anything that should be ignored. If every remaining pair matches, the string is a palindrome.

Approach

  1. Initialize pointers at the start and end of the string.
  2. Move the left pointer past non-alphanumeric characters.
  3. Move the right pointer past non-alphanumeric characters.
  4. Compare the lowercase forms of the characters at the pointers; return False if they differ.
  5. Move both pointers inward and continue. If they meet or cross, return True.
class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left < right:
            # Ignore characters that are not letters or digits.
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1

            # Compare without regard to letter case.
            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

Complexity:

  • Time: O(n), where n is the string length; each pointer moves only inward.
  • Space: O(1), since the comparisons use no additional data structure.

Common follow-ups

  • What if the input contains no letters or digits? It is considered a palindrome, since there are no mismatching characters.
  • Can you avoid creating a normalized copy of the string? Yes; the two-pointer scan uses constant extra space.
  • How would you handle Unicode normalization? Normalize the string first if canonically equivalent characters should compare as equal; that may require additional space.
CodingMediumUKGSoftware Engineer

4. Maximum Area Rectangle With Point Constraints I (LeetCode)

Model answer

The task

Given points on a 2D plane, find the largest area of an axis-aligned rectangle whose four corners are points and whose interior and boundary contain no other points. Return -1 if no such rectangle exists.

Key idea

Try each pair of points as opposite corners. The other two corners are determined by their coordinates; if they exist, scan all points to check that no non-corner lies inside or on the rectangle.

Approach

  1. Store all point coordinates in a set for quick corner lookups.
  2. Enumerate pairs with distinct x- and y-coordinates as candidate opposite corners.
  3. Check whether the two implied corners are also in the set.
  4. Scan the points and reject the candidate if any non-corner lies in the rectangle’s closed bounds.
  5. Track the largest valid area, or return -1 if none is found.
from typing import List

class Solution:
    def maxRectangleArea(self, points: List[List[int]]) -> int:
        point_set = {tuple(point) for point in points}
        best = -1

        # Choose two points as opposite corners.
        for i in range(len(points)):
            x1, y1 = points[i]

            for j in range(i + 1, len(points)):
                x2, y2 = points[j]

                if x1 == x2 or y1 == y2:
                    continue

                corners = {
                    (x1, y1),
                    (x2, y2),
                    (x1, y2),
                    (x2, y1),
                }

                if not corners.issubset(point_set):
                    continue

                min_x, max_x = sorted((x1, x2))
                min_y, max_y = sorted((y1, y2))

                # Any non-corner on or within the boundary invalidates it.
                valid = True
                for x, y in points:
                    if (x, y) in corners:
                        continue
                    if min_x <= x <= max_x and min_y <= y <= max_y:
                        valid = False
                        break

                if valid:
                    area = (max_x - min_x) * (max_y - min_y)
                    best = max(best, area)

        return best

Complexity:

  • Time: O(n³), for O(n²) candidate pairs and an O(n) validation scan.
  • Space: O(n), for the coordinate set.

Common follow-ups

  • How could this handle many more points? Use spatial indexing or range-query structures to speed up checking points inside candidate rectangles.
  • What if rectangles need not be axis-aligned? Candidate corners and validation would need to account for rotated geometry.
  • What if only interior points are forbidden? Change the validation bounds to strict inequalities, while handling edge points separately.
CodingMediumUKGSoftware Engineer

5. Count the Number of Good Subsequences (LeetCode)

Model answer

The task

Count the non-empty subsequences in a lowercase string for which every character that appears does so the same positive number of times. Different choices of positions count as different subsequences.

Key idea

Fix the common count k. For each distinct character, either omit it or choose exactly k of its positions. Multiply those choices across characters, then subtract one to exclude the choice that omits every character.

Approach

  1. Count each character’s frequency.
  2. Precompute factorials and inverse factorials to evaluate combinations modulo 10⁹ + 7.
  3. Try every k from 1 through the largest frequency.
  4. For each k, multiply 1 + C(freq, k) for every character with frequency at least k.
  5. Add the product minus one to the answer.
from collections import Counter

class Solution:
    def countGoodSubsequences(self, s: str) -> int:
        mod = 10**9 + 7
        freq = Counter(s)
        n = len(s)

        # Factorials support constant-time combination queries.
        fact = [1] * (n + 1)
        for i in range(1, n + 1):
            fact[i] = fact[i - 1] * i % mod

        inv_fact = [1] * (n + 1)
        inv_fact[n] = pow(fact[n], mod - 2, mod)
        for i in range(n, 0, -1):
            inv_fact[i - 1] = inv_fact[i] * i % mod

        def choose(a: int, b: int) -> int:
            return fact[a] * inv_fact[b] % mod * inv_fact[a - b] % mod

        answer = 0
        for k in range(1, max(freq.values(), default=0) + 1):
            ways = 1
            for count in freq.values():
                if count >= k:
                    # This character is absent, or appears exactly k times.
                    ways = ways * (1 + choose(count, k)) % mod

            # Exclude the subsequence containing no characters.
            answer = (answer + ways - 1) % mod

        return answer

Complexity:

  • Time: O(n + σF), where F is the largest frequency and σ is the number of distinct characters.
  • Space: O(n + σ) for factorial tables and frequencies.

Common follow-ups

  • What if subsequences are counted by distinct resulting strings? The counting method must account for duplicate strings formed from different position choices.
  • Can this be optimized for a large alphabet? Group characters by frequency so each frequency’s contribution can be exponentiated.
  • Why subtract one for each k? It removes the single choice that omits every character, which is not a non-empty subsequence.
CodingMediumUKGSoftware Engineer

6. Minimum Length of Anagram Concatenation (LeetCode)

Model answer

The task

Find the shortest block length such that the string can be split into equal-sized blocks, and every block has the same character frequencies.

Key idea

A valid block length must divide the string length. For each possible divisor, compare every block’s character counts with the first block’s; the first length that passes is the minimum.

Approach

  1. Try block lengths in increasing order.
  2. Skip lengths that do not divide the string length.
  3. Count the characters in the first block.
  4. Compare each remaining block’s character counts with that count.
  5. Return the first valid length.
from collections import Counter

class Solution:
    def minAnagramLength(self, s: str) -> int:
        n = len(s)

        # Increasing order ensures the first valid length is minimal.
        for length in range(1, n + 1):
            if n % length != 0:
                continue

            target_counts = Counter(s[:length])
            valid = True

            for start in range(length, n, length):
                if Counter(s[start:start + length]) != target_counts:
                    valid = False
                    break

            if valid:
                return length

        # The full string is always a valid single block.
        return n

Complexity:

  • Time: O(n · τ(n)), where τ(n) is the number of divisors of n; each candidate checks all characters.
  • Space: O(n) for temporary block slices and character counts.

Common follow-ups

  • How could this be faster for a fixed alphabet? Use a fixed-size frequency array instead of Counter.
  • Can non-divisor lengths be valid? No; equal-sized blocks must divide the total string length.
  • Can the method return a shortest representative block too? Yes; return the first block along with its length when a candidate passes.
CodingMediumUKGSoftware Engineer

7. Maximize Greatness of an Array (LeetCode)

Model answer

The task

Reorder the array to maximize how many positions contain a value greater than the value at the same position in the original array. Return that maximum count.

Key idea

Sort the values and greedily pair each value being compared with the smallest unused value that is strictly larger. Choosing the smallest such value preserves larger values for comparisons that need them.

Approach

  1. Sort the array.
  2. Scan its values in ascending order as comparison targets.
  3. Keep a pointer to the smallest candidate not yet used.
  4. When that candidate is greater than the current target, count a successful pairing and advance the candidate pointer.
  5. Return the number of successful pairings.
from typing import List

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        values = sorted(nums)
        candidate = 0
        greatness = 0

        for target in values:
            # Use the smallest available value that beats this target.
            if values[candidate] > target:
                greatness += 1
                candidate += 1

        return greatness

Complexity:

  • Time: O(n log n), due to sorting.
  • Space: O(n), for the sorted copy.

Common follow-ups

  • Why does the greedy choice work? Pairing with the smallest available value that wins avoids wasting a larger value that could win against a harder target.
  • How are duplicates handled? The comparison is strict, so equal values are never counted as a successful pairing.
  • Can extra space be reduced? Sorting nums in place avoids the separate sorted copy, though it modifies the input.
  • What if the array is empty? The loop makes no pairings, so the result is 0.
CodingMediumUKGSoftware Engineer

8. Make a Positive Array (LeetCode)

Model answer

The task

The title and tags suggest that positivity is defined using array prefix sums. They don’t specify the allowed operation or what must be minimized, so the exact transformation problem can’t be determined reliably.

Key idea

A prefix scan is the basic tool: maintain the running sum and check whether it satisfies the required positivity condition. A greedy transformation strategy depends on the missing operation and objective.

Approach

  1. Scan the array from left to right.
  2. Add each value to a running sum.
  3. Check whether every nonempty prefix sum is strictly positive.
  4. Use this as a validity check; the permitted operation is needed to derive a transformation algorithm.
def has_positive_prefix_sums(nums):
    """Check whether every nonempty prefix has a positive sum."""
    prefix_sum = 0

    for value in nums:
        prefix_sum += value
        if prefix_sum <= 0:
            return False

    return True

Complexity:

  • Time: O(n), one pass through the array.
  • Space: O(1), using a running sum.

Common follow-ups

  • Should prefix sums be strictly positive or nonnegative? This changes the check from <= 0 to < 0.
  • What operation is allowed to modify the array? The greedy strategy depends on whether values can be flipped, incremented, or removed.
  • Is the goal to minimize operations or total adjustment? Specify the objective to choose the right optimization.
  • Must the final array itself be strictly positive element by element? That is different from requiring positive prefix sums.
CodingHardUKGSoftware Engineer

9. Special Binary String (LeetCode)

Model answer

The task

Rearrange the special binary string by swapping adjacent special substrings to obtain the lexicographically largest possible string. A special string has balanced counts of 1s and 0s, with no prefix containing more 0s than 1s.

Key idea

A special string splits into top-level pieces, each shaped like 1 + interior + 0. Recursively maximize each interior, then sort the resulting pieces in descending lexicographic order; placing the largest piece first gives the largest result.

Approach

  1. Scan the string while tracking the balance: add one for 1, subtract one for 0.
  2. Whenever the balance returns to zero, a complete top-level piece has been found.
  3. Recursively process the substring inside that piece’s outer 1 and 0.
  4. Collect the rebuilt pieces, sort them in descending order, and concatenate them.
class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        def maximize(text: str) -> str:
            pieces = []
            start = 0
            balance = 0

            for i, bit in enumerate(text):
                balance += 1 if bit == "1" else -1

                # The current prefix is a complete special substring.
                if balance == 0:
                    interior = maximize(text[start + 1:i])
                    pieces.append("1" + interior + "0")
                    start = i + 1

            # Larger special pieces must come first.
            pieces.sort(reverse=True)
            return "".join(pieces)

        return maximize(s)

Complexity:

  • Time: O(n² log n) in the worst case, accounting for recursive string construction and sorting.
  • Space: O(n²) in the worst case for intermediate strings; recursion uses up to O(n) stack space.

Common follow-ups

  • Why sort in descending lexicographic order? The top-level pieces are interchangeable, and putting the largest piece first maximizes the concatenation.
  • Can the sorting be done by length instead? No; lexicographic order, not length, determines which piece should come first.
  • What changes for a different ordering goal? Keep the same decomposition and recursion, but order the rebuilt pieces according to the desired comparison rule.
CodingHardUKGSoftware Engineer

10. Split Array Largest Sum (LeetCode)

Model answer

The task

Divide an array into exactly m nonempty contiguous parts. Minimize the largest sum among those parts.

Key idea

For a candidate maximum sum limit, greedily pack each part as full as possible without exceeding it. This gives the fewest parts needed; the limit works if that count is at most m.

Feasibility is monotonic: if a limit works, every larger limit works too. Binary search between the largest element and the total sum.

Approach

  1. Set the search bounds to max(nums) and sum(nums).
  2. For each midpoint, scan the array and start a new part whenever adding the next value would exceed the midpoint.
  3. If the greedy scan needs at most m parts, lower the upper bound; otherwise raise the lower bound.
  4. Return the smallest feasible limit.
class Solution:
    def splitArray(self, nums: list[int], m: int) -> int:
        def parts_needed(limit: int) -> int:
            parts = 1
            current_sum = 0

            for value in nums:
                if current_sum + value > limit:
                    parts += 1
                    current_sum = 0
                current_sum += value

            return parts

        low = max(nums)
        high = sum(nums)

        while low < high:
            mid = (low + high) // 2

            if parts_needed(mid) <= m:
                high = mid
            else:
                low = mid + 1

        return low

Complexity:

  • Time: O(n log(sum(nums) - max(nums) + 1)); each feasibility check scans the array.
  • Space: O(1); the scan uses only a few variables.

Common follow-ups

  • Why does “at most m parts” suffice when exactly m are required? With nonnegative values, a part can be split without increasing its sum, until there are exactly m nonempty parts.
  • What changes if values can be negative? The greedy feasibility check and its monotonic reasoning no longer apply; a dynamic programming approach may be needed.
  • Can the actual partition be returned? Yes. Record where the greedy scan starts new parts, then split additional parts as needed to reach exactly m.
CodingHardUKGSoftware Engineer

11. Maximum Area Rectangle With Point Constraints II (LeetCode)

Model answer

The task

Find the largest area of an axis-aligned rectangle whose four corners are given points, with no other point inside or on its boundary. Return -1 if no such rectangle exists.

Key idea

At either vertical side, the rectangle’s bottom and top points must be adjacent in that side’s sorted list of y-coordinates; otherwise another point lies on the side. For a repeated adjacent pair, a range-maximum query over the y-interval checks whether any point appeared between the two x-coordinates.

Approach

  1. Sort points by x, then group points that share an x-coordinate.
  2. Compress all y-coordinates and use a segment tree to track the latest x-coordinate seen at each y.
  3. For each x-group, examine every pair of consecutive y-values.
  4. If the pair occurred at an earlier x, query the maximum latest x over the inclusive y-interval. The rectangle is clear when that maximum equals the earlier x.
  5. Update the best area, then record the current x for each y in the group.
from typing import List

class SegmentTree:
    """Supports point updates and range-maximum queries."""

    def __init__(self, n: int) -> None:
        size = 1
        while size < n:
            size *= 2
        self.size = size
        self.tree = [-1] * (2 * size)

    def update(self, index: int, value: int) -> None:
        pos = index + self.size
        self.tree[pos] = value
        pos //= 2

        while pos:
            self.tree[pos] = max(self.tree[2 * pos], self.tree[2 * pos + 1])
            pos //= 2

    def query(self, left: int, right: int) -> int:
        """Return the maximum on the half-open interval [left, right)."""
        left += self.size
        right += self.size
        result = -1

        while left < right:
            if left & 1:
                result = max(result, self.tree[left])
                left += 1
            if right & 1:
                right -= 1
                result = max(result, self.tree[right])
            left //= 2
            right //= 2

        return result

class Solution:
    def maxRectangleArea(self, points: List[List[int]]) -> int:
        points.sort()
        ys = sorted({y for _, y in points})
        y_index = {y: i for i, y in enumerate(ys)}
        latest_x = SegmentTree(len(ys))

        # Maps an adjacent pair of y-values to its most recent x-coordinate.
        last_pair_x = {}
        best_area = -1

        i = 0
        while i < len(points):
            x = points[i][0]
            group_ys = []

            while i < len(points) and points[i][0] == x:
                group_ys.append(points[i][1])
                i += 1

            # Check consecutive points on this vertical side.
            for bottom, top in zip(group_ys, group_ys[1:]):
                pair = (bottom, top)

                if pair in last_pair_x:
                    left_x = last_pair_x[pair]
                    low = y_index[bottom]
                    high = y_index[top]

                    # Before processing this x-group, the maximum must be
                    # the left side's x: no intervening point lies in range.
                    if latest_x.query(low, high + 1) == left_x:
                        area = (x - left_x) * (top - bottom)
                        best_area = max(best_area, area)

                last_pair_x[pair] = x

            # Add this x-group after checking, so its points are not treated
            # as points strictly between the rectangle's vertical sides.
            for y in group_ys:
                latest_x.update(y_index[y], x)

        return best_area

Complexity:

  • Time: O(n log n) for sorting and segment-tree operations.
  • Space: O(n) for coordinate compression, the tree, and pair records.

Common follow-ups

  • What if points on the rectangle’s boundary are allowed? Adjust the side-adjacency and range checks to match which boundary points are permitted.
  • Can the segment tree be replaced? A range-maximum structure is needed; a standard Fenwick tree does not directly support arbitrary range maxima.
  • What if coordinates are very large or negative? Coordinate compression handles them without changing the algorithm.

Practice these out loud, don't memorise them

Reading an answer is not the same as being able to give one under pressure. ChannelPulse plays the interviewer, asks the follow-ups, and scores each answer with feedback and a model answer so you can hear the gap between what you said and what lands.

Get ChannelPulse Browse all questions