May 07, 2022

Improve your problem solving skills

In this post, I would like to give a tip that helped me a lot. If you are at the beginning of your career, is very important to expose yourself to a lot of different problems. A good way to do this is to find a site with algorithm problems. A very good is https://www.beecrowd.com.br. Problems are organized by category and difficulty so you can find a problem that fit your level.

Just an observation and curiosity about myself, when I was in the college this type of site was my passion, at that time I had a team that competed in the national programming contest http://maratona.sbc.org.br, and we used this kind of problem for training.

Today I want to solve a problem and explain how I do this. I selected the problem https://www.beecrowd.com.br/judge/en/problems/view/1255. This is a problem involving string manipulation.

The Problem

➡️ Given a string you should output the letter that has the most frequency, if there are ties, output all letters in alphabetical order. Some examples

INPUT: Computers account for only 5% of the country's commercial electricity consumption.
OUTPUT: co

INPUT: frequency letters 
OUTPUT: e

Solution

The first thing that I will do is create a file containing the input described in the problem:
problem.in

3
Computers account for only 5% of the country's commercial electricity consumption.
Input
frequency letters

After that, I will create the structure to work with this input, and just print some information to validate that my code is correct:

n = gets.chomp.to_i
n.times do
  line = gets.chomp
  puts "LINE: #{line}"
end

Running:

ruby problem.rb < problem.in
LINE: Computers account for only 5% of the country's commercial electricity consumption.
LINE: Input
LINE: frequency letters

Great, right now I have a simple code that correctly reads the input. The first step was ok 🥳.

The second and most important step is to create an algorithm to solve the problem, there are a few different approaches, and I will share my solution to this problem using ruby. Remember that you use your favorite language, there are many options on the site:

n = gets.chomp.to_i
n.times do
  line = gets.chomp

  # According to the description, we must consider only the 26 letters of the alphabet in lower case
  parsed_line = line.downcase.gsub(/[^a-z]/, '') 
  
  # We should count the number of each letter (In my first option I was using reduce but I got time limit exceed)
  indexed = {}
  parsed_line.chars.each do |char|
    indexed[char] = indexed[char].to_i.next
  end
  # {
  #   "e" => 10,
  #   "c" => 5,
  # }

  # It is in this step that we get the number of the letter that appears most
  maximum_value = indexed.values.max

  # Now we select only the letters that have the highest frequency of appearance
  result = indexed.select { |key, value| value == maximum_value }.keys.sort.join

  puts result
end

The best feature of contest sites is that you submit your code and the site evaluates and responds if is correct or not. Remember that the site has a larger input cases than the example.

I sent the code and received SUCCESS 🎇

Mateus Nava

Improve your problem solving skills

The Problem

Solution