Showing posts from November, 2017

The use of nested Hashtables

Sometimes a solution to a problem requires the use of nested hash-tables, that is, a hash table whose values are other hash tables. This problem exemplifies this technique. It comes from Leetcode, here it is: : Given two sentences  words1, words2  (each represented as an array of strings), and a list of similar word pairs  pairs , determine if two sentences are similar. For example, "great acting skills" and "fine drama talent" are similar, if the similar word pairs are  pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]] . Note that the similarity relation is not transitive. For example, if "great" and "fine" are similar, and "fine" and "good" are similar, "great" and "good" are  not  necessarily similar. However, similarity is symmetric. For example, "g

Self Dividing Numbers

An easy problem to finish the week, from LeetCode: : A  self-dividing number  is a number that is divisible by every digit it contains. For example, 128 is a self-dividing number because  128 % 1 == 0 ,  128 % 2 == 0 , and  128 % 8 == 0 . Also, a self-dividing number is not allowed to contain the digit zero. Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible. Example 1: Input: left = 1, right = 22 Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22] Given the low ranges for the input, a simple check across all the digits for each number in the range should do it. The main logic is highlighted in green  below. Basically to check whether a given number is self-dividing, go thru its digits (that's the module ten in the code) and if the digit is zero or if it doesn't divide the number, then the number is not self-dividing. Ot

Find Pivot Index: a linear solution

Another LeetCode, right here: Given an array of integers  nums , write a method that returns the "pivot" index of this array. We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index. If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index. Example 1: Input: nums = [1, 7, 3, 6, 5, 6] Output: 3 Explanation: The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3. Also, 3 is the first index where this occurs. Example 2: Input: nums = [1, 2, 3] Output: -1 Explanation: There is no index that satisfies the conditions in the problem statement. Note: The length of nums will be in the range [0, 10000]. Each element nums[i] will be an integer in the range [-1000, 1000].

1-bit and 2-bit Characters

Sometimes a recursive approach to a problem might seem like a bad idea "because of the stack overhead and potential explosion of permutations and overly complicated logic"... yada, yada, yada. Sure, sometimes such arguments are right on the target, but sometimes (many times) computer science problems can mirror life problems quite accurately, where the answer to the problem can be a boring "it depends". Take a look at this problem by LeetCode: We have two special characters. The first character can be represented by one bit   0 . The second character can be represented by two bits ( 10   or   11 ). Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero. Example 1: Input: bits = [1, 0, 0] Output: True Explanation: The only way to decode it is two-bit character and one-bit c