Dave Davis

@ddavisgraphics

Pointless? Programming Problems

Pointless or Perfect? That is the war I wage in my head about these types of problems.

Programming challenges, interview questions, and programming brain teasers. In an attempt for personal growth or insight to why these are used so much, especially for interview questions, I’ll be doing challenges from hackerrank.com, googled searches, and maybe even some from your suggestions.

First let me express some of my unadulterated thoughts on these types of problems. Programming challenges like these are often used in interviews in a cryptic way to find out how someone programs. I often find myself in a personal struggle when dealing with these types of problems and most of the time I fear they are pointless and not seen in the real world programming. Also I find when doing them that I learn a lot about certain aspects of the problem and things about my programming style. Typically these types of problems are also handed out in front of a whiteboard, for that I defer to Eric Elliot who says, “Whiteboarding is for drawing not coding.”

For you hiring managers out there, instead of just giving these types of problems to someone on a whiteboard and asking them to solve it, make a suggestion of how you want it solved. In my opinion transparency is best, not hiding what your truly looking for from the question. “Can you solve this problem using arithmetic instead of string comparison?” or “Can you show me how to solve this using regular expressions and pattern matching?” Leaving it open can leave a sour taste in your mouth because that may not be how you would end up with a final solution in the day-to-day work that has to be done. That being said also understand for the interviewee solving the problem in-front of you may be a quick first thought on the problem and not the way they would handle something in a production setting.

This will be my diagnosis one day.

Why did I re-do these problems? I’ve done problems like fizz-buzz, and reversing arrays, finding and replacing values before why waste the time? The shorthand answer is my curiosity. I wanted to not only solve the problems, but also do benchmark testing and apply a test driven approach to solving these problems. Not only am I challenging myself in the interview type of way, but also by seeing which solutions are better and how much better. I’m also building a repertoire should the time come that I need to do various types of mathematical comparisons, string comparisons, or pattern matching for a future endeavor I know which way to jump right off the bat when given a certain type of problem.

Reverse Vowels Problem

This problem requires you to take an input string and reverse the vowels. At first I did this in JavaScript, but didn’t really like it and had no real reason to keep doing it in JS (not that I have a problem with JS), so I moved that over to Ruby for this article. Although the first attempts were pretty much the JavaScript solutions ported to Ruby.

First Attempt

This is my first attempt at the problem, that looked like an exact port over of my JavaScript solution, but in Ruby (this is ugly and not a great solution) and was made slightly better by working from both ends of the string instead of just one way.

class ReverseVowels
# the string that gets reversed
attr_accessor :string_to_reverse
  # init method that sets the string to an instance variable
def initialize(string_to_reverse)
@string_to_reverse = string_to_reverse
end

# method that does all the work
def reverse_vowels
# temp arrays
vowels = []
indexes = []

# iterators for while
i = 0
j = string_to_reverse.length - 1
half_way = (j/2.to_f).ceil

# shorten var name temporarily, maybe more in the future
str = string_to_reverse

# iterate stuff
while i <= half_way && j >= half_way
if is_vowel?(str[i])
indexes << i
vowels << str[i]
end

if is_vowel?(str[j])
indexes << j
vowels << str[j]
end

i += 1
j -= 1
end

indexes = indexes.map(&:to_i).sort
vowels.reverse!

vowels.each_with_index do |v,i|
str[indexes[i]] = v
end

return str
end

# checks the vowels except y
def is_vowel?(character)
vowels = ['a', 'e', 'i', 'o', 'u']
vowels.include? character.to_s.downcase
end
end

Second Attempt

This was my obvious refactor and attempt to remove the number of loops. The tests didn’t change, so a refactor was simple and easy to test. The only method that really cleaned up was the one that reversed the vowels. The thought process that this can be made better by using a loop that meets in the middle and makes the adjustments on the fly.

 def reverse_vowels
# iterators for while
i = 0
j = string_to_reverse.length - 1
str = string_to_reverse

# iterate stuff
while i < j
if !is_vowel?(str[i])
i += 1
next
end
if !is_vowel?(str[j])
j -= 1
next
end

str[i], str[j] = str[j], str[i]

i += 1
j -= 1
end

str
end

Third Attempt

This attempt was by far the shortest, and didn’t require using the is_vowel method. I wish that I had come up with this on my own but I found it while looking at the scan method in ruby api docs. Trying to figure out how to use the scan method, the reverse vowels problem actually came up. This solution was absolutely brilliant and it belongs to the StefanPochmann. The scan method finds the pattern and turns the items into indexed items in an array. Then it uses a gsub regex pattern to put the last item in the array into the first found vowels.

def reverse_vowels    
vowels = @string_to_reverse.scan(/[aeiou]/i)
@string_to_reverse.gsub(/[aeiou]/i) { vowels.pop }
end

Performance Results

