DP World interview questions & answers

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

CodingMediumDP WorldSoftware Engineer

1. Evaluate Division (LeetCode)

Model answer

The task

Given equations that define ratios between variables, answer queries asking for a ratio between two variables. Return -1.0 when the ratio cannot be determined.

Key idea

Represent each equation as two directed graph edges: from a to b with weight a / b, and from b to a with the reciprocal weight. A path’s edge weights multiply to give the ratio between its endpoints.

Approach

  1. Build a weighted adjacency list from the equations.
  2. For each query, return -1.0 if either variable is unknown.
  3. Otherwise, use DFS to find a path between the variables, multiplying edge weights along the way.
  4. Track visited variables so cycles do not cause repeated exploration.
  5. If the variables are the same and known, the ratio is 1.0.
from collections import defaultdict
from typing import List

class Solution:
    def calcEquation(
        self,
        equations: List[List[str]],
        values: List[float],
        queries: List[List[str]]
    ) -> List[float]:
        graph = defaultdict(list)

        for (numerator, denominator), value in zip(equations, values):
            graph[numerator].append((denominator, value))
            graph[denominator].append((numerator, 1.0 / value))

        def find_ratio(start: str, target: str) -> float:
            if start not in graph or target not in graph:
                return -1.0
            if start == target:
                return 1.0

            stack = [(start, 1.0)]
            visited = {start}

            while stack:
                variable, product = stack.pop()

                for neighbor, edge_value in graph[variable]:
                    if neighbor in visited:
                        continue

                    next_product = product * edge_value
                    if neighbor == target:
                        return next_product

                    visited.add(neighbor)
                    stack.append((neighbor, next_product))

            return -1.0

        return [find_ratio(a, b) for a, b in queries]

Complexity:

  • Time: O(Q(V + E)), where each query may traverse the full graph.
  • Space: O(V + E) for the graph and the DFS state.

Common follow-ups

  • How can repeated queries be sped up? Use weighted union-find to answer each query in near-constant time after preprocessing.
  • How would you handle inconsistent equations? Detect conflicting ratios when connecting variables or revisiting an already-connected pair.
  • What if the graph is very large but queries are few? Keep DFS/BFS per query to avoid more elaborate preprocessing.
CodingMediumDP WorldSoftware Engineer

2. 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.
CodingMediumDP WorldSoftware Engineer

3. Capacity To Ship Packages Within D Days (LeetCode)

Model answer

The task

Find the smallest ship capacity that can transport all packages within the given number of days, shipping packages in their original order.

Key idea

If a capacity works, any larger capacity also works, so feasibility is monotonic and can be searched with binary search. For a candidate capacity, greedily load each day as many consecutive packages as fit.

Approach

  1. The capacity must be at least the heaviest package.
  2. The sum of all weights is always sufficient, since it can ship everything in one day.
  3. Binary-search this range.
  4. For each candidate, greedily count how many days are needed, starting a new day when the next package would exceed capacity.
  5. Keep the candidate if the required days are within the limit; otherwise, increase the capacity.
class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        def can_ship(capacity: int) -> bool:
            used_days = 1
            load = 0

            for weight in weights:
                if load + weight > capacity:
                    used_days += 1
                    load = 0

                load += weight

            return used_days <= days

        left = max(weights)
        right = sum(weights)

        while left < right:
            capacity = (left + right) // 2

            if can_ship(capacity):
                right = capacity
            else:
                left = capacity + 1

        return left

Complexity:

  • Time: O(n log(sum(weights) - max(weights) + 1)), for the binary search and feasibility checks.
  • Space: O(1), excluding the input.

Common follow-ups

  • What if packages can be reordered? The greedy check changes; for positive weights, packing the largest packages first may help, but the original-order constraint is essential to this solution.
  • Can you return the day-by-day assignments too? Record each greedy day’s packages during a final feasibility pass.
  • What if the number of days is very large? The same bounds and binary search apply; capacities below the heaviest package remain impossible.
CodingMediumDP WorldSoftware Engineer

4. Find the Duplicate Number (LeetCode)

Model answer

The task

Given an array of length n + 1 whose values are in the range 1 to n, find the value that appears more than once. The usual guarantees allow solving it without changing the array or using extra storage proportional to its size.

Key idea

