Software / Programming/ CS

Origins of code interviews questions

2011-11-19T23:03:00.000-08:00

Have you ever wondered where are all those brain teasing ,programming interview questions coming from? You can find them gathered and published in at least a dozen of web sites and books. You read the book before the interview and try to memorize, ideally understand the answers. Then when the interview is over, you forget them.
I was curious where are any of those problems used in practice. I mean, there must be some application. For example, take the short formula (n&(n-1)) ==0, where do you ever need to determine if a number is a power of 2? Of course, since computers are using binary arithmetics, you would think this has many application. I tried googling and I could not find any. I found out about perfect numbers http://mathforum.org/dr.math/faq/faq.perfect.html that are computed based on but I don't think you need to verify if a number is a power of 2 there.
Finding a missing integer in an array of consecutive integers has a simple solution using bit manipulation. I was able to find one application thanks to this site: http://blogs.oracle.com/malkit/entry/finding_missing_value
and after reading it, I got the idea of another application: to find a missing packet in a sequence of received packets, where each one has a sequence number (like in TCP protocol).

Parallel sorting algorithms in databases - reading papers

2011-09-01T22:01:00.000-07:00

I'm reading a lot of papers about sorting these days and it's getting a little funny. Pretty much every paper starts the same.

A guide for writing the "Introduction" of a paper about parallel sorting algorithms:

- Your first sentence : Sorting is a (fundamental/most important) (kernel/operation/building block/task) in databases.
- Say some of the common uses of sorting in databases (ORDER BY, Merge Join, etc.)
- Mention Moore's law
- Future trends: The number of cores will be increasing in the future (of course it will)

Apart from finding the introductions a little funny, the content of the papers is getting rather complex once you are done with the introduction. For example this paper "Fast Sort on CPUs and GPUs:
A Case for Bandwidth Oblivious SIMD Sort" that has won an award has some of the most sophisticated aanlysis and terms. It helped me understand my own parallel algorithms better.

2011-03-05T16:49:00.000-08:00

After reading http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx
I will rewrite all my methods to use a List instead of an ArrayList.

Difference between List, HashTable and Dictionary

2011-03-05T16:28:00.000-08:00

According to http://msdn.microsoft.com/en-us/library/ms379571(v=vs.80).aspx, a Hash table is the fastest data structure in C# when you know the number of records you are going to store because of the collision resulution method.

The better performance of a Hshtable over a Dictionary is doubtful however, due to boxing/unboxing which occurs when using a HashTable (http://msdn.microsoft.com/en-us/library/4yh14awz(v=vs.80).aspx).

Some sources say that HastTable is simply used for backward compability, and the new programs should always use a Dictionary.

My approach will be to use a Dictionary when I have to search for records and a List when I simply add new records or process records one by one. I will be curious to test the performance of a HastTable over a Dictionary though for a fixed-size array.

2011-03-05T16:23:00.000-08:00

A good article about how to improve the performance of a DataReader:

http://sqlblog.com/blogs/adam_machanic/archive/2006/07/12/sqldatareader-performance-tips.aspx