Search⌘ K
AI Features
Home
Courses
Decode the Coding Interview in Elixir: Real-World Examples

Feature #6: Most Common Token

Explore how to analyze a program's code string to find the most common variable or function name, excluding language keywords and syntax. Learn to normalize code, count token frequencies, and apply efficient algorithms with O(n + m) time and space complexity to solve this compiler feature problem.

We'll cover the following...

Description

For this feature of the language compiler, the program statements are given to us as a string. We want to determine the variable or function that is most commonly referred to in a program. In this process, we want to ignore the language keywords. For example, a keyword may be used more frequently than any variable or function. The language keywords are given as an array of strings.

Let’s say you are given the following program as input:

C++
int main() {
  int value = getValue();  
  int sum = value + getRandom();
  int subs = value - getRandom();
  return 0;
}

The list of keywords given to you is ["int", "main", "return"]. In this example, your function will return "value". Note that, your functions should ignore syntax, such as parentheses, operators, semicolons, etc.

Solution

We can solve this problem by normalizing the code string and processing it step by step. The complete algorithm is as follows:

  • First, we replace all the syntax, including parentheses, operators, semicolons, etc., with spaces. Now, the string only contains alphanumeric tokens.

  • Then, we split the code obtained from the previous step into tokens.

  • We iterate through the tokens to count the appearance of each unique token as keys, excluding the keywords.

  • We create a hash map count, which has tokens as keys and occurrences as values.

  • In the end, we check the tokens in count to find the token with the highest frequency.

Elixir
defmodule Compiler do
  def isalnum?(c), do: String.match?(c, ~r/^[[:alnum:]]+$/)
  def most_common_token(code, keywords) do
    # Replacing the syntax with spaces
    tokens = 
      code 
      |> String.graphemes
      |> Enum.map(fn c -> if isalnum?(c), do: String.downcase(c), else: " " end) 
      |> Enum.join("")
      |> String.split(" ", trim: true)
    count = %{}
    banned_words = MapSet.new(keywords)
    # Count occurrence of each token, excluding the keywords
    tokens
    |> Enum.reduce(count, fn(token, count) ->
      cond do
        !MapSet.member?(banned_words, token) -> Map.put(count, token, Map.get(count, token, 0) + 1)
        true -> count
      end 
    end)
    |> Enum.max_by(&elem(&1, 1))
    |> elem(0)
  end
end
# Driver code
IO.puts "-----------------------------"
IO.puts "PROGRAM OUTPUT:"
code = "int main() {
  int value = getValue();  
  int sum = value + getRandom();
  int subs = value - getRandom();
  return 0;
}"
keywords = ["int", "main", "return"]
IO.inspect Compiler.most_common_token(code, keywords)

Complexity measures

Time complexity Space complexity
...