30 Days of Algorithms — December 2017

It’s my last post of the year and it’s been satisfying to look back at what I’ve learned in the past 12 months. I’ve built a couple of apps, completed a few coding challenges, learned another language, and solved hundreds of white-boarding problems. There’s still a lot to learn and I have been trying not to get down on myself for not learning as quickly as I hope to.

One thing I’d like to note is that while I was previously solving these white-boarding problems in Swift, I’ve learned C# and December’s problems were completed entirely in C#. Additionally, I’ve been practicing how to write unit tests for these in Visual Studio, so for each of these problems below, I wrote a unit test. Yay, testing life!

Things I have learned/discovered by solving algos in C#:

• Writing unit tests is helpful and satisfying (when they pass :-).
• Arrays in Swift appear to be mutable and in C#, Lists have the same functionality (i.e. .Append() vs. .Add()).
• Recursion can be utilized if you consider the “base case” that each problem eventually heads toward.
• Understanding how the call stack works can help you understand how recursion works — they go hand in hand.

Dec 1 — Alternating Sums (CodeFights)

Several people are standing in a row and need to be divided into two teams. The first person goes into team 1, the second goes into team 2, the third goes into team 1 again, the fourth into team 2, and so on. You are given an array of positive integers - the weights of the people. Return an array of two integers, where the first element is the total weight of team 1, and the second element is the total weight of team 2 after the division is complete.

Dec 2 — Are Triangles Similar (CodeFights)

You have two triangles A1B1C1 and A2B2C2 on a plane. Your task is to determine whether they are rather similar, i.e. if their corresponding angles have the same measurements.       
In order for two triangles to be rather similar, the following equations must be true:        
angle(A1B1, B1C1) = angle(A2B2, B2C2)        
angle(A1C1, C1B1) = angle(A2C2, C2B2)        
angle(B1A1, A1C1) = angle(B2A2, A2C2)        
where angle(AB, CD) refers to an angle between segments AB and CD in the triangle.        
Example        
For coordinates = [0, 0, 0, 1, 1, 0, 0, 0, 0, -3, -3, 0], the output should be        
areTrianglesSimilar(coordinates) = true.

Dec 3 — Check Same Element Existence (CodeFights)

Given two sorted arrays of integers, check if there is at least one element which occurs in both arrays.        
Example        
For arr1 = [1, 2, 3, 5] and arr2 = [1, 4, 5], the output should be        checkSameElementExistence(arr1, arr2) = true;        
For arr1 = [1, 3, 5] and arr2 = [-2, 0, 2, 4, 6], the output should be        
checkSameElementExistence(arr1, arr2) = false.

Dec 4 — Extract Each Kth (CodeFights)

Given array of integers, remove each kth element from it.        Example 2, 5, 8        
For inputArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and k = 3,         the output should be        
extractEachKth(inputArray, k) = [1, 2, 4, 5, 7, 8, 10].

Dec 5 — Fill Room With Boxes (from colleague)

1. Write a function called FillRoomWithBoxes that takes in an int called roomSize, a List<int> called possibleSizes, and a List<int> called boxes.        
  a. The possibleSizes list should contain all possible box sizes.You can assume this list is sorted in descending order. 
       
2.The function should implement a greedy recursive algorithm to        fill the room as full as it can get with the least number of boxes,         and should store the size of each box used in the boxes list, one entry per box        
  a.For example, if your possible sizes list contained 7, 3, 1, and your roomSize was 25, the boxes list should contain 7, 7, 7, 3, 1 when your function exits

Dec 6 — Fraction Comparison (CodeFights)

Compare the two given fractions.
Example

• For a = [3, 4] and b = [6, 8], the output should be
  fractionComparison(a, b) = '=';
• For a = [3, 2] and b = [2, 5], the output should be
  fractionComparison(a, b) = '>';
• For a = [3, 5] and b = [2, 3], the output should be
  fractionComparison(a, b) = '<'.

Dec 7 — Get Sum Between Numbers (from colleague)

