There is a set of 9 students and 3 schools Every school can be alloted
atmax 3 students .Every school and student has its coordinates .Now we have
to allot student in such a way that the sum of distance from all the
student to the school should be minimum.
We have to solve this in less than O(n^3)
seems like Hungarian algorithm will work .
On Wed, Aug 1, 2012 at 12:18 PM, vikas rai vikasloves...@gmail.com wrote:
There is a set of 9 students and 3 schools Every school can be alloted
atmax 3 students .Every school and student has its coordinates .Now we have
to allot student in such a
the DP is not clear, can you give example on how this DP would work for n
invoices and k bills?
Why is F(0,k) = 1?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Mar 26, 2012 at 2:16 PM, atul anand atul.87fri...@gmail.com wrote:
it is
There are 210 Invoices and 1700 bills – these bills add up to these invoices
The association between bills and invoices is lost . The only way to
match them is by adding them up to correct amounts that are equal to
the invoices.
For Example : there were 2 invoices for 80, 210 and you have
it is similar to sum-subset problem following recurrance will solve this
problem , you need to run algo for each invoice to find all combination
F(n,k) = F(n,k-1) or F(n - a[k], k-1)
base case :F(0,k)=1 for k=0
F(n,0)= 0 for n0.
On Mon, Mar 26, 2012 at 1:34 PM, Ankush
Ok now you have combination of each invoice . What is the approach to
take mutual exclusive combinations for so that sum of all bills equals
sum of all invoices
On Mon, Mar 26, 2012 at 2:16 PM, atul anand atul.87fri...@gmail.com wrote:
it is similar to sum-subset problem following recurrance
one way to do it , is say first combination for invoice 80= 50 + 30
now remove 80 and 30 from the input bills while finding combination from
210 , check if it is possible
if yes , we got one solution
not select another invoice combination 80= 50 + 10 + 20
now dont consider these values while find
Well, they have specified in the question that you are dealing with
big-data sets. So, recursion won't be a good option I guess.
Can we solve it with dynamic programming technique?
On Mon, Mar 26, 2012 at 2:24 PM, atul anand atul.87fri...@gmail.com wrote:
one way to do it , is say first
@umer : dp approach is given in above post.
On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq the.um...@gmail.com wrote:
Well, they have specified in the question that you are dealing with
big-data sets. So, recursion won't be a good option I guess.
Can we solve it with dynamic programming
@googlegroups.com
Subject: Re: [algogeeks] Google Question Invoice -bills
@umer : dp approach is given in above post.
On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq the.um...@gmail.com wrote:
Well, they have specified in the question that you are dealing with
big-data sets. So, recursion won't
*To: *algogeeks@googlegroups.com
*ReplyTo: * algogeeks@googlegroups.com
*Subject: *Re: [algogeeks] Google Question Invoice -bills
@umer : dp approach is given in above post.
On Mon, Mar 26, 2012 at 4:11 PM, Umer Farooq the.um...@gmail.com wrote:
Well, they have specified in the question that you
|_|
|_| |_|
|_| |_| |_|
|_| |_| |_| |_|
|_| |_| |_| |_| |_|
Each cup has capacity C and once a cup gets full, it drops half extra
amount to left child and half extra amount to right child
for Eg : let' first cups get 2C amount of liquid then extra amount C(2C-C)
will be divided equally to left
i guess this would work...
n=number of nodes
h=height;
pour=quantity poured;
capacity = capacity of each cup
n=pow(2,h+1) -1;
call(capacity,pour,0,n)
node* fillCup(float capacity,float pour,int left,int right)
{
node *root;
int mid;
if(left right)
return NULL;
root=(node
You have an array with *n* elements. The elements are either 0 or 1. You
want to *split the array into kcontiguous subarrays*. The size of each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that
k n. After you split the array into k subarrays. One element of each
subarray
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com wrote:
You have an array with *n* elements. The elements are either 0 or 1. You
Given a string of lowercase characters, reorder them such that the same
characters are at least distance d from each other.
Input: { a, b, b }, distance = 2
Output: { b, a, b }
How to approach this question ?
--
You received this message because you are subscribed to the Google Groups
Start with counting sort of the input.
Use shuffling algorithm on it.
Store index as cumulative sums of counts.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
How to find the number users connected to the web??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
google this question!!
On Fri, Jul 8, 2011 at 11:47 AM, priyanshu priyanshuro...@gmail.com wrote:
How to find the number users connected to the web??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
may be by checking the server logs !!
On Fri, Jul 8, 2011 at 11:48 AM, Vishal Thanki vishaltha...@gmail.comwrote:
google this question!!
On Fri, Jul 8, 2011 at 11:47 AM, priyanshu priyanshuro...@gmail.com
wrote:
How to find the number users connected to the web??
--
You received
if no of waiting process is required, it can be obtained by length of
listen queue on server.
if no of running process is required , it can be done by getting process
id's currently running,
if no of hits in a time range is required, it can be done by server log
as well.
--
Best Wishes
What is the most efficient way, memory-wise, to store 1 million phone
numbers?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
go through the archives you will definitely find the answer :)
On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR monsieur@gmail.com wrote:
What is the most efficient way, memory-wise, to store 1 million phone
numbers?
--
You received this message because you are subscribed to the Google Groups
USE TRIE
On Wed, Jun 29, 2011 at 6:10 PM, shady sinv...@gmail.com wrote:
go through the archives you will definitely find the answer :)
On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR monsieur@gmail.com wrote:
What is the most efficient way, memory-wise, to store 1 million phone
numbers?
How we will get phone number of a particular person?
Thanks Regards,
Anantha Krishnan
On Wed, Jun 29, 2011 at 6:22 PM, sudheer kumar
chigullapallysudh...@gmail.com wrote:
USE TRIE
On Wed, Jun 29, 2011 at 6:10 PM, shady sinv...@gmail.com wrote:
go through the archives you will definitely
@MONSIEUR Use Binary Search Tree as the data Structure to store the values
for the Phone numbers because insertion and deletion is easy plus you will
get the additional advantage of sorted list of phone numbers . So Binary
search tree is better than using hash data structure .
Regards
Rajeev N B
Hey guys, phone usually has comparatively very less memory. So, we
can't afford to have pointers for each phone no. So, the idea of
having a tree is rooted out. The best way can be to use a fixed array
with circular indexing which is sorted by name, because the most
frequent query is to search a
Given an array of size n wherein elements keep on increasing
monotonically upto a certain location after which they keep on
decreasing monotonically, then again keep on increasing, then
decreasing again and so on. Sort the array in O(n) and O(1).
I didn't understand the question, any array of n
This question has been discussed over here once...It was concluded
that this can be solved in O(n) if we know there is a fixed range up
to which the elements keep on increasing and decreasing..for example
in an array of 12 elements, we know 3 elements keep on increasing
monotonically, then 3
How will you design a site similar to tinyurl.com?
Simple hashing may require a lot of space, and collisions is another
issue. Any other approch other than just hashing?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
Why to do hashing?? rather generate a unique id everytime...
On Fri, Jun 3, 2011 at 9:50 PM, Nate nate.archibal...@gmail.com wrote:
How will you design a site similar to tinyurl.com?
Simple hashing may require a lot of space, and collisions is another
issue. Any other approch other than just
hashing for lookup. where key will be the tinyurl generated and value will
be the actual url. We need to lookup the actual url everytime a client
queries with a tinyurl. The question is how will you make this search
faster.
On Fri, Jun 3, 2011 at 10:17 PM, vaibhav agrawal
1. You are given the ‘downloads’ folder on a computer which may
contain a number of files that are duplicates of each other. (these
files are the same byte-wise but may have diff names) describe a
method which identifies all duplicates in the least amount of time.
2. Now there are k
regarding doenloads folder..tiger tree hash(TTH) as we use it in
file sharing (DC++) might help
look this - http://www.dslreports.com/faq/9677
Once DC++ hashes all of your share (yes, this *will* take a while), it will
only hash new files. The hashing thread in DC++ is set to low
No special approach is needed. In O(log n), you can find the minimum element
of the array which makes your circular array - normal array.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Assume you are writing number in ascending order to an array of constant
size.once you reach the end of the array,you start writing from the
beginning, thus writing over the oldest entries.Write an algorithm for
finding a specific number in this array.
--
You received this message because you
It will be like a circularly sorted array.There exists a binary search type
divide and conquer mechanism to find a specific number in such type of
arrays.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
Given
1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
If you can only press the keyboard for N times (with the above four
keys), please write a program to produce maximum numbers of A. If
possible, please also print out the sequence of keys.
So the input parameter is N (No. of keys that you can press), the
You have a stream of infinite queries (ie: real time Google search
queries that people are entering). Describe how you would go about
finding a good estimate of 1000 samples from this never ending set of
data and then write code for it.
Thanks Regards
Shashank
--
You received this message
you are given 2 arrays sorted in decreasing order of size m and n
respectively.
Input: a number k = m*n and = 1
Output: the kth largest sum(a+b) possible. where
a (any element from array 1)
b (any element from array 2)
The Brute force approach will take O(n*n). can anyone find a better
logic.
You are given a function shortest_path(node *n1,node *n2,setEdge edges)
which finds the second shortest path. We need to find a second shortest path
in constant time.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
Let S(k) indicate the kth largest sum as per the question. We can also say
that every S corresponds to a pair, (u,v) such that S=a[u]+b[v].
Now the idea is to keep track of two previous S's (in turn two pairs) such
that one pair has the greatest 'u' of all so-far pairs. That is, this pair
has
Correction:
On Thu, Oct 7, 2010 at 11:12 AM, sumant hegde sumant@gmail.com wrote:
If S(h)= a[p]+b[q] and S(i)= a[r]+b[s], then obviously p = r and q= s,
.. then p = r and q = s..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
43 matches
Mail list logo