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

Is Unique

Implement an algorithm that determines if all characters in a String are unique.

Once you solve it, how would you implement it if you can't use other additional data structures like Arrays, etc?

πŸ‘‰ Link here to the repo where you can solve the problem

imagen

πŸ‘Œ Tips

Try a HashTable

Could you try it with a BitVector?

Could you solve it in a time 0(N log N)?

πŸ‘Š Solution 1

A very simple solution would be to create an array of booleans, where we would get the character's position in the alphabet, and in that position in the booleans array we would convert it to true. If true already exists in that array position, it means that we have repeated character.

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

The complexity of this solution is 0(N), where N is string.length().

πŸ‘Š Solution 2

We could reduce the use of space using a BitVector in the form of an Int.

If we assume that we will only use the letters "a" to "z" in lowercase letters, we will not need more than 28 flags, which are in an Int (28 bits).

This solution is very similar to the previous one, but instead of an Array with 128 spaces, we use a BitWise Operator to light the flags from 0s to 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;
}

Borrowed question from the book "Cracking the coding interview"

Last updated on 3/3/2020
← Dynamic ProgrammingString Rotation β†’
  • πŸ‘‰ Link here to the repo where you can solve the problem
  • πŸ‘Œ Tips
  • πŸ‘Š Solution 1
  • πŸ‘Š Solution 2
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright Β© 2021 Kodr