some algorithmic puzzles, tutorials, interview questions... and stuff...

Saturday, October 03, 2009

How to find the longest continuous increasing sequence

How to find the longest continuous increasing sequence in a array of numbers is one of the questions I was asked in a interview at Microsoft, Copenhagen. The solution I provided then was not the best one, since I wasn't so well prepared (I gave a O(n*log2n) solution which is better than the basic O(n2) solution, but still not the optimum one). This can be done with O(n) time complexity. Hopefully writing these things here will help me in my future interviews.

The idea for the O(n) solution is to keep track of the start of the longest continuous increasing sequence and it's length. At each item, if it's bigger than the previous, then we have a sequence. If it's longer then the current maximum length, then we have a new longest increasing sequence, longer than the previous one.

The same principle can be applied to similar problem which I'll post later. Until then, here's the algorithm:

   1:  void longestContinuousIncrSeq(int* a, int size) {
   2:      int maxstart = 0;
   3:      int max = 1;
   4:      int start = 0;
   5:      for (int i = 1; i < size; i++) {
   6:          if (a[i] > a[i - 1]) {
   7:              if (i - start + 1 > max) {
   8:                  max = i - start + 1;
   9:                  maxstart = start;
  10:              }
  11:          } else {
  12:              start = i;
  13:          }
  14:      }
  15:      cout << "Longest sequence starts at " << maxstart << " and is " << max << " numbers long." << endl;
  16:      for (int i = 0; i < max; i++) {
  17:          cout << a[maxstart + i] << " ";
  18:      }
  19:      cout << endl;
  20:  }

36 comments:

  1. Just to let you know, this doesn't work because you are only checking for contiguous sequences.

    ReplyDelete
    Replies
    1. just to let you know, that is what they asked him to do in his microsoft interview :P

      Delete
  2. Presсhoοl online gamеѕ aгe Outstаnԁing waу to
    Fаcilitate κiԁѕ site incluԁing chіlԁren, teenagerѕ and bеsiԁes old mаssеѕ.



    Herе іs my website: game

    ReplyDelete
  3. Which can bе leѵeragеԁ to
    make punter thеsе onlіne gamеѕ аre without сost!


    My page earphoria.fm

    ReplyDelete
  4. Frіv 2 online website Оnline Gameѕ аre а Coгking way to Amend уour Μentаl power!
    Don't concern too a lot: you perpetually get a new bike, for Loose, of the characters bet on the advancement of the biz. So how is in the beginning, could make it harder to Make your phonograph record in the next. The increasing measure of Liberate online games, delivery fun and entertainment in dedicated residential district certain to Proceed you in laughs.

    Stop by my blog post ... game

    ReplyDelete
  5. Having read this I believed it was very enlightening.

    I appreciate you spending some time and effort to put this short article
    together. I once again find myself spending a lot of time
    both reading and leaving comments. But so what, it was still worth it!


    My homepage Gucci Borse

    ReplyDelete
  6. Hi there fantastic website! Does running a blog like this take a great deal of
    work? I've absolutely no knowledge of computer programming but I had been hoping to start my own blog soon. Anyways, should you have any ideas or techniques for new blog owners please share. I understand this is off topic but I just had to ask. Kudos!

    Visit my weblog: Evgeni Malkin Authentic Jersey

    ReplyDelete
  7. Hi, every time i used to check website posts here early in the dawn, for the reason that
    i love to learn more and more.

    Here is my page: Louis Vuitton Handbags

    ReplyDelete
  8. Hi, There's no doubt that your website might be having web browser compatibility problems. Whenever I look at your site in Safari, it looks fine however, if opening in IE, it has some overlapping issues. I merely wanted to give you a quick heads up! Other than that, fantastic website!

    Feel free to surf to my blog post ... Converse

    ReplyDelete
  9. Quality posts is the secret to be a focus for the visitors to visit
    the web page, that's what this web page is providing.

    Feel free to surf to my site ... Abercrombie & Fitch

    ReplyDelete
  10. I for all time emailed this web site post page to all my friends, because if like to read it then my contacts will too.


    Feel free to surf to my site ... http://www.23hq.com/nickel27virgo/story/10685333

    ReplyDelete
  11. Amazing things here. I'm very satisfied to peer your post. Thanks a lot and I am taking a look ahead to contact you. Will you please drop me a e-mail?

    Here is my web-site: Click Here

    ReplyDelete
  12. Hi there everyone, it's my first pay a visit at this site, and piece of writing is really fruitful in favor of me, keep up posting these articles or reviews.

    Stop by my blog post - more

    ReplyDelete
  13. Does your blog have a contact page? I'm having problems locating it but, I'd like to send
    you an e-mail. I've got some recommendations for your blog you might be interested in hearing. Either way, great website and I look forward to seeing it improve over time.

    Have a look at my page ... Solde Air Jordan

    ReplyDelete
  14. Have you ever thought about publishing an e-book or guest authoring on other sites?

    I have a blog based upon on the same information you discuss and would love to have you share some stories/information.
    I know my visitors would appreciate your work. If you're even remotely interested, feel free to shoot me an email.

    My web page; Louis Vuitton Bags

    ReplyDelete
  15. Hey there! I simply wish to offer you a huge thumbs
    up for the great info you've got right here on this post. I am coming back to your web site for more soon.

    Here is my website - pointe shoes information

    ReplyDelete
  16. Hello Dear, are you truly visiting this site daily, if so after that you will absolutely obtain nice experience.


    Also visit my webpage - Sac Louis Vuitton Pas Cher

    ReplyDelete
  17. When someone writes an piece of writing he/she retains the thought of a user in his/her
    brain that how a user can be aware of it.
    Thus that's why this paragraph is perfect. Thanks!

    Look at my webpage ... Abercrombie and Fitch

    ReplyDelete
  18. Liberation: There is no liberation without labor.
    , a pot and a lid - but this one is truly different.
    The pressure created inside is what allows water to rise at higher temperatures.


    my homepage - noi ap suat

    ReplyDelete
  19. Thankfulness to my father who informed me concerning this blog, this web
    site is genuinely amazing.

    my homepage; Louis Vuitton Purses

    ReplyDelete
  20. I love your blog.. very nice colors & theme.
    Did you create this website yourself or did you hire someone to
    do it for you? Plz respond as I'm looking to design my own blog and would like to know where u got this from. appreciate it

    Feel free to surf to my site :: Sac Guess Pas Cher

    ReplyDelete
  21. I do not even know how I ended up here, but I thought this post was great.
    I do not know who you are but definitely you are going to a famous blogger if you are not already ;) Cheers!


    My weblog: Cheap Jerseys

    ReplyDelete
  22. I love it when individuals come together and share views.

    Great website, keep it up!

    Also visit my webpage http://slc-Wireless.com/

    ReplyDelete
  23. Touche. Solid arguments. Keep up the amazing work.

    My web-site ... web site - mightytrinity.com -

    ReplyDelete
  24. This web site certainly has all of the information I wanted about this subject and didn't know who to ask.

    Visit my web site: Tory Burch Handbags

    ReplyDelete
  25. Nice response in return of this issue with real arguments and telling everything about that.


    Feel free to visit my weblog link (www.pdadmin-wiki.de)

    ReplyDelete
  26. Nice response in return of this issue with real arguments and telling everything about that.


    my web blog; link (www.pdadmin-wiki.de)

    ReplyDelete
  27. wonderful points altogether, you simply received a new reader.
    What could you recommend about your put up that you made a few days
    in the past? Any certain?

    Feel free to surf to my web blog ... Learn More

    ReplyDelete
  28. Fine way of describing, and fastidious article to obtain information concerning my presentation subject,
    which i am going to deliver in academy.

    Feel free to surf to my web blog: Oakley Frogskins

    ReplyDelete
  29. Yes! Finally something about mastiff.

    my web page; Abercrombie Et Fitch

    ReplyDelete
  30. of course like your web-site however you have to test the spelling on several of your
    posts. Several of them are rife with spelling problems and I to
    find it very troublesome to tell the truth on the other hand I
    will surely come back again.

    Here is my web blog: Borsa Gucci

    ReplyDelete
  31. Wow, that's what I was looking for, what a information! existing here at this webpage, thanks admin of this site.

    Feel free to visit my homepage :: Nike Air Max (http://smu-fr.org)

    ReplyDelete
  32. I am sure this post has touched all the internet viewers,
    its really really good post on building up new web site.



    my blog Sac A Main Louis Vuitton

    ReplyDelete
  33. Unquestionably believe that that you said. Your favorite
    justification appeared to be at the internet the simplest factor to remember of.

    I say to you, I certainly get irked whilst other people think about concerns that they just do not realize about.
    You controlled to hit the nail upon the top and outlined out the whole thing without having side effect ,
    other people could take a signal. Will likely be back to get more.
    Thanks

    Also visit my web site ... Going Here ()

    ReplyDelete
  34. Why haven't you removed all these spam "comments"?

    ReplyDelete