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

String Rotation

Write a method to check if given a string (S1) there is a way to rotate it so it matches another given string.

What an efficient way of rotating:

String s1 = "erbottlewat"
// so we get S2
String s2 = "waterbottle"

πŸ‘‰ Link here to the repo to solve the problem

imagen

πŸ‘Œ Tips

Remember that concatenating Strings is a very expensive process

Could you use a StringBuilder to optimise the time?

πŸ‘Š Solution 1

This is a fairly easy question, an easy straightforward solution in O(N), would be to iterate from left to right - grabbing each initial letter as a pivot and appending it to the end of the StringBuilder, effectively moving one letter at the time until we see if one combination will match S2.

boolean solution(String s1, String s2) {
    StringBuilder stringBuilder = new StringBuilder();
    String placeHolder = s2;

    for (int i = 0; i < s2.length(); i++) {
      String left = placeHolder.substring(1);
      char right = placeHolder.charAt(0);
      stringBuilder.append(left);
      stringBuilder.append(right);
      placeHolder = stringBuilder.toString();
      stringBuilder.delete(0, stringBuilder.length());
      if (placeHolder.charAt(0) == s1.charAt(0) && placeHolder.equals(s1)) return true;
    }

    return false;
}

Question added by Diego Romero

Last updated on 3/4/2020
← Is UniqueCheck Permutation β†’
  • πŸ‘‰ 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