31 Days of Algorithms — July 2017
Over the last two months, I’ve been doing an white-boarding algorithm a day in an Xcode playground. From these daily exercises, I’ve used higher-order methods more confidently (map!), practiced my work with double for-loops and gained muscle memory from coding coding coding.
I thought I’d share my daily algos in a blog post.
These algos were gathered from friends, LeetCode, Codewars, and Hackerrank.
July 1
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.
July 2
Reverse digits of an integer.Example1: x = 123, return 321Example2: x = -123, return -321Have you thought about this?Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.Note:The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.
July 3
Write a program to check whether a given number is an ugly number.Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.Note that 1 is typically treated as an ugly number.
July 4
Your task is to write a function that prints out the nth card of the standard card deck. Each of the cards has a rank which can be, in order of ascending value, a number in range from 2 to 10 (depicted as '0'), a Jack ('J'), a Queen ('Q'), a King ('K'), or an Ace ('A'). Each of the cards also has a suit: clubs ('C'), diamonds ('D'), hearts ('H'), or spades ('S').The cards in the deck are sorted first by their suits in lexicographical order, and then by the value of their ranks. Return the nth (0-based) card in the deck as a string with a length of two, with the first character representing the rank and the second character representing the suit.ExampleFor n = 0, the output should becards(n) = "2C".The very first card in the deck is 2 of clubs, so the answer is "2C".For n = 34, the output should becards(n) = "OH".The 34th card in the deck is 10 of hearts, making the answer "0H"
July 5 (from Hackerrank)
July 6
Write a function to calculate the number of characters used to print the numbers “0” to “1000" (inclusive) when spelled out, with whitespace, hyphens and “and” omitted. For example, “525" would spell out “fivehundredtwentyfive”, so your function should return “21". Your function should adhere to the following signature:func countCharacters(from start: Int, to end: Int) -> IntConsider, for example, one through three, would be “onetwothree”, which uses “11" characters; “fortyone” uses “8" characters; and “onehundredone” uses “13" characters. Therefore:“countCharacters(from: 1, to: 3)” should return “11"“countCharacters(from: 41, to: 41)” should return “8"“countCharacters(from: 101, to: 101)” should return “13"Your definition of “countCharacters” should return the correct answer for “countCharacters(from: 0, to: 1000)
July 7
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.
July 8
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].Note:You must do this in-place without making a copy of the array.Minimize the total number of operations.
July 9 (from Leetcode)
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).Example 1:Input: [3, 2, 1]Output: 1Explanation: The third maximum is 1.Example 2:Input: [1, 2]Output: 2Explanation: The third maximum does not exist, so the maximum (2) is returned instead.Example 3:Input: [2, 2, 3, 1]Output: 1Explanation: Note that the third maximum here means the third maximum distinct number.Both numbers with value 2 are both considered as second maximum.
July 10 (from Leetcode)
Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.Examples:s = "leetcode"return 0.s = "loveleetcode",return 2.Note: You may assume the string contain only lowercase letters.
July 11 (from Leetcode)
Write an algorithm to determine if a number is "happy".A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.Example: 19 is a happy number1^2 + 9^2 = 828^2 + 2^2 = 686^2 + 8^2 = 1001^2 + 0^2 + 0^2 = 1
July 12 (from Codewars)
It's bonus time in the big city! The fatcats are rubbing their paws in anticipation... but who is going to make the most money?Build a function that takes in two arguments (salary, bonus). Salary will be an integer, and bonus a boolean.If bonus is true, the salary should be multiplied by 10. If bonus is false, the fatcat did not make enough money and must receive only his stated salary.Return the total figure the individual will receive as a string prefixed with '$' .
July 13 (from Leetcode)
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [-2,1,-3,4,-1,2,1,-5,4],the contiguous subarray [4,-1,2,1] has the largest sum = 6.
July 14
Write a function that takes an array of Ints as input and returns how many numbers are odd, how many are even, and how many are divisible by three.
July 15
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.You may assume no duplicates in the array.Here are few examples.[1,3,5,6], 5 → 2[1,3,5,6], 2 → 1[1,3,5,6], 7 → 4[1,3,5,6], 0 → 0
July 16 (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].
July 17 (from Leetcode)
This algo I wasn’t able to do. If you have a solution, please share!
Given a roman numeral, convert it to an integer.Input is guaranteed to be within the range from 1 to 3999.
July 18
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.Note:You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.
July 19 (from Leetcode)
Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.Example 1:Input: candies = [1,1,2,2,3,3]Output: 3Explanation:There are three different kinds of candies (1, 2 and 3), and two candies for each kind.Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.The sister has three different kinds of candies.Example 2:Input: candies = [1,1,2,3]Output: 2Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1].The sister has two different kinds of candies, the brother has only one kind of candies.Note:The length of the given array is in range [2, 10,000], and will be even.The number in given array is in range [-100,000, 100,000].
July 20
We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.Example:Input: 28Output: TrueExplanation: 28 = 1 + 2 + 4 + 7 + 14Note: The input number n will not exceed 100,000,000. (1e8)
July 21
This algo is another one I wasn’t able to solve. Maybe I need to finally watch Die Hard?
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.Operations allowed:Fill any of the jugs completely with water.Empty any of the jugs.Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.Example 1: (From the famous "Die Hard" example)Input: x = 3, y = 5, z = 4Output: TrueExample 2:Input: x = 2, y = 6, z = 5Output: False
July 22 (from Leetcode)
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.Example:Given n = 3.At first, the three bulbs are [off, off, off].After first round, the three bulbs are [on, on, on].After second round, the three bulbs are [on, off, on].After third round, the three bulbs are [on, off, off].So you should return 1, because there is only one bulb is on.
July 23 (from Leetcode)
Given a word, you need to judge whether the usage of capitals in it is right or not.We define the usage of capitals in a word to be right when one of the following cases holds:All letters in this word are capitals, like "USA".All letters in this word are not capitals, like "leetcode".Only the first letter in this word is capital if it has more than one letter, like "Google".Otherwise, we define that this word doesn't use capitals in a right way.Example 1:Input: "USA"Output: TrueExample 2:Input: "FlaG"Output: FalseNote: The input will be a non-empty word consisting of uppercase and lowercase latin letters.
July 24 (from Leetcode)
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.Each letter in the magazine string can only be used once in your ransom note.Note:You may assume that both strings contain only lowercase letters.canConstruct("a", "b") -> falsecanConstruct("aa", "ab") -> falsecanConstruct("aa", "aab") -> true
July 25 (from Codewars)
The Arara are an isolated tribe found in the Amazon who count in pairs. For example one to eight is as follows:1 = anane2 = adak3 = adak anane4 = adak adak5 = adak adak anane6 = adak adak adak7 = adak adak adak anane8 = adak adak adak adakTake a given number and return the Arara's equivalent.e.g.countArara(3) // "adak anane"countArara(8) // "adak adak adak"
July 26 (from Codewars)
Create a function that gives a personalized greeting. This function takes two parameters: name and owner.Use conditionals to return the proper message: case | return --- | --- name equals owner | 'Hello boss' otherwise | 'Hello guest'
July 27 (from Leetcode)
Given an array of integers, every element appears twice except for one. Find that single one.
July 28 (from Codewars)
When provided with a number between 0-9, return it in words.Input :: 1Output :: "One".
July 29 (from Codewars)
This kata is about multiplying a given number by eight if it is an even number and by nine otherwise.
July 30 (from Hackerrank)
You are given sticks, where the length of each stick is a positive integer. A cut operation is performed on the sticks such that all of them are reduced by the length of the smallest stick.Suppose we have six sticks of the following lengths:5 4 4 2 2 8Then, in one cut operation we make a cut of length 2 from each of the six sticks. For the next cut operation four sticks are left (of non-zero length), whose lengths are the following:3 2 2 6The above step is repeated until no sticks are left.Given the length of sticks, print the number of sticks that are left before each subsequent cut operations.Note: For each cut operation, you have to recalcuate the length of smallest sticks (excluding zero-length sticks).Input FormatThe first line contains a single integer .The next line contains integers: a0, a1,...aN-1 separated by space, where represents the length of the stick.Output FormatFor each operation, print the number of sticks that are cut, on separate lines.
July 31
Given array of integers, remove each kth element from it.ExampleFor inputArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and k = 3, the output should beextractEachKth(inputArray, k) = [1, 2, 4, 5, 7, 8, 10].
Leave a comment if you solve any — I would love to see your solutions!