Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Re: Puzzle

Reply
Thread Tools

Re: Puzzle

 
 
Kevin D. Quitt
Guest
Posts: n/a
 
      07-29-2003
Is it September already?


--
#include <standard.disclaimer>
_
Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up
Per the FCA, this address may not be added to any commercial mail list
 
Reply With Quote
 
 
 
 
Ramgopal
Guest
Posts: n/a
 
      07-30-2003
Jeez !!
Ppl take immediate offense to a puzzle ..
Some clarifications:
Its not part of my homework. I was just browsing through some
Microsoft interview Qs and got stumped over this one. Agreed I might
be low on the IQ front but just to prove my homework
I had figured out a soln already. But it was O(N^2).
Understanding the problem -
To figure out the sum of the elements of those ordered sub-sets of the
set {X1,..,Xn} such that:
for any sub-set {Xi,..,Xj}, (i < j) && ((j - i) = Cardinality of
{Xi,..,Xj}).
Soln to the problem -
This boils down to running two nested for loops as we do in case of
bubble sort.

But I am still looking for the O(N) algo.
~RG
ps -> Spare me for the mistakes in the formal notations. I am not good
at them.
 
Reply With Quote
 
 
 
 
Alf P. Steinbach
Guest
Posts: n/a
 
      07-30-2003
On 29 Jul 2003 21:32:37 -0700, http://www.velocityreviews.com/forums/(E-Mail Removed) (Ramgopal) wrote:

>Jeez !!
>Ppl take immediate offense to a puzzle ..


To a question for a solution to obvious homework.


>Some clarifications:
>Its not part of my homework. I was just browsing through some
>Microsoft interview Qs and got stumped over this one. Agreed I might
>be low on the IQ front but just to prove my homework
>I had figured out a soln already. But it was O(N^2).
>Understanding the problem -
>To figure out the sum of the elements of those ordered sub-sets of the
>set {X1,..,Xn} such that:
>for any sub-set {Xi,..,Xj}, (i < j) && ((j - i) = Cardinality of
>{Xi,..,Xj}).
>Soln to the problem -
>This boils down to running two nested for loops as we do in case of
>bubble sort.
>
>But I am still looking for the O(N) algo.


I already gave you a very strong hint.


 
Reply With Quote
 
MG
Guest
Posts: n/a
 
      07-30-2003

> To figure out the sum of the elements of those ordered sub-sets of the
> set {X1,..,Xn} such that:
> for any sub-set {Xi,..,Xj}, (i < j) && ((j - i) = Cardinality of
> {Xi,..,Xj}).


I assume the cardinality is known ( say m)

> Soln to the problem -
> This boils down to running two nested for loops as we do in case of
> bubble sort.


why do u need 2 loops??
u need to add the m number starting from index 0, and keep a track of the
sum and the index of the substring corresponding to that sum...
then use sliding window protocol...and at each step...compare the values of
the sum...and update the sum and the index pointer as required.....

by the end of the loop...u know the index of the sub aray which has the
maximum sum..

> But I am still looking for the O(N) algo.

this takes O(N)

HTH
manish


 
Reply With Quote
 
Default User
Guest
Posts: n/a
 
      07-30-2003


Ramgopal wrote:
>
> Jeez !!
> Ppl take immediate offense to a puzzle ..



Where did you get the idea that we are interested in random people
quizzing us? Most of us have plenty of real puzzles in our everyday work
to keep up occupied. If a problem interests you, work it out yourself
and post your solution. We'll be happy to comment on that.




Brian Rodenborn
 
Reply With Quote
 
Kevin Easton
Guest
Posts: n/a
 
      07-30-2003
Ramgopal <(E-Mail Removed)> wrote:
> Jeez !!
> Ppl take immediate offense to a puzzle ..
> Some clarifications:
> Its not part of my homework. I was just browsing through some
> Microsoft interview Qs and got stumped over this one. Agreed I might
> be low on the IQ front but just to prove my homework
> I had figured out a soln already. But it was O(N^2).
> Understanding the problem -
> To figure out the sum of the elements of those ordered sub-sets of the
> set {X1,..,Xn} such that:
> for any sub-set {Xi,..,Xj}, (i < j) && ((j - i) = Cardinality of
> {Xi,..,Xj}).
> Soln to the problem -
> This boils down to running two nested for loops as we do in case of
> bubble sort.
>
> But I am still looking for the O(N) algo.
> ~RG
> ps -> Spare me for the mistakes in the formal notations. I am not good
> at them.


The solution is something like this (this works, except for the edge-cases,
like an empty array or an array composed entirely of negative numbers -
you'll have to modify it a bit to get those right, but you get the
general idea):

struct subarray {
size_t left, right;
};

void maxsubarray(struct subarray *result, int array[], size_t arraylen)
{
size_t max_l, max_r;
size_t cur_l;
int maxsum = 0;
int cursum = 0;
size_t i;

for (max_l = 0, max_r = 0, cur_l = 0, i = 0; i < arraylen; i++) {
cursum += array[i];
if (cursum < 0) {
cursum = 0;
cur_l = i + 1;
} else if (cursum > maxsum) {
maxsum = cursum;
max_l = cur_l;
max_r = i;
}
}

result->left = max_l;
result->right = max_r;
}

- Kevin.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
What is the extra bar along top in v1.5 with puzzle image? Can we get rid of? S.Rodgers Firefox 9 12-14-2005 11:15 AM
Home networking puzzle?!? =?Utf-8?B?Qm9ya28=?= Wireless Networking 3 01-25-2005 06:49 AM
A NS puzzle:) Brad Snow Firefox 6 09-03-2004 04:54 AM
A puzzle to puzzle you sk A+ Certification 1 07-17-2004 05:19 PM
PUZZLE Getting DropDownList Index of Matching Value Earl Teigrob ASP .Net 3 08-06-2003 09:41 PM



Advertisments