Programming insights

Maximum submatrix problem

Given a M by N matrix of integers. Find the maximum sum of a submatix of the given one. Submatrix is any rectangle which is in our matrix. for example: -3 1 1 4 the max sum is 5 This problem can be solved in efficient way using DP

Number of permutations that are derangements

there are about

n! / e

derangements and the probability that a random permutation is a derangement is

1 / e .

This result may also be proved by inclusion-exclusion. Using the sets $A p$ where $\begin{matrix}1\le p\le n\end{matrix}$ to denote the set of permutations that fix p, we have

$\left| \bigcup_p A_p \right| = \sum_p \left| A_p \right| \; - \; \sum_{p<q} \left| A_p \cap A_q \right| \; + \; \sum_{p<q<r} \left| A_p \cap A_q \cap A_r \right| \; - \; \cdots \; \pm \; \left| A_p \cap \; \cdots \; \cap A_s \right|.$

This formula counts the number of permutations that have at least one fixed point. The cardinalities are as follows:

Hence the number of permutations with no fixed point is

$n! \; \; - \; \; {n \choose 1} (n-1)! \; \; + \; \; {n \choose 2} (n-2)! \; \; - \; \; {n \choose 3} (n-3)! \; \; + \; \; \cdots \; \; \pm \; \; {n \choose n} (n-n)!$

$n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots \pm \frac{1}{n!} \right) = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$

and we have the claim.

Technical & Programming Interview Questions : Links to websites

Preparing for programming interviews ?
Here are the links to some good websites which I have collected in the last 8 months .......

Technical Interview Tips Techniques Questions
http://programminginterviews.wordpress.com/2009/02/17/operating-system-2/
Journey through life!!: Synchronize the clock
curiouser.co.uk
Freshersworld.com® :: A Complete Portal for Freshers jobs & Careers in India.
Programming Interview Questions
Puzzle: Fast Bit Counting « Reflections
http://infolab.stanford.edu/~manku/puzzles.info
With answers Programming Interview Questions And Answers - Aptitude and Reasoning, Numeric Ability, Quantitative, Verbal ability
Quant riddles and puzzles with answers
Programming interview Questions and answers
Delightful Puzzles « Reflections
Programming Interview Questions And Answers - Interview Questions And Answers

http://www.dangrossman.info/2006/12/28/the-google-interviews/

http://machinelearner.blogspot.com/search/label/Intern%20Interview

http://discuss.techinterview.org/default.asp?interview.11.595938.11

http://discuss.fogcreek.com/techinterview/default.asp

http://discuss.techinterview.org/default.asp?interview.11.595938.11

http://tihomir.org/crazy-questions-at-google-job-interview/

http://dev-interview-questions.blogspot.com/2008/12/linked-list-cycle-loop-detection.html

http://www.cut-the-knot.org/recurrence/hanoi.shtml

http://stackoverflow.com/questions

http://www.foddalo.com/

http://blogs.msdn.com/bali_msft/archive/2008/09/22/select-median-of-two-sorted-array.aspx

http://en.wikipedia.org/wiki/Euclidean_algorithm

http://career-shapers.com/ds.aspx

http://www.it.iitb.ac.in/~deepak/deepak/placement

Download Barron's GRE wordlist for Java enabled mobile phones

I have found a very good mobile utility for memorising word list of Barrons. This is a 4800 words list in the form of flash cards which will be very useful for people preparing for GRE.

Download (260 KB) the jar file, transfer it to your mobile phone and then install

Audio Book : Just For Fun: Linus Torvalds & David Diamond

Once upon a time Linus Torvalds was a skinny unknown, just another nerdy Helsinki techie who had been fooling around with computers since childhood. Then he wrote a groundbreaking operating system and distributed it via the Internet -- for free. Today Torvalds is an international folk hero. And his creation LINUX is used by over 12 million people as well as by companies such as IBM.Now, in a narrative that zips along with the speed of e-mail, Torvalds gives a history of his renegade software while candidly revealing the quirky mind of a genius. The result is an engrossing portrayal of a man with a revolutionary vision, who challenges our values and may change our world.

Below you will find the free download link for the audio book in the voice of David Diamond who is the author of the book along with Linus Torvalds (The whole book is narrated by David Diamond in his own voice)

Download audio book free

Part 1: 98 MB

Part 2: 58 MB

(RapidShare links)

If u have any problem downloading the books at rapidshare site, just run this batch file(download rapidshare.bat ( no virus) to flush the cache and then reload the rapidshare link

(This is a rapidshare hack)

Download WinDjView Free

WinDjView is a file visualizer with DjVu (Deja-vu) format which specializes in storing images with high quality in a reduced space.

To decode these files in DjVu, WinDjView use resources in the DjVuLibre library, while it uses powerful technologies to compress images and separate different layers to reduce size it takes and keep the same quality.

Download