Boris Coding Blog

You know when you jot down some phone numbers in the little memo near your phone? Well, not sure how many people still do that, but whenever they do it they are doing what Computer Scientists call Memoization : the process of annotating data in a memo for quick reference in the future. Memoization is the technique primarily used in a field of Algorithms called "Dynamic Programming", commonly known as DP. DP is hard to grasp. At least for me. It is a different paradigm compared to Recursion, and similarly to recursion, you need to solve hundreds of problems before getting any good at DP. I'm not good at DP at all. But I do want to exemplify a simple use of memoization, using a generalization of the second most famous DP problem (the first most famous being Factorial): Fibonacci. As you may recall, Fibonacci is a simple recursive formula that describes the growth in population for a certain species of rats. It is defined as follows: Fib(n) = n (for n<=1) Fib

  Recently I decided to resume my activities on Project Euler at night (no, I don't play xbox at night, although I do watch Netflix & Amazon Streaming!). Since I got to 192 problems solved on Project Euler, I decided to take a break since the problems were getting excruciatingly complicated (I mean, having to go deep into Diophantine Equations , Pell's Equation , all possible Fermat Theorems was just too much). I then switched to HackerRank  which is a little more academic and less brutal than Project Euler. But after solving 166 problems on HackerRank, again it got painful. So I decided to give it another try to Project Euler, and have solved 5 more problems in the past week (I now have 197 problems solved. Goal is 200).   My username on both is Relentless . With all that meaning and stuff.   Project Euler problems, especially the ones after #146, are in general hard problems (module a dozen or so easy ones). I wanted to tell in this post how I tackle them.   The p

Look, this is a weird result, but it is 100% trick-free, correct, provable result. I can prove to you the following statement: The sum of all positive even integers is -1/6 Relax, don't freak out, just take another sip of the wine and abstract your mind for few minutes. This will be proved. Without further due, let's get to work: What we want to prove is this: S_even = 2 + 4 + 6 + 8 + .... + oo = -1/6. First, we'll define few other sums: S1 = 1 - 1 + 1 - 1 + 1 - 1 + 1.... So S1 keeps alternating between 0 and 1. Here is how to solve it, subtract one from it and you'll end up with: 1 - S1 = 1 - (1 - 1 + 1 - 1 + 1 - 1 + 1....) getting rid of the brackets: 1 - S1 = 1 - 1 + 1 - 1 + 1... but the right side is S1 itself, hence: 1 - S1 = S1 2S1 = 1 S1 = 1/2 The second sum will be a slightly more complicated: S2 = 1 - 2 + 3 - 4 + 5 - 6 + .... To solve it, let's add S2 to itself: S2 + S2 However, to solve that addition we'll shift the botto

Checking whether a string is a palindrome  should be a straightforward question for any programmer. As a matter of fact, this is one of the most boring interview questions on par with the infamous " reverse a linked list ". A more interesting question is the following: given a number N and a string STR, is there a way to remove up to N characters in STR in such a way to make the resulting string a palindrome? As an example, suppose that the string given is " emordnpalindrome " and N=3. Notice that if we remove the 3 characters highlighted below, we end up with a valid palindrome: Moreover, if there is a way to do so, can you also output the minimum number of changes as well as which characters to change? That seems a more interesting problem, especially given the constraints: 0 <= N <= 13 0 <= Len(STR) <= 120,000 Careful with the execution time here!!! Remember that if you want to select 13 characters randomly out of 120,000 characters, you&#

The Ultimate Tree is the fastest Tree data structure ever built. Trees are one of the most powerful data structures in Computer Science. They are fast. They allow you to have a well-structured, total ordered view of your data with fast retrieval (search), insertion and deletion. There are many different types of Trees, and when I say fast, what I mean is O(Log(n)), which IS fast. Check this out:   As you can see, all sophisticated trees above have retrieval, insertion and deletion in O(Log(n)). The question then becomes: is it possible to come up with The Ultimate Tree , a Tree capable of search, insertion and deletion in constant time (O(1))? The claim in this post is that yes, there IS a way to do that. Here is how it will work: 1)       First, no free lunch here! Such a massive speed up in search, insertion and deletion will require extra space, hence we’ll not be optimizing for space here, and will tolerate up to O(n)-space. Space is cheap. Most of the time. 2

