Random Puzzles

Facebook Superpatterns puzzle - The solution 2

2007-07-27T17:38:00.000-07:00

My earlier blog post had a brute force approach to solving the super patterns puzzle. The order of the program was in the order of n!. Didnt think it was worth coding it up. Might use it to validate this new solution. The solution is based on building larger superpatterns from smaller ones. This is how the solution would look like ..
Take a 2 -subpattern for eg. The subpatterns would be
{1,2} and {2,1} .. the superpattern is {1,3,2} other "superpatterns" that are not combinatorially smallest are {2,1,3}, {2,3,1} and {3,1,2}.
We can build higher superpattern from lower ones like this.
For the 2-subpatterns to become a 3 -subpatterns, it would have to satisfy ..
{3,1,2}
{3,2,1}
{1,3,2}
{2,3,1}
{1,2,3}
{2,1,3}
Which in a way means that we will have to add a "higher" element in the sequence or superpatterns that generated the lower or 2-subpatterns to get the 3-subpattern.

The trick if figuring out the smallest combination of adding this additional number. More commong soon ...

Facebook puzzle - SuperPatterns the solution

2007-07-22T15:51:00.000-07:00

Here's my solution to the facebook superpatterns puzzle. The actual puzzle is available here. The solution will follow a pattern that I used to solve the GridFlip puzzle, again from facebook.

This solution is completely based on information on superpatterns available from this wikipaedia article

Identify characteristics of the problem space and define rules that will reduce it.
1. The relative weights of the numbers in the superpattern are important, the actual numbers dont matter. What I mean by that is, if [25314] is a superpattern, then adding one to all numbers we get [36425] which is also a super pattern. Based on this, we can safely assume that if n is the length of the super pattern, the possible numbers in the pattern can only be 1 to n.

2. If [25314] is a super pattern, then inverse [41352] is also a super pattern. This true because if 123 is present in a subpattern, 321 is also present in the subpattern ??

3. There can be no repetitions.

4. Minimum lenght of a super patterns with a k-subpattern is k+k -1 (The inclusion and exclusion principle in the wiki page).

Based on the above principles. The size of a problem space for a k-subpattern (subpattern of size k) will be ..
*Minimum lenght of the superpattern n = 2*k -1.
*Number of possible number we can generate for n = n! (Assuming numbers are unique).
*Since the inverse is equal problem size = n!/2;

so if we have a 3-subpattern (k=3), which has 3! permutations, we have to make sure that each of the n!/2 possible solutions satisfy the k! subpatterns.

=> Complexity of the algorithm = (2*k-1)!/2 * k!

Using the above rules, I constructed a base solution set, assuming k =3 -> n =5.
The solution set would look like this.
12345, 12354 ... 54321.

*We can further reduce the problem by adding more constraints on the possible values for each number in the superpattern. What I mean by that is ..
lets say x1, x2, x3 .. xn are the number in the superpattern and if y1, y2, y3 ..yk are the elements in the subpattern. Each subpattern must have k number => the first number in the subpattern y1 can be selected from numbers x1- xl (where l = (n-k) +1), similarly y2 can be selected from x2 - xl (where l = (n-k) +2).
Here's an example .. if [25314] is the superpattern the subpatterns of length 3 can be
214, 514, 314 => the first number in the subpatterns is selected from 253.
254, 234, 214 => the first number in the subpatterns is selected from 531.

Output Rule.
*If you look at the subsets you will notice that the first number in the subset will have all possible relative values. What I mean is that for a 3-subset, the first number must be 1,2,3 (Relative weights). The same with the remaining numbers.

We now have a possilbe solution set.
Rules that we can impose on the solution set ie, the set of possible values for the first number in the subpattern must contain the largest in the sequence, the second largest in the sequence .. the smallest in the sequence ..

The solution:
Generate possible solutions and validate against the output rules.

Solution and source code to this puzzle comming soon ..

Find something wrong with this solution, or want to add something .. please add a comment or email me at my gm@il acccount blogtamma.

Using a counting semaphores to control queue access

2007-07-21T01:06:00.001-07:00

Controlling data transfer between threads in a multi-threaded application can be quite a challange. I recently had a problem where a thread in a program was generating data and another thread is needed to process the data. This a classic problem for any web service. There is a thread that listens to data on a socket. As soon as it receives data on a socket it build a request / or can just read data and add it to a queue.
Once the data hits the queue, another thread reads the data from the queue and processes the data.
This is a classis multi-threaded problem, there are two threads trying to access a shared resource - the queue. The solution to this problem, use a counting semaphore to restric access to the queue. The pseudo code for this would look like this.

This is also a classic case of the producer consumer design pattern.

Here's the sample pseudo code ..
Main thread..

