Re: Puzzle

Discussion in 'C Programming' started by Kevin D. Quitt, Jul 29, 2003.

  1. 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
     
    Kevin D. Quitt, Jul 29, 2003
    #1
    1. Advertising

  2. Kevin D. Quitt

    Ramgopal Guest

    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.
     
    Ramgopal, Jul 30, 2003
    #2
    1. Advertising

  3. On 29 Jul 2003 21:32:37 -0700, (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.
     
    Alf P. Steinbach, Jul 30, 2003
    #3
  4. Kevin D. Quitt

    MG Guest


    > 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
     
    MG, Jul 30, 2003
    #4
  5. Kevin D. Quitt

    Default User Guest

    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
     
    Default User, Jul 30, 2003
    #5
  6. Kevin D. Quitt

    Kevin Easton Guest

    Ramgopal <> 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;
    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.
     
    Kevin Easton, Jul 30, 2003
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Earl Teigrob
    Replies:
    3
    Views:
    6,662
    Nedu N
    Aug 6, 2003
  2. dwa

    Design Puzzle!

    dwa, Jun 10, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    373
    Cowboy \(Gregory A. Beamer\) [MVP]
    Jun 10, 2004
  3. Shankara Narayanan

    Booking puzzle....

    Shankara Narayanan, Jun 17, 2004, in forum: ASP .Net
    Replies:
    20
    Views:
    938
    bredal Jensen
    Jun 30, 2004
  4. VB Programmer
    Replies:
    2
    Views:
    432
    Alan Lambert
    Nov 4, 2004
  5. G. Stewart

    regex puzzle!

    G. Stewart, Nov 23, 2004, in forum: ASP .Net
    Replies:
    8
    Views:
    524
    G. Stewart
    Nov 25, 2004
Loading...

Share This Page