Josh Technology Group interview questions & answers

20 real Josh Technology Group interview questions with full model answers — Coding. Drawn from the same verified bank ChannelPulse drills from (34 Josh Technology Group questions in total).

CodingEasyJosh Technology GroupSoftware Engineer

1. Island Perimeter (LeetCode)

Model answer

The task

Given a grid of land and water cells, calculate the total length of the land’s outer boundary. Each cell is square, and only sides next to water or outside the grid count.

Key idea

Start with four sides for every land cell. Subtract one for each side shared with another land cell; equivalently, count a side only when its neighbor is water or out of bounds.

Approach

  1. Record the grid’s row and column counts.
  2. Visit every cell.
  3. For each land cell, check its four neighboring positions.
  4. Add one to the perimeter for each neighbor that is outside the grid or water.
  5. Return the accumulated perimeter.
from typing import List

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        perimeter = 0

        # Each exposed side of a land cell contributes one unit.
        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 0:
                    continue

                for dr, dc in directions:
                    neighbor_row = row + dr
                    neighbor_col = col + dc

                    # An out-of-grid or water neighbor leaves this side exposed.
                    if (
                        neighbor_row < 0
                        or neighbor_row >= rows
                        or neighbor_col < 0
                        or neighbor_col >= cols
                        or grid[neighbor_row][neighbor_col] == 0
                    ):
                        perimeter += 1

        return perimeter

Complexity:

  • Time: O(RC), where R and C are the grid dimensions; each cell checks four neighbors.
  • Space: O(1), excluding the input grid; only a fixed number of variables are used.

Common follow-ups

  • Can you use DFS or BFS? Yes; traverse the island and count exposed sides for each visited land cell, though a full grid scan is simpler.
  • What if the grid has multiple islands? The same scan returns the sum of their perimeters.
  • How would you handle a very large grid that does not fit in memory? Process it in chunks while retaining boundary rows or columns needed to check neighbors.
CodingEasyJosh Technology GroupSoftware Engineer

2. Unique Email Addresses (LeetCode)

Model answer

The task

Given a list of email addresses, count how many are distinct after applying the address’s normalization rules. In the local part, ignore periods and discard a plus sign and everything after it; leave the domain unchanged.

Key idea

Normalize each address before comparing it. A hash set stores the normalized addresses, so duplicates are counted only once.

Approach

  1. Create an empty set for normalized addresses.
  2. For each address, split it into its local part and domain at @.
  3. In the local part, keep only the text before the first +, if present.
  4. Remove all periods from the remaining local part.
  5. Join the normalized local part with the original domain and add it to the set.
  6. Return the set’s size.
from typing import List

class Solution:
    def numUniqueEmails(self, emails: List[str]) -> int:
        normalized = set()

        for email in emails:
            local, domain = email.split("@", 1)

            # Ignore the plus sign and everything that follows it.
            local = local.split("+", 1)[0]

            # Periods do not affect the local part.
            local = local.replace(".", "")

            normalized.add(local + "@" + domain)

        return len(normalized)

Complexity:

  • Time: O(C), where C is the total number of characters across all addresses; each address is processed a constant number of times.
  • Space: O(U), where U is the total number of characters stored across the U distinct normalized addresses.

Common follow-ups

  • What if the rules differ by domain? Apply the appropriate normalization based on the parsed domain.
  • How would you handle very large input streams? Normalize each address as it arrives and maintain a set; memory is proportional to the number of unique addresses.
  • What if addresses may not contain @? Validate each address before splitting and decide how invalid inputs should be handled.
CodingEasyJosh Technology GroupSoftware Engineer

3. Merge Two Binary Trees (LeetCode)

Model answer

The task

Combine two binary trees by adding values where both trees have a node at the same position. Where only one tree has a node, keep that node and its subtree.

Key idea

Traverse both trees together. When both nodes exist, add the second node’s value to the first and merge their children recursively; when either node is missing, return the other subtree.

Approach

  1. If the first node is missing, return the second.
  2. If the second node is missing, return the first.
  3. Add the second node’s value to the first.
  4. Merge the corresponding left and right children.
  5. Return the first node as the merged root.