Treat each array index as pointing to the index named by its value. Since there are more indices than possible values, following these pointers eventually enters a cycle; the cycle’s entry corresponds to the duplicate. Floyd’s cycle-finding algorithm locates that entry in linear time and constant space.

Approach

  1. Start two pointers at index 0.
  2. Move the slow pointer one step and the fast pointer two steps until they meet.
  3. Reset the slow pointer to index 0.
  4. Move both pointers one step at a time; their next meeting point is the duplicate value.
from typing import List

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # Find a meeting point inside the cycle.
        slow = nums[0]
        fast = nums[0]

        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        # Find the cycle entry, which is the duplicate value.
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        return slow

Complexity:

  • Time: O(n), since each pointer traverses at most a linear number of links.
  • Space: O(1), using only two pointers.

Common follow-ups

  • How can binary search solve it? Count values at most the midpoint; if the count exceeds the midpoint, the duplicate lies in the lower value range.
  • Can the array be sorted first? Yes, adjacent equal values reveal the duplicate, but sorting changes the array and takes O(n log n) time.
  • What if there may be several distinct duplicated values? This cycle-entry method is not guaranteed to identify all of them; the single-distinct-duplicate guarantee is important.
CodingMediumDP WorldSoftware Engineer

5. Group Anagrams (LeetCode)

Model answer

The task

Partition the input strings into groups so that strings in the same group contain the same characters with the same frequencies. The order of the groups does not matter.

Key idea

Sort the characters of each string to create a canonical key. Anagrams produce the same key, so a hash table can collect them together.

Approach

  1. Create a mapping from canonical keys to lists of original strings.
  2. For each string, sort its characters and use the result as its key.
  3. Append the string to the list for that key.
  4. Return all grouped lists.
from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)

        for word in strs:
            # Anagrams have identical sorted-character representations.
            key = "".join(sorted(word))
            groups[key].append(word)

        return list(groups.values())

Complexity:

  • Time: O(n · k log k), where n is the number of strings and k is the maximum string length.
  • Space: O(n · k) to store the grouped strings and their keys.

Common follow-ups

  • Can this be faster for a fixed alphabet? Use a character-frequency tuple as the key, computing it in O(k) per string.
  • Does this work with uppercase letters or Unicode? Yes; sorting characters works for any Python strings.
  • Can groups be returned in a deterministic order? Sort the groups, or their keys, before returning them.
  • What if memory is limited? Consider processing input in batches or grouping externally by canonical key.
CodingMediumDP WorldSoftware Engineer

6. Rabbits in Forest (LeetCode)

Model answer

The task

Given a list of rabbits’ reported counts of other rabbits with the same color, find the smallest possible total number of rabbits consistent with those reports.

Key idea

If a rabbit reports x, its color group has exactly x + 1 rabbits. Reports with the same value can share a group, but any partially filled final group still contributes its full size.

Approach

  1. Count how often each report value appears.
  2. For a value x, let the group size be x + 1.
  3. Compute how many such groups are needed to fit all reports: round the report count up to a whole number of groups.
  4. Add each group’s full size to the total.
from collections import Counter
from typing import List

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        frequencies = Counter(answers)
        total = 0

        for reported_count, frequency in frequencies.items():
            group_size = reported_count + 1
            groups_needed = (frequency + group_size - 1) // group_size
            total += groups_needed * group_size

        return total

Complexity:

  • Time: O(n), to count and process the reports.
  • Space: O(k), for k distinct reported counts.

Common follow-ups

  • What if reports arrive as a stream? Keep a frequency counter and update the total whenever a report completes a group.
  • Can the same report value represent multiple color groups? Yes; divide its frequency into groups of at most x + 1.
  • What if the answers are already sorted? Count consecutive equal values and apply the same group calculation.
CodingMediumDP WorldSoftware Engineer

7. Longest Substring Without Repeating Characters (LeetCode)

Model answer

The task

Find the length of the longest contiguous section of a string in which every character appears at most once.

Key idea

Maintain a sliding window with no repeated characters. When a character repeats within the window, move the left edge just past its previous occurrence.

