LaithBasilDotNet
BAN USERit should be sorted first
- LaithBasilDotNet May 18, 2015Here is a NLogN solution, first thing we sort the kids which will take O(nlogN), then we do as
2 sum problem but here we do not search for exact value, we search for any combination from R and L that is less than 150, and we count 1.
class Kid{
public:
double weight;
Kid(double w=0) :weight(w){}
bool operator<(const Kid& k)const{
return weight < k.weight;
}
};
int minNumberOfCanoe(const vector<Kid>& kids){
vector<Kid> sortedKids = kids;
sort(sortedKids.begin(), sortedKids.end());
int L = 0;
int R = sortedKids.size() - 1;
int canonCount = 0;
while (L <= R){
int wBig = sortedKids[R].weight;
int wSmall = sortedKids[L].weight;
if (wBig + wSmall <= 150){
canonCount++;
R--;
L++;
}
else if (wBig <= 150){
canonCount++;
R--;
}
}
return canonCount;
}
Simply, since each query has a count, we build array of ranges and each range represent a query, then we use rand()%countSum , where countSum is the sum of all counts for all queries, after that we do binary search to see this fits in which range and we return the query that represent this range !
here is the code, O(N)
class Range : public pair<int,int>{
public:
int queryIndex;
Range(int f, int s, int qindex=0) : pair<int, int>(f, s), queryIndex(qindex){}
};
int binarySearch(vector< Range >& rangesList,int value, int L, int R){
if (L <= R)
{
int m = (L + R) / 2;
if (rangesList[m].first <= value && value <= rangesList[m].second)
return m;
else
if (value > rangesList[m].second){
return binarySearch(rangesList, value, m + 1, R);
}
else{
return binarySearch(rangesList, value, L, m - 1);
}
}
return -1;
}
string getRandomQuery(const vector< pair<string, int> >& queries){
vector< Range > rangesList;
int rangeCount = 0;
int countSum = 0;
for (int i = 0; i < queries.size(); i++){
Range range(rangeCount, rangeCount + queries[i].second - 1, i);
rangesList.push_back(range);
countSum += queries[i].second;
rangeCount += queries[i].second;
}
int randomValue = rand() % countSum;
int index = binarySearch(rangesList, randomValue, 0, rangesList.size() - 1);
return queries[index].first;
}
what if digits is 1000, you missed the point of this question !
- LaithBasilDotNet May 18, 2015Looks like that everyone forgot the possibility of getting negative number.
like -5/3, most of the solutions will give 1.-6-6
void nDigits(int n, int d, int c){
cout << n / d << ".";
int count = 0;
while (count < c){
n = (n%d) * 10;;
cout << abs(n / d);
count++;
}
}
Impressive !!
- LaithBasilDotNet May 17, 2015This is one tricky question, okay here is the solution idea and code.
assume you have these input: [bat , tab , tabaa , aatab]
that output should be [ bat , tab ] [ tabaa, bat ] [ bat , aatab ]
step 1: we will store all words as following in hash table as following that has *key as string*
and value as *hash set* let say for strings to make it easier
( but in my code I store only the index of the word )
for word "bat"
b -> { bat }
ba -> { bat }
bat -> { bat }
no we store it also in reverse direction but not reverse string like this
t - > { bat }
at -> { bat }
bat -> { bat } // it will not repeated since its hash set
this operation will take O(NK) where k is the length of maximum word in the input
Step 2: we will iterate through the words again, and for each word we get the reverse of this word
and look in the hash table for the potential string that will cause them to give correct answer.
ex. if we have bat, we will look for "tab" and in the step one we will have in key "tab" 3 strings
which is { tab , tabaa , aatab }
we will check ( battab && tabbat ), ( battabaa & tabaabat ) , ( tabaatab && tabtabaa) and we will
pick the correct ones without repeating ( sure this will cost us another hash set to make sure no
duplicates in output )
here in my code, I used indices rather than store strings, and the output is pair indices for the
2 words.
Sure someone will ask, is the second for loop O( N K ), try your self any sample input, and you
will find that it will never exceed O( N K ) !
bool isPalindrome(const string& w){
for (int i = 0; i < w.size(); i++){
if (w[i] != w[w.size() - 1 - i])
return false;
}
return true;
}
vector<pair<int, int> > findPalindrome(const vector<string>& words){
unordered_map<string, unordered_set<int> > wordsMap;
unordered_set< pair< int, int > > visitedPairs;
// O( N * K ) where K is the length of the maximum word characters length in the vector
for (int i = 0; i < words.size(); i++){
string s;
string revDirS;
s.reserve(words[i].size());
revDirS.reserve(words[i].size());
for (int j = 0; j < words[i].size(); j++){
// ex. tabaa -> t , ta , tab , taba, tabaa
s += words[i][j];
//ex. tabaa -> a , aa , baa , abaa , tabaa
revDirS = words[i][words[i].size() - 1 - j] + revDirS;
wordsMap[s].insert(i); // saving the indices rather than the words
wordsMap[revDirS].insert(i);
}
}
vector< pair<int, int> > ret;
for (int i = 0; i < words.size(); i++){
string revWord(words[i]);
reverse(revWord.begin(), revWord.end());
for (auto wordsIndex : wordsMap[revWord]){
if (i == wordsIndex)
continue;
int minIndex = min(i, wordsIndex);
int maxIndex = max(i, wordsIndex);
if (visitedPairs.count(make_pair(minIndex, maxIndex)) == 0){
if (isPalindrome(words[i] + words[wordsIndex])){
ret.push_back(make_pair(i, wordsIndex));
visitedPairs.insert(make_pair(minIndex, maxIndex));
}else if (isPalindrome(words[wordsIndex] + words[i])){
ret.push_back(make_pair(wordsIndex,i));
visitedPairs.insert(make_pair(minIndex, maxIndex));
}
}
}
}
return ret;
}
to get my idea, just try your code or my latest code with this input
[1,10],[1,100000000],[0,6], if its only N it should run as fast is for [1,10] [0,6] [1,3] but you will notice that it will get many seconds before it return the result to you !
that because you iterate all the distance between *iter to the max in your code.
I think he wrote a correct answer, but without a code to describe it, this is how this written ! its the idea of counter sort
vector<int> findOverLappingJobs2(vector< pair<int, int> >& jobs) {
vector<int> dayTime(24, 0);
vector<int> res;
for (int i = 0; i < jobs.size(); i++) {
for (int s = jobs[i].first; s <= jobs[i].second; s++) {
dayTime[s]++; // those who overlapp will have count more than 1
}
}
for (int i = 0; i < jobs.size(); i++) {
for (int s = jobs[i].first; s <= jobs[i].second; s++) {
if (dayTime[s] > 1) {
res.push_back(i);
break;
}
}
}
return res;
}
I got your solution, I think its not O(N) since you iterate from *iter to max which mean its O(NM) where M is the maximum range distance, since its a time we are limited by 24 hour a day, which make since then. its like counting sort!
by the way its a nice trick :)
here is a simpler way to write the code
vector<int> findOverLappingJobs2(vector< pair<int, int> >& jobs) {
vector<int> dayTime(24, 0);
vector<int> res;
for (int i = 0; i < jobs.size(); i++) {
for (int s = jobs[i].first; s <= jobs[i].second; s++) {
dayTime[s]++; // those who overlapp will have count more than 1
}
}
for (int i = 0; i < jobs.size(); i++) {
for (int s = jobs[i].first; s <= jobs[i].second; s++) {
if (dayTime[s] > 1) {
res.push_back(i);
break;
}
}
}
return res;
}
I don't understand how it should work, but what your code execution time is it N^2 or NLogN or N
- LaithBasilDotNet May 13, 2015What is RangeSet ? and how it works ?
- LaithBasilDotNet May 13, 2015This one a tricky question, it does seem easy at first but when you try with values like [0,6] , [1,2],[3,5] you will notice what goes wrong,
so this is the solution,
0. we should store the old indices of ranges in a map.
1. then we should sort the intervals according to start then according to end
2. we will keep track of the latest merged range and compare it with the new range, its a dynamic programming solution, where we will assume the first merged range is range number zero in the sorted ranges array.
3. we will iterate through the sorted range array from index 1 to end, and check
if( current range intersect with latest merged range ) {
latest marge range = { min( current range.start , mergedRange.start ) ,
max( current range.end , mergedRange.end )
}
if( i -1 == 0) // to consider the first element that we put in the range
add 0 result vector;
add current range *Original* index ( before the sort ) to the result vector
}else{
latest merged range = current range;
}
5. sort the result vector
6. return the result vector;
here is the code, this solution is O(nlogN) , since the sort takes the most of the time.
template<>
class hash< pair<int, int> >
{
public:
bool operator()(const pair<int, int>& p)const {
return hash<int>()(p.first) ^ hash<int>()(p.second);
}
};
bool isInRange(int index, pair<int, int> range) {
return index >= range.first && index <= range.second;
}
vector<int> findOverlapps(vector<pair<int, int> > & jobs) {
if (jobs.size() <= 1)
return{};
unordered_map<pair<int, int>, int > rangeOrgIndexMap;
for (int i = 0; i < jobs.size(); i++) {
rangeOrgIndexMap[jobs[i]] = i;
}
vector<int> overlappIndex;
vector<pair<int, int> > sortedJobs = jobs;
sort(sortedJobs.begin(), sortedJobs.end());
pair<int, int> mergedRange = sortedJobs[0];
for (int i = 1; i < sortedJobs.size() ; i++) {
if( isInRange(sortedJobs[i].first, mergedRange) || isInRange(sortedJobs[i].second, mergedRange) ) {
mergedRange = { min(sortedJobs[i].first , mergedRange.first) , max(sortedJobs[i].second , mergedRange.second) };
if (i - 1 == 0)
overlappIndex.push_back(rangeOrgIndexMap[sortedJobs[i-1]]);
overlappIndex.push_back(rangeOrgIndexMap[sortedJobs[i]]);
}
else {
mergedRange = sortedJobs[i];
}
}
sort(overlappIndex.begin(), overlappIndex.end());
return overlappIndex;
}
does your solution works with [1,2][3,5][0,6] ?
- LaithBasilDotNet May 13, 2015Does your solution keep track of the indices after the sort ? we need to keep tack of them !
- LaithBasilDotNet May 13, 2015Here is the solution:
we will have 3 maps,
1. map<int, set<int> > uniqueVisitsToPageMap
which will rank pages according to unique visits for each page, assume page 1 visited by
2 unique users then a new unique user visited it, we will remove the page 1 from
2 visits key and add it to 3 visits key.
2. map<int, set<int> > pageToUsersTracMap;
this map will tell each page and which user visited it, as you can notice this is a set so no duplicates in users ID
3.map<int, map<int, int> > userToPageMap;
this map between user ID and the pages he visited and how much time he visit each page
UsersID -> { pageID -> visit times }
Now, I will assume that map is hash table ( unordered_map ) and set is hash set ( unordered_set ),
* for the first requirement it will cost O(1) to *find the pages*
* for the second requirement it will cost O(1) to find the pages and N to *find the page with 2 visit times *
where N here is the number of pages with 1 unique visit. yes we can do better if we user Bi Map
* for third requirement, it will cost O(1) to find the user, and N to find the page where N is the #
of pages visited by this user.
Here is the code, where I use map and set here just to minimize the code text size for me, but you replace it with unordered_map and unordered_set
class LogFileQuery {
public:
void addLog(int userID, int pageID) {
int visitsRank = pageToUsersTracMap[pageID].size();
if (pageToUsersTracMap[pageID].count(userID) <= 0 && visitsRank>0) {
uniqueVisitsToPageMap[visitsRank].erase(pageID);
visitsRank = visitsRank + 1;
uniqueVisitsToPageMap[visitsRank].insert(pageID);
}
pageToUsersTracMap[pageID].insert(userID);
userToPageMap[userID][pageID]++; // user ID -> pageID | visits
}
vector<int> pagesByVisits(int numberOfUniqueUsers) {
vector<int> pages;
if (uniqueVisitsToPageMap.count(numberOfUniqueUsers) >= 0) {
auto retPages = uniqueVisitsToPageMap[numberOfUniqueUsers];
for (auto& p : retPages) {
pages.push_back(p);
}
}
return pages;
}
vector<int> pagesVisitedByOnlyOneUser(int times) {
vector<int> pages;
set<int> pages1TimeUnqiueVisit;
pages1TimeUnqiueVisit = uniqueVisitsToPageMap[1];
for (auto& pageID : pages1TimeUnqiueVisit) {
set<int> users = pageToUsersTracMap[pageID];
for (auto& userID : users) {
if (userToPageMap[userID][pageID] == times)
pages.push_back(pageID);
}
}
return pages;
}
vector<int> pagesVisitedByUser(int userID, int moreThanTimes) {
vector<int> pages;
if (userToPageMap.count(userID) >= 0) {
for (auto& p : userToPageMap[userID]) {
if (p.second > moreThanTimes)
pages.push_back(p.first);
}
}
return pages;
}
protected:
map<int, map<int, int> > userToPageMap; // usersID -> pageID | visits
map<int, set<int> > pageToUsersTracMap; // pageID -> visitied user ID
map<int, set<int> > uniqueVisitsToPageMap; // unqie visites# -> page ID
};
here is a simple solution
- LaithBasilDotNet May 19, 2015