class Solution:
    def mergeTrees(self, root1, root2):
        # If one side is empty, reuse the other subtree.
        if root1 is None:
            return root2
        if root2 is None:
            return root1

        # Merge in place into the first tree.
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)

        return root1

Complexity:

  • Time: O(min(m, n)), where m and n are the numbers of nodes in the trees; only positions with nodes in both trees require merging.
  • Space: O(h) for recursive calls, where h is the height of the overlapping traversal.

Common follow-ups

  • Can the inputs be left unchanged? Build new nodes for overlapping positions instead of modifying the first tree.
  • Can this be done iteratively? Use a stack or queue of pairs of corresponding nodes.
  • What if values should be combined differently? Replace addition with the required operation while keeping the same traversal.
CodingEasyJosh Technology GroupSoftware Engineer

4. Merge Two Sorted Lists (LeetCode)

Model answer

The task

Given the heads of two sorted singly linked lists, combine their nodes into one sorted list. Return the head of the merged list.

Key idea

At each step, append the smaller of the two current nodes, then advance that list. A dummy node simplifies handling the merged list’s head.

Approach

  1. Create a dummy node and set a pointer to it.
  2. While both lists have nodes, compare their values.
  3. Link the smaller node after the pointer and advance its source list.
  4. Advance the pointer.
  5. Link any remaining nodes and return the node after the dummy.
# LeetCode provides the ListNode class.
class Solution:
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode(0)
        tail = dummy

        # Repeatedly attach the smaller current node.
        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next

            tail = tail.next

        # At most one list remains; it is already sorted.
        tail.next = list1 if list1 else list2
        return dummy.next

Complexity:

  • Time: O(m + n), where m and n are the lengths of the lists.
  • Space: O(1) extra space; the existing nodes are relinked.

Common follow-ups

  • How would you implement this recursively? Choose the smaller head and recursively merge the rest; this uses O(m + n) call-stack space.
  • What if the lists are sorted in descending order? Adjust the comparison or reverse the merged result, depending on the desired output order.
  • What if one list is empty? The remaining list is returned directly.
CodingEasyJosh Technology GroupSoftware Engineer

5. Move Zeroes (LeetCode)

Model answer

The task

Rearrange an integer array in place so all zeroes come after the nonzero values. Keep the nonzero values in their original relative order.

Key idea

Use a write pointer to mark where the next nonzero value belongs. Scan the array once, swapping each nonzero value into that position; this keeps the nonzero values stable and uses constant extra space.

Approach

  1. Set write to the first available position for a nonzero value.
  2. Scan each index from left to right.
  3. When a nonzero value is found, swap it with the value at write.
  4. Advance write after each nonzero value.
  5. Once the scan ends, all remaining positions contain zeroes.
from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        # The next nonzero value belongs at index write.
        write = 0

        for read in range(len(nums)):
            if nums[read] != 0:
                nums[write], nums[read] = nums[read], nums[write]
                write += 1

Complexity:

  • Time: O(n), where n is the array length; each value is examined once.
  • Space: O(1), since rearrangement is done in place.

Common follow-ups

  • What if relative order does not matter? Partitioning zeroes and nonzeroes can be done with two pointers, potentially with fewer assignments.
  • Can you reduce unnecessary writes? Swap only when read != write; this avoids self-swaps.
  • What if the input is a linked list? Relink nonzero nodes in their original order, then append the zero-valued nodes.
CodingEasyJosh Technology GroupSoftware Engineer

6. Climbing Stairs (LeetCode)

Model answer

The task

Count how many distinct ways there are to reach the top of a staircase with n steps when each move advances either one or two steps.

Key idea

To reach step i, the last move must come from step i - 1 or i - 2. Thus the number of ways to reach i is the sum of the ways to reach those two earlier steps. Only the previous two counts are needed, so there is no need to store a full table.

Approach

  1. Set the number of ways to reach step 0 to 1, representing the single empty sequence of moves.
  2. Set the number of ways to reach step 1 to 1.
  3. For each step from 2 through n, add the counts for the preceding two steps.
  4. Return the count for step n.
