31 Days of Algorithms — August 2017

In keeping with last month’s post of my daily algorithms, I thought I would continue to share the white-boarding problems that I have been working with. Every day, I try to work on at least one white-boarding problem to keep my brain fresh and my muscle memory intact.

I’ve noticed that from doing these problems I am a bit more comfortable with:

• using higher-order functions such as .map, .filter and .reduce
• using recursion or at least recognizing when recursion could be used
• refactoring my code to run faster

You’ll note that the “levels” of these problems vary so don’t be surprised if you spot an “easy” problem or two in the middle of the month. Also, if I don’t note the source of the problem, it means that I don’t remember the source 🤷🏼‍♀. Lastly, some of these problems might be repeats from last month. Why, you ask? Practice makes perfect.

Aug 1 (from Codewars)

Find the sum of the odd numbers within an array, after cubing the initial integers. This function will return undefined (NULL in PHP) if any of the values aren't numbers.

Aug 2 (from Leetcode)

Write a function that takes a string as input and returns the string reversed.
Example:
Given s = "hello", return "olleh".

Aug 3 (from Leetcode)

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

Aug 4

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal".
Example 1:
//0, 1, 2, 3, 4
Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal".
For the left two athletes, you just need to output their relative ranks according to their scores.
Note:
N is a positive integer and won't exceed 10,000.
All the scores of athletes are guaranteed to be unique.

Aug 5 (from Codewars)

Given an array of numbers, determine whether the sum of all of the numbers is odd or even.
Give your answer in string format as 'odd' or 'even'.
If the input array is empty consider it as: [0] (array with a zero).
Example:
oddOrEven([0]) returns "even"
oddOrEven([2, 5, 34, 6]) returns "odd"
oddOrEven([0, -1, -5]) returns "even"

Aug 6 (from Codewars)

You are given a string of numbers between 0-9. Find the average of these numbers and return it as a floored whole number (ie: no decimal places) written out as a string. Eg:
"zero nine five two" -> "four"
If the string is empty or includes a number greater than 9, return "n/a"

Aug 7

