Dataford
Interview QuestionsInterview GuidesExperiencesMock InterviewsPricing
Get started

Edits Within Two Steps

HardPython00:00
Practice interviewer
In session
5 left
00:00

Your question is Edits Within Two Steps. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

Viasat network diagnostics may compare normalized telemetry tokens that differ because of a single transmission or formatting error. Given two words, determine whether the second can be obtained from the first using fewer than two edits.

An edit is exactly one of the following:

  1. Addition: Insert one character at any position.
  2. Deletion: Remove one character from any position.
  3. Swap: Exchange the characters at any two distinct positions. The positions do not need to be adjacent.

Zero edits is also valid. Character substitutions are not valid unless they are produced by a swap. Return True if the transformation requires zero or one edit, and otherwise return False.

Formal Specification

Implement one_edit_or_swap(word1, word2), where both inputs are strings. Return a boolean. The comparison is case-sensitive, and characters may be any standard string characters.

Constraints

  • 0 <= len(word1), len(word2) <= 100000
  • Inputs contain characters from standard Python strings
  • A swap exchanges exactly two distinct positions
  • Only zero or one allowed edit may be used

Function Signature

def one_edit_or_swap(word1, word2):
Your solutionPython 3
You need to log in / sign up to run or submit.
Run your code to see test output