[... do something ...]
Semaphore _queueSema = new Semaphore(0,1000); //Initial count 0, max 1000;
[.....]

Producder Thread ..
queue.Enqueue(item);
_queueSema.release();

Consumer Thread ..
_queueSeam.Aquire();
queue.Dequeue();

Note: This is assuming that there is only one consumer and one producer. If there are multiple consumers and producers the queue access will have to be protected by a CriticalSection or some mutual exclusion class and its always a good idea to do this.

SiteMap

2007-07-21T00:17:00.000-07:00

Facebook GridFlip - The solution
Facebook puzzle GridFlip - the problem
Thread Deadlocks
Getting google to crawl your site
Find the missing number
Anagram - Generate all possible dictionary words from a given word
Find the number of bits set in a number
Probability function
Why mobile companies should get into maps and traffic
Thread Deadlocks
Google Interview Questions
Using a counting semaphores to control queue access
Facebook puzzle - SuperPatterns the solution
Facebook Superpatterns puzzle - The solution 2
CPPRocks
TestingRocks

Getting google to crawl your site

2007-07-17T17:40:00.000-07:00

An interesting behaviour I noticed with the google crawler. I was experimenting with the different features google analytics and adsense provides and discovered an interesting way to get the google crawler to crawl this blog - adsense.
I posted a few blogs in this blog and a few days later, "googled" for this blog content and I got zero / zilch results. And looking through the adsense features I realised, adding adsense to my blog template might force google to crawl this blog to display relevant ads blah blah.. I added google adsense ads to this account and within a few hours my blog started showing up on google results. I think this will happed until they realise they dont make any money from the ads on my blog :). I will wait and see ;)

Anagram - Generate all possible dictionary words from a given word

2007-07-17T17:29:00.000-07:00

A contributed question ..
Generate all possible anagrams given a word.

The solution:
Create a hash dictionary (a one time operation). Which basically is a dictionay where each word is hashed to a value. The hash function must not take into accout the order in which the alpabets occur. Eg: rat and tar hash to the same value.
Once the hash lookup dictionary is in place, take the input and generate the hash using hte same hash function. This will point to a hash bucket whcih contains the list of all possible anagrams.

Running Time: constant. (Not considering generating the hash dictionary).

The same technique can be used if the question is extended to give all possible words where repetitions are allowed. The hash function should now ignore repeated alphabets. ie: shoot and shot should generate the same hash.

Find the missing number

2007-07-14T14:12:00.000-07:00

You are given an array of size n-1. The array contains numbers 1-n. All numbers in the array are unique. Find the missing number

The solution .. add up all the numbers in the given array. The missing number is the difference between the n(n+1)/2 and the sum.

Find the number of bits set in a number

2007-07-14T14:04:00.000-07:00

Given an integer n find the number of bits set to 1 in the number.
Solution.
1. Split the integer into 4 bit blocks. (n & 0xf << i) where i = 1to 8
2. Pre - populate and array of size 16 whcih represent the number of bit set for the number 1-15.
3. get the number of bits set in each of the 8 blocks and add them up :).

Probability function

2007-07-14T13:56:00.000-07:00

This is apparently another Google interview question ..
Write a function that take a number between 1 and n as input such that it returns true 1/n times and every other time it returns a false.

My solution, the function generates a random number between 1 and n, including 1&n. The function will return 1 every time the generated number is 1, every other time it returns a 0.

Why mobile companies should get into maps and traffic

2007-07-13T14:55:00.000-07:00

Why mobile companies should do real time traffic analysis ? sounds wierd but the more you think of it .. why dont they do it already. I was thinking about real time traffic analysis and an interesting idea cropped up.
What network enabled device is present in almost every car on the street radios and cell phones. We use radio waves (XM radio ) today to get real time traffic data. The XM transmitter gets this data from all sorts of sources. But the draw back is these sources are only available on the larger highways and mostly in north america and europe. The rest of the world doesnt have this technology, but what most of the remaining world has is cell phones. Cell networks cover almost every corner of the world (well all the important corners anyway). They have the ability to pinpoint any cell phone suscriber (most subscribers have this ability in most places .. think they use triangulation) and they have access to maps. Almost every car / bike has a cell phone these days.
Combine the fact that cell phone providers have access to maps, ability to located subscribers we get real time traffic reports for almost every road in the world :). There will always be minor (?) technical difficulties in getting live traffic reports on and from cell phones, but nothing that cant be solved with a little bits of traffic prediction technologies and data aggregation.

Want to share an idea.. this is my g m @ i l :b l o g t a m m a

Thread Deadlocks

2007-07-12T08:02:00.001-07:00