class Solution:
    def climbStairs(self, n: int) -> int:
        # Ways to reach steps 0 and 1.
        two_back = 1
        one_back = 1

        # Build the count using the two preceding results.
        for _ in range(2, n + 1):
            current = two_back + one_back
            two_back = one_back
            one_back = current

        return one_back

Complexity:

  • Time: O(n), since each step is processed once.
  • Space: O(1), since only two prior counts are retained.

Common follow-ups

  • What if each move can advance 1, 2, or 3 steps? Sum the counts for the previous three steps.
  • What if the result must be returned modulo a number? Apply the modulus after each addition.
  • What if some steps are forbidden? Set their ways count to zero and use dynamic programming for the allowed steps.
CodingEasyJosh Technology GroupSoftware Engineer

7. Invert Binary Tree (LeetCode)

Model answer

The task

Given the root of a binary tree, swap the left and right child of every node. Return the root of the resulting tree.

Key idea

A node’s children can be swapped independently of the rest of the tree. Visit each node once, swap its children, then process the children now attached to it.

Approach

  1. If the current node is empty, return it.
  2. Swap its left and right children.
  3. Recursively invert both children.
  4. Return the original root.
class Solution:
    def invertTree(self, root):
        # An empty subtree needs no changes.
        if root is None:
            return None

        # Swap the two subtrees rooted at this node.
        root.left, root.right = root.right, root.left

        # Invert each subtree.
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

Complexity:

  • Time: O(n), where n is the number of nodes; each node is visited once.
  • Space: O(h), where h is the tree height, due to the recursion stack.

Common follow-ups

  • What if the tree is very deep? Use an iterative traversal to avoid recursion-depth limits.
  • Can this be done with breadth-first search? Yes; enqueue each node, swapping its children as it is visited.
  • Does the method create a new tree? No; it modifies the existing tree in place.
CodingMediumJosh Technology GroupSoftware Engineer

8. Reverse Nodes in Even Length Groups (LeetCode)

Model answer

The task

Given a singly linked list, divide its nodes into consecutive groups with target sizes 1, 2, 3, and so on. Reverse each group whose actual size is even, including a final group that may be shorter than its target size.

Key idea

Process one group at a time, first counting how many nodes it actually contains. For an even-sized group, reverse its links in place and reconnect it to the surrounding list.

Approach

  1. Use a dummy node to simplify handling the list head.
  2. Track the node before the current group and the group’s target size.
  3. Count up to that many nodes, stopping at the end of the list.
  4. If the actual count is even, reverse those nodes and reconnect the group.
  5. Advance to the next group, increasing the target size.
from typing import Optional

# ListNode is provided by the platform.
class Solution:
    def reverseEvenLengthGroups(
        self, head: Optional["ListNode"]
    ) -> Optional["ListNode"]:
        dummy = ListNode(0)
        dummy.next = head

        group_prev = dummy
        group_size = 1

        while group_prev.next is not None:
            # Find the end of this group and count its actual nodes.
            group_end = group_prev
            count = 0
            while count < group_size and group_end.next is not None:
                group_end = group_end.next
                count += 1

            if count % 2 == 0:
                group_start = group_prev.next
                after_group = group_end.next

                # Reverse this group, linking its old head to the next group.
                prev = after_group
                curr = group_start
                for _ in range(count):
                    next_node = curr.next
                    curr.next = prev
                    prev = curr
                    curr = next_node

                group_prev.next = group_end
                group_prev = group_start  # The old head is now the group's tail.
            else:
                group_prev = group_end

            group_size += 1

        return dummy.next

Complexity:

  • Time: O(n), since each node is visited a constant number of times.
  • Space: O(1), since the list is modified in place.

Common follow-ups

  • How would you reverse odd-sized groups instead? Change the parity check to count % 2 == 1.
  • What if groups had a fixed size k? Use k as the target size for each group.
  • Can this be done recursively? Yes, but recursion may use O(n) stack space in the worst case.
CodingMediumJosh Technology GroupSoftware Engineer

9. Spiral Matrix (LeetCode)

Model answer

The task

Return the matrix values in clockwise spiral order, starting from the top-left corner and moving inward.

Key idea

