Openlayer

Openlayer offers a programmatic way for accessing bing, google, yahoo and other maps system with one javascript api. I am using it for my next playground project.

Points of Interest

Openstreetmap has a collection of 2.5M points of interest distributed world wide. I am using them for my next playground project.

(n & (n-1)) =- 0

Check if a list of characters is palidrome

It would be easy to compare it if you have an array, some additional difficulties because you have a list. Not that much.

Given a string s and a regular expression r match the regular expression

Supported operators :

•  ^, match the beginning of the string
• $, match the end of string
• * match a sequence of characters
• [a-z][A-Z] matches the correspondent character
• Assume that there are no parenthesis

Solution

this is an interesting application of recursion

Subsequence

Find the maximum sum of a sub-sequence from an positive integer array where any two numbers of sub-sequence are not adjacent to each other in the original sequence

Solution
Max(i) = max(Ni + Max(i+2), Max(i + 1)) foreach i

Compute n to the power of m

You can make it in log (m) and that's a nice thing. X^8= (X^2)^4 so i can actually reduce the size by half at each step. Anyway if n is odd there is the need of an additional multiplication X^9=X * (X^8).

Compute (n k)

The solution to this should be recursive and similar to the classical fibonacci one,
given that (n k) = (n-1 k-1) (n-1 k)

A couple of new features to PicPlacer

Mario added a couple of new features to PicPlacer (I wanted to have more time to work on this myself). Now it's possible to tag a whole album with a location and to search locations.

A robot is moving in a rectangular board

It can move either down or right and the board is N x M. How many path does the robot have?

Solution:

Steps are N+M and we can chose N, so ( N+M  N) is the binomial factor we are looking for.

A children can hop either 1, 2, or 3 steps in a stairway of N steps.

How many combinations do you have?

Design a smart pointer in C++

Solution Draft:

reference counter should be shared among all the instance of the pointers referring to the same object. So it's better to dynamically allocate a pointer.

Given a list and a pointer to a node delete that node.

Generate all the valid parenthesis for a string whose length is n

Solution:

- left parenthesis ( is valid if we have any left
- right parenthesis ) is valid if we have any left and there is no syntax error

An interesting problem is to validate a string made of parenthesis

Generate all the subsets of a given set

This could be tricky unless you realize that given an set of size n there are 2^n subsets. An element can be in or out, so 0/1 and this means that you just need to generate all the binary numbers from 0  to n. The binary representation of each number will tell you whether or not you need to include the element (bit i = 1 means element in).

Attaching a wall to physical locations: friendships is about sharing common experiences over the time

How many times you go to a museum, see a painting and wanted to express your opinion about it? How many times you go to a new restaurant, have a good dinner and wanted to leave a good comment about the chef? How many times you enjoy your night in that new pub and wanted to say this in public and not just to your friends. How many times you are in a physical place and wanted to know what are the nice places to see in the nearby, and wanted read the opinions of the people who have been there before?

Imagine a mashup between Bing (or Google) Maps and Facebook Wall. You can attach a Wall to any physical location in the map and you can immediately start commenting and leave your opinion in these walls. You go to see a movie and you can get the comments of the people who have been in the cinema before, and leave yours if you like. You just want to find good places for an hangout, well you take your mobile and the map will suggest where to go given the experiences of past people. Anyone, not just your already known friends.

This will be an extension of current Facebook Wall.

This is my current playground project. Reattach Walls to physical locations, and give the opportunity to different people to get in touch just because they share an experience in place and not because they are already friends. They don't need to be there at the same time, they just need to share the place.

place n queens on a chessboard

typical recursive solution where we tentatively put a queen, if this doesn't violate conditions in column i. Then continue in  submatrix i+1, i+1. Then remove the queen. the important thing is that we accumulate the intermediate result.

Generate all the permutations of a given set.

This can be solved recursively.

{a1} -> a1
{a1, a2} -> {a1, a2}, {a2, a1}
{a1, a2, a3} -> {a1, a2, a3}, {a1, a3, a2}, {a3, a1, a2} , {a2, a1, a3}, {a2, a3, a1}, {a3, a2, a1}

So you can generate f(n) given f(n-1). pretty easy

Mixing reality with other sources: can I have Facebook there?

Wikitude and Layar are two lovely apps for your mobile. Both of them use your physical location and provide information about what is in the nearby including Wikipedia pages, Images from Panoramio, Videos from youtube and many other additional layers.

The only thing that is missing is a layer with the Facebook pages describing closer places or closer shops. I believe that this application can be useful to monetize in the mobile world. If I am in a mobile environment my location is my query. There is no need to submit a query based on keywords to get some information in return. Similarly, there is no need to subscribe a feed. I can just use my location and get what is interesting around me.

Stack a set of n boxes from largest to smallest

Recursively or with dynamic programming