Here's an interesting technique on deadlock avoidance. We had a pretty complex multi-threaded application running C/C++ code. As with any multi-threaded application deadlocks were a major problem. The solution, serialize access to resources. This ensures that all threads enter the critical region in a serial order avoiding deadlocks.

How does it work ?
Lets say we have three threads t1, t2 and t3 that need to access resources r1, r2, r3. We create three locks/ semaphores s1, s2, s3. We enforce the rule that the locks must be aquired in the following order r1, r2, r3 ie. no thread can aquire r3 before r2 & releasing the locks must be in the reverse order.

Assuming t2 requires resources r1 r2 and r3. It first aquires the lock for r1, r2 and r3. But before t1 aquires r3 , t2 comes along, it needs resources r3 and r2. Even though the lock for r3 is available it cant aquire r3 because of the order restriction we impose. T2 waits for till t1 releases the r2 and starts processing. If we did not impose this order restriction, t2 would have aquired r3 and would be waiting for t1 to release r2. While t1 would be waiting for t2 to release r3, resulting in a deadlock.

Another interesting deadlock detection technique a little simpler to program but a little less efficient. Everytime a thread is unable to aquire a lock, it releases all its locks and calls a scheduled yeild or kills itself. Although this method works in most cases it is not really guaranteed to work at all times.

Google Interview Questions

2007-07-12T07:54:00.000-07:00

This was apparently a google interview question ..
Given a list of a billion URL's, determine if any of the URL's repeat, and the number of times the URL's repeat.

Think this is a typical crawler question. The best solution I can think of is hashing.
Hash a each URL and check the hash bucket to see if any of the URL's repeat and keep track of the counter.

Facebook puzzle GridFlip - the problem

2007-07-09T23:36:00.000-07:00

The facebook gridflip puzzle :
The puzzle goes like this .. you are given and mxn matrix consisting of integers. Two operations are permitted on the matrix, flip_row and flip_colomn.
Flip_row(x) -> Flips the sign of all numbers in the row
Flip_colomns(x) -> Flips the sign of all numbers in the colomn.

Need to calculate the smallest S with the minimun set of row / colomn operatiosn, where S is defined as the sum of SR(1-m) and SC(1-n).
SR(x) - is defined as the sum of all numbers in row x
SC(x) - is defined as the sum of all numbers in colomn x
Additionally SR(x) for all x=1-m should be posotive & SC(x) for x=1-n should be positive &

The actual puzzle is available here
The solution to this puzzle is available here ..

Facebook GridFlip - The solution

2007-07-09T01:04:00.000-07:00

Here's a solution to the facebook GridFlip puzzle. To get to the actual puzzle, navigate to GridFlip from here. Incase the puzzle has been deleted a copy of the puzzle is available here.

Before I start on the solution to the puzzle, here are a couple of rules / properties of the flip_row (R(x) ) and flip_colomns (C(x)) operation.

The order of the operations doesnt matter. eg: R(1) C(1) = C(1) R(1)
Repeated operations cancel each other. eg: R(1) R(2) C(1) R(1) = R(2) C(1)
Every operation has an "inverse" which is euqual to the operation itself. eg: for a 3x3 matrix, the following operations are valid R(0) R(1) R(2) and C(0) C(1) C(2). The following operations are equal R(0) R(1) C(2) = R(2) C(1) C(2). Ie the "inverse" of an operation and an operation are equal.
The row sum (SR(x) ) and colomn sum (SC(x)) is effected by the following operations: SR(x) is influenced by all colomn operations and just one row operation R(x). eg: SR(x) would not change if any row operation other than R(x) is applied on the input. This is similar for the SC(x).

Rules on the solution.

Sum of each row SR(x) and sum of each colomn SC(x) should be non-negative.

Here's the solution to the GridFlip puzzle based on the above rules..

Create an array with all possible colomn operations. Set the row operations to false. This array would have 2^n rows where n is the number of colomns in the input matrix. Eg: The operations would be C(0), C(1), C(0) C(1), ...
Apply each operation on each row. If after applying an operation on row x SR(x) is negative, edit the operation and set R(x) for the operation. Apply R(x) when SR(x) is negative flips the signs for all values in the row and SR(x) will become positive.
If R(x) is zero. These rows need to addressed seperately as this row will always be non-negative, but the row operation will effect C(1..n).
We now have a matrix of moves where all SR(x) is positive.
Apply the edited moves and calulate the SC(x) for each move. If SC(x) is negative the move is invalid. If both SC(x) is positive, calculate the array total S = SR(x) and SC(x).
Keep track of the smallest S to print the answer.

C++ code comming soon .....

The c++ code is located here.

Code license: Code is provided as-is .. no implied guarantess. You can pretty much do whatever you want with it. Just dont sue me if something goes wrong.

About the code .. I am a C++ newbie, this is one of my first programs in C++ and the first one using stl.