PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This multi-part problem evaluates string manipulation and parity/combinatorics for constructing odd-occurrence strings, greedy optimization and minimal-change reasoning for digit-swap distance minimization, and bipartite matching/assignment skills for patient slot allocation.

  • Medium
  • DRW
  • Coding & Algorithms
  • Software Engineer

Solve odd-string, digit swap, patient slot assignment

Company: DRW

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

##### Question Task 1 – Odd-occurrence string: Write a function that, given an integer N (1..200 000), returns a length-N lowercase string in which every letter that appears occurs an odd number of times. ​ Task 2 – Min-swap closest numbers: Write a function solution(string S, string T) that, given two digit strings S and T of equal length N (1..100 000) with no leading zeros, returns the minimum number of position-wise digit swaps needed to minimize |int(S) – int(T)|. ​ Task 3 – Patient slot assignment: Write a function solution(int[] A, int[] B, int S) that, given two arrays A and B of length N (1..100 000) containing preferred doctor-appointment slots (1..S, where S ≤ 100 000) for each patient, returns true if all patients can be assigned one of their two preferred slots with no slot shared by more than one patient, otherwise false.

Quick Answer: This multi-part problem evaluates string manipulation and parity/combinatorics for constructing odd-occurrence strings, greedy optimization and minimal-change reasoning for digit-swap distance minimization, and bipartite matching/assignment skills for patient slot allocation.

Odd-Occurrence String

Given an integer N (1 ≤ N ≤ 200000), build and return any length-N string of lowercase English letters in which every distinct letter that appears occurs an **odd** number of times. For example, for N = 4 the string "aaab" is valid: 'a' appears 3 times (odd) and 'b' appears 1 time (odd). The string "aabb" is **not** valid because both letters appear an even number of times. Many answers are possible; the console grades your function against a fixed reference construction, so return exactly: - if N is odd: the single letter 'a' repeated N times; - if N is even: 'a' repeated (N-1) times followed by a single 'b'. Clarifying questions to consider: Is the empty string possible? (No — N ≥ 1.) Must the answer be unique? (Conceptually no, but this console pins one canonical construction.) Can a letter appear zero times? (Yes — only letters that *appear* must have odd counts.)

Constraints

  • 1 ≤ N ≤ 200000
  • The returned string must have length exactly N.
  • Every lowercase letter that appears in the result must appear an odd number of times.
  • Letters that do not appear are unconstrained.

Examples

Input: (1,)

Expected Output: 'a'

Explanation: N is odd, so a single 'a' (count 1, odd) is returned.

Input: (2,)

Expected Output: 'ab'

Explanation: N is even: 'a' once and 'b' once — both counts odd.

Input: (3,)

Expected Output: 'aaa'

Explanation: N is odd: 'a' three times (count 3, odd).

Input: (6,)

Expected Output: 'aaaaab'

Explanation: N is even: 'a' five times (odd) and 'b' once (odd).

Input: (7,)

Expected Output: 'aaaaaaa'

Explanation: N is odd: 'a' seven times (odd).

Hints

  1. If N is odd, a single repeated letter already satisfies the condition.
  2. If N is even, you cannot use a single letter (it would appear an even number of times). Split off exactly one occurrence of a second letter so both counts become odd.
  3. N-1 is odd whenever N is even, and 1 is odd, so 'a'*(N-1) + 'b' works for even N.

Minimum Position-Wise Swaps to Close Two Numbers

You are given two digit strings S and T of equal length N (1 ≤ N ≤ 100000), each with no leading zeros. At each position i you may **swap S[i] with T[i]** (counting as one swap) or leave the position unchanged. After choosing a set of positions to swap, the two strings become two integers int(S') and int(T'). First choose swaps so that |int(S') − int(T')| is as small as possible. Among all swap sets achieving that minimum absolute difference, return the **minimum number of swaps** used. Key observation: swapping position i negates that position's contribution (S[i]−T[i])·10^(N−1−i) to int(S)−int(T). So you are choosing a sign for each position's contribution to drive the signed total toward zero, then minimizing how many signs you flipped. The console grades small inputs, so the reference enumerates all keep/swap choices; on the small test sizes this is exact. Clarifying questions to consider: Are S and T always the same length? (Yes.) Can a swap create a leading zero? (The model allows it — we compare integer values, so a leading zero just yields a smaller magnitude.) Is the answer the minimum *difference* or the minimum *swap count*? (The swap count, subject to first minimizing the difference.)

