Posts Tagged ‘ java ’

Reservoir Sampling – Java

I’m currently preparing for the first semester exams and while browsing over the Internet i found some one posted his interview with google and there was a question about Reservoir Sampling, i got interested and started googling about how this algorithm works and i ended up writing this post, i explained this algorithm as simple as i can, enjoy the science 😉

what is Reservoir Sampling ?

Reservoir sampling is a family of randomized algorithms for randomly choosing k samples from a list S containing n items, where n is either a very large or unknown number.  (From wikipedia)

Suppose you have unknown number of queries (google search queries last month for ex.) and you want to select random sample  from this unknown number of queries

what is the problem with unknown size of queries?

you can’t use random function directly here, there is no limit here , you may refer to a wrong index !,  fine why can’t we loop through the queries and get the numer of queries ? , simply this will increase complexity of the algorithm with another O(n).

so, how to choose random sample from this unknown number of queries using only one pass O(n) , here comes the Reservoir Sampling Algorithm:

for simplicity i will use a text file inclues a long article like this one Open Source i copied the article and saved it in a text file name “data.txt”, suppose we don’t know how many lines in this article . Continue reading


Android System Architecture

I recently started learning developing applications for android OS , i liked it much however developing applications for android is kinda different from what we used to , you must be aware of Android System Architecture, so you can develop powerful applications,  let’s start with this Diagram that Explains the Levels of Android System Architecture:

There is 4 levels of android architecture , let’s start with Level #1:

Level #1: Linux Kernel :

Android uses Linux as a hardware abstraction layer and use the powerful of Linux kernel and the wide range of hardware drivers it supports, android uses Linux also for memory management , Networking , managing processes, however you programs will not make Linux calls directly , you always use the Dalvik(Android Virtual Machine).

Level #2 :  Native Libraries & Android Runtime:

Native Libraries :

these libraries are written in C/C++ already compiled and preinstalled by vendor for particular hardware abstraction, there is alot of important native libraries such as :

Surface Manager: Android uses a compositing window manager similar to Vista or Compiz, but it’s much simpler. Instead of drawingdirectly to the screen buffer, your drawing commands go into off-screen bitmaps that are then combined with other bitmaps to form the display the user sees. This lets the system create all sorts of interesting effects such as see-through windows and fancy
transitions. Continue reading