Posts

Showing posts from June, 2014

Messing around with infinity

Image
Infinity is a fascinating topic. When we start taking a close look at infinity (as if this was possible) we realize that infinity is actually something much more tangible than one may think. First, it is amazing to see that some infinite sums actually converge. Counterintuitive, isn't it? Starting with something like this: 1 + 1/2 + 1/4 + 1/8 +.... There is a very simple technique to solve this problem. Here it is: S = 1 + 1/2 + 1/4 + 1/8 +.... Now multiply both sides by 2 and you get: 2S = 2 + 1 + 1/2 + 1/4 + .... Take a look closely at this : 2S = 2 + 1 + 1/2 + 1/4 + .... Well, this is S, right? Hence: 2S = 2 + S which leads to S = 2 . One way to think about the above sum is as follow: suppose that you want to cross a bridge that is a mile long, and you want to cross it and come back. So you cross it first, travelling 1 mile. On your way back, first you have to cross half of the bridge (1/2). Then the half of the half (1/4). And so on. Hence the distance that you

All Possible Codes

One of the most famous interview questions is to generate all possible codes given a string. Here is the extract from http://www.careercup.com/page?pid=facebook-interview-questions&sort=comments : If a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings. For example: Input: "1123". You need to general all valid alphabet codes from this string. Output List aabc //a = 1, a = 1, b = 2, c = 3 kbc // since k is 11, b = 2, c= 3 alc // a = 1, l = 12, c = 3 aaw // a= 1, a =1, w= 23 kw // k = 11, w = 23 Notice that the induction part of the recursive solution isn't that complicated because we're only dealing with a mapping of either one digit (1-9) or two digits (10-26). The base case is simple. It seems exponential or highly polynomial, but works fine with moderate input size. using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace AllPossibleCode