Assign unique company usernames

Coding Challenges
, , ,
1

Problem. Process username requests from left to right.

  • If a name has not been used before, assign it as-is.
  • Otherwise append the smallest positive integer suffix that makes it unique.

For example:

requests = ["alice", "bob", "alice", "bob", "alice"]

should return

["alice", "bob", "alice1", "bob1", "alice2"]

This is a classic hash map / first-unused suffix problem.

Solution. Maintain:

  • used: every username that has already been assigned
  • next_suffix[name]: the next suffix worth trying for the base name

When a duplicate request arrives, start from next_suffix[name] and advance until the generated username is unused.

def assign_usernames(requests):
	used = set()
	next_suffix = {}
	assigned = []

	for name in requests:
		if name not in used:
			used.add(name)
			next_suffix.setdefault(name, 1)
			assigned.append(name)
			continue

		suffix = next_suffix.get(name, 1)
		candidate = f"{name}{suffix}"

		while candidate in used:
			suffix += 1
			candidate = f"{name}{suffix}"

		used.add(candidate)
		next_suffix[name] = suffix + 1
		next_suffix.setdefault(candidate, 1)
		assigned.append(candidate)

	return assigned

Average runtime is O(n) with hash-table lookups. Extra space is O(n).

Gotchas.

  • Keep the next suffix per base name so you do not restart from 1 every time.
  • Even if the original problem only allows lowercase letters, the while candidate in used guard is still the safe general solution.
  • Process requests in order; the output depends on arrival order.

Run: company usernames