Approach

  1. Track each character’s most recent index in a dictionary.
  2. Keep left as the window’s starting index and best as its longest length so far.
  3. For each character, move left forward if its previous occurrence is inside the current window.
  4. Record the character’s current index and update best using the window length.
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}
        left = 0
        best = 0

        for right, char in enumerate(s):
            # Skip past a repeated character if it is in the current window.
            if char in last_seen and last_seen[char] >= left:
                left = last_seen[char] + 1

            last_seen[char] = right
            best = max(best, right - left + 1)

        return best

Complexity:

  • Time: O(n), because each character is processed once.
  • Space: O(k), where k is the number of distinct characters encountered.

Common follow-ups

  • Return the substring itself: store the best window’s start and end indices when updating best.
  • Handle a stream of characters: keep the same window state and process each arriving character incrementally.
  • Use a fixed-size character set: replace the dictionary with an array of last-seen indices.
CodingHardDP WorldSoftware Engineer

8. Minimum Window Substring (LeetCode)

Model answer

The task

Given strings s and t, return the shortest contiguous substring of s that contains every character in t, including repeated characters. Return an empty string if no such substring exists.

Key idea

Use a sliding window and character counts. Expand the right edge until the window contains all required character frequencies, then move the left edge rightward as far as possible while keeping the window valid.

Approach

  1. Count the required characters in t.
  2. Move the right edge across s, updating counts for relevant characters.
  3. Track how many distinct required characters have reached their needed frequencies.
  4. Whenever all are satisfied, record the window if it is shorter than the best found.
  5. Shrink from the left until the window is no longer valid, then continue expanding.
from collections import Counter, defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""

        need = Counter(t)
        window = defaultdict(int)
        required = len(need)
        formed = 0

        best_start = 0
        best_length = float("inf")
        left = 0

        for right, char in enumerate(s):
            if char in need:
                window[char] += 1
                if window[char] == need[char]:
                    formed += 1

            # Shrink while all required character counts are satisfied.
            while formed == required:
                length = right - left + 1
                if length < best_length:
                    best_start = left
                    best_length = length

                left_char = s[left]
                if left_char in need:
                    if window[left_char] == need[left_char]:
                        formed -= 1
                    window[left_char] -= 1
                left += 1

        if best_length == float("inf"):
            return ""
        return s[best_start:best_start + best_length]

Complexity:

  • Time: O(|s| + |t|), since each pointer advances at most the length of s.
  • Space: O(d), where d is the number of distinct characters in t.

Common follow-ups

  • What if t is empty? Return an empty string immediately, as handled above.
  • Can you return all shortest windows? Keep each window matching the minimum length instead of only one.
  • How does this scale to a stream? Maintain counts and window positions, while accounting for the storage needed to retain candidate characters.
CodingHardDP WorldSoftware Engineer

9. Wildcard Matching (LeetCode)

Model answer

The task

Determine whether a string matches a pattern containing ? for any one character and * for any sequence of characters, including an empty sequence.

Key idea

Scan both strings while remembering the most recent * and where it began matching the input. If a later match fails, extend that star’s match by one character and retry from just after the star.

Approach

  1. Keep indices into the input and pattern, plus the position of the last *.
  2. Advance both indices when characters match or the pattern has ?.
  3. When encountering *, record its position and the current input index; initially let it match nothing.
  4. On a mismatch, expand the recorded star’s match by one input character and resume after the star.
  5. After consuming the input, skip remaining * characters and check whether the pattern is exhausted.
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        i = j = 0
        star = -1
        star_match_start = 0

        while i < len(s):
            # Exact match or single-character wildcard.
            if j < len(p) and (p[j] == s[i] or p[j] == "?"):
                i += 1
                j += 1
            elif j < len(p) and p[j] == "*":
                # Let this star match an empty sequence for now.
                star = j
                star_match_start = i
                j += 1
            elif star != -1:
                # Extend the most recent star's match by one character.
                star_match_start += 1
                i = star_match_start
                j = star + 1
            else:
                return False

        # Any remaining pattern characters must be stars.
        while j < len(p) and p[j] == "*":
            j += 1

        return j == len(p)

Complexity:

  • Time: O(len(s) × len(p)) worst case, because a mismatch can cause retries from the most recent star.
  • Space: O(1), using only a fixed number of indices.

