← DocuSign Interview Insights

DocuSign·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

DocuSign software engineer interview, got a graph/union-find problem that I'd seen variants of before but still had to think through carefully. Nothing too surprising about the format.

Questions Asked (1)

Q1

You're given a list of accounts, each with a username and a set of email addresses. Merge any accounts that share at least one email address, since they belong to the same person. Return the merged accounts with emails sorted and the username attached.

Algorithms & Data Structures
Author's notes

I knew union-find was the right move pretty quickly, map every email to a parent, union them when they appear under the same account, then group by root and slap the username back on.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a graph where each email is a node and accounts are connected if they share an email. Use Union-Find (Disjoint Set Union) to efficiently group emails into connected components, then aggregate usernames and sort emails for each component.

Pro tip: Emphasize that Union-Find with path compression and union by rank gives near O(N) time, which is optimal for this problem. Also, mention that you would clarify whether usernames are unique or if multiple usernames can map to the same person, as that affects the merging logic.

1. Clarify requirements and edge cases

Ask about input size, whether usernames are unique, and if emails are case-sensitive. Confirm that merged accounts should have a single username (e.g., the first encountered) and emails sorted lexicographically.

2. Choose data structures

Use a hash map to map each email to its parent account index (for Union-Find) and a hash map to map root to a list of emails. Alternatively, use a graph with DFS/BFS, but Union-Find is more efficient.

3. Implement Union-Find

Initialize each account as its own parent. For each account, union all its emails together by setting the parent of each email's root to the first email's root. Use path compression and union by rank for efficiency.

4. Group emails by root

After processing all accounts, iterate through the email-to-parent map, find the root for each email, and group emails under that root. Also, associate the username of the account that first introduced the root.

5. Format output

For each group, sort the emails, prepend the username, and collect the results. Ensure the output format matches the expected structure (e.g., list of lists with username first).

Key Points to Mention

  • Union-Find (Disjoint Set Union) with path compression and union by rank for near O(N) time complexity.
  • Handling of duplicate emails within the same account and across accounts.
  • Choice of username when merging multiple accounts (e.g., first encountered or any).
  • Time and space complexity analysis: O(N α(N)) time, O(N) space, where N is total number of emails.
  • Edge cases: empty input, accounts with no emails, all accounts sharing one email.
  • Alternative approaches like graph traversal (DFS/BFS) and their trade-offs.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.