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:
- counting_letters method is for counting distinct chars
- 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( '({[])', {'(' => ')', '[' => ']', '{' => '}'})}"