Roy's musings

Some time back a friend asked me an algorithm question: Given an integer random number generator randomN() that can generate random number in the range [0, N), how will you generate random numbers in the range [0, M) where M I used modulo arithmetic to generate the desired random numbers in the range [0, M). And I reasoned out that if N = q*M + r, every number in the range [0, r] has an occurrence probability of (q+1)/N, but the numbers in the range [r+1, M) has an occurrence probability of only q/N. It is easy to visualize this. See the diagram below: You can see that we can divide line of length N units (given in green) by lines of length M units (given in black). When N is not exactly divisible by M, in the last part alone we have only r units. So if we choose a random integer in the line represented in green, and then take a modulo M on the value, all the values except the values in the range [r+1, M) (represented in red) will occur q+1 times. But the values in that int...

This is an interesting problem that I ran into. The problem definition goes like this. You are given an array of integers. The array is considerably large (say 5 million elements). You are given two inputs: an index i in the array and an integer value v . Start searching the array for value v from the index i , and expand your search towards the two edges of the array. Return the index where the value v occurs closest to index  i . If the value v  occurs on both sides of index i at an equal distance, return the lower of the two indices. If the value v  does not occur at all, return -1. It was very interesting to solve this problem. Give it a shot, you might also like it.

The  answer  to the question "which hashing algorithm to use?"  in StackOverflow is one of the best answers I have ever read. You can find the answer here: http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed/145633#145633 Mr Ian Boyd , thank you so much for taking time to come up with such an excellent answer.

Puzzle statement: You are given the reference to the head of a singly linked list. Come up with an algorithm to find out if the linked list has a loop.  Credit:  I believe I read this problem in Sedgewick's Algorithms in C book first.

I love to come up with elegant and simple algorithms for hard problems. Recently one thought came to my mind: why don't I create a catalog of interesting puzzles that I come across. I am sure it will be useful to some people. At least to those who are preparing for an interview. So here is my first in the series. Disclaimer: I do not claim ownership of any of these puzzles that you will see in this series, unless explicitly noted. If I know the source, I give credit to the source. If I don't know the source and you do, please drop a comment pointing me to the original source of the puzzle. Here is the problem: You are given a binary search tree. For the sake of simplicity, assume that each node in the binary search tree holds an integer value and all the values are unique. Each node in the binary search tree has a reference to its right child and left child, but not to its parent. Given root, and two random nodes, find the first common parent of these two nodes. In case ...

My friend Siva asked me this puzzle. There is a set of N numbers. All numbers in this set repeat even number of times, except two numbers that repeat odd number of times. Develop an algorithm that will find these two numbers in O(N) space & time complexity. I couldn't find the solution, but the solution Siva gave and another variant of that solution that his friend gave were simply amazing. Not to spoil the fun, I am not giving any of those solutions here :-)

There could possibly be a lot of reasons for application slow down. Identifying the cause for the slow down could be a bit tricky. iostat is a tool that helps in monitoring I/O activities in the system, which might have been caused your application slowdown. iostat helps to monitor I/O activity on a per-disk and per-partition basis. There are a number of options that might suite your particular need. But I find the ones below to be good enough for my needs: iostat -x -n -p -z 5 10 -x : Show me extended statistics for each disk. -n : Don't show cryptic names of devices, if possible show readable names. -p : Show per device statistics and per partition statistics. -z : Don't show me the rows that have all zeros in them. Let us take a sample output and explore. extended device statistics r/s w/s kr/s kw/s wait actv wsvc_t asvc_t %w %b device 0.0 0.8 0.0 10.8 0.0 0.0 0.0 0.6 0 0 c2t7d3s6 The following is what the 'man i...

I was thinking about an interesting question regarding the Fibonacci series. Here it is. Assume that we draw the Fibonacci series of n as an inverted tree, where each node has its two additive terms as child nodes. For e.g. root node F(n) has F(n-1) and F(n-2) as children, and so on. Give an expression for the number of times node i occurs in the entire tree, where 1 Try to solve this problem. There is an interesting pattern to observe here.