# One Edit Distance - Amazon Top Interview Questions

### Problem Statement :

```Given two strings s0 and s1 determine whether they are one or zero edit distance away. An edit can be described as deleting a character, adding a character, or replacing a character with another character.

Constraints

n ≤ 100,000 where n is the length of s0.
m ≤ 100,000 where m is the length of s1.

Example 1

Input

s0 = "quicksort"

s1 = "quicksort"

Output

True

Explanation

This has the edit distance of 0, since they are the same string.

Example 2

Input

s0 = "mergesort"

s1 = "mergesorts"

Output

True

Explanation

This has the edit distance 1, since s was added to the second string.
Example 3

Input

s0 = "mergeport"

s1 = "mergesorts"

Output

False

Explanation

This has edit distance of 2.```

### Solution :

```                        ```Solution in C++ :

bool equal(string& s0, int i, string& s1, int j) {
while (i < s0.size() && j < s1.size() && s0[i] == s1[j]) {
i++, j++;
}
return i == s0.size() && j == s1.size();
}

bool solve(string s0, string s1) {
int m = s0.size(), n = s1.size();
if (m > 1 + n || n > 1 + m) return false;
for (int i = 0; i < min(m, n); i++) {
if (s0[i] != s1[i])
return equal(s0, i + 1, s1, i) || equal(s0, i, s1, i + 1) ||
equal(s0, i + 1, s1, i + 1);
}
return true;
}```
```

```                        ```Solution in Java :

class Solution {
public boolean solve(String s0, String s1) {
int m = s0.length(), n = s1.length();
if (Math.abs(m - n) > 1) {
return false;
}

int i = 0, j = 0, edit = 0;
while (i < m && j < n) {
if (s0.charAt(i) != s1.charAt(j)) {
edit += 1;
if (m < n) {
i--;
} else if (m > n) {
j--;
}
}
i++;
j++;
}
return (edit < 2);
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, s0, s1):
# Get dimensions
n = len(s0)
m = len(s1)

# Ensure n < m
if m < n:
return self.solve(s1, s0)

# Check if length diff is > 1
if abs(n - m) > 1:
return False

# index i -> s0, index j -> s1
i = 0
j = 0
edits = 0
while i < n:
# chars match, increment i, j :D
if s0[i] == s1[j]:
i += 1
j += 1
# mismatch, count edit >:(
else:
edits += 1

# same length, replace char in s0, move i, j
if n == m:
i += 1
j += 1
# not same length, delete char from s1 by moving j
else:
j += 1

# too many edits, terminate
if edits > 1:
break

# 1 edit or less?
return edits <= 1```
```

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element