Another Casual Coder

Latest LeetCode problem deals with classical binary search, here it is:  https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/ Given a list of sorted characters  letters  containing only lowercase letters, and given a target letter  target , find the smallest element in the list that is larger than the given target. Letters also wrap around. For example, if the target is  target = 'z'  and  letters = ['a', 'b'] , the answer is  'a' . Examples: Input: letters = ["c", "f", "j"] target = "a" Output: "c" Input: letters = ["c", "f", "j"] target = "c" Output: "f" Input: letters = ["c", "f", "j"] target = "d" Output: "f" Input: letters = ["c", "f", "j"] target = "g" Output: "j" Input: letters = ["c", ...

3 comments

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:  https://leetcode.com/problems/sentence-similarity/description/ : 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...

1 comment

An easy problem to finish the week, from LeetCode:  https://leetcode.com/problems/self-dividing-numbers/description/ : 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 numbe...

2 comments

Another LeetCode, right here:  https://leetcode.com/problems/find-pivot-index/description/ 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]....

2 comments

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: https://leetcode.com/problems/1-bit-and-2-bit-characters/description/ 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...

4 comments

Here is a problem: you're given a binary tree, say something like this: Now what we want to do is delete all the leaves from this tree whose value is equal to a certain target value. For this example's sake, the target value will be 5. That seems pretty straightforward: traverse down the tree, and the moment that you find a leave whose value equals to 5, chop it off: But hang on, what if the problem requires you to ensure that the remaining tree, after deleting any leaf whose value was 5, does not have any resulting leaf with value equals to five? Suppose for example that instead of "4", that node had the value "5": It would then trigger a cascading event where not only the "5" leaves would be deleted, but also their parent would be deleted too. This is because after deleting the "5"s, you'd end up with a new tree with new leaves whose values are also 5 :). Those should be deleted too. How to do that? A simple appr...

3 comments

Howdy!!! I had solved 203 problems on Project Euler, until it got hacked. I had solved 200+ problems on Hacker-Rank, until I ran out of easy/medium problems to solve. Now I've crossed the 200 problems mark on LeetCode. I think I can get to the 300 there, assuming they keep on posting easy/medium problems, and that my interest for TV shows continue to be zero. The 200th problem was this one:  https://leetcode.com/problems/set-mismatch/description/ : The set  S  originally contains numbers from 1 to  n . But unfortunately, due to the data error, one of the numbers in the set got duplicated to  another  number in the set, which results in repetition of one number and loss of another number. Given an array  nums  representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array. Example 1: Input: nums = [...

1 comment