Programming Interview Tip : What is the probability that when you open a random page in a phone book the contact you are looking for is in there?

Lets say the phone book pages are numbered from  1 - 1000. And assume that the contact is definitely there in the book.

So when you randomly flip open a book there are 1 of 500 choices that it is one one of the two pages that appear before you.

So the probability is 1/500.

Next Question : How many attempts will it take for me to be certain that the contact is there? 
Well you can NEVER be 100% sure .... for obvious reasons :)

Next Question : So how many attempts will it take for me to be 50% sure that the contact is found in one of the two pages that show up?
The 50% is called percent confidence in statistics lingo.
This is best solved by the difference from 1 for the probability of the contact NOT being on the page.
For each attempt to fail we need to multiply 499/500 . So for n attempts to fail it is (499/500)^n. So the probability of it being successful in n attempts is {1-(499/500)^n}
So you need to solve the equation :
{1-(499/500)^n} = .5
which is obviously :
(499/500)^n = .5
And taking log to the base 499/500 on both sides (using python) :

>>> math.log(.5,499/500.0)
346.22690104949118

n = 347 attempts

double verify :

>>> math.pow(499/500.0,346.22690104949118)
0.5

An awesome C# template engine

There literally isn't anything (beyond writing your own operating system level stuff .... and I sure someone did that too ;) ) that I do not see being (already) done with .NET

Want to embed a programming language .... been there done that.
Want to write a highly scale-able object / document database .... done.
Additionally there are a large number of projects that were written first in java and ported to C# (e.g. sharpssh).

And the latest case in point and the reason for this post is a template engine. The StringTemplate. (If you want to learn how to write your own engine ... even that information is available!)

For StringTemplate I suggest that you first view the Five Minute Introduction : http://www.antlr.org/wiki/display/ST/Five+minute+Introduction

And to see it in use take a look at a code project article : http://www.codeproject.com/KB/codegen/DotNetCodeGeneration.aspx

Next you should look at the cheat sheet : http://www.antlr.org/wiki/display/ST/StringTemplate+cheat+sheet

One point to note is that stringtemplate takes an innovative approach to for loops. It does this by using anonymous subtemplates.
Basically :

<attribute:{anonymous-template}>	Apply an anonymous template to each element of attribute. The iterated it atribute is set automatically.
<attribute:{argument-name_ | _anonymous-template}>	Apply an anonymous template to each element of attribute. Set the argument-name to the iterated value and also set it.

Looping through a hashtables and lists e.g. is covered in an example here : http://stackoverflow.com/questions/2325782/nested-loop-in-stringtemplate


And if this doesn't suit you (why wouldn't it? ... I'd like to know). Some project from here definitely will : http://csharp-source.net/open-source/template-engines
Enjoy!

Programming interview tip : Finding anagrams

Find all the words in a list of words (listA) which are anagrams of a single input word (wordA).

Bad solution (the trap): 
look at all the possible permutations of wordA and find them in listA.

This is a terrible solution and has a complexity of countOfCharactersInWord(wordA)!
where ! is the factorial symbol :)

Good solution:
take all the characters in wordA and sort them. Then compare it with the each item in listA first sorting the characters of that item as well :)

In python :


This yields for my friend "omair" the following interesting (i made them bold) anagrams:

mario
arimo
moria
omari
maori
moira

I used the SCOWL wordlist for this. You can get the complete working code (including the wordlist) from here:
https://bitbucket.org/basarat/pyanagram/overview
Enjoy!

Programming interview tip : Combinations from a list

This question will be discussed in python, since it is uber simple to write functioning yet short programs in :)

Say you have a list of n items e.g.
seq = [1,2,3]

Find products of all items with each other
This is the simplest question.
Solution:


This gives the following output:

1 * 1 = 1
1 * 2 = 2
1 * 3 = 3
2 * 1 = 2
2 * 2 = 4
2 * 3 = 6
3 * 1 = 3
3 * 2 = 6
3 * 3 = 9

Find unique products of the items with each other
This means that you need that you can only have 1*2 or 2*1 etc
Solution: Really simple to do. Each time in the inner loop start at i rather than 0 as shown:


This gives the following output:

1 * 1 = 1
1 * 2 = 2
1 * 3 = 3
2 * 2 = 4
2 * 3 = 6
3 * 3 = 9

Basically notice at each increment of i we do not allow j to go back.

Find unique products and do not multiply a list item with itself
This means that you cannot have 1*1 , 2*2 etc.
Solution: In the inner loop you need to avoid starting at i and rather start at i+1 (since this is the i*i case we need to avoid).

Also if this is all you do at i = n the inner loop will not run so its better to stop the outer loop at n-1


In both cases the output will be:

1 * 2 = 2
1 * 3 = 3
2 * 3 = 6

Enjoy!

Actionscript Tip : The text layout framework

A great podcast by Lynda.com explains in great detail the new features provided by TLF over classic text fields.