For a web developer, it is very important to know how to design a web page's size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:
1. The area of the rectangular web page you designed must equal to the given target area.
2. The width W should not be larger than the length L, which means L >= W.
3. The difference between length L and width W should be as small as possible.
You need to output the length L and the width W of the web page you designed in sequence.
Example:
Input: 4
Output: [2, 2]
Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1].
But according to requirement 2, [1,4] is illegal; according to requirement 3,  [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.
Note:
The given area won't exceed 10,000,000 and is a positive integer
The web page's width and length you designed must be positive integers.

Aug 8 (from Leetcode)

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.
Given n, find the total number of full staircase rows that can be formed.
n is a non-negative integer and fits within the range of a 32-bit signed integer.

Aug 9 (from Leetcode)

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = "Hello World",
return 5.

Aug 10 (from Women Who Code NYC July 2017 Algorithms)

A palindromic number reads the same both ways.
The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

Aug 11 (from Women Who Code NYC July 2017 Algorithms)

Write a recursive method that takes as parameters an initial investment amount, an annual interest rate, and a number of years. The method should return the value of the investment after the given number of years, assuming that the interest is compounded annually. (For example, if the initial investment is 1000 and the interest rate is 10 percent, then after one year the investment will be worth 1100, after two years 1210, after three years 1331, etc.)

Aug 12 (from Leetcode)

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.

Aug 13 (from Women Who Code NYC June 2017 Algorithms)

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, 5! = 5 x 4 x 3 x 2 x 1 = 120
Write a program that can find the factorial of a number. Can you do it recursively?

Aug 14 (from Leetcode)

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.
You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.
Example 1:
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".
Example 2:
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

Aug 15 (from Leetcode)

Given an integer, write a function to determine if it is a power of two.

Aug 16 (from Leetcode)

Given a List of words, return the words that can be typed using letters of alphabet on only one row's of American keyboard like the image below.
Example 1:
Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

Aug 17 (from Leetcode)

Given two strings s and t which consist of only lowercase letters.
String t is generated by random shuffling string s and then add one more letter at a random position.
Find the letter that was added in t.
Example:
Input:
s = "abcd"
t = "abcde"
Output:
e
Explanation:
'e' is the letter that was added.

Aug 18 (from Codewars)

Given 4 integers a, b, c, d (positive or negative) we form the sum of the squares of a and b and then the sum of the squares of c and d. We multiply the two sums hence a number n and we try to decompose n in a sum of two squares e and f (e and f integers >= 0) so that n = e² + f².
More: e and f must result only from sums (or differences) of products between on the one hand (a, b) and on the other (c, d) each of a, b, c, d taken only once.
Suppose we have a = 1, b = 2, c = 1, d = 3. First we calculate the sums 1² + 2² = 5 and 1² + 3² = 10 hence n = 50.
50 = 1² + 7² or 50 = 7² + 1² (we'll consider that these two solutions are the same) or 50 = 5² + 5².
The return of our function will be an array of subarrays (in C an array of Pairs) sorted on the first elements of the subarrays. In each subarray the lower element should be the first.
prod2sum(1, 2, 1, 3) should return [[1, 7], [5, 5]]
prod2sum(2, 3, 4, 5) should return [[2, 23], [7, 22]]
because (2² + 3²) * (4² + 5²) = 533 = (7² + 22²) = (23² + 2²)
prod2sum(1, 2, 2, 3) should return [[1, 8], [4, 7]]
prod2sum(1, 1, 3, 5) should return [[2, 8]] (there are not always 2 solutions).

Aug 19 (from Codewars)

You will have a list of rationals in the form
m = [ [numer_1, denom_1] , ... , [numer_n, denom_n] ] or m = [ (numer_1, denom_1) , ... , (numer_n, denom_n) ]
where all numbers are positive integers. You have to produce the sum N/D of these rationals in an irreducible form ie N and D have only 1 for divisor.
#Example:
[ [1, 2], [1, 3], [1, 4] ] ---->
(13, 12) Swift

Aug 20

Each day a plant is growing by upSpeed meters. Each night that plant's height decreases by downSpeed meters due to the lack of sun heat. Initially, plant is 0 meters tall. We plant the seed at the beginning of a day. We want to know when the height of the plant will reach a certain level.
Example:
For upSpeed = 100, downSpeed = 10 and desiredHeight = 910, the output should be
growingPlant(upSpeed, downSpeed, desiredHeight) = 10.

Aug 21 (from Leetcode)

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Aug 22 (from Leetcode)

Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.
The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.
Example 1:
Input: "UD"
Output: true
Example 2:
Input: "LL"
Output: false

Aug 23 (from my friend Ben)

Your favorite restaurant can take reservations for n people. They have an interesting algorithm to determine how many tables they will need to set up based on these reservations. They take the number of people who have reservations, and then dividing it by ever incrementing integers. They start at 1, because they always need to have at least 1 table set up. They do this until the number of tables is greater than n. So your task is to find out how many times n will be divided until they determine the number of tables they need to set up.
Example
For n = 100, the output should be
dinerTables(n) = 5.
Walk-through:
[100, 1] < We start with 1 table for 100 people (100 / 1);
[100, 2] < 100 people / 2 tables = 50 people per table;
[50, 3] < 50 people / 3 tables = 16 people per table;
[16, 4] < 16 people / 4 tables = 4 people per table;
[4, 5] < 4 people / 5 tables = done.
Since n was divided 5 times before the number of tables was greater than the number of people, the answer is 5.

Aug 24 (from Leetcode) — this is a classic one!

Write a program that outputs the string representation of numbers from 1 to n.
But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.
Example:
n = 15,
Return:
["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

Aug 25 (from Leetcode) — I solved this more efficiently than 100% of the other solutions! YAY, ALGEBRA.

You need to return a string representing their multiplication. Note i2 = -1 according to the definition.
Example 1:
Input: "1+1i", "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.
Example 2:
Input: "1+-1i", "1+-1i"
Output: "0+-2i"
Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.
Note:
The input strings will not have extra blank.
The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form.

Aug 26 (from Coderbyte)

Using the Swift language, have the function FirstFactorial(num) take the num parameter being passed and return the factorial of it (e.g. if num = 4, return (4 * 3 * 2 * 1)). For the test cases, the range will be between 1 and 18 and the input will always be an integer.

Aug 27 (from Coderbyte)

Using the Swift language, have the function LongestWord(sen) take the sen parameter being passed and return the largest word in the string. If there are two or more words that are the same length, return the first word from the string with that length. Ignore punctuation and assume sen will not be empty.

Aug 28 (from Leetcode)

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Aug 29 (from Leetcode)

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Aug 30 (from Women Who Code NYC June 2017 Algorithms)

Easy mode: Check if the number of letters in a word are even or odd.
Medium mode: Check if the number of unique letters in a word are even or odd. For example, "llama" has 3 unique letters, which is odd.

Aug 31 (from Women Who Code NYC June 2017 Algorithms)

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Let me know if you have any good problems you can share — I need some for September!