Solve Morse and Network Access Tasks
Company: Oscar
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Solve the following two independent coding problems.
### Problem 1: Convert Between Text and Morse Code
You are given the standard Morse-code mapping for lowercase English letters:
- a: .-
- b: -...
- c: -.-.
- d: -..
- e: .
- f: ..-.
- g: --.
- h: ....
- i: ..
- j: .---
- k: -.-
- l: .-..
- m: --
- n: -.
- o: ---
- p: .--.
- q: --.-
- r: .-.
- s: ...
- t: -
- u: ..-
- v: ...-
- w: .--
- x: -..-
- y: -.--
- z: --..
Given a string consisting only of lowercase English letters, return the concatenated Morse-code representation of the string.
Example:
Input: `"gin"`
Output: `"--...-."`
Follow-up: Given a Morse-code string with no separators between letters, generate all possible original lowercase strings that could have produced it.
### Problem 2: Find Members Without Adequate Provider Access
You are given:
- A list of providers, where each provider has an `id`, `specialty`, and 2D `location`.
- A list of members, where each member has an `id`, 2D `location`, and a list of `required_specialties`.
- A `max_distance` value.
A member has adequate network access if, for every specialty they require, there is at least one provider of that specialty within `max_distance` of the member. Use Euclidean distance between locations.
Return the list of member IDs who do not have adequate network access.
Example:
```text
providers = [
{"id": 1, "specialty": "Cardiology", "location": (1, 2)},
{"id": 2, "specialty": "Dermatology", "location": (3, 4)}
]
members = [
{"id": 101, "location": (2, 3), "required_specialties": ["Cardiology", "Dermatology"]},
{"id": 102, "location": (10, 10), "required_specialties": ["Cardiology"]}
]
max_distance = 5
```
Output:
```text
[102]
```
Quick Answer: This question evaluates string encoding/decoding and combinatorial parsing skills (Morse code conversion and ambiguous decoding) alongside spatial search and filtering competencies for proximity-based access checks, testing algorithmic reasoning, pattern recognition, backtracking possibilities, distance computation, and data-structure use.
Text to Morse Code
You are given the standard Morse-code mapping for the 26 lowercase English letters:
```
a .- b -... c -.-. d -.. e . f ..-.
g --. h .... i .. j .--- k -.- l .-..
m -- n -. o --- p .--. q --.- r .-.
s ... t - u ..- v ...- w .-- x -..-
y -.-- z --..
```
Given a string `s` consisting only of lowercase English letters, return the concatenated Morse-code representation of the string (no separators between letters).
**Example**
```
Input: s = "gin"
Output: "--...-."
```
Explanation: g = `--.`, i = `..`, n = `-.`, concatenated gives `--...-.`.
Constraints
- 0 <= len(s) <= 10^5
- s consists only of lowercase English letters 'a'-'z'.
- The empty string maps to the empty string.
Examples
Input: ("gin",)
Expected Output: "--...-."
Explanation: g=--. , i=.. , n=-. concatenated.
Input: ("",)
Expected Output: ""
Explanation: Empty input yields empty output.
Input: ("e",)
Expected Output: "."
Explanation: Single letter e maps to a single dot.
Input: ("sos",)
Expected Output: "...---..."
Explanation: s=... o=--- s=...
Input: ("abz",)
Expected Output: ".--...--.."
Explanation: a=.- b=-... z=--.. concatenated.
Hints
- Store the 26-letter mapping in a dictionary/array, then look up each character.
- Concatenate the per-letter Morse codes directly; there are no separators between letters.
Decode Morse Code (All Possible Words)
This is the follow-up to the Text-to-Morse problem. Because the Morse string has **no separators** between letters, a single Morse string may decode to many different lowercase strings.
Given a Morse-code string `code` made up only of `.` and `-`, return **all** lowercase strings that could have produced it, using the standard 26-letter mapping (each letter's code is between 1 and 4 symbols long). Return the results **sorted** in ascending (lexicographic) order. If the string cannot be fully decoded, return an empty list. The empty Morse string decodes to the single empty string `""`.
**Example**
```
Input: code = ".-"
Output: ["a", "et"]
```
Explanation: `.-` is the code for `a`; it can also be split as `.` (e) + `-` (t) giving `et`.
Constraints
- 0 <= len(code) <= ~40 (exponential blow-up makes very long inputs impractical to fully enumerate).
- code consists only of the characters '.' and '-'.
- Each letter's Morse code is 1 to 4 symbols long.
- Return results sorted in ascending lexicographic order; the empty code returns [""].
Examples
Input: (".-",)
Expected Output: ["a", "et"]
Explanation: .- = a, or . (e) + - (t) = et.
Input: ("",)
Expected Output: [""]
Explanation: Empty code decodes to the single empty string.
Input: (".",)
Expected Output: ["e"]
Explanation: . is only the code for e.
Input: ("...",)
Expected Output: ["eee", "ei", "ie", "s"]
Explanation: ... = s; .+.. = e+i; ..+. = i+e; .+.+. = eee.
Input: ("--",)
Expected Output: ["m", "tt"]
Explanation: -- = m, or - (t) + - (t) = tt.
Hints
- Build a reverse map from each Morse pattern (length 1..4) to its letter, then DFS/backtrack over split points.
- At each position try every prefix of length 1 to 4; if it's a valid letter code, recurse on the remainder.
- Sort the final list so the output is deterministic, and remember the empty string decodes to [""].
Members Without Adequate Provider Access
You manage a healthcare network of providers and members.
Each **provider** has a specialty and a 2D location. Each **member** has an id, a 2D location, and a list of required specialties. A member has **adequate network access** if, for **every** specialty they require, there is at least one provider of that specialty whose location is within `max_distance` (Euclidean distance, inclusive) of the member.
Return the list of member ids who do **not** have adequate access, in the same order the members are given.
To keep the signature language-agnostic, the data is passed as parallel arrays:
- `provider_specialties[j]` / `provider_x[j]` / `provider_y[j]` describe provider j.
- `member_ids[i]` / `member_x[i]` / `member_y[i]` / `member_required[i]` (a list of specialty strings) describe member i.
- `max_distance` is the inclusive radius.
**Example**
```
provider_specialties = ["Cardiology", "Dermatology"]
provider_x = [1, 3]; provider_y = [2, 4]
member_ids = [101, 102]
member_x = [2, 10]; member_y = [3, 10]
member_required = [["Cardiology", "Dermatology"], ["Cardiology"]]
max_distance = 5
Output: [102]
```
Explanation: member 101 is within 5 of both a Cardiology and a Dermatology provider; member 102 at (10,10) is ~12.04 away from the only Cardiology provider, so it lacks access.
Constraints
- 0 <= number of providers, members.
- Use Euclidean distance; a provider exactly at distance == max_distance counts as within range (inclusive).
- A member that requires no specialties always has adequate access.
- Compare squared distances against max_distance squared to avoid floating-point sqrt error.
Examples
Input: (["Cardiology", "Dermatology"], [1.0, 3.0], [2.0, 4.0], [101, 102], [2.0, 10.0], [3.0, 10.0], [["Cardiology", "Dermatology"], ["Cardiology"]], 5.0)
Expected Output: [102]
Explanation: 101 reaches both specialties within 5; 102 is ~12.04 from the only Cardiology provider.
Input: ([], [], [], [201], [0.0], [0.0], [["Cardiology"]], 5.0)
Expected Output: [201]
Explanation: No providers at all, so the member requiring Cardiology lacks access.
Input: (["Cardiology"], [0.0], [0.0], [301], [0.0], [0.0], [[]], 1.0)
Expected Output: []
Explanation: A member requiring no specialties always has adequate access.
Input: (["Cardiology"], [3.0], [4.0], [401], [0.0], [0.0], [["Cardiology"]], 5.0)
Expected Output: []
Explanation: Distance is exactly 5 (== max_distance), which is inclusive, so access is adequate.
Input: (["X"], [0.0], [0.0], [501, 502], [0.0, 100.0], [0.0, 100.0], [["X"], ["X"]], 5.0)
Expected Output: [502]
Explanation: 501 is co-located with the provider; 502 at (100,100) is far out of range.
Hints
- A member lacks access if there exists at least one required specialty with no in-range provider.
- Compare squared Euclidean distance to max_distance squared so you never call sqrt.
- Treat the boundary as inclusive: distance == max_distance still counts as in range. An optional speed-up is to group providers by specialty first.