Track the unvisited rectangle with four boundaries. Visit its top, right, bottom, and left edges in turn, then shrink the rectangle and repeat.

Approach

  1. Return an empty list if the matrix has no rows or columns.
  2. Initialize boundaries for the top, bottom, left, and right edges.
  3. Traverse the top edge, then move the top boundary inward.
  4. Traverse the right edge, then move the right boundary inward.
  5. If rows remain, traverse the bottom edge in reverse; if columns remain, traverse the left edge upward.
  6. Repeat until the boundaries cross.
from typing import List

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []

        result = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1

        while top <= bottom and left <= right:
            # Traverse the top edge from left to right.
            for col in range(left, right + 1):
                result.append(matrix[top][col])
            top += 1

            # Traverse the right edge from top to bottom.
            for row in range(top, bottom + 1):
                result.append(matrix[row][right])
            right -= 1

            # Traverse the bottom edge only if it has not been visited.
            if top <= bottom:
                for col in range(right, left - 1, -1):
                    result.append(matrix[bottom][col])
                bottom -= 1

            # Traverse the left edge only if it has not been visited.
            if left <= right:
                for row in range(bottom, top - 1, -1):
                    result.append(matrix[row][left])
                left += 1

        return result

Complexity: Time: O(m × n), where each cell is visited once.

Complexity: Space: O(1) auxiliary space, excluding the output list.

Common follow-ups

  • How would you return the values counterclockwise? Change the traversal order and edge directions while maintaining the same boundary updates.
  • How does this handle a single row or column? The boundary checks prevent an edge from being visited twice.
  • Can the traversal be done without boundary variables? Yes, by marking visited cells and turning when blocked, but that requires O(m × n) extra space.
CodingMediumJosh Technology GroupSoftware Engineer

10. Longest Palindromic Substring (LeetCode)

Model answer

The task

Given a string, return its longest contiguous substring that reads the same forward and backward. If several substrings have the same maximum length, returning any of them is acceptable.

Key idea

Every palindrome has a center: either a character (odd length) or the gap between two characters (even length). Expand outward from each possible center while the characters match, keeping track of the longest range found.

Approach

  1. Initialize the best range to an empty substring.
  2. For each character position, expand from that position to check odd-length palindromes.
  3. Also expand from the gap after that position to check even-length palindromes.
  4. When an expansion finds a longer palindrome, save its start and end indices.
  5. Return the substring covered by the saved range.
class Solution:
    def longestPalindrome(self, s: str) -> str:
        best_start = 0
        best_length = 0

        def expand(left: int, right: int) -> None:
            nonlocal best_start, best_length

            # Keep expanding while the current range is a palindrome.
            while left >= 0 and right < len(s) and s[left] == s[right]:
                length = right - left + 1
                if length > best_length:
                    best_start = left
                    best_length = length
                left -= 1
                right += 1

        for center in range(len(s)):
            expand(center, center)      # Odd-length palindromes
            expand(center, center + 1)  # Even-length palindromes

        return s[best_start:best_start + best_length]

Complexity:

  • Time: O(n²), since each of the O(n) centers can expand across O(n) characters.
  • Space: O(1), excluding the returned substring.

Common follow-ups

  • How can this be made linear time? Use Manacher’s algorithm to reuse information from previously explored centers.
  • How would you return all longest palindromic substrings? Track every range tied for the maximum length.
  • What if the input is empty? The method returns an empty string.
  • How would you count all palindromic substrings? Count each successful expansion instead of only saving the longest range.
CodingMediumJosh Technology GroupSoftware Engineer

11. Daily Temperatures (LeetCode)

Model answer

The task

For each day in a temperature list, find how many days later a warmer temperature first occurs. If no warmer day follows, its answer is zero.

Key idea

Keep a stack of indices whose temperatures are still waiting for a warmer day. Their temperatures are in non-increasing order; when a warmer day arrives, it resolves the waiting indices at the top.

Approach

  1. Create an answer array filled with zeros and an empty stack of indices.
  2. Scan the temperatures from left to right.
  3. While the current temperature is warmer than the temperature at the stack’s top index, pop that index.
  4. Set its answer to the difference between the current index and the popped index.
  5. Push the current index; unresolved indices remain zero.
