jeremy.william.murphy
BAN USER
Comments (3)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
C++11. I couldn't think of a better name for the sorting semantics.
/*
Given a list of integers, find the highest value obtainable by concatenating
these together.
For example, given 9, 918, 917  The answer is 9918917.
But given 1,112,113  The answer is 1131121
Written in C++11.
*/
#include <iostream>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
using namespace std;
// a < ab < ac < bb < b < cb < c < cd
template <typename Container>
struct pseudo_lexicographical_less
{
bool operator()(Container a, Container b) const
{
bool swapped = false;
if (b.size() < a.size())
{
swap(a, b);
swapped = true;
}
// a.size() <= b.size()
auto const p = mismatch(begin(a), end(a), begin(b));
if (p.first == end(a))
{
if (a.size() == b.size())
return false; // swap is irrelevant
else
{
auto const x = *(begin(b) + a.size()  1);
auto const f = [&](char z) {
return z == x;
};
auto const q = find_if_not(begin(b) + a.size(), end(b), f);
return q == end(b) ? swapped : (*q < x) == swapped;
}
}
else
return (*p.first < *p.second) != swapped;
}
};
template <typename Container>
struct pseudo_lexicographical_greater
{
bool operator()(Container a, Container b) const
{
return pseudo_lexicographical_less<Container>()(b, a);
}
};
int main(int argc, char **argv)
{
if (argc < 2)
exit(EXIT_FAILURE);
vector<string> data(argv + 1, argv + argc);
sort(begin(data), end(data), pseudo_lexicographical_greater<string>());
for (auto i : data)
cout << i << " ";
cout << endl;
}

jeremy.william.murphy
November 29, 2015 Comment hidden because of low score. Click to expand.
0
of 0 vote
I found the edge cases in this problem really kept me on my toes. I'm not 100% happy with my solution  it's more geared towards simplicity than efficiency (believe it or not), but I'm happy enough to share it with the world. It treats matchboxes as integers and prints out the value of the matchboxes chosen, not their index.
I assume the time complexity is O(C(n, k) ⋅ n).
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <cassert>
using namespace std;
template <typename I0, typename I1, typename T = typename iterator_traits<I0>::value_type>
T count_matches(I0 f_matchbox, I0 l_matchbox, I1 f_combination)
{
// Not the most efficient method but straightforward.
return inner_product(f_matchbox, l_matchbox, f_combination, 0); // O(n)
}
// Select K matchboxes such that M % F == 0 and minimize(M)
// Requires random access iterators to nonconst matchbox range.
template <typename I, typename O>
O minimize_M_multiple_F(I first, I last, O result, size_t F, size_t K)
{
assert(F != 0);
assert(K < last  first && K != 0);
using matchbox_t = typename iterator_traits<I>::value_type;
sort(first, last, greater<matchbox_t>()); // O(n lg n) time.
auto const n = last  first;
vector<bool> combination; // O(n) bits space.
combination.resize(n);
fill(combination.rbegin(), combination.rbegin() + K, true);
bool searching = true;
size_t M = count_matches(first, last, begin(combination));
while (M == 0 && searching) // Get past the zero edge case.
{
searching = next_permutation(begin(combination), end(combination));
M = count_matches(first, last, begin(combination));
}
size_t target = F;
while (searching && M % F)
{
target = M  M % F + F; // Simplifies inner loop condition.
do
{
searching = next_permutation(begin(combination), end(combination));
M = count_matches(first, last, begin(combination));
}
while (searching && M < target);
}
if (M % F == 0)
{
for (size_t i = n; i > 0; i)
if (combination[i1])
*result++ = first[i1];
}
return result;
}
int main(int argc, char **argv)
{
if (argc < 3)
exit(EXIT_FAILURE);
using matchbox_t = int;
vector<matchbox_t> matchboxes = {0, 0, 1, 2, 2, 7, 12};
vector<matchbox_t> answer;
auto const F = strtoul(argv[1], nullptr, 10);
auto const K = strtoul(argv[2], nullptr, 10);
answer.reserve(K);
minimize_M_multiple_F(begin(matchboxes), end(matchboxes), back_inserter(answer), F, K);
for (auto matchbox : answer)
cout << matchbox << " ";
cout << endl;
}

jeremy.william.murphy
November 22, 2015 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
memoreku makes a great observation that the set for a basic character string can just be an array of bool that fits in a 32bit integer (or 64bit if you want mixed case). I decided to stick with the more conservative standard library data structure, mostly for expository purposes.
This algorithm solves the problem in amortized worstcase O(n lg n) by sorting the list of words in decreasing order of size first. This allows you to test the best possible answers in decreasing order by traversing the words appropriately.
It is also worth noting that you only need to store the set of one word at a time and only calculate the set of each word once.
There are tradeoffs to be made depending on the average word length M.
 jeremy.william.murphy December 16, 2015