Each performance test was done on an iteration of 1000 attempts and three times per run. Each average was created running 3000 attempts of the object.

# First Attempt
# Realtime per 1000 attempts
# ----------------------------------
0.02257158898282796
0.011442353017628193
0.010828958998899907
Average Time: 0.01494763366645202
# Second Attempt
# Realtime per 1000 attempts
# ----------------------------------
0.01959512199391611ms
0.00883392000105232ms
0.008858179993694648ms
Average Time: 0.012429073996221026ms
# Third Attempt
# Realtime per 1000 Attempts
# -----------------------------------
0.017268108000280336ms
0.007276029995409772ms
0.007084235025104135ms
Average Time: 0.010542791006931415ms

The performance results are interesting and each person can interpret these in a different way. Looking at the big picture I don’t think any of these results made a significant difference in speed, but the one that would be easiest to maintain was also the fastest.

Sum Problem

The problem is taking a large number, sum each of its digits and return the value. Although, fairly simple at first I blanked completely on how to break apart this number. My solution for all of these without intervention was to expand to an array, then iterate over the numbers to sum them up. I was informed later, that mathematical programming would be the better way and show serious performance gains.

First Attempt

The wonderful thing about non-strict typings is that I can mangle this into many different types of solutions. The first was to use a string comparison to split the objects into an array and then add them together, returning the sum at the very end. It doesn’t look elegant or saucy, so a definite refactor was in order, but instead of refactoring this how about mathematically?

class Sum
attr_accessor :input
  def initialize(input_num)
@input = input_num
end

def sum_input
digits = @input.to_s.split('')
sum = 0
digits.each do |digit|
sum += digit.to_i
end
sum
end
end

Second Attempt

The second attempt was my attempt at doing it mathematically. I know that our number systems is by tens, so I can pop number off the end by diving it by 10, and I also know that the modulo operator returns the remainder. Using modulo operator I was able to get the numerical value of the first digit, then dividing helped me to remove it from the temporary iterator. This method was a lot easier to figure out with subtle clues and when thinking about numerical problems is something I hope to remember and think about in the future.

class Sum
attr_accessor :input
  def initialize(input_num)
@input = input_num
end

def sum_input
i = @input
sum = 0
while i > 0
sum += (i % 10)
i = (i / 10)
end
sum
end
end

Third Attempt

This attempt was trying to see how small of a method I could create to solve the problem that still passed the tests. There were many 4/5 liners before this one and a few experiments, but this one was the one that I settled on for the smallest attempt.

class Sum
attr_accessor :input
  def initialize(input_num)
@input = input_num
end

def sum_input
digits = @input.to_s.split('')
sum = eval digits.join '+'
end
end

Third Attempt Refactor

The third attempt rated so poorly in the performance tests that I ran the tests several times and went over them for some kind of bug. I thought it would be the same as the first attempt, but instead was by far the slowest. I found that eval is a slow process and after some digging I was pointed to the inject method, which basically sums the contents of an array assuming they are integers. After this refactor the third method was able to achieve similar performance results to the first method and pass all tests.

class Sum
attr_accessor :input

def initialize(input_num)
@input = input_num
end
  def sum_input
digits = @input.to_s.split('').map(&:to_i)
sum = digits.inject(0, :+)
end
end

Performance Results

These were a real eye opener. Each one of these tests are in milliseconds at over 3000 total attempts averaged together with random digits from 1 to 9999999. The mathematic expression was insanely faster, not just a few milliseconds as I expected. Whats worse is the clever shorthand methods that

# First Attempt
# Realtime per 1000 attempts
# ----------------------------------
0.007490240968763828
0.006662635016255081
0.0066195380059070885
Average Time: 0.0069241379969753325
# Second Attempt
# Realtime per 1000 attempts
# ----------------------------------
0.0007742019952274859
0.0007528960122726858
0.0007553229806944728
Average Time: 0.0007608069960648814
# Third Attempt
# Realtime per 1000 Attempts
# -----------------------------------
0.01474869396770373
0.014116039033979177
0.01710168702993542
Average Time: 0.015322140010539442
# Third Attempt (Refactor) 
# Realtime per 1000 Attempts
# -----------------------------------
0.007556420983746648
0.00706747395452112
0.006896736973430961
Average Time: 0.007173543970566243

Conclusion

Wrapping up this process was probably the most difficult for me to swallow, because I’ve already stated that I feel these problems are pointless. Pointless as they may seem, they made me think, learn, and gave some me some go-to answers to use when facing similar problems. If its text-based, regular expressions may prove to be the fastest and easiest to maintain. If it is a numerical problem I should try to figure out a mathematical way to solve the problem.

TL;DR

I’m curious AF and had to look into some coding challenges a little further and will probably be doing more.

More by Dave Davis

Topics of interest

More Related Stories