Antonio Gulli's coding playground

Books: "Cracking the coding interview"

2012-01-24T23:37:00.000-08:00

Cracking the coding interview is one book you should definitively have in your bookshelf, and you should keep reading it now and then.

I have a passion for reading and solving coding interview questions and never found such a detailed source of information.

The book starts with several suggestions on how preparing yourself for an interview. This is an aspect that many people underestimate, whilst having a well-written CV, a personal blog, and possibly a number of open source projects is definitively important. This book gives you a number of good suggestions.

Then there is long part discussing interview questions with a broad coverage of basic data structures, algorithms, programming languages, databases and threads and some advanced coding questions.

The style is concise and you can read each Chapter in isolation. Gayle made an amazing job in illustrating not just the solutions, but several techniques that you can use for solving new problems. Plus, those interview questions, the solutions and the techniques, are not just hypothetical but are very useful in your day by day life as Dev or Researcher.

I would suggest the author splitting the Chapter 7 "Mathematics and Probability" into two separate parts and expand both of them because they are very important during interviews and the current description is probably too synthetic. Also, a Chapter on String algorithms and another one on Parallel programming would be probably useful to have because people will look for them elsewhere.

Having said that, this is definitively a must have book and the money you spend will definitively generate a great return on the investment.

Thanks Gayle for writing it.

Compute if a number is a multiple of 5

2012-01-07T23:33:00.000-08:00

You can use just bit operations

Discuss memory layout for C programs

2012-01-07T00:11:00.000-08:00

Ideally you should discuss all the different areas that are used

Find if there is a number duplicated in an array

2012-01-06T23:24:00.000-08:00

Good collection of different techniques. useful to know.

Let's talk about C++ const

2012-01-05T23:13:00.000-08:00

when and where do you use it?

Sphinx: open source search

2012-01-04T10:45:00.000-08:00

Sphinxsearch is a scalable open source search server that seamlessly integrates with Mysql. Documents are stored in mysql and the server creates its own external indices. The index and search performance are quite good (60+ MB/sec per server, 500+ queries/sec), and the server allows to easily extend your own ranking functions. A sql-like language is supported for searching. Apparently, the largest cluster of sphinx servers is currently indexing 3billions of documents and it serves 50M queries per day. An interesting feature I am going to use is the ability to search all the geo-points within a fixed radius.

News dataset

2012-01-03T11:26:00.000-08:00

Republishing my link to the open collection of news articles.

AG's corpus of news articles

Openlayer: an example of geo-location

2012-01-02T22:03:00.000-08:00

Openlayer an example of map switching

2012-01-01T21:56:00.000-08:00

Openlayer

2011-12-17T21:23:00.000-08:00

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

2011-12-16T21:09:00.000-08:00

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

2011-12-15T05:59:00.001-08:00

Check if a list of characters is palidrome

2011-12-14T13:30:00.000-08:00

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

2011-12-14T09:41:00.000-08:00

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

2011-12-13T10:49:00.000-08:00

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

2011-12-12T17:20:00.000-08:00

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)

2011-12-12T15:47:00.000-08:00

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

2011-12-11T06:39:00.000-08:00

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

2011-12-10T06:40:00.000-08:00

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.

2011-12-09T06:40:00.000-08:00

How many combinations do you have?

Design a smart pointer in C++

2011-12-08T06:40:00.000-08:00

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.

2011-12-07T00:23:00.003-08:00

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

2011-12-06T06:40:00.000-08:00

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

2011-12-05T06:40:00.000-08:00

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

2011-12-04T02:39:00.000-08:00

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.