"Balance" Coding Challenge
Tue 26 Feb 2019

Requirement: Check if the input string has balanced chars. More details please have a look at the "Result" section below. This a an interview challenge in "XYZ" company.

1. Solution.

I apply single responsibility principle:

isBalanced method involves: 

  1. counting_letters method is for counting distinct chars
  2. balance? method is for checking the result.
class Balance

  def isBalanced(str, opts = {})
    return if str == ''
    letters = count_letters(str)

    if block_given?
      yield(letters)
    else
      first = opts[:first] || '('
      second = opts[:second] || ')'
      balance?(letters, first, second)
    end
  end

  private

  def count_letters(str)
    pattern = {}
    str.chars.each do |char|
      pattern[char] = (pattern[char] || 0) + 1
    end
    pattern
  end

  def balance?(letters, first, second)
    letters[first] == letters[second]
  end
end

I found that the validation would be changed in future so I allowed to input a block (additional validation).

2. Extending the functionality

class MultBalance < Balance
  # patterns = {'(' => ')', '[' => ']', '{' => '}'}
  def areBalanced(str, patterns)
    isBalanced(str) do |letters|
      patterns.each do |first, second|
        return false unless balance?(letters, first, second)
      end
    end
    true
  end
end

I extend the functionality by using inheritance. Adding more steps to isBalanced by using block. 

isBalanced(str) do |letters|
  patterns.each do |first, second|
    return false unless balance?(letters, first, second)
  end
end

Now we can do more with isBalanced without making any changes on legacy code (Balance class). Actually, if we override the whole isBalanced method, it's still Open/Close principle. Because we don't make any changes on legacy code but we expand the functionality. The other legacy codes which involve this isBalanced method is still working correctly. Using inheritance is Open/Close principle as well. We add extra method, expanding the behaviors without changing any legacy code.

Applying single responsibility makes our code readable. The method name is also important. 

The complexity is O(n).

3. Result

balance = MultBalance.new
puts "()()()()()(: #{balance.isBalanced( '()()()()()(')}"
puts "[][][][]:    #{balance.isBalanced( '[][][][]', {first: '[', second: ']'})}"

puts "({[]}):      #{balance.areBalanced( '({[]})', {'(' => ')', '[' => ']', '{' => '}'})}"
puts "({[]):       #{balance.areBalanced( '({[])', {'(' => ')', '[' => ']', '{' => '}'})}"

Console:

()()()()()(: false
[][][][]: true
({[]}): true
({[]): false

Full code:

# Challence:
# isBalanced( “()()()()()(” ); // false
# isBalanced( “(()()()()())” ); // true

class Balance

  def isBalanced(str, opts = {})
    return if str == ''
    letters = count_letters(str)

    if block_given?
      yield(letters)
    else
      first = opts[:first] || '('
      second = opts[:second] || ')'
      balance?(letters, first, second)
    end
  end

  private

  def count_letters(str)
    pattern = {}
    str.chars.each do |char|
      pattern[char] = (pattern[char] || 0) + 1
    end
    pattern
  end

  def balance?(letters, first, second)
    letters[first] == letters[second]
  end
end

class MultBalance < Balance
  # patterns = {'(' => ')', '[' => ']', '{' => '}'}
  def areBalanced(str, patterns)
    isBalanced(str) do |letters|
      patterns.each do |first, second|
        return false unless balance?(letters, first, second)
      end
    end
    true
  end
end

balance = MultBalance.new
puts "()()()()()(: #{balance.isBalanced( '()()()()()(')}"
puts "[][][][]:    #{balance.isBalanced( '[][][][]', {first: '[', second: ']'})}"

puts "({[]}):      #{balance.areBalanced( '({[]})', {'(' => ')', '[' => ']', '{' => '}'})}"
puts "({[]):       #{balance.areBalanced( '({[])', {'(' => ')', '[' => ']', '{' => '}'})}"