CtCi: Arrays and Strings 1 - No Additional Data Structures

# Dependencies
Mix.install([
  {:heap, "~> 3.0"},
  # visualizations for Livebooks
  {:kino, "~> 0.11.0"},
  # http request library
  {:req, "~> 0.4.4"},
  # Repository data mapper
  {:ecto, "~> 3.10"},
  # GraphQL library
  {:absinthe, "~> 1.7"}
])

# Test Framework
ExUnit.start(autorun: false)

Requirements

Story:

> Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Questions / Clarifications

• “No additional structures” - does that mean one instance of a string, or multiple strings are allowed? what does this mean? Let’s assume we can use strings.

Approach

Brute Force

1. For each characer in string s, iterate through the rest of the characters. if the characters are equal, return false, else continue. if we get through the whole string, return true
   • O(n^2)

Best case would be O(n)… let’s try for something better

boolean flags with a bitstring

1. Create a bitmask

Examples

defmodule Assignment.Fixtures do
  use ExUnit.CaseTemplate

  setup _context do
    %{
      example_false: "example",
      example_true: "abcdefg",
      edge_empty: "",
      edge_nil: nil
    }
  end
end

Implementation

defmodule Assignment do
  import Bitwise

  def run(string) when is_binary(string) do
    # for << char::utf8 <- string >> do
    #   index = rem(char, 97)
    #   test = checker &&& (1 <<< index)
    #   # if (test > 0) do: return false, else:

    #         # // set bit in checker
    #         # checker |= (1 << val);
    # end
    # codepoints = String.graphemes(string)
    case Enum.reduce_while(String.to_charlist(string), 0, &amp;check_unique/2) do
      false -> false
      _ -> true
    end
  end

  defp check_unique(codepoint, checker) do
    index = rem(codepoint, 97)
    test = checker &amp;&amp;&amp; 1 <<< index
    exists_in_checker(test, checker, index) |> IO.inspect(base: :binary)
  end

  defp exists_in_checker(test, _, _) when test > 0, do: {:halt, false}
  defp exists_in_checker(_, checker, index), do: {:cont, checker ||| 1 <<< index}
end

Testing

defmodule Test.Assignment do
  import Assignment
  use ExUnit.Case, async: true
  use Assignment.Fixtures

  describe "Assignment.run/1" do
    test "it returns false for duplicates", %{example_false: example_false} do
      assert run(example_false) == false
    end

    test "it returns true for no duplicates", %{example_true: example_true} do
      assert run(example_true) == true
    end

    test "it returns true for empty", %{edge_empty: edge_empty} do
      assert run(edge_empty) == true
    end

    test "it raises when nil", %{edge_nil: edge_nil} do
      assert_raise FunctionClauseError, "no function clause matching in Assignment.run/1", fn ->
        run(edge_nil)
      end
    end
  end
end

ExUnit.run()

Retrospective

Timeline

Results / Feedback

• 42 minutes over, searching for how to add a guard (use parenthesis around function parameters)
• ignored the “no extra data structures”, but identified half-way through implementation the hashmap was unecessary
• didn’t add testcases out the gate (midway through implementation) *