from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        answer = [0] * n
        waiting: List[int] = []

        for day, temperature in enumerate(temperatures):
            # Resolve every earlier day for which today is the first
            # warmer day encountered.
            while waiting and temperatures[waiting[-1]] < temperature:
                earlier_day = waiting.pop()
                answer[earlier_day] = day - earlier_day

            # This day is now waiting for a warmer temperature.
            waiting.append(day)

        return answer

Complexity:

  • Time: O(n), since each index is pushed and popped at most once.
  • Space: O(n), for the answer array and the stack.

Common follow-ups

  • How would you handle temperatures arriving as a stream? Keep the unresolved indices and their temperatures in a stack, and emit answers when warmer values arrive; some earlier outputs may remain pending.
  • What changes if the question asks for the next colder day? Reverse the comparison so an index is resolved by a lower temperature.
  • Can the stack store temperatures instead of indices? Not for this output, because the index difference is needed to calculate the number of days.
  • What happens when temperatures are equal? Equal values do not resolve each other; only a strictly warmer temperature does.
CodingMediumJosh Technology GroupSoftware Engineer

12. All Nodes Distance K in Binary Tree (LeetCode)

Model answer

The task

Return the values of all nodes exactly k edges from a given target node in a binary tree. The nodes may be reached through child links or by moving to a parent.

Key idea

Add parent links to the tree, turning it into a graph where each node has at most three neighbors. Then use breadth-first search from the target, stopping after k layers.

Approach

  1. Traverse the tree and record each node’s parent.
  2. Start BFS at the target, marking it visited.
  3. For each node, consider its left child, right child, and parent.
  4. After k layers, return the values in the queue.
from collections import deque
from typing import List

class Solution:
    def distanceK(self, root, target, k: int) -> List[int]:
        if root is None or k < 0:
            return []

        # Record each node's parent so the tree can be traversed in both directions.
        parent = {root: None}
        stack = [root]

        while stack:
            node = stack.pop()

            if node.left:
                parent[node.left] = node
                stack.append(node.left)

            if node.right:
                parent[node.right] = node
                stack.append(node.right)

        if target not in parent:
            return []

        queue = deque([target])
        visited = {target}
        distance = 0

        while queue and distance < k:
            for _ in range(len(queue)):
                node = queue.popleft()

                for neighbor in (node.left, node.right, parent[node]):
                    if neighbor is not None and neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)

            distance += 1

        return [node.val for node in queue] if distance == k else []

Complexity:

  • Time: O(n), to build parent links and perform BFS.
  • Space: O(n), for the parent map, queue, and visited set.

Common follow-ups

  • What if node values are duplicated? Identify nodes by object identity, not by value.
  • Can the tree remain unchanged? Yes; the parent map is stored separately.
  • What if many targets are queried? Build the parent map once and reuse it.
CodingMediumJosh Technology GroupSoftware Engineer

13. Maximum Width Ramp (LeetCode)

Model answer

The task

Given an array, find the largest distance between two indices i < j where the value at i is no greater than the value at j.

Key idea

Keep a stack of indices whose values form a strictly decreasing sequence. These are the best candidates for the left endpoint: any later index with an equal or greater value is a worse left endpoint. Scan possible right endpoints from right to left, matching each with every stack candidate it can reach.

Approach

  1. Scan left to right, pushing an index only when its value is smaller than the value at the top of the stack.
  2. This leaves candidate left endpoints ordered from largest to smallest index, with strictly decreasing values.
  3. Scan right endpoints from right to left.
  4. While the top candidate's value is no greater than the current value, calculate the width and remove that candidate. It cannot produce a wider ramp with any earlier right endpoint.
  5. Return the greatest width found.
from typing import List

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        # Keep indices with strictly decreasing values.
        candidates = []
        for i, value in enumerate(nums):
            if not candidates or value < nums[candidates[-1]]:
                candidates.append(i)

        widest = 0

        # Later right endpoints can only give equal or greater widths,
        # so scan from right to left and discard matched candidates.
        for j in range(len(nums) - 1, -1, -1):
            while candidates and nums[candidates[-1]] <= nums[j]:
                i = candidates.pop()
                widest = max(widest, j - i)

        return widest

