IdeaHat
BAN USERLazy C++ verson
std::vector<uint64_t> histo_people(const std::vector<int>& s) {
using namespace std;
vector<uint64_t> counts(s.back()+1);
auto cur_age = s.cbegin();
while (cur_age != s.end()) {
auto ub = upper_bound(cur_age,s.cend(),*cur_age);
counts[*cur_age] = ub-cur_age;
cur_age = ub;
}
return counts;
}
@Victor since we are checking if *all* paths are push to the fire exit (not shortest path, or even if there is exists a path, but if ALL paths go to it) then we have to conclude that we are talking about acyclic paths to the exit, else any building with two rooms would fail the test (I can walk through push door 1, then walk about through it, and thus fail).
- IdeaHat January 03, 2015@rizhang more accurately, anon has speed up the asymptotic behavior of the sorting problem by using counting sort rather then the O(n*lg(n)) sorts others have used. This indeed have a O(n*m) run time...but IMHO a good interviewee would know the limitations of counting sort and the actual meaning of O notation. The real runtime of counting sort is O(n+k), where k is the number of buckets (26, in this case). So the overall runtime is O(n*m+k*m) (degenerates to k*m when n < m). Asymptotically, this will perform better when n gets very large. However, n*lg(n) run times will most likely be faster when n<<k, and wolfram alpha puts the average length of a word at 5.1. This is one of those cases where measuring would be the only way to prove things out. I'd guess either solution is fine as long as one could explain the other, why they chose the one they did, what the implementations of are of each, ect.
- IdeaHat December 14, 2014A C++ solution. If n is the charaters in the string, and m is number of the strings, Calculating the key is O(nlgn), adding it to the hash is O(n) (for the copy and calculating the key, do that m times, overall O(m*n*lg(n));
#include <iostream>
#include <unordered_map>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
typedef std::unordered_map<std::string,std::vector<std::string> > MM;
template <typename ITER>
MM find_anagrams(ITER b, ITER e) {
MM ret;
for ( ; b != e; ++b) {
std::string key{*b};
std::sort(key.begin(),key.end());
ret[key].push_back(*b);
}
return ret;
}
int main()
{
std::vector<std::string> x{"trees", "bike", "cars", "steer", "arcs"} ;
auto y = find_anagrams(x.begin(),x.end());
for (auto& v : y) {
std::cout << "Bucket " << v.first << std::endl;
for (auto& s : v.second) {
std::cout << " " << s << std::endl;
}
}
return 0;
}
O(n*k*m)...could be improved to O(n*m) by using a smart queue to do the windowed min, but uh...lazy.
- IdeaHat January 06, 2015