Re: [algogeeks] Puzzle
19-(9/1). -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: do this: two numbers with min diff
step1construct heap using siftdown. // time complexity wil be O(n) and
space complexity O(1).
step2take mindifference=a[1].
step3for i=1 ,i=n/2 do
{ find the difference of (root,root-left),(root,root-right)and
(root-left,root-right).and maintain mindifference is the smallest
difference of among
three differences.
}
step4return mindifference.
plz correct me if im wrong
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Subsequence
@Rahul
#includestdio.h
#includestdlib.h
int nondecresing_maxsum(int *a,int n,int k)
{ int sum=0,i,count=k+1,prev_num=a[0],*dp,count1=0;;
dp=(int *)malloc(sizeof(int)*(k+1));
for(i=0;in;++i)
if(prev_num=a[i])
{ sum+=a[i];
prev_num=a[i];
dp[count1%(k+1)]=a[i];
count1++;
count--;
if(!count)
{ sum-=dp[(count1)%(k+1)];
count++;
}
}
return sum;
}
int main()
{ int *arr,arr_size,i,k;
printf(give array size and k);
scanf(%d%d,arr_size,k);
arr=(int *)malloc(sizeof(int)*(arr_size+1));
printf(give elements);
for(i=0;iarr_size;++i)
scanf(%d,arr[i]);
printf( %d,nondecresing_maxsum(arr,arr_size,k));
}
this is my first post
plz correct me if im wrong
but this wil not work if all array numbers r negetive...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Subsequence
@Adam
i ran the program with n=4 and k=2 and sequence as 2,3,999,
i got 10998(i.e999+).
plz check it
On Sat, Aug 28, 2010 at 10:25 AM, Adam wangyanadam1...@gmail.com wrote:
Actually, your code just considers the only non-decreasing subsequence
which starts from a[0] and is the most 'LEFT' one in this situation
rather than all the possible subsequences.
For example, we have such sequence as 2,3,999,, and k = 2.
In this situation, your code will give the subsequence {2,3} as the
result rather than the true one {999,}.
On Aug 28, 3:36 am, satish satish satish@gmail.com wrote:
@Rahul
#includestdio.h
#includestdlib.h
int nondecresing_maxsum(int *a,int n,int k)
{ int sum=0,i,count=k+1,prev_num=a[0],*dp,count1=0;;
dp=(int *)malloc(sizeof(int)*(k+1));
for(i=0;in;++i)
if(prev_num=a[i])
{ sum+=a[i];
prev_num=a[i];
dp[count1%(k+1)]=a[i];
count1++;
count--;
if(!count)
{ sum-=dp[(count1)%(k+1)];
count++;
}
}
return sum;}
int main()
{ int *arr,arr_size,i,k;
printf(give array size and k);
scanf(%d%d,arr_size,k);
arr=(int *)malloc(sizeof(int)*(arr_size+1));
printf(give elements);
for(i=0;iarr_size;++i)
scanf(%d,arr[i]);
printf( %d,nondecresing_maxsum(arr,arr_size,k));
}
this is my first post
plz correct me if im wrong
but this wil not work if all array numbers r negetive...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: a google question
This problem can be simplified to a variation of merge part of merge
sort algorithm.
- Break the set S having n^2 values into n individual arrays of length
n, say S1, S2,..Sn, where S1 = [a1+b1, a1+b2,...a1+bn].
- One can observe that each Si has entries which are themselves sorted
within Si.
- Perform merge of S1, S2,..Sn where take the largest values of each
Si, and create a heap of these individual max values.
- In each step, return the max value from heap and then add the next
max value from the Si that had the current max value and add it in the
max-heap.
- Repeat this step n times and then exit.
Time: O(n).
Satish
On May 2, 5:41 pm, Algoose Chase harishp...@gmail.com wrote:
Hi
will this work ?
since we need Set S with n pairs of largest values , any such pair within
the set would (always) contain A[0] or B[0] because they maximize the value
of the pair.
so
// code snippet
typedef std::vectorint,int Pairs;
Pairs.push(A[0],B[0])
int i = 1; // index for ListA
int j = 1; // index for list B
count = 1;
while( count = n)
{
if( A[0] + B[j] B[0] + A[i] )
{
Pairs.push(A[0],B[j])
j++;
}
else
{
Pairs.Add(A[i],B[0])
i++;
}
count++;
}
since there are n items in both the lists, j and i wont go beyond n in the
while loop
On Sun, May 2, 2010 at 3:44 PM, Shishir Mittal 1987.shis...@gmail.comwrote:
This problem has been discussed before @
http://groups.google.co.in/group/algogeeks/browse_thread/thread/9c1e1...
I believe, the problem can't be solved in O(n) but only in O(nlog n).
@Divya: Are you sure the interviewer explicitly asked for an O(n) time
algorithm?
On Sun, May 2, 2010 at 1:48 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:
@divya You're rite. Post a solution if you have one.
--
Regards,
Vignesh
On 2 May 2010 13:14, divya jain sweetdivya@gmail.com wrote:
@Mohit
according to ur algo if a[1], b[0] has sum greater than a[0],b[1]
then i is incremented i is now 2 so for next iteration u ll compare
a[2] b[0] and a[1] b1]. but what about a[0] b[1] this pair s lost forever.
think for ths case also.
On 2 May 2010 11:22, mohit ranjan shoonya.mo...@gmail.com wrote:
@Algoose Chase
point taken
Thanks
Mohit Ranjan
Samsung India Software Operations.
On Sat, May 1, 2010 at 8:43 PM, Algoose Chase
harishp...@gmail.comwrote:
@mohit
The idea of DP is fine.
When you find the Max i dont think you need to include A[i+1]+B[j+1]
because it can never be greater than both A[i+1]+B[j] and A[i]+B[j+1]
since
both the lists are sorted in decreasing order.
On Fri, Apr 30, 2010 at 8:47 PM, mohit ranjan shoonya.mo...@gmail.com
wrote:
oops
Sorry didn't read properly
last algo was for array sorted in ascending order
for this case, just reverse the process
A[n] and B[n] are two array
loop=n, i=0, j=0;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of first index from both array will
be max
foo = MAX ( A[i+1]+B[j], A[i+1]+B[j+1], A[i]+B[j+1] ) // using
DP, moving forward
if foo==A[i+1]+B[j]; i++ // only increment A
if foo==A[i+1]+B[j+1]; i++; j++ // increment both A and B
if foo==A[i]+B[j+1]; j++ // increment only B
}
Mohit Ranjan
Samsung India Software Operations.
On Fri, Apr 30, 2010 at 8:40 PM, mohit ranjan
shoonya.mo...@gmail.com wrote:
Hi Divya,
A[n] and B[n] are two array
loop=n, i=n-1, j=n-1;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of last index from both array will
be max
foo = MAX ( A[i-1]+B[j], A[i-1]+B[j-1], A[i]+B[j-1] ) // using
DP moving backward
if foo=A[i-1]+B[j]; i-- // only reduce A
if foo=A[i-1]+B[j-1]; i--; j-- // reduce both A and B
if foo=A[i]+B[j-1]; j-- // reduce only B
}
Time: O(n)
Mohit Ranjan
On Fri, Apr 30, 2010 at 5:35 PM, divya
sweetdivya@gmail.comwrote:
Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G,
let's
say they are decreasingly sorted), we define a set S = {(a,b) | a
\in
A
and b \in B}. Obviously there are n^2 elements in S. The value of
such
a pair is defined as Val(a,b) = a + b. Now we want to get the n
pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email
[algogeeks] Re: An interesting graph problem
Suppose the graph has n colors. Think of all vertices with same color
as lying in a same cluster. Hence all we need is the shortest path
that goes through some vertex in each of the n clusters.
After the ith step suppose we have all the shortest paths, starting
from each vertex in the ith cluster, that goes through all the
remaining clusters. In the (i+1)th step, we add a new cluster. Try to
find out the shortest path that starts from each vertex Vj lying in
this new cluster such that:
Shortest path starting from Vj = min{ dist(Vj, Vi) + Shortest path
starting from Vi}; where Vi is any vertex belonging to the ith
cluster.
At the end of nth step, take the minimum of all shortest paths
starting from the nth cluster.
Regards,
Satish
On Feb 25, 6:47 pm, Ridvan [EMAIL PROTECTED] wrote:
Maybe this will work:
Starting from each vertex using BFS calculate the shortest path which
passes through vertexes from all the colors.
Best,
Ridvan
On Feb 24, 2:00 pm, Ajinkya Kale [EMAIL PROTECTED] wrote:
On 2/24/08, Sticker [EMAIL PROTECTED] wrote:
I have a graph problem, which is different from the standard salesman
problem. I say it is more difficult.
In a graph, I have many vertexes with different colors. It is more
easier to think of each vertex as a shop selling only one goods and
vertexes with the same color selling the same goods. There are edges
between any two vertexes, with different distances.
You start at a specific position (different from any vertex), and have
a list of goods you need to buy. Figure out an optimal path with
shortest distance so you can get all the goods from the shops on the
path. You are not required to start and end at the same position and
edges and vertexes can be visited more than once if you want.
If there is no color on vertex, or in other words, each vertex sells a
distinct goods, then the above problem is identical to salesman
problem.
I dont think that makes is identical to TSP. Cause in TSP you have to visit
every node.
But in this case you are given a list of goods and each vetex sells unique
good.
Also in TSP we have to return to the start point , but this is not the case
here !
But now we have colors on vertexes and once a vertex with a
color is visited, you don't want to visit vertex with the same color
(which will only increase the total distance).
Since this problem is an extension of the standard salesman problem,
the practical solution is probably heuristic. The key is, what
heuristic strategy are you going to use.
I think the problem a bit and come up with a very naive solution:
For each vertex, calculate its distances to the closest vertexes with
other colors. For vertexes with the same color, choose the one with
the minimum total/average such distances. Then, only one vertex with a
color is remained in the graph. Then use heuristic strategy for
salesman problem.
any other idea?
--
Ciao,
Ajinkya- Hide quoted text -
- Show quoted text -
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Dynamic Programming Algorithm for swim relay team
We can use dynamic programming here to find out the team configuration
with minimum time.
Define a function f(P1,P2, P3,...Pn) that returns the players sequence
(given n players for n rounds, which swimmer swims at which position)
that would return the total minimum time.
Then f() can be defined recursively as f(P1, P2, P3,... Pn) = min {T11
+ f(P2, P3,...Pn); T21 + f(P1, P3,...Pn); T31 + f(P1,
P2,...Pn); ..}
where Tij is the time taken by the ith player in the jth round.
The above recursion can be solved in an iterative manner using
dynammic programming.
HTH,
Satish
On Jan 4, 1:45 am, hc busy [EMAIL PROTECTED] wrote:
At risk of stating the incredibly obvious, or giving away answer to a
fun interview question.
The naive but correct algorithm that gives the solution will have
tried every combination M of K swimmers in M events. which will give
you K!/(K-M)! arrangements, and the algorithm would then compare the
timing and chose the best arrangement.
Anything better than that?
Does allowing any swimmer to swim up to M events at same performance
level make this problem harder?
What about fractional event? (allow relay so that more than one
swimmer can swim in one event)?
On Jan 1, 1:19 am, Arikan [EMAIL PROTECTED] wrote:
Hi, i hope you can help me with this problem?
A coach is putting a relay team together for a 400-meter relay.
Each swimmer must swim 100 meters of breaststroke, backstroke,
butterfly, or freestyle.
!There are at least four swimmers
Is there a algorithm to find the optimum solution to minimize the
team's time?
(similar to dynamic programming solution for knapsack problem!)
for example(5 swimmers):
1 2 3 4
1 30 34 26 29
2 31 37 31 36
3 32 29 41 40
4 29 40 37 31
5 33 32 35 24
first i thought i can solve this problem with the hungarian algorithm,
but that's out of the question..- Hide quoted text -
- Show quoted text -
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: min height rootless tree
If the 'root' node has to be such that the height of the resultant tree should be minimum, then this root node must lie in the middle of the largest possible path between any 2 points in this graph. Given above, start doing a DFS from any arbitrary node. This is doable in O(n). It will return return the heights of all its sub-trees. Pick up the top 2 heights (say a, b where a b). The longest path now in this graph is of length a + b. The root should lie at a+b/2 from either ends, which is at distance a-(a+b/2) from the current node. Thanks, Satish On Oct 29, 6:22 pm, Yingjie Xu [EMAIL PROTECTED] wrote: Calculate center of a tree, can be solved in O(n). On 10/25/07, dkrai [EMAIL PROTECTED] wrote: Another approach can be to eliminate leaf nodes iteratively from tree. At last only root node or nodes on same level will be left. Adjency list representation of graph will make it easier to imlplement. Run time cost will be O(n*n) On Oct 24, 12:37 pm, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Two methods: 1. try BFS on each vertex, calculate the longest shortest path to each other vertex, compare them It is easy to implement, but gives O(n*n) running time 2. divide and conquer randomly divide the tree into two parts, calculate the height of the two subtrees then merge them. This is not so easy to implement, but really gives a good running time which is O(nlogn) On Oct 21, 9:21 am, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Q) You are given a root-less tree (which can also be thought of as an undirected acyclic connected graph). The problem is to choose one of the nodes from the tree as root such that the height of the resultant tree is minimum. Device an appropriate data-structure and write a program for the same. mum height possible is 2. So for this example the code should return the node '3'. Note: All nodes are numbered from 1 to n, where 'n' is the number of nodes. Incase there are more than one roots possible, then your program can return any one of them.- Hide quoted text - - Show quoted text - --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: whats the fastest way to find the odd man out?
Got it.. basically i thought that 1. XOR at bit level is OK.. but for any number a, i was wondering what would ~a be.. (0?). But actually a XOR b would be nothing but their corresponding bitwise XORs. 2. Also, a XOR b = a. ~b + ~a.b. Thus if we expand the expression [a XOR b XOR c n numbers] it would give many terms, each having multiplications of n numbers, i.e. O(n) multiplication, which I thought is expensive. But then that would be a wrong way to evaluate the expression; we can easily iteratively find the XOR as mentioned above! --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: whats the fastest way to find the odd man out?
Hangjin Zhang wrote: Do an XOR on all numbers. The resulte is the number which occurs only once HZ On 12/30/06, Abhishek [EMAIL PROTECTED] wrote: Hi, Suppose I have a sequence of numbers in which every number occurs twice in the sequence except one. Whats the fastest way of finding that number which occurs only once? With Regards, Abhishek S I am not sure how XOR will be defined on numbers. Also, calculating XOR for any sequence of N numbers where N is not known a priori is computationally very expensive. A simple way could be to keep additional large bit vector memory. where we have 2 bits per number. For each number visited in sequence, mark the corresponding bit b1 as visited once. On revisiting, mark another corresponding bit b2. At the end, just look for the number that has only b1 set and b2 unset. SKM --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem
The minimum case would be if you can place all these 4 input rectangles in the vertical plane of the resultant recatangle, and along its diagonal. So suppose dimensions of 4 rectangles are (x1,y1),(x2,y2),(x3,y3),(x4,y4) and of the resultant rectangle is (x,y). Then solution is all (x,y) that satisfy the condition min(x1,y1,x2,y2,x3,y3,x4,y4) = (x,y)^(1/2). Thanks, Satish --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
