optimal soln

This is a discussion on optimal soln within the C Programming forums, part of the General Programming Boards category; You are given an int array and a integer n.you have to display all the index pairs in array whc ...

  1. #1
    Registered User cbastard's Avatar
    Join Date
    Jul 2005
    Location
    India
    Posts
    167

    optimal soln

    You are given an int array and a integer n.you have to display all the index pairs in array whc will have a sum of n. write a code for that??
    this question was asked in 2nd round of microsoft interview in our campus today.i wrote a code with O(n square) complexity.but they expected O(n).wat will be the algo for O(n)???? i just need to know about the soln they hv kicked me out in this question

  2. #2
    Registered User white's Avatar
    Join Date
    Nov 2004
    Posts
    39
    well I can think of several solutions far better than O(n^2) but not O(n) ...I would be very interested in seeing an O(n) solution.

  3. #3
    Registered User cbastard's Avatar
    Join Date
    Jul 2005
    Location
    India
    Posts
    167
    post your soln watever u hv in mind or ur approach.just the algo

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Do your own homework.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    cwr
    cwr is offline
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    869
    I can think of an O(n) solution provided you have a huge amount of memory, but see quzah's reply.

  6. #6
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Closed due to lack of attempt on OP's part

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dynammic programming - optimal Routes Listing
    By Sober in forum C++ Programming
    Replies: 10
    Last Post: 08-26-2008, 02:37 PM
  2. Guidelines for writing optimal C program
    By Moony in forum C Programming
    Replies: 7
    Last Post: 06-30-2006, 09:08 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21