Complexity:

  • Time: O(n), since each index is pushed and popped at most once.
  • Space: O(n) for the candidate stack.

Common follow-ups

  • Return the endpoint indices, not just the width? Store the pair (i, j) whenever a larger width is found.
  • Can this be solved without a stack? A prefix-minimum array plus a right-to-left scan also gives an O(n) solution.
  • What if the condition is strict (nums[i] < nums[j])? Change the matching comparison from <= to <.
CodingMediumJosh Technology GroupSoftware Engineer

14. Maximum Twin Sum of a Linked List (LeetCode)

Model answer

The task

For an even-length linked list, pair each node in the first half with its matching node from the end. Return the largest sum among those pairs.

Key idea

Reverse the second half of the list. Its nodes then line up with the first half in twin-pair order, so we can calculate every sum using two pointers and constant extra space.

Approach

  1. Use slow and fast pointers to find the start of the second half.
  2. Reverse the second half in place.
  3. Walk the first half and reversed half together, tracking the largest pair sum.
  4. Reverse the second half again to restore the original list.
from typing import Optional

class Solution:
    def pairSum(self, head: Optional["ListNode"]) -> int:
        # Find the start of the second half.
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Reverse the second half in place.
        def reverse(node):
            previous = None
            while node:
                following = node.next
                node.next = previous
                previous = node
                node = following
            return previous

        second_half = reverse(slow)

        # Compare corresponding nodes from each half.
        left = head
        right = second_half
        largest = 0
        while right:
            largest = max(largest, left.val + right.val)
            left = left.next
            right = right.next

        # Restore the original list structure.
        reverse(second_half)

        return largest

Complexity:

  • Time: O(n), for midpoint search, reversal, and pair evaluation.
  • Space: O(1), using only a fixed number of pointers.

Common follow-ups

  • How would you solve it with a stack? Push the first half’s values, then pop while traversing the second half; this uses O(n) extra space.
  • Can the input list remain unchanged? Yes; reverse the second half again after computing the maximum, as above.
  • What if the list length is odd? Define how the middle node should be treated, then adjust the midpoint logic to exclude or pair it as required.
CodingMediumJosh Technology GroupSoftware Engineer

15. Reverse Odd Levels of Binary Tree (LeetCode)

Model answer

The task

Given a perfect binary tree, reverse the node values at every odd-numbered level, leaving the tree structure unchanged. Return the root of the modified tree.

Key idea

At each odd level, swap values in pairs of nodes that are symmetric around the level’s midpoint. A breadth-first traversal visits one level at a time, making those pairs easy to identify.

Approach

  1. Put the root in a queue.
  2. Process the queue one level at a time.
  3. On odd-numbered levels, swap values at symmetric positions in that level’s node list.
  4. Add the current level’s children to the queue.
  5. Return the original root.
from collections import deque
from typing import Optional

class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None

        queue = deque([root])
        level = 0

        while queue:
            # Capture all nodes at this level in left-to-right order.
            level_size = len(queue)
            nodes = [queue.popleft() for _ in range(level_size)]

            if level % 2 == 1:
                left, right = 0, len(nodes) - 1
                while left < right:
                    nodes[left].val, nodes[right].val = (
                        nodes[right].val,
                        nodes[left].val,
                    )
                    left += 1
                    right -= 1

            for node in nodes:
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            level += 1

        return root

Complexity:

  • Time: O(n), since each node is visited once.
  • Space: O(n) in the worst case for the queue and current level.

Common follow-ups

  • Can you do this with DFS? Pair mirror-positioned nodes and swap their values at odd depths.
  • Can you avoid storing a whole level? Use the paired DFS approach, which uses O(h) recursion space.
  • What if the tree is not perfect? Define how missing nodes affect the reversal; positional symmetry may no longer be well-defined.
CodingMediumJosh Technology GroupSoftware Engineer

16. Subarray Sum Equals K (LeetCode)

Model answer

The task

