The problem:

Given two sorted arrays, “a” and “b”, with sizes “sa” and “sb” respectively, find the median of the union of these arrays.

Complexity requirements: O(log(sa + sb)) in the worst case, both time and space.

There are a few solutions for this problem, but non of them is as intuitive as the solution of a more general problem: The Select Problem:

Given two sorted arrays, “a” and “b”, with sizes “sa” and “sb” respectively, find the k-th smallest element of the union of these arrays. Under the same complexity requirements as above.

Once the select problem is solved, the median problem is solved as well, since the median is the ((sa + sb)/2 + 1)th smallest element (if sa+sb is odd), or the average of the two middle elements (if sa+sb is even).

So, let’s solve the select problem first:

The idea is to (virtually) partition “a” into two arrays: “a_left” and “a_right”, and the same for “b”: “b_left” and “b_right”, such that the size of “a_left” plus the size of “b_left” is exactly k.

Ideally, a_left will be a[0..(k/2-1)] and b_left will be b[0..(k/2-1)]. Unless, of course, a is smaller than k/2, in that case we’ll take “sa” elements from “a” (i.e. the whole array), and the rest of the elements (k – sa elements) from”b”.

Let’s assume that a_left has “na” elemetns, and b_left has “nb” elements. As we stated before, na+nb = k.

Trivial case 1:

k = 1. i.e., we need to find the smallest element of the union of “a” and “b”. Obviously, it’s either the first element of “a” or the first element of “b”. This operation is cheap. O(1)

Trivial case 2:

a[na-1] = b[nb-1]

In this case, the k-th smallest element is a[na-1] (or b[nb-1]): We have exactly (na + nb = k) elements smaller than it.

Case 3:

a[na-1] < b[nb-1]

This is the interesting case. If a[na-1] is smaller than b[nb-1], then:

1. The k-th smallest element cannot be in the “a_left” array:

All elements in “a_right” are greater than any of those in “a_left” (“a” is sorted). Total: sa – na elements

All elements in “b_right” are greater than any of those in “a_left” (“b” is sorted and a[na-1] < b[nb-1]). Total: sb – nb elements

At least one element in “b_left” is greater than any of those in “a_left” (we already know that b[nb-1] is such an element). Total: 1 (at least)

So, for any element in “a_left”, there are at least (sa – na + sb – nb + 1 = sa + sb – k + 1) elements which are greater than it.

The k-th smallest element must have exactly (sa + sb – k) elements greater than it. Hence, none of the elements in “a_left” can be the k-th smallest element.

2. What we do know about the elements in “a_left”, is that all of them are among the k smallest elements (but none is the k-th smallest) – Using the same logics above.

3. None of the elements in “b_right” are the k-th smallest element. We already know that all the elements in “a_left” and all the elements in “b_left” (total: k elements) are smaller than any element in “b_right”

From the three observation above, we can state that the k-th smallest element of the union of “a” and “b”, is the (k – na)th smallest element of the union of “a_right” and “b_left”: We excluded “a_left” in (1), excluded “b_right” in (3), and we already have “na” of the k smallest elements, so we need to find the (k-na)th smallest in the arrays not excluded.

The last case, where a[na-1] > b[nb-1] is similar to the previous case, except that “a” and “b” have exchanged there roles.

Here is the implementation in C of the above:

--------- Note: Some RSS readers might display this post with incorrect format. View original post at AmirWatad.com

Finding The Median Of Two Sorted Arrays

--------- Note: Some RSS readers might display this post with incorrect format. View original post at AmirWatad.com

Array Indexing in C

Have fun

--------- Note: Some RSS readers might display this post with incorrect format. View original post at AmirWatad.com

Infinite zip File

Have fun

--------- Note: Some RSS readers might display this post with incorrect format. View original post at AmirWatad.com

Blogging From BlackBerry

In your shell, type this:

You’ll get this:

The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren’t special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one– and preferably only one –obvious way to do it.
Although that way may not be obvious at first unless you’re Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it’s a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea — let’s do more of those!

via commandlinefu

Have fun

--------- Note: Some RSS readers might display this post with incorrect format. View original post at AmirWatad.com

Wisdom by Python (Easter Egg)

After a search at Google, I found the problem, and the way to fix it: Looks like Ubuntu had decided to rename the user-agent into “Shiretoko” which is the codename of firefox 3.5, instead of “firefox”.

Because of the new user-agent name, Facebook does not recognize the browser as firefox, and thus disables some features that are browser dependent.

In order to fix the problem:

1. In the URI bar (that’s the place where you type the URLs of websites you want to visit), type “about:config” (without the double quotes).

2. Click the funny button “I’ll be carefull, I promise”.

3. Now look for “general.useragent.extra.firefox”, right click it, and choose “Modify”.

4. Instead of “Shiretoko”, type “Firefox”. (e.g. if you had “Shiretoko/3.5.4pre” it should become “Firefox/3.5.4pre”.

That’s it, now the world should be a better place

via vimtips.

--------- Note: Some RSS readers might display this post with incorrect format. View original post at AmirWatad.com

Fix Facebook Chat in Firefox 3.5 (Shiretoko) in Ubuntu

You will get something similar to this:

The code I used for the above is:

Or in general:

Where DOCUMENT_URL_HERE should be replaced by the document’s URL

via Google Operating System.
Smile

--------- Note: Some RSS readers might display this post with incorrect format. View original post at AmirWatad.com

Embed A Document Using Google Docs

Now you want to run the same command, but with 2.34 instead of 1.23
A nice way to do it is this:

Meaning, run the last command (!! is also called ‘bang bang’, and it’s substituted by the last command you executed), and replace every instance of 1.23 by 2.34

via Unix Bash Scripting.
Have fun

--------- Note: Some RSS readers might display this post with incorrect format. View original post at AmirWatad.com

Re-Use A Bash Command With Different Parameters

By adding the following line to your vimrc file (typically, it’s located at ~/.vimrc), scripts will automatically become executable.

au BufWritePost * if getline(1) =~ “^#!” | if getline(1) =~ “/bin/” | silent !chmod a+x <afile> | endif | endif

(meaning, if the file includes #! with “/bin/” in the path, apply “chmod a+x” on this file).

via shell-fu.

Have fun

--------- Note: Some RSS readers might display this post with incorrect format. View original post at AmirWatad.com

Make Shell Scripts Executable By Default

A cool service, Readtwit, solves this problem intelligently: Using Readtwit, you can easily create a RSS feed of all links appearing in your twitter stream. The service will fetch the links, and send the full story to your RSS reader. It allows you to filter the tweets (block people and block hashtags).

Neat and time-saving. Try it and have fun

--------- Note: Some RSS readers might display this post with incorrect format. View original post at AmirWatad.com

Fetch Links From Twitter Into Your RSS Reader