Wondering if there is a lower O(n) I can go to..

Question

Stupid question: The below is O(n^3). I'm sure there is a way to improve this, so any help is appreciated.

//vector<string> flight_path; given as parameter
//vector<int> flight_number; need to fill
//vector<segment> flight_segments; known, contains segments (dep, arr, flightnum)

//Purpose of the function is to take in a flight_path and give back a list of
// flight numbers for each segment
//
// Input: New York, London, Kolkata
// Output: 101 201 301, 102 939

vector<string> get_flight_numbers (vector<string> flight_path) {

    vector<int> flight_number;

    for (int i = 0; i < flight_path.size() - 1; i++) {

        string dep = flight_path.at(i);
        string arr = flight_path.at(i+1);

        for (int j = 0; j < flight_segments.size(); j ++) {
            if (flight_segments.at(j).departure == dep && flight_segments.at(j).arrival == arr) {
                for (int k = 0; k < flight_segments.at(j).segment_numbers.size(); k++) {
                    flight_numbers.push_back(atoi(flight_segments.at(j).segment_numbers.at(k).c_str()));
                }
            }
        }

    }
}

Answer 1

If I understand this, you have a directed graph that consists of a series of flight segments. You are given a series of flight segments, say, A -> B -> C, that makes up a flight path.

In addition, you have a group of flight numbers. The flight numbers correspond to paths. Flight number 1 will be tagged as [A,B,1], for example. Time is not an issue, all flights are assumed to be available at all times.

Can you, in less than n^3 time, figure out what flight numbers can take you from one segment to the next?

Well, on approach might be to go through the array exactly once in order to separate out all the flights that depart from your first departure gate, your second departure gate, and so forth. That's order n.

Then go through each of those lists (once) and remove all the flights that don't have the right destination gate. That's order n again.

At that point, you're pretty much done.

So think your big mistake here is going through your big loop (the flights) INSIDE your little loop (your flight path). You'd be much better off going through the small loop inside the big loop and breaking if you find a match. This loop only nests once, also, instead of twice. If you really really wanted to, you could check each departure as you find it to see if it matches an arrival. In psuedo-code

for (i in each flight) do
    for (j in each pathpoint except the last one) do
        if flight[i][departure][i] == pathpoint[j] then
            if flight[j][arrival] == pathpoint[j+1]
                put flight in the good flights vector
            end if
        end if
    end for
end for

That's O(n*m) where m is the length of the path and n is the number of flights. This should be, in any reasonable world, O(n).

Answer 2

c++ solution: i wrote result in common list, but you can make vector < vector< string > >.

#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <iostream>

class Segment
{
public:
    Segment(std::string const& departure, std::string const& arrival, int flighNum)
    :m_departure(departure)
    ,m_arrival(arrival)
    ,m_flightNumber(flighNum)
    {
    }
    std::string Departure() const { return m_departure; }
    std::string Arrival() const { return m_arrival; }
    int FlightNumber() const { return m_flightNumber; }
private:
    std::string m_departure;
    std::string m_arrival;
    int         m_flightNumber;
};

class FillFlightNumbers
{
public:
    FillFlightNumbers(std::vector<std::string> &flights, std::string const& departure, std::string const& arrival)
    :m_flights(flights)
    ,m_departure(departure)
    ,m_arrival(arrival)
    {
    }
    void operator()(Segment const& item) const
    {
        if (m_departure == item.Departure() && m_arrival == item.Arrival())
        {
            std::ostringstream oss;
            oss << item.FlightNumber();
            m_flights.push_back(oss.str());
        }
    }
private:
    std::vector<std::string>    &m_flights;
    std::string                 m_departure;
    std::string                 m_arrival;
};

void GetFlightNumbers(std::vector<Segment> const& segmentList, std::vector<std::string> const& roadList, std::vector<std::string> &result)
{
    std::vector<std::string>::const_iterator iteratorPath = roadList.begin(), endPath = roadList.end();
    for ( ; iteratorPath != endPath; ++iteratorPath)
    {
        std::vector<std::string>::const_iterator nextIt = iteratorPath + 1;
        if (endPath == nextIt)
        {
            return;
        }
        std::for_each(segmentList.begin(), segmentList.end(), FillFlightNumbers(result, (*iteratorPath), (*nextIt)));
    }
}

// test solution
void main()
{
    std::vector<std::string> result;
    std::vector<Segment> segmentList;
    segmentList.push_back(Segment("New York", "London", 101));
    segmentList.push_back(Segment("New York", "London", 202));
    segmentList.push_back(Segment("New York", "London", 909));
    segmentList.push_back(Segment("London", "Kolkata", 2222));
    segmentList.push_back(Segment("London", "Kolkata", 3333));
    segmentList.push_back(Segment("London", "Kolkata1", 3344));
    std::vector<std::string> roadList;
    roadList.push_back(std::string("New York"));
    roadList.push_back(std::string("London"));
    roadList.push_back(std::string("Kolkata"));
    GetFlightNumbers(segmentList, roadList, result);
}