ultras
BAN USER
Employee at None
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
I would say the following is the most optimal.
typedef ::std::pair<int, int> IntPair;
typedef ::std::vector<IntPair> IntPairVector;
typedef ::std::list<int> IntList;
void pairs(IntList list, IntPairVector & result)
{
result.clear();
// make number map, O(N)
::std::vector<bool> map(100, false);
for (auto iter : list)
{
map[iter] = true;
}
// all numbers from [1, 99], O(1)
for (int i = 1; i <= 99; ++i)
{
const int j = 100 - i;
if (map[i] && map[j]) // do we have this number?
{
result.push_back(IntPair(i, j));
}
}
}
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
I don't use any std map. I just iterate once over all list.
It's not big deal to support your special cases and still having O(N). The following code is the solution:
- ultras October 29, 2014