Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Problems: Arrays & Strings

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

One Edit Away

There are three types of edits that can be made in a String: insert a character, delete a character or replace a character. Given two Strings, write a function to verify if they are one edition (or zero editions) away. For example:

EXAMPLE
    
pale, ple -> true 
pales, pale -> true 
pale, bale -> true 
pale, bake -> false 

👉 Link here to the repo to solve the problem

imagen

👌 Tips

Start with something simple. Can you check each of the conditions you need separately?

What is the relationship between the options to insert and remove characters? Do you think they have to be on separate checkups?

Could you do all three checks at once?

👊 Solution 1

To understand this problem well it is important to know the difference between the 3 different operations with which we can know if the Strings are at 0 or 1 edition.

  • Replace: If we change 1 character from "bale" to "pale" we know that they are only different in one place.
  • Insert: If we insert a character from “aple” to “apple” we know that they are only 1 character apart.
  • remove: the same as the previous one - if we remove a character from “apple” to “aple” we know that they are 1 character away.

Then we can begin to develop functions that will help us for each of these scenarios:

boolean solution(String s1, String s2) {
  int s1Length = s1.length();
  int s2Length = s2.length();

  // should also perform checks to see if the strings lengths are in the valid “range”
  if (s1Length == s2Length) {
    return oneReplaceAway(s1, s2);
  } else if (s1Length > s2Length) {
    return oneInsertAway(s1, s2);
  } else if (s2Length > s1Length) {
    return oneInsertAway(s2, s1);
  }
  return false;
}

private boolean oneReplaceAway(String s1, String s2) {
  boolean difference = false;
  for (int I = 0; I < s1.length(); I++) {
      char c1 = s1.charAt(i);
      char c2 = s2.charAt(i);
      if (c1 != c2) {
        if ( difference) return false;
        difference = true;
      };

  }
  return true;
}

private boolean oneInsertAway(String s1, String s2) {
  ArrayList<Character> s1Chars = Utils.stringToCharArrayList(s1);
  ArrayList<Character> s2Chars = Utils.stringToCharArrayList(s2);
  boolean difference = false;

  for (int i = 0; i < s2.length(); i++) {
    char c1 = s1Chars.get(i);
    char c2 = s2Chars.get(i);

    if (c1 != c2) {
      if (difference) return false;
      s1Chars.remove(i);
      i--;
      difference = true;
    }
  }
  return true;
}

If you realize "oneInsertAway" can also be used to "remove" because you can simply invert the Strings that are being passed to the function to know if they are to an insert instead of "oneRemovalAway".


Borrowed question from the book “Cracking the coding interview”

Last updated on 3/3/2020
← URLifyString Compression →
  • 👉 Link here to the repo to solve the problem
  • 👌 Tips
  • 👊 Solution 1
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr