## Posts

Showing posts from May, 2018

### Split Array into Fibonacci Sequence

Memorial Day Problem:  https://leetcode.com/problems/split-array-into-fibonacci-sequence/description/ Given a string  S  of digits, such as  S = "123456579" , we can split it into a  Fibonacci-like sequence   [123, 456, 579]. Formally, a Fibonacci-like sequence is a list  F  of non-negative integers such that: 0 <= F[i] <= 2^31 - 1 , (that is, each integer fits a 32-bit signed integer type); F.length >= 3 ; and  F[i] + F[i+1] = F[i+2]  for all  0 <= i < F.length - 2 . Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself. Return any Fibonacci-like sequence split from  S , or return  []  if it cannot be done. One strategy to solve the problem is to do an N^2 nested-loop thru the array (given that the array length is 200, this would cost you 40,000, which is reasonable) where the outer-loop corresponds to the F1 in the Fibonacci sequence and the  inner-loop c

### Most Common Word, by LeetCode

Problem is this one https://leetcode.com/problems/most-common-word/description/ . String and Counting problems are (for the most part) solvable by using the string operators within your programming language (avoid reinventing the wheel, there is no need to do a lot of the parsing by hand anymore. If your programming language doesn’t support the basic string operations, time to switch languages) and hash-tables to quickly access specific substrings. This is exactly the approach that will be taken here. First a quick prep where we add the banned words to a hash-table and we also split all the words in the paragraph. Then it is just a matter of going thru the words in the paragraph, make sure they are not in the banned list, and keep track of the most common used so far. Code is below, Boris.                public class Solution                {                               public string MostCommonWord(string paragraph, string[] banned)                               {

### Shortest Distance to a Character

Hi folks, long time no see! This problem deals with the time-space trade-off, if you're studying for interviews, please keep that in mind :) Usually problems whose solutions are N^2 and whose N is in the 10,000 range are not really tractable so you should be looking for linear or NLogN solutions. To reduce from an N^2 to an N usually you'll be required to use some extra space. If the optimization function is time, it is usually quite OK to utilize some extra memory. So without further a due, here is today's problem: https://leetcode.com/submissions/detail/154955695/ Given a string  S  and a character  C , return an array of integers representing the shortest distance from the character  C  in the string. Example 1: Input: S = "loveleetcode", C = 'e' Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0] Given that N is in the order of 10K, we should try to optimize from the get-go. There is an O(N) solution (technically 3N) with an O(N)-space trade-off:

### Positions of Large Groups, by LeetCode

Hi folks, long time no see! Problem is here:  https://leetcode.com/problems/positions-of-large-groups/description/ : In a string  S  of lowercase letters, these letters form consecutive groups of the same character. For example, a string like  S = "abbxxxxzyy"  has the groups  "a" ,  "bb" ,  "xxxx" ,  "z"  and  "yy" . Call a group  large  if it has 3 or more characters.  We would like the starting and ending positions of every large group. The final answer should be in lexicographic order. The solution is straightforward: index manipulation, understanding some of the data structures of your favorite language (in my case C#), linear pass keeping track of the beginning of the current block (in the code below expressed by "previousIndex"), and that's pretty much it! Have fun, code is below, many hugs!!! Boris public class Solution { public IList<IList<int>> LargeGroupPositions(string