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

URLify

Write a function that replaces all spaces in a String with a "%20". You have to assume that the String is long enough to contain the additional characters it needs. Within this function you will also be given the "true length" - this means the length of the string without the additional spaces.

For example if we give you:

String:

String s = "Mr John Smith    ";
int TrueLength = 13;

It should return:

"Mr%20John%20Smith"

👉 Link here to the repo where you can solve the problem

imagen

👌 Tips

Many times it is easier to modify a String iterating with a loop from the end to the beginning

You may need to know in advance the number of spaces you need, could you simply count them?

👊 Solution 1

A very common and efficient way to edit Strings is to edit it starting at the end. This is quite useful since we have a certain “buffer” at the end that allows us to edit without worrying about what we are writing about.

In this solution we will use two "scans" in the first we will count the spaces that we have in the "trueLength", if we multiply this by 2 and add it to trueLength we will have the total length of the String already with the "% 20" added.

In the second scan (which will be done backwards) when we find a space we will add a “02%”, and if we find a character we simply copy it.

public void solution(char[] str, Integer trueLength) {
  int spaceCount = 0, index;

  for (int i = 0; i < trueLength; i++) {
    if(str[i] == ' ') spaceCount++;
  }

  index = trueLength + (spaceCount * 2);
  if (trueLength < str.length) str[trueLength] = '\0'; // end array

  for (int i = trueLength - 1; i >= 0; i--) {
    if (str[I] == ' ') {
      str[index - 1] = '0';
      str[index - 2] = '2';
      str[index - 3] = '%';
      index = index - 3;
    } else {
      str[index - 1] = str[i];
      index--;
    }
  }
}

Borrowed question from the book “Cracking the coding interview”

Last updated on 3/3/2020
← Check PermutationOne Edit Away →
  • 👉 Link here to the repo where you can 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