Constraints

  • 1 ≤ N ≤ 100000
  • len(S) == len(T) == N
  • S and T consist of digits '0'..'9' with no leading zeros.
  • Only same-position S[i] ↔ T[i] swaps are allowed; each such swap costs 1.

Examples

Input: ('12', '12')

Expected Output: 0

Explanation: S and T are identical; difference is already 0, so no swaps are needed.

Input: ('19', '91')

Expected Output: 0

Explanation: Keeping both positions gives |19-91|=72; any single swap gives the same magnitude, so 0 swaps already minimizes.

Input: ('3', '8')

Expected Output: 0

Explanation: |3-8|=5 and swapping gives |8-3|=5 — same magnitude, so the minimum-swap minimizer uses 0 swaps.

Input: ('99', '11')

Expected Output: 1

Explanation: Keeping gives |99-11|=88; swapping the tens position once yields |19-91|=72, the smallest achievable, using 1 swap.

Input: ('73511', '77975')

Expected Output: 1

Explanation: Swapping only the most significant differing position drives the difference to its minimum 3536 with a single swap.

Input: ('532', '900')

Expected Output: 0

Explanation: Keeping all positions already yields the minimum achievable |difference|, so 0 swaps.

Hints

  1. Swapping position i flips the sign of that position's contribution (S[i]−T[i])·10^(N−1−i) to int(S)−int(T).
  2. First make the absolute difference as small as possible; only then minimize the number of sign flips (swaps).
  3. If S and T are already equal, the difference is 0 and zero swaps are needed.

Patient Slot Assignment

There are N patients (1 ≤ N ≤ 100000) and S available appointment slots numbered 1..S (S ≤ 100000). Patient i has two preferred slots, A[i] and B[i] (each in 1..S). Assign every patient exactly one of their two preferred slots so that **no slot is given to more than one patient**. Return true if such an assignment exists, otherwise false. Model each patient as an undirected edge connecting the two slot-nodes A[i] and B[i]. A valid assignment exists iff each connected component of this graph can be oriented so that every node receives at most one incoming edge — equivalently, every connected component has at most as many edges (patients) as nodes (distinct slots). A component with more patients than slots is over-subscribed and makes the answer false. Clarifying questions to consider: Can A[i] equal B[i] (both preferences the same slot)? (Yes — that patient must take that one slot; two such patients on the same slot conflict.) Do all S slots have to be used? (No — only one slot per patient, with no sharing.) Are there always exactly two preferences? (Yes, A[i] and B[i].)

Constraints

  • 1 ≤ N ≤ 100000 (N = len(A) = len(B))
  • 1 ≤ S ≤ 100000
  • 1 ≤ A[i], B[i] ≤ S for every patient i
  • A[i] may equal B[i].

Examples

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

Expected Output: True

Explanation: Two patients, edges 1-2 and 2-3; the component has 2 edges and 3 nodes, so assignment is possible (e.g. patient 0 → slot 1, patient 1 → slot 3).

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

Expected Output: True

Explanation: Edges 1-2 and 1-2 form a 2-edge, 2-node component (edges ≤ nodes); assign one patient to slot 1 and the other to slot 2.

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

Expected Output: True

Explanation: A single patient whose two preferences are both slot 1: one edge, one node, so it takes slot 1.

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

Expected Output: True

Explanation: A 3-cycle: 3 edges, 3 nodes (edges ≤ nodes), so the cycle can be oriented to assign each patient a distinct slot.

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

Expected Output: False

Explanation: Four patients but only slots {1,2,3}: the component has 4 edges and 3 nodes, so two patients must collide — impossible.

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

Expected Output: False

Explanation: Two patients both only want slot 1: a 2-edge, 1-node component (edges > nodes), so they cannot both be seated.

Hints

  1. Treat each patient as an undirected edge between their two preferred slot-nodes.
  2. An assignment exists iff every connected component has at most as many edges (patients) as nodes (distinct slots) — a pseudoforest condition.
  3. Use union-find to group slots into components, then compare each component's edge count against its node count.
Last updated: Jun 25, 2026

Loading coding console...

PracHub

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

Product

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

Browse

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

Support

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

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Solve three algorithmic OA problems - DRW (medium)
  • Compute rolling standard deviation in O(n) - DRW (Medium)
  • Implement portfolio optimization simulation - DRW (Medium)
  • Solve movie ratings, array, release scheduler - DRW (Medium)
  • Solve three algorithmic OA tasks - DRW (Medium)