Write a function called GetSumBetweenNumbers that takes in an int min and an int max and returns an int. The function should get the sum of all the numbers between (and including) min and max. The function should solve the problem using iteration. If min > max, the function should return 0. Solve the problem using recursion and test it.

Dec 8 — High Entropy Passphrases (CodeFights)

A new system policy has been put in place that requires all accounts to use a passphrase instead of simply a password. A passphrase consists of a series of words (lowercase letters) separated by spaces.  To ensure security, a valid passphrase must contain no duplicate words.    
For example:    
aa bb cc dd ee is valid.    
aa bb cc dd aa is not valid - the word aa appears more than once.    aa bb cc dd aaa is valid - aa and aaa count as different words.    The system's full passphrase list is available as your puzzle input. How many passphrases are valid?

Dec 9 — House Number Sum (CodeFights)

A boy is walking a long way from school to his home.  
To make the walk more fun he decides to add up all the numbers         of the houses that he passes by during his walk. Unfortunately,         not all of the houses have numbers written on them, and on top of         that the boy is regularly taking turns to change streets, so the         numbers don't appear to him in any particular order.        
At some point during the walk the boy encounters a house with number         0 written on it, which surprises him so much that he stops adding         numbers to his total right after seeing that house.        
For the given sequence of houses determine the sum that the boy        will get.It is guaranteed that there will always be at least one         0 house on the path.        
Example        
For inputArray = [5, 1, 2, 3, 0, 1, 5, 0, 2], the output should be        houseNumbersSum(inputArray) = 11.        
The answer was obtained as 5 + 1 + 2 + 3 = 11.

Dec 10 — Is Arithmetic Progression (CodeFights)

Given a sequence of integers find the length of its largest subsequence that forms an arithmetic progression.
Example
For a = [1, 7, 3, 5, 4, 2], the output should be
longestSequence(a) = 3.
Explanation: [1, 3, 5] is a subsequence that's also an arithmetic progression.

Dec 11 — Is Divisible by 6 (CodeFights)

A masked number is a string that consists of digits and one asterisk (*) that should be replaced by exactly one digit. Given a masked number find all the possible options to replace the asterisk with a digit to produce an integer divisible by 6.
Example
For inputString = "1*0", the output should be
isDivisibleBy6(inputString) = ["120", "150", "180"].

Dec 12 — Is First Char Repeated (from colleague)

Write a function called IsFirstCharRepeated that takes in a string and returns a bool.  The function should return true if the first character is repeated anywhere else in the string.

Dec 13 — Is Lucky (CodeFights)

Ticket numbers usually consist of an even number of digits. A ticket number is considered lucky if the sum of the first half of the digits is equal to the sum of the second half.        
Given a ticket number n, determine if it's lucky or not.        Example        
For n = 1230, the output should be        
isLucky(n) = true;        
For n = 239017, the output should be        
isLucky(n) = false.

Dec 14 — Is Lucky Number (CodeFights)

Lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7.        Example        
For n = 47, the output should be        
isLuckyNumber(n) = true.

Dec 15 — Late Ride (CodeFights)

One night you go for a ride on your motorcycle. At 00:00 you start        your engine, and the built-in timer automatically begins counting        the length of your ride, in minutes. Off you go to explore the         neighborhood.  When you finally decide to head back, you realize there's a chance the bridges on your route home are up, leaving you stranded! Unfortunately, you don't have your watch on you and don't know what time it is. All you know thanks to the bike's timer is that n minutes have passed since 00:00. Using the bike's timer, calculate the current time. Return an answer as the sum of digits that the digital timer in the format hh:mm would show.        Example        
For n = 240, the output should be lateRide(n) = 4. Since 240 minutes have passed, the current time is 04:00. The digits sum up to 0 + 4 + 0 + 0 = 4, which is the answer.        
For n = 808, the output should be lateRide(n) = 14. 808 minutes mean that it's 13:28 now, so the answer should be 1 + 3 + 2 + 8 = 14.

Dec 16 — Max Divisor (CodeFights)

Given a number and a range, find the largest integer within the given range that's divisible by the given number.        
Example        
For left = 1, right = 10 and divisor = 3, the output should be        maxDivisor(left, right, divisor) = 9.        
The largest integer divisible by 3 in range[1, 10] is 9.

