Kodr

Kodr

  • Contenido
  • Blog
  • About
  • Languages iconEspañol
    • English

›Problems: Arrays & Strings

Technical Interviews

  • What are technical interviews based on?
  • Contenido esencial y cómo resolver algoritmos

Notación Big-O

  • Notación Big-O
  • Ejemplos Big-O
  • Ejercicios Big-O

Optimisation Techniques

  • Optimización BUD
  • DIY Optimisation

Key Concepts

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

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutacion
  • 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

Escribe una función que remplace todos los espacios en un String por un “%20”. Has de suponer de que el String tiene la longitud suficiente para contener los caracteres adicionales que necesita. Dentro de esta función también se te dará la “longitud verdadera” - esto quiere decir la longitud que tiene el string sin los espacios adicionales.

Por ejemplo si te damos:

String:

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

Deberías de retornar: “Mr%20John%20Smith”

👉 Link aquí hacia el repo para solucionar el problema

imagen

👌 Tips

Muchas veces es mas fácil modificar un String iterando con un loop desde el final hasta el principio

Puede que necesites saber de antemano el numero de espacios que necesitas, podrías simplemente contarlos?

👊 Solución 1

Una forma muy común y eficiente de hacer edición de Strings es editándola comenzando por el final. Esto es bastante util ya que contamos con un cierto “buffer” al final que nos permite editar sin preocuparnos por lo que estamos sobre escribiendo.

En esta solución emplearemos dos "scans” en el primero contaremos los espacios que tenemos en el “trueLength”, si multiplicamos esto por 2 y lo sumamos al trueLength tendremos el length total del String ya con los “%20” añadidos.

En el segundo scan (que se hará de atras hacia adelante) cuando encontremos un espacio añadiremos un “02%”, y si encontramos un carácter simplemente lo copiamos.

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—;
    }
  }
}

Pregunta prestada del libro “Cracking the coding interview”

Last updated on 2/23/2020
← Check PermutacionOne Edit Away →
  • 👉 Link aquí hacia el repo para solucionar el problema
  • 👌 Tips
  • 👊 Solución 1
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr