Another Casual Coder

A common question, especially as warm-up question in technical interviews, is the following: given a sorted list of colored balls where some balls are black and some are white, rearrange the set in such a way to have the black balls ahead of the white ones. Once the candidate is done with it, a follow-up question comes with an introduction of a third color, say green. The image below exemplifies the before-after states for this question: I've seen solutions using the following approaches: 1) Brute-force N^2-time (similar to BubbleSort) 2) Two-pointers (head and tail) solutions (which gets complicated with more colors) 3) Even a QuickSort-like solution (attempting to get it down to NLogN-time) There is an easier solution that works well for this case, but there is one key characteristic for this problem: the order of the balls within a group with the same color is irrelevant . This is crucial in order to be able to use a bucket (or count) sort approach. The approach wil...

I just saw a nice talk from a good friend of mine about load balancing techniques, you can take a look here:  https://www.infoq.com/presentations/load-balancing . One of the interesting approaches mentioned in the talk is the "Power of Two Choices" algorithm, which has been explained in detailed here:  http://www.eecs.harvard.edu/~michaelm/postscripts/tpds2001.pdf . It is amazing for its simplicity and effectiveness: a simple variation of random choice, but instead of selecting a bin (server) randomly, the idea becomes the following: Pick two bins (servers) randomly, call them "A" and "B" If "A" is under less load (define load as you wish), then select "A" as your target Otherwise, "B" The simplicity is striking, to a point that it is even questionable whether or not it works. But comparing the approach with a simple random approach you can definitely see that the distribution of the servers load balanced becomes much ...

https://leetcode.com/problems/lexicographical-numbers/ , problem statement: Given an integer  n , return 1 -  n  in lexicographical order. For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9]. Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000. Definitely the solution must be at least O(n) to work, anything higher than that and we'll have a problem given the 5M ceiling for the input size. I tried a couple of ideas to come up with the proper lexicographic order. One possible hypothesis was: As you try number "i", see if the number 10*i also works. If so it should come next after "i" instead of i+1 Also, when calling recursively  for 10*i, make sure you only go up to 10*i+10, after that point you'll be repeating numbers (and in non-lexicographic order), hence stop there. Not the most efficient solution (possibly because of the stack overhead), but passable in O(n)-time. Code's below....

https://leetcode.com/problems/kth-largest-element-in-an-array/ , problem statement: Find the  k th largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. For example, Given  [3,2,1,5,6,4]  and k = 2, return 5. Note:  You may assume k is always valid, 1 ≤ k ≤ array's length. Two-lines solution: sort & index. Code's below, cheers, Marcelo.     public class Solution     {         public int FindKthLargest(int[] nums, int k)         {             Array.Sort(nums);             return nums[nums.Length - k];         }     }

https://leetcode.com/problems/perfect-squares/ , problem statement: Given a positive integer  n , find the least number of perfect square numbers (for example,  1, 4, 9, 16, ... ) which sum to  n . For example, given  n  =  12 , return  3  because  12 = 4 + 4 + 4 ; given  n  =  13 , return  2  because  13 = 4 + 9 . Assume you know the solution for all values from 1..N-1. Then when evaluating the solution for N, subtract from N all the squares up to N and see which ones from the previous solutions (DP), plus one, gives you the least number of solutions. At the end the solution will be stored in the position n. Complexity is somewhere in the neighborhood of N*Sqrt(N) and N*Log(N). Code's below, cheers, Marcelo.     public class Solution     {         public int NumSquares(int n)         {             int[]...

https://leetcode.com/problems/find-peak-element/ , problem statement A peak element is an element that is greater than its neighbors. Given an input array where  num[i] ≠ num[i+1] , find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that  num[-1] = num[n] = -∞ . For example, in array  [1, 2, 3, 1] , 3 is a peak element and your function should return the index number 2. Straightforward code, the only caveat is the line in yellow above. It gives you a hint to pay attention to the data types: instead of using an int, use a long and in that case you won't have to worry about boundary conditions. Code below.     public class Solution     {         public int FindPeakElement(int[] nums)         {             for (int i = 0; i < nums.Length; i++) ...

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/ , problem statement: Given an array where elements are sorted in ascending order, convert it to a height balanced BST. Since the tree has to be height balanced, the array needs to be divided in half all the time in order to create the BST properly. It will be a standard DFS and as we go down split the array in half similar to binary search techniques. We only visit the elements of the array once, hence it is O(n). Code below, cheers, Marcelo.     public class Solution     {         public TreeNode SortedArrayToBST(int[] nums)         {             return SortedArrayToBSTInternal(nums, 0, nums.Length - 1);         }         private TreeNode SortedArrayToBSTInternal(int[] nums, int left, int right)         {             ...