Bubble Sort

Write a function ‘bubble_sort(arr)’ which will sort an array of integers using the “bubble sort” methodology.  (http://en.wikipedia.org/wiki/Bubble_sort)

Solution:

First and foremost, understand the difference between insertion sort and bubble sort.

Insertion sort:  Faster because it compares a value against the entire array and places it in the right location in one go.  (The .sort method does this).

insertion-sort-example

Bubble sort: Slower because it compares only against the next index, thus resulting in more comparison steps before ending up in the right location.

bubble-sort

screen-shot-2016-11-30-at-5-16-06-pm

Test Cases:

screen-shot-2016-11-30-at-5-16-34-pm

 

Advertisements
Bubble Sort

Rectangle Intersection

Write a function, `rec_intersection(rect1, rect2)` and returns the intersection of the two.

Rectangles are represented as a pair of coordinate-pairs: the bottom-left and top-right coordinates (given in `[x, y]` notation).

Hint: You can calculate the left-most x coordinate of the intersection by taking the maximum of the left-most x coordinate of each rectangle. Likewise, you can calculate the top-most y coordinate of the intersection by taking the minimum of the top most y coordinate of each rectangle.

This is probably the hardest problem I’ve encountered do date.  It’s a bit more logic than math and I definitely overcomplicated it by trying to make sense of it with math, which is not my strength..

Some helpful things to remember:

  • Plot out the coordinates and draw the rectangles on a piece of paper first.
  • Try not to confuse the (x,y) coordinates with arrays.  (This part tripped me up the most).
  • The trick is to use max and min to get the left and right coordinates of the intersection, respectively.   (This is a bit counterintuitive).
  • To access a value of a multidimensional array, use a[i][j], where i is the index of a, and j is the index of a[i] array.

Anyways, here’s the solution with my annotated comments:

screen-shot-2016-11-30-at-2-38-20-pm

Test Cases: 

Screen Shot 2016-11-30 at 2.37.47 PM.png

Rectangle Intersection

Word Unscrambler

Write a function word_unscrambler that takes two inputs: a scrambled word and a dictionary of real words. Your program must then output all words that our scrambled word can unscramble to.

Hint: To see if a string `s1` is an anagram of `s2`, split both strings into arrays of letters. Sort the two arrays. If they are equal, then they are anagrams.

My solution: 

screen-shot-2016-11-29-at-6-45-34-pm

Provided solution: 

screen-shot-2016-11-29-at-6-46-52-pm

Test Cases: 

screen-shot-2016-11-29-at-6-46-13-pm

 

Word Unscrambler

Morse Code

Build a function, ‘morse_encode(str)’ that takes in a string (no numbers or punctuation) and outputs the morse code for it. See http://en.wikipedia.org/wiki/Morse_code. Put two spaces between words and one space between letters.

You’ll have to type in morse code: I’d use a hash to map letters to codes. Don’t worry about numbers.

My solution:

I learned the difference between global variables and Ruby constants while solving this problem.  They both serve similar purposes but global variables’ values can be changed while Ruby constants cannot.  Also, constants are written in all uppercase and global variables start with “$”.

Another thing to remember is how to retrieve key/value from hash.  Here’s a handy cheat sheet of shortcuts for Ruby hashes.

screen-shot-2016-11-29-at-5-48-39-pm

Test Cases: 

screen-shot-2016-11-29-at-5-41-43-pm

Morse Code

Wonky Coins

Catsylvanian money is a strange thing: they have a coin for every denomination (including zero!). A wonky change machine in Catsylvania takes any coin of value N and returns 3 new coins, valued at N/2, N/3 and N/4 (rounding down).

Write a method `wonky_coins(n)` that returns the number of coins you are left with if you take all non-zero coins and keep feeding them back into the machine until you are left with only zero-value coins.

Test Cases:

puts wonky_coins(1).should == 3
puts wonky_coins(5).should ==  11
# => [2, 1, 1]
# => [[1, 0, 0], [0, 0, 0], [0, 0, 0]]
# => [[[0, 0, 0], 0, 0], [0, 0, 0], [0, 0, 0]]
puts wonky_coins(6).should == 15
puts wonky_coins(0).should == 1

My solution (w/ arrays and recursion): 

screen-shot-2016-11-28-at-10-25-19-pm

Jimmy’s solution (w/o recursion): 

The idea is you draw a coin from a pouch (array).  If the coin is 0, count it.  If it’s not, redraw another coin until the pouch is empty.

screen-shot-2016-11-28-at-10-25-36-pm

Provided solution (w/ recursion):

screen-shot-2016-11-28-at-10-25-46-pm

Wonky Coins

Ordered Vowels

Write a method, ‘ordered_vowel_words(str)’ that takes a string of
lowercase words and returns a string with just the words containing
all their vowels (excluding “y”) in alphabetical order. Vowels may
be repeated (“afoot” is an ordered vowel word).

You will probably want a helper method, ‘ordered_vowel_word?(word)’
which returns true/false if a word’s vowels are ordered.

Solution:

screen-shot-2016-11-21-at-6-12-18-pm

Surprisingly, it’s the helper function that was the challenge in this problem.  The trick is to create an array of all the vowels in the alphabet (except “y”). To check if each word has its vowels in order, split the word into letters, and then use .include? to check if those letters are included in the vowel array.

Test Cases:

screen-shot-2016-11-21-at-6-15-29-pm

Ordered Vowels

Letter Count

Write a function, ‘letter_count(str)’ that takes a string and
returns a hash mapping each letter to its frequency. Do not include
spaces:

Test Cases:

screen-shot-2016-11-18-at-5-42-12-pm

My Solution:

screen-shot-2016-11-21-at-12-37-37-pm

Runtime:  0.00059 seconds

Provided Solution:

Screen Shot 2016-11-21 at 12.38.20 PM.png

Runtime:  0.00053 seconds

By using each_char (an enumerator), you’re able to skip splitting the string into words and then into letters. Instead, you can directly pull letters from the string as is.

Letter Count