O(N) if everybody knows everybody.
O(N^2) if there is no such condition. (i.e. Ask for each person to
everybody.)
On Mon, Dec 20, 2010 at 9:43 PM, Bhavesh Chauhan chauhan.bhave...@gmail.com
wrote:
Every question can eliminate 1 person so you can identify the spy in N-1
questions.
Bhavesh
http://en.wikipedia.org/wiki/Run-length_encoding
On Wed, Sep 15, 2010 at 5:51 PM, bittu shashank7andr...@gmail.com wrote:
A file is given with many 0s stored in continuous way , store it in
another file such that when you store try saving the space by using
minimum amount of space. When you
How about keeping heap?
Have two heaps 1. max heap and 2. min heap
keep them equal size all the time and shift top element from one to
other when required...
On Wed, Jul 28, 2010 at 7:46 AM, Gene gene.ress...@gmail.com wrote:
I think you have confused the statement of this problem. The (in
Suffix tree is obviously there but
1. It requires more lots of space. Just draw a suffix tree and you will know.
2. Pre-processing takes time. We cant ignore this time because its
proportional to N.
There is one linear solution described here:
Use hash table with customer ID as key.
There can be three components in value: 1. num_days 2. pages 3. flag
For each line, calculate hash, find value for given key.
Increment appropriate values (i.e. pages or num_days).
If num_days 1 pages 1, add this customer to result array, mark
this
1. have an array of N years. starting with first year and ending at last year.
O(N) space here. initialise all elements to zero.
2. Take array of E and birthyear first. Whenever you encounter new
birthyear, do array[year]++.
3. Take array of E and deathyear now. Whenever you encounter new
On Mon, May 31, 2010 at 10:01 PM, souravsain souravs...@gmail.com wrote:
Hi All
This is my first post to this community and so am exited. The problem
is to find the no. that has maximum frequency in an array (size n) of
integers.
The approach to use a hash table, itereate through array
step 1: Sort array in place. Lets call it A. (N log N)
step 2: Create two additional copies of array, lets call them B and C. (this
is just for explanation, we can operate on same array A).
step 3: Take first element from array A. lets say its value is X. Find pair
from B and C whose sum is