Common follow-ups

  • How would you implement this with dynamic programming? Use a table where each cell records whether a pattern prefix matches a string prefix.
  • How can consecutive stars be handled? Collapse each run of * characters to one; this preserves matching behavior.
  • What if the pattern must support escaping wildcards? Tokenize it first so escaped * and ? are treated as literals.
CodingHardDP WorldSoftware Engineer

10. Binary Tree Cameras (LeetCode)

Model answer

The task

Place the fewest cameras in a binary tree so every node is watched. A camera watches its own node, its parent, and its immediate children.

Key idea

A postorder traversal lets each node decide based on whether its children are uncovered, have cameras, or are already covered. Place a camera only when a child is uncovered; if the root remains uncovered, add one there.

Approach

  1. Traverse the tree in postorder so child states are known before processing a node.
  2. Return one of three states: NEEDS_CAMERA, HAS_CAMERA, or COVERED.
  3. Treat a missing child as covered.
  4. If either child needs a camera, place one at the current node.
  5. Otherwise, if either child has a camera, the current node is covered; if neither does, it needs a camera.
  6. After traversal, place a camera at the root if it still needs one.
# TreeNode is assumed to provide left and right attributes.

class Solution:
    def minCameraCover(self, root):
        NEEDS_CAMERA = 0
        HAS_CAMERA = 1
        COVERED = 2

        cameras = 0

        def dfs(node):
            nonlocal cameras

            # A missing child is already covered.
            if node is None:
                return COVERED

            left_state = dfs(node.left)
            right_state = dfs(node.right)

            # An uncovered child must be watched by a camera here.
            if left_state == NEEDS_CAMERA or right_state == NEEDS_CAMERA:
                cameras += 1
                return HAS_CAMERA

            # A child camera also watches this node.
            if left_state == HAS_CAMERA or right_state == HAS_CAMERA:
                return COVERED

            # No child has a camera, so this node may need one above.
            return NEEDS_CAMERA

        if dfs(root) == NEEDS_CAMERA:
            cameras += 1

        return cameras

Complexity:

  • Time: O(n), since each node is visited once.
  • Space: O(h), for the recursion stack, where h is the tree height.

Common follow-ups

  • How can this avoid recursion-depth limits? Use an explicit stack to perform postorder traversal.
  • What if cameras have different costs? Use tree DP with minimum-cost states instead of a single camera count.
  • What if cameras can watch beyond immediate neighbors? Redefine the states to track the required coverage distance.
CodingHardDP WorldSoftware Engineer

11. Set Intersection Size At Least Two (LeetCode)

Model answer

The task

Choose as few integers as possible so every interval contains at least two chosen integers.

Key idea

Process intervals by increasing right endpoint, breaking ties by decreasing left endpoint. When an interval is missing points, add them as far to its right as possible; that preserves the most options for intervals processed later.

Approach

  1. Sort by (right endpoint, -left endpoint).
  2. Track the two largest selected integers, along with how many have been selected.
  3. If both tracked integers are in the current interval, add nothing.
  4. If only the larger one is in it, add the interval’s right endpoint.
  5. If neither is in it, add the two largest integers in the interval.
from typing import List

class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        # For equal right endpoints, handle the narrower interval first.
        intervals.sort(key=lambda interval: (interval[1], -interval[0]))

        # a and b are the two largest selected values, with a <= b.
        a = b = 0
        selected_count = 0

        for left, right in intervals:
            if selected_count >= 2 and left <= a:
                # Both tracked values lie in this interval.
                continue

            if selected_count >= 1 and left <= b:
                # Only b is guaranteed to lie in the interval.
                a, b = b, right
                selected_count += 1
            else:
                # Add the two largest integers in the interval.
                a, b = right - 1, right
                selected_count += 2

        return selected_count

Complexity:

  • Time: O(n log n), dominated by sorting the intervals.
  • Space: O(n) for Python’s sorting; the greedy scan uses O(1) extra bookkeeping.

Common follow-ups

  • What if each interval must contain at least k chosen integers? Track the largest k selected values and add enough rightmost points when needed.
  • Why sort equal endpoints by decreasing left endpoint? It processes narrower intervals first, so satisfying one can also satisfy wider intervals with the same right endpoint.
  • What if intervals contain real numbers rather than integers? The greedy choices depend on discrete consecutive points; the problem needs a different point-domain interpretation.

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