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

Is Unique

Implementa un algoritmo que determine si en un String todos sus caracteres son unicos.

Una vez lo resuelvas, como lo implementarias si no puedes usar otras estructuras de datos adicionales como Arrays, etc?

👉 Link aquí hacia el repo para solucionar el problema

imagen

👌 Tips

Intenta con un HashTable

Podrias intentarlo con un Bit Vector?

Podrias resolverlo en un tiempo 0(N log N )?

👊 Solución 1

Una solucion muy sencilla seria crear una array de booleans, en donde conseguiriamos la posicion del caracter en el alfabeto, y en esa posicion en el array de booleans lo convertiriamos a true. Si true ya existe en esa posicion del array, significa que hemos repetido de caracter.

boolean isUnique(String s) {
    if (s.length() > 128) return false;

    boolean[] set = new boolean[128];
    for (int i = 0; i < s.length(); i++) {
        int v = s.charAt(i);
        if (set[v]) {
            return false;
        }
        set[v] = true;
    }
    return true;
}

La complejidad en el tiempo de esta solucion es de 0 (N), en donde N es string.length().

👊 Solución 2

Podriamos reducir la utilizacion del espacio usando un BitVector en forma de Int.

Si asumimos que solamente utilizaremos las letras de la "a" a la "z" en minusculas, no necesitaremos mas de 28 banderas, que se encuentran en un Int.

Esta solucion es muy similar a la anterior, pero en vez de un Array con 128 espacios, usamos un BitWise Operator para encender las banderas de 0s a 1s.

boolean isUniqueBitVector(String s) {
    int checker = 0;
    for (int i = 0; i < s.length(); i++) {
        int v = s.charAt(i);
        if ((checker & (1 << v)) > 0) {
            return false;
        }
        checker |= (1 << v);
    }
    return true;
}

Pregunta prestada del libro "Cracking the coding interview”

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