Dec 17 — Multiply List With Divide and Conquer (from colleague)

Write a function that takes in a List of ints that multiplies all values in the list.  Use "divide and conquer" with recursion.

Dec 18 — Only Even Numbers (CodeFights)

Return a strictly increasing array of all even numbers between given left and right (both inclusive).
Example
For left = 5 and right = 10, the output should be
onlyEvenNumbers(left, right) = [6, 8, 10].

Dec 19 — Digit Sums Difference (CodeFights)

Given an integer n, find the difference between the sums of its even and odd digits.
Example
For n = 412, the output should be
digitSumsDifference(n) = 5;
For n = 1203, the output should be digitSumsDifference(n) = -2.

Dec 20 — Pep Eight (CodeFights)

PEP 8, Style Guide for Python Code, requires a coder to write lines no longer than 79 characters. Given some line's length, find out if it satisfies PEP 8 requirements.
Example

• For line = 35, the output should be
  pepEight(line) = true;
• For line = 85, the output should be
  pepEight(line) = false.

Dec 21 — Array Max Consecutive Sum (CodeFights)

Given array of integers, find the maximal possible sum of some of its k consecutive elements.
Example
For inputArray = [2, 3, 5, 1, 6] and k = 2, the output should be        arrayMaxConsecutiveSum(inputArray, k) = 8.
All possible sums of 2 consecutive elements are:
2 + 3 = 5;
3 + 5 = 8;
5 + 1 = 6;
1 + 6 = 7.
Thus, the answer is 8.

Dec 22 — Orthogonal Lines (CodeFights)

Two lines ax + by + c = 0 and a'x + b'y + c' = 0 are orthogonal if and only if a* a' + b * b' = 0. Check if the two given lines are orthogonal.
Example
For line1 = [1, -1, 0] and line2 = [1, 1, 0], the output should be
orthogonalLines(line1, line2) = true.

Dec 23 — kth Digit (CodeFights)

Given an integer, find its kth digit.
Example
For n = 578943 and k = 2, the output should be
kthDigit(n, k) = 7.

Dec 24 — Share an Apple (CodeFights)

You have a apples, and your friend has b apples.You will be happy if - and only if - you both have the same number of apples.
Given integers a and b, check if you will be happy after you give your friend one of your apples.
Example
For a = 3 and b = 1, the output should be
shareAnApple(a, b) = true.

Dec 25 — Extract Matrix Column (CodeFights)

Given a rectangular matrix and an integer column, return an array containing the elements of the columnth column of the given matrix(the leftmost column is the 0th one).
Example
Formatrix = [[1, 1, 1, 2], [0, 5, 0, 4], [2, 1, 3, 6]]
and column = 2, the output should be
extractMatrixColumn(matrix, column) = [1, 0, 3].

Dec 26 — Find Sum (from colleague)

Given a List of ints, find the sum of all elements by using recursion.

Dec 27 — Reverse Characters in String (from colleague)

Given a string, reverse the characters in the string by using recursion.

Dec 28 — Right Triangle (CodeFights)

For a given triangle determine if it is a right triangle.        Example        
For sides = [3, 5, 4], the output should be        rightTriangle(sides) = true.

Dec 29 — Sum Below Bound (CodeFights)

Given an integer bound, find the maximal integer n such that 1 + 2 + ... + n ≤ bound.        
Example        
For bound = 14, the output should be        
sumBelowBound(bound) = 4.

Dec 30 — Three and Four (CodeFights)

Return a sorted array of all non-negative numbers less than the given n which are divisible both by 3 and 4.

For n = 30, the output should be

threeAndFour(n) = [0, 12, 24].

Dec 31 — X to the Y Power (from colleague)

Write a function called XToTheYPower that takes in an int x and an int y, and returns an int. The function should return x^y. Solve with recursion.

I hope you have a lovely winter holiday and hope to see you in the new year. Thanks for reading, subscribing, following, and learning along with me!

🍾 🎉 🎊