At Bing we do something super cool to protect our users: whenever we detect that an image or video may contain adult content, and if the user's search safety setting is set to "Moderate" , we do a nice fuzzy of the image to prevent potential adult leakage, such as in this example: You won't find this feature on Google . As a matter of fact we at Bing love playing with images, even trying to guess your age based on your own picture ! We use very sophisticated, state-of-the-art techniques of image processing to come up with the ideal masks, filters and algorithms in order to properly perform the fuzzing task at massive scale . Suppose that you were to write a very-very simple code to perform any kind of fuzzing on a given image - how would you do that? In this post I discuss three very simple techniques to perform such a fuzzing (none of them are what we actually use here in Bing! the ones below is just for fun coding!). I've named the techniques as follows:

If you studied Computer Science, at some point, usually in the beginning of your algorithm courses, you learn about sorting algorithms, the most famous one being Quicksort. Studies show that the most frequent reactions to those who learn about Quicksort for the very first time are: 1) Wow!!! How could anyone possibly come up with that idea? 2) Hmm, explain it to me one more time please? 3) #1 followed by #2, or #2 follower by #1 Not surprisingly I was right there in the #3 category. To learn about Quicksort just Bing it , but this blog post isn't about Quicksort necessarily, but rather about the person who invented it, Sir Tony Hoare . The winner of the Turing Award prize in 1980, Sir Tony Hoare currently works at Microsoft, just like me, and he was kind enough to give me the honor to interview him for my coding blog. Without any further due, here it is - I hope you Quick-enjoy it too! :) [Boris Vasilenko] First, thank you Tony for the incredible opportunity to ask you f

"Salvation lies within" - that's the famous punch line from Andy Dufresne in the The Shawshank Redemption. In the case of this post, however, salvation lies with BFS. As my friend (and arguably one of the top 10 developers alive on the planet) Taras correctly mentioned, doing a Depth-First Search (DFS) to solve the previous problem won't lead you anywhere. The reasons are twofold: An DFS will pick one straight path in the search space and will go as deep as it can within that path until a solution is found. Problem is that, if we're unlucky enough, that path won't contain any solution whatsoever, and hence the program will continue to run indefinitely until a stack overflow blows up in your face. Assuming that the DFS, due to a miracle, picks a path which leads to a possible solution: there is no guarantee that the solution is a minimal solution, though. Hence the program may stop, but the solution found might not be the optimal one, hence qualifying i

As an old wise man used to say: “for every complicated problem, there is always an easy solution, albeit a wrong one”. Indeed.   Problem I stumbled upon was the following: take a digit D1. Take another digit D2. You’re allowed to generate numbers using only D1 and D2. Call the numbers that you generate this way M. Take a number N. Find the smallest M that is a multiple of N. Ok, an example with real numbers will make this easier to visualize. D1 = 1 D2 = 4 N = 16 What’s the smallest number composed of only “1”s and “4”s that is a multiple of 16? The answer is 144. Also, assume that there is always a solution. One would be tempted to write a recursive solution like this (sketch, pseudo-code): FindMinMultiple(int d1, int d2, int n, int generatedNumber){   If(generatedNumber%n == 0) è found!   FindMinMultiple(d1, d2, n, 10 * generatedNumber + Min(d1,d2))   FindMinMultiple(d1, d2, n, 10 * generatedNumber + Max(d1,d2)) } What’s wrong with this solution,

This week I was teaching my daughter the concept of a “birthdate magic number”. It was a way to get her thinking about math and algorithms. And also to keep her busy – she was bored. In any case, the concept of a “birthdate magic number” also known as BMN, doesn’t formally exist, but it was rather fabricated, as far as I’m aware. BMN was defined as being the following: 1.  Take your birthdate, in the format MMDDYYYY 2.  Read it as a number N, so N = Number(MMDDYYYY) 3.  Now if N has only a single digit, N is your BMN 4.  Otherwise make N = SumDigits(N) and go back to step 3 An example is ideal here. Take a random birthdate, say 03/14/15 (totally random!). In such a case the format should be 03142015. Hence N = 3142015 (as a number). Great, now we land at step #3. Not a single digit. Step #4, N becomes 3+1+4+2+0+1+5 = 16. Not a single digit. N then becomes 1+6 = 7. Single digit. BMN(03142015) = 7. She got it, was excited and start calculating the BMN for the members of our family