One-Pass Character Difference | Dataford Interview Questions

BAE Systems USA mission-system software receives two character sequences representing the same telemetry symbols, except the second sequence contains one additional character. The characters may appear in any order and may repeat.

Given arrays first and second, where second contains every character from first plus exactly one additional occurrence, return the extra character. Your solution must use exactly one explicit iteration, must not sort either array, and must use O(1) additional space.

Formal Specification

Input: two arrays of one-character strings, first with length n and second with length n + 1.
Output: the one-character string whose occurrence count is greater in second.
Character comparison is case-sensitive. You may use ord() to convert a character to its integer code point.

Constraints

1 <= len(first) <= 10^5
len(second) == len(first) + 1
Every element is a one-character string
second contains all occurrences from first plus exactly one extra occurrence
The solution must use one loop and O(1) auxiliary space

Function Signature

def find_extra_character(first, second):

Your question is One-Pass Character Difference. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Formal Specification

Input: two arrays of one-character strings, first with length n and second with length n + 1.
Output: the one-character string whose occurrence count is greater in second.
Character comparison is case-sensitive. You may use ord() to convert a character to its integer code point.

Constraints

1 <= len(first) <= 10^5
len(second) == len(first) + 1
Every element is a one-character string
second contains all occurrences from first plus exactly one extra occurrence
The solution must use one loop and O(1) auxiliary space

Function Signature

def find_extra_character(first, second):

Your question is One-Pass Character Difference. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.