Count the contiguous subarrays whose elements sum to a given target k. The array may contain negative numbers, so subarray sums do not necessarily grow as the subarray gets longer.

Key idea

For each position, let prefix be the sum of all elements seen so far. A subarray ending here sums to k exactly when an earlier prefix sum equals prefix - k. Keep counts of earlier prefix sums in a hash table.

Approach

  1. Start with prefix sum 0 occurring once, representing the empty prefix.
  2. Scan the array and add each value to the running prefix sum.
  3. Add the number of times prefix - k has appeared to the answer.
  4. Record the current prefix sum for future positions.
from collections import defaultdict
from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # Counts of prefix sums seen so far.
        prefix_counts = defaultdict(int)
        prefix_counts[0] = 1

        prefix_sum = 0
        subarray_count = 0

        for value in nums:
            prefix_sum += value

            # Each matching earlier prefix identifies one subarray
            # ending at the current position.
            subarray_count += prefix_counts[prefix_sum - k]

            # Record this prefix only after counting, so the match
            # refers to an earlier position.
            prefix_counts[prefix_sum] += 1

        return subarray_count

Complexity: Time: O(n), where n is the number of elements; each element is processed once.

Complexity: Space: O(n) in the worst case, for the distinct prefix sums stored.

Common follow-ups

  • Why not use a sliding window? Negative values break the monotonic behavior of window sums that sliding-window techniques rely on.
  • What if all values are nonnegative? A sliding window can be used, though prefix sums still provide a straightforward solution.
  • Can this count subarrays for many target values? The prefix-frequency scan is target-specific; repeated queries may need a different strategy depending on the input size and query count.
CodingMediumJosh Technology GroupSoftware Engineer

17. Rotate List (LeetCode)

Model answer

The task

Shift a singly linked list to the right by a given number of positions. Return the new head, preserving the order of the nodes.

Key idea

A right rotation can be made by temporarily treating the list as a cycle, then breaking it at the right point. Reduce the number of rotations modulo the list length, since a full-length rotation changes nothing.

Approach

  1. Return the head if the list is empty or has one node.
  2. Traverse the list to count its length and find its tail.
  3. Compute k % length; if it is zero, return the original head.
  4. Connect the tail to the head to form a cycle.
  5. Walk length - k - 1 steps from the head to find the new tail, then break the cycle after it.
class Solution:
    def rotateRight(self, head, k):
        # Empty and single-node lists do not change when rotated.
        if head is None or head.next is None:
            return head

        # Find the length and the current tail.
        length = 1
        tail = head
        while tail.next is not None:
            tail = tail.next
            length += 1

        # Rotating by a multiple of the length leaves the list unchanged.
        k %= length
        if k == 0:
            return head

        # Make the list circular, then locate the new tail.
        tail.next = head
        new_tail = head
        for _ in range(length - k - 1):
            new_tail = new_tail.next

        # Break the cycle; the next node is the new head.
        new_head = new_tail.next
        new_tail.next = None
        return new_head

Complexity:

  • Time: O(n), for one traversal to find the length and at most one more traversal to find the new tail.
  • Space: O(1), since only a fixed number of pointers and counters are used.

Common follow-ups

  • What if k is much larger than the list length? Reduce it modulo the length before finding the new tail.
  • Can this be done without changing the original list? Not in place; a separate copy would require O(n) additional space.
  • What if the list is empty or has one node? Return it immediately, as rotation cannot change it.
CodingMediumJosh Technology GroupSoftware Engineer

18. Flatten Binary Tree to Linked List (LeetCode)

Model answer

The task

Rearrange a binary tree in place into a right-only chain whose node order matches preorder traversal. Each node’s left pointer should be cleared.

Key idea

At each node with a left subtree, find the rightmost node in that subtree. Link it to the node’s original right subtree, then move the left subtree to the right. This preserves preorder while using constant extra space.

Approach

  1. Start at the root and walk along the resulting right chain.
  2. If the current node has a left child, locate the rightmost node of that left subtree.
  3. Attach the current node’s original right subtree to that rightmost node.
  4. Move the left subtree to the current node’s right pointer and clear its left pointer.
  5. Continue to the next node on the right.
from typing import Optional

