Another Casual Coder

I've first seen this problem posted by  HackerRank , which I thought was super interesting: You're given a string with characters from the alphabet {0,1} (only zeroes and ones allowed), such as "0010". The task is to count the number of sub-strings S that satisfy the following pattern: Length of S must be greater than 0 and even Assume S = S1 + S2 where S1 (and S2) length is equal to half of S length: Either S1 contains only zeros and S2 contains only ones Or S1 contains only ones and S2 contains only zeroes An example makes thinks easier: suppose the input string is "00110". We see the following strings matching S's pattern: S1 = "0 01 10" S2 = " 0011 0" S3 = "001 10 " OK, so the return value here should be 3. Quadratic Solution: An initial quadratic (O(n^2)-time, O(1)-space) can be accomplished in a relatively simple manner: Traverse the string from iterator i = 1..n-1 For each i: Check...

Leetcode:  https://leetcode.com/problems/first-missing-positive/ , or copied/pasted here: Given an unsorted integer array, find the first missing positive integer. For example, Given  [1,2,0]  return  3 , and  [3,4,-1,1]  return  2 . Your algorithm should run in  O ( n ) time and uses constant space. The problem asks for an O(n)-time solution and O(1)-space. I couldn't do that, I'm sorry. But, I did in NLogN which still beats 70% of the C# submissions. The idea is simple: Sort the array (NLogN, use QuickSort) Traverse it once (N): If non-positive, continue (remember we're looking for the first positive missing number!) If equal to the previous, continue If not equal to the first positive number (set it to 1), you found the solution! Increment the "first" positive number O(1)-space. Code is below - cheers, Marcelo.     public class Solution     {         public int FirstMis...

Leetcode again:  https://leetcode.com/problems/combination-sum-ii/ , and here is the description: Given a collection of candidate numbers ( C ) and a target number ( T ), find all unique combinations in  C  where the candidate numbers sums to  T . Each number in  C  may only be used  once  in the combination. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set  [10, 1, 2, 7, 6, 1, 5]  and target  8 , A solution set is:  [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] I've done this type of problem multiple times over and over, so in my mind this wouldn't take that long. There was one caveat to this problem (the fact that we don't want duplicated lists) which I did not give much attention in the beginning (a hash table would eventually help, I thought). Procedure to solve this kind of problem usually involves...

We interrupt this program to thank people and entities who are important to The Casual Coder . We're doing it in Random Order. This is the output. Cheers! Thank you to Brian, for the innovative mindset Thank you to Lili, the UX ninja Thank you to Rafael, for being my little mathematician Thank you to Prateek, who turn the impossible into possibilities Thank you to Shantanu, the amazing super-fast coder Thank you to Dija, for being my brother Thank you to Javier, the one and only one architect Thank you to Sarah, for bringing accessibility and computing together Thank you to Ricardo, a big engineer with an even bigger heart Thank you to Ethan, for helping my kids with math, and being such a great friend Thank you to Wes, pushing the limits of the cloud Thank you to Sidd, for teaching me the math and coding of risk taking Thank you to Patrick B, for hiring me into Microsoft after inserting a node in a BST Thank you to Keith R, a legend Thank you to Visw, for solving...

https://leetcode.com/problems/letter-combinations-of-a-phone-number/ , here is the problem description (image): This problem is commonly used in technical interviews. It is a good DFS problem, however the drawback that some might argue is that it is a one-solution problem: there are no multiple ways to solve it (other than recursive versus non-recursive, but the strategy is the same: DFS), and it is by design an exponential problem (although the limits are small). Notice that the problem asks for all the solutions, hence no DP or math shortcut can be applied. The DFS is very straightforward: Build a mapping between the phone digits and the strings (as given). I used an array of strings The recursive call has three key parameters (the only ones changing): The current index (which we'll use to index the digits) The current combination The solution (ref-based list of strings) The DFS has two cases: Base: when the index is greater than or equal to the digits length ...

https://leetcode.com/problems/serialize-and-deserialize-bst/ , I've solved a similar problem before for a generic tree, but couldn't quite remember the solution. This one here uses a DFS-recursion to serialize and use a non-recursive method using a stack for de-serialization. Here is the problem statement: Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a  binary search tree . There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure. The encoded string should be as compact as possible. Note:  Do not use class member/global/static ...

https://leetcode.com/problems/3sum/ , or copied/pasted here: Given an array  S  of  n  integers, are there elements  a ,  b ,  c  in  S  such that  a  +  b  +  c  = 0? Find all unique triplets in the array which gives the sum of zero. Note:  The solution set must not contain duplicate triplets. For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ] A naive solution would take N^3-time (3 nested loops). Here is a faster one: Start by sorting the input array (NLogN) Transform the equation into a+b=-c The outer loop will be the "-c", which will go from 0 to nums.length - 1 For the inner loop, use the 2-pointers technique: one pointing to the leftmost index, one pointing to the rightmost index, and move them accordingly depending on the result of the addition in respect to "-c". The inner loop will also be O(N). There is a need for a hash table...

Problem is posted here:  https://leetcode.com/problems/ugly-number-ii/ , or copied/pasted: Write a program to find the  n -th ugly number. Ugly numbers are positive numbers whose prime factors only include  2, 3, 5 . For example,  1, 2, 3, 4, 5, 6, 8, 9, 10, 12  is the sequence of the first  10  ugly numbers. Note that  1  is typically treated as an ugly number, and  n   does not exceed 1690 . The limits are small enough (N<=1690) that I thought a not fancy solution (meaning not Dynamic Programming one) could do the trick. The solution will run in O(NLogN)-time: a) First we'll use a heap based on a priority queue implementation to store all the numbers from the 1st to the Nth (the solution). It will clearly consume some good amount of extra memory. b) At the same time we use hash table to mark the numbers seen before and already added to the heap c) We'll iterate from 1..N (hence the "N" in the Big-O time complex...