Amongst other things I was really blown away by the flow of text between various text fields which you can watch at 5:30.
Enjoy!

C# 101

This came up on my reader.google.com :

And I thought I had added c# expert blogs :)

Using advertisements in android with flex

It is really easy to setup admob with a flash / flex android application. The primary objective is to make free applications for the android marketplace and make revenue with advertisements.

Basically:

• You need to setup a website with admob. 
• Use the javascript that admob gives you and host it in an html file on your own site (or google appspot!).
• Test your website html page in your phone's browser to make sure it displays the way you want
• Simply use StageWebView (http://help.adobe.com/en_US/FlashPlatform/reference/actionscript/3/flash/media/StageWebView.html) to host the html web content in your application 
• Wait for the money to roll in :) 

Source : http://blog.dreamflashstudio.com/2011/02/admob-in-flash-with-adobe-air-for-android/

Enjoy!

Actionscript Creme 3

Here's what I found really interesting recently regarding actionscript / flash / flex


Deploying to and android device from Flash Professional

Really simple to do :)


Implementing multitouch gestures : zoom / rotate on Android : 

And you can do them simultaneously as well of course!

Converting an Android flex application to iOS
Can be done in just 6 minutes :)



Enjoy!

Fastest way to get your web application on chrome web store

Hands down its appmator : http://appmator.appspot.com/

You just give it your url
Screenshot:

Fill in some basic Optional information and it gives you a zip file.

Upload that file to chrome web store and you are good to go!
It cannot get any simpler than this :)
Enjoy!

How angry birds for chrome web store was written

GWT (Google Web Toolkit) ! A complete presentation on the subject was given at Google I/O 2011 titled "Kick-Ass game programming with GWT". Google released a library forplay : http://code.google.com/p/forplay/ which makes game programming with GWT easier (includes things like a Box2D physics engine port for GWT).

You can find the presentation below for your offline viewing pleasure :



Enjoy!

Actionscript Creme 2 : Books!

And all of these books have great reviews. I believe that flash is the best platform for indie games. You can target the key main dream platforms (android, iphone, facebook, chrome web store) will the same code. And that is simply unbeatable.

So here is a list of books that I would like to go through to be an mid level expert in the matter of flash gaming :

Beginning 
This book is a beginners guide and has 4.6 stars as of this writing on amazon!














Going Advanced! 
By the same fellow (rex spuy) that wrote the above title. Again amazing amazon reviews!












Go multiplayer! 
Start here:
And at 400 pages not a heavy read :)














Enjoy!

Actionscript Creme :1

There is a lot of great actionscript content being generated by the community. I thought I'd start a series of blog post about these so here goes.

Handling Orientation in Flash CS5.5 for Android
http://www.youtube.com/watch?v=TKtMEzzzf4I

Basically you create two keyframes with different orientations of the stage and toggle them using actionscript on the resize event by comparing the device height with device width.

Flash Typing text effect 
http://www.youtube.com/watch?v=rjCo0w3u2cg
This was super neat and easy to do. I wonder why I didn't think of it. You just split the string you want to type on the screen and store it in an array. Then in the ENTER_FRAME event you simply shift the array appending the shifted character to a textfield on the screen making sure you remove the event listener after all characters in the array have been printed to screen.

Creating Paypal buttons in Flash 
http://tutfree.com/active/quick-guide-creating-paypal-buttons-with-actionscript-3-0.html
Really simple to do really :)

A simple lottery application
http://www.ilike2flash.com/2011/06/lottery-app-in-actionscript-3.html
An easy to follow tutorial that actually makes a somewhat useful application :)

Creating a Picture gallery

http://www.youtube.com/watch?v=q5pVocHKcS8&feature=player_embedded
A simple tutorial. More about a simple gallery banner rather than a Gallery. Just useful to get the creative juices flowing for a newbie.


Now for a book I would like to read about actionscript :















Enjoy!

Code first development with .NET hits primetime

I remember code first development since the days of django :
https://docs.djangoproject.com/en/dev/intro/tutorial01/

This was on of the best database experience I have had.

Now the same thing is possible out of the box with .NET using code first devleopment. The launch blog post is here :
http://weblogs.asp.net/scottgu/archive/2010/07/16/code-first-development-with-entity-framework-4.aspx

I just came across a really nice Associations tutorial here : http://weblogs.asp.net/manavi/archive/2011/05/17/associations-in-ef-4-1-code-first-part-6-many-valued-associations.aspx

Enjoy!

WPF Tip : Dependency Property changed callback not getting called

If you have a dependecy property of type IEnumerable databound to an INPC property simply raising a propertychanged event in the INPC property will not cause the changed callback of the dependency property to get called.

This is because apparently WPF internally uses an optimization where it checks the equality before calling the callback mentioned in the dependency property metadata. 

To force this callback you can assign the a new Enumerable instance to the INPC property. 

WPF Tip : Events Or commands which is called first?

The answer is Event. This is because the event is used to create the command by the control internally. Even click is handled before the command on a button :)