# TreeNode is provided by the coding platform.
class Solution:
    def flatten(self, root: Optional["TreeNode"]) -> None:
        """Flatten the tree in place; the result is a right-only chain."""
        current = root

        while current:
            if current.left:
                # Find the last node in the left subtree's rightmost path.
                predecessor = current.left
                while predecessor.right:
                    predecessor = predecessor.right

                # Preserve the original right subtree after the left subtree.
                predecessor.right = current.right
                current.right = current.left
                current.left = None

            current = current.right

Complexity:

  • Time: O(n), as each tree edge is traversed a bounded number of times.
  • Space: O(1), since the tree is rewired in place.

Common follow-ups

  • How can this be done iteratively with a stack? Push right before left, then link popped nodes in order.
  • Can recursion be used? Process right, then left, and link each node to the previously processed node; this uses O(h) call-stack space.
  • How would you verify the result? Walk the right chain, confirm all left pointers are null, and compare its order with preorder traversal.
CodingMediumJosh Technology GroupSoftware Engineer

19. Odd Even Linked List (LeetCode)

Model answer

The task

Rearrange a singly linked list so nodes at odd positions come first, followed by nodes at even positions. Keep the original relative order within both groups.

Key idea

Build the odd-position and even-position chains in place as we traverse the list. Keep the even-chain head so it can be attached after the odd chain when traversal ends.

Approach

  1. Return the list unchanged if it has fewer than two nodes.
  2. Set pointers for the current odd node, current even node, and the head of the even chain.
  3. Repeatedly link the next odd node into the odd chain, then the next even node into the even chain.
  4. Attach the even-chain head after the last odd node.
  5. Return the original head.
# Definition for singly-linked list:
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def oddEvenList(self, head: ListNode | None) -> ListNode | None:
        if head is None or head.next is None:
            return head

        odd = head
        even = head.next
        even_head = even

        while even is not None and even.next is not None:
            # Append the next node in the original sequence to the odd chain.
            odd.next = even.next
            odd = odd.next

            # Append the following node to the even chain.
            even.next = odd.next
            even = even.next

        # Join the two stable chains.
        odd.next = even_head
        return head

Complexity:

  • Time: O(n), where n is the number of nodes visited once.
  • Space: O(1), using only a fixed number of pointers.

Common follow-ups

  • What if the list has zero or one node? Return it unchanged.
  • Are nodes grouped by their values? No; grouping is by one-based position, regardless of values.
  • Can the relative order within each group change? No; this algorithm preserves it.
  • Can this be done without modifying links? Yes, but it would require extra storage to collect and rebuild the node order.
CodingMediumJosh Technology GroupSoftware Engineer

20. Binary Tree Level Order Traversal (LeetCode)

Model answer

The task

Given the root of a binary tree, return its node values grouped by depth, from the root level down. Within each level, list values from left to right.

Key idea

Breadth-first search visits nodes in level order. At the start of each iteration, record how many nodes are currently queued; processing exactly that many captures one whole level.

Approach

  1. Return an empty list if the tree has no root.
  2. Put the root in a queue.
  3. For each level, save the queue’s current size.
  4. Remove that many nodes, recording their values and adding their children to the queue from left to right.
  5. Append the completed level to the result and repeat until the queue is empty.
from collections import deque
from typing import List, Optional

# Assumes TreeNode has attributes: val, left, and right.
class Solution:
    def levelOrder(self, root: Optional["TreeNode"]) -> List[List[int]]:
        if root is None:
            return []

        result: List[List[int]] = []
        queue = deque([root])

        while queue:
            level_size = len(queue)
            level_values: List[int] = []

            for _ in range(level_size):
                node = queue.popleft()
                level_values.append(node.val)

                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)

            result.append(level_values)

        return result

Complexity:

  • Time: O(n), because each node is processed once.
  • Space: O(n), for the queue in the widest level and the returned values.

Common follow-ups

  • How would you return values from bottom to top? Reverse the list of levels before returning.
  • How would you return only the nodes at a particular depth? Track the level number and stop after processing the requested depth.
  • How would you compute the maximum width of the tree? Track the largest level_size while processing levels.

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