Josh
BAN USERA C++ solution
This takes advantage of the pre-sorted nature (though an additional sort would only be required for lists 2 and 3, adding a (log(x) + log(y).) We loop only through list 1 (O(n)), find the closest values in lists 2 and 3 via binary search (log(x) + log(y)), and save the best min distance.
std::pair<int, int> getMinPair(
const std::set<int>& set1,
const std::set<int>& set2,
const std::set<int>& set3)
{
// Prepare the min distance return value
std::pair<int, int> minDist(0, 0);
// Save best min distance separately to avoid having to
// constantly subtract the two minDist numbers
int bestDist = INT_MAX;
// Loop through each value in vector 1 - O(n)
for (std::set<int>::const_iterator itr = set1.begin();
itr != set1.end();
++itr)
{
// Find the closest values from itr to set2 and set3
// via a binary search - nlog(x) + nlog(y)
int x = getClosest(*itr, set2);
int y = getClosest(*itr, set3);
// Quickly sort the three values of interest
std::set<int> sorted = {x, y, *itr};
// Compare the distance
int dist = *sorted.rbegin() - *sorted.begin();
if (dist < bestDist)
{
// Save the new best distance
bestDist = dist;
minDist = std::make_pair(*sorted.begin(), *sorted.rbegin());
}
}
return minDist;
}
Here's the helper method getClosest() which finds the closest value. A little verbose, but takes care of the edge cases.
int getClosest(int value, const std::set<int>& values)
{
// We start by finding the lowerbound (which is >= value)
// We then check the previous value (if exists) to see if
// its closer than the lowerbound
std::set<int>::const_iterator lb = values.lower_bound(value);
// If we reached the end, the last value is the closest
if (lb == values.end()) return *values.rbegin();
// Check if we're at the first value
if (lb == values.begin()) return *lb;
// Compare the value with the previous in the list
int lbVal = *lb;
--lb;
int prevVal = *lb;
int lbDist = lbVal - value;
int prevDist = prevVal - value;
// Return the closer of the two
if (std::abs(prevDist) < std::abs(lbDist))
return prevVal;
return lbVal;
}
A C++ solution
This strategy builds a list of values needed to reach the sum. The second loop searches the sum list for each value. The trick is to take advantage of hash maps (unordered_set), although if space concerns exist, a binary search tree can be used instead (set).
Using std::unordered_set
Time: O(n) to O(n^2)
Space: O(n)
Using std::set
Time: O(nlogn)
Space: O(n)
bool check(int list1[], int list2[], int sum,
int count1, int count2)
{
// Corner/Edge cases
if (sum <= 0 || count1 < 1 || count2 < 0) return false;
// Create a list of sum values needed for the second list
std::unordered_set<int> sums;
// Add the needed sum values to a hash map
for (int i = 0; i < count1; ++i)
if (list1[i] <= sum)
sums.insert(sum - list1[i]);
// Check each value in list2 if it exists in the hash map
for (int i = 0; i < count2; ++i)
if (sums.find(list2[i]) != sums.end())
return true;
return false;
}
A C++ solution
This problem is neat because you naturally want to sort such a problem, but the words need to remain next to each other. The solution below uses the concept of a queue in that it pushes values onto a sum, and pops off the oldest value (found by "i - len"). Also this algorithm doesn't bother reducing the length ever as the length essentially "raises the bar" for the next max length.
Time: O(n)
Space: O(1)
int maxLen(int arr[], int max, int count)
{
// Corner cases and edge cases
if (count < 1 || max < 1) return 0;
int sum = 0;
int len = 0;
for (int i = 0; i < count; ++i)
{
sum += arr[i];
if (sum <= max)
++len;
else
sum -= arr[i - len];
}
return len;
}
A C++ solution
The strategy here is to take advantage of two data structures to
accommodate our needs. The important data structure is the hashmap
(std::map in C++), which will lets us efficiently get duplicate counts and
unique letter counts in O(1) time.
The stringstream is the other structure used, though a queue may be
just as appropriate. The stringstream is expanded to the largest it can be,
then just stays that size, but only gets copied to the new max string if
the stringstream fits inside the required unique count.
std::string getMaxString(const char* input, size_t count, size_t k)
{
// Corner cases and edge cases
if (count <= k) return std::string(input);
if (k == 0) return std::string();
if (k == 1) return std::string(input).substr(0, 1);
// Map letter to num duplicates
std::map<char, int> hashmap;
std::string maxString;
std::stringstream currentString;
char trash;
while (input[0])
{
// Push the next character onto the queue
currentString << input[0];
// Ensure character exists and default to 0
hashmap.insert(std::make_pair(input[0], 0));
// Increment count of duplicated for current letter
++hashmap[input[0]];
// Shrink map if unique count hit cap
if (hashmap.size() > k)
{
// Pop the first character into a dummy variable
currentString >> trash;
std::map<char, int>::iterator itr = hashmap.find(trash);
--itr->second;
if (itr->second == 0)
hashmap.erase(itr);
}
// Set max string
if (hashmap.size() <= k &&
currentString.str().size() > maxString.size())
maxString = currentString.str();
}
return maxString;
}
C++ solution
This solution assumes substrings only consists of letters
next to each other. The strategy is to start with the full
string, and instead of a standard Trie search, when a string
is found, keep searching. Then keep chopping off the first
letter and restarting the search.
void getStrings(TrieNode* trie,
const char* string, std::list<std::string>& strings)
{
strings.clear();
if (!trie) return;
if (!string) return;
// Loop through the full string
while (string[0])
{
// Get all sub-strings
getAllStrings(trie, string, strings);
// Chop off the left-most letter
++string;
}
}
void getAllStrings(TrieNode* trie,
const char* word, std::list<std::string>& strings)
{
if (!trie) return;
if (!word) return;
TrieNode* crawl = trie;
// Search the entire word
while (word[0])
{
int index = charToIndex(word[0]);
// No more valid words possible
if (!crawl->children[index]) return;
crawl = crawl->children[index];
// Add the sub-string if found
if (crawl->leaf) strings.push_back(word);
// Keep searching for more sub-strings
++word;
}
}
Extra stuff needed for the solution above
#include <list>
#include <string>
const int NUM_LETTERS = (int)'z' - (int)'a' + 1;
struct TrieNode
{
TrieNode* children[NUM_LETTERS];
bool leaf;
TrieNode() : leaf(false)
{
for (size_t i = 0; i < NUM_LETTERS; ++i)
children[i] = NULL;
}
};
int charToIndex(const char& ch)
{
if ((int)ch >= (int)'a') return (int)ch - (int)'a';
return (int)ch - (int)'A';
}
C++ solution
int getRandomOdd(int left, int right)
{
// Exclude right-most odd number
right = right % 2 == 1 ? right - 1 : right;
// Error checking
if (left >= right) return 0;
// Divide out even numbers and shift to the left
int leftRng = rand() % ((right - left + 1) / 2) - 1;
// Check for left even shift
int leftShift = left % 2 == 0 ? 1 : 0;
// Shift it back to the right and expand to all odd numbers
return left + leftShift + 2 * (leftRng + 1);
}
A C++ solution
Part 1 - Using O(n) for both time and space complexity.
Nothing special here. Just loops through and stores
max indices into a vector, and resetting the vector
when a new max is found.
int getMax(const std::vector<int>& arr)
{
if (arr.size() == 0) return -1;
int max = arr[0] - 1; // Guarantee first index
std::vector<int> maxes; // Vector of indices
maxes.reserve(arr.size()); // Vector memory efficiency
// Get the max value
for (size_t i = 0; i < arr.size(); ++i)
{
// Refresh vector on new max
if (arr[i] > max)
{
maxes.clear();
max = arr[i];
}
// Store the index
if (arr[i] >= max) maxes.push_back(i);
}
return maxes[rand() % maxes.size()];
}
Part 2 - Using O(n) for time and O(1) for space
This is similar to the above solution but doesn't save
each max index found. Instead, when a new max is found,
the max index is refreshed, and when a duplicate max is
found, the max index has a probability to flip to the new
index, based on a degrading probability.
int getMax(const std::vector<int>& arr)
{
if (arr.size() == 0) return -1;
int max = arr[0] - 1; // Guarantee first index
int maxIndex = 0;
int numMaxFound = 0; // Save number of max indices
// Get the max value
for (size_t i = 0; i < arr.size(); ++i)
{
// Refresh count on new max
if (arr[i] > max)
{
numMaxFound = 1;
max = arr[i];
maxIndex = i;
}
// Random chance to flip the max index
// based on a degrading probability
else if (arr[i] == max)
if (rand() % ++numMaxFound == 1)
maxIndex = i;
}
return maxIndex;
}
Two C++ solutions, based on STL. The first solution may or may not be
good enough as it considers {a, b}, {cat, cat} to be a match, but that
depends on the nature of the problem
bool matched(const std::vector<std::string>& pat,
const std::vector<std::string>& str)
{
if (pat.size() != str.size()) return false;
std::map<std::string, std::string> match;
for (size_t i = 0; i < pat.size(); ++i)
{
if (match.insert(std::make_pair(pat[i], str[i]))
.first->second != str[i])
return false;
}
return true;
}
//a,a == cat,dog => false
//a,b == cat,dog => true
//a,b == cat,cat => true (Is this OK?)
//a,b == cat,dog,moo => false
Now lets say we want to match the pattern with the strings, and the
strings back with the pattern, thus avoiding the third result above.
We simply add another map to match in reverse.
bool matched(const std::vector<std::string>& pat,
const std::vector<std::string>& str)
{
if (pat.size() != str.size()) return false;
std::map<std::string, std::string> patMatch;
std::map<std::string, std::string> strMatch;
for (size_t i = 0; i < pat.size(); ++i)
{
if (patMatch.insert(std::make_pair(pat[i], str[i]))
.first->second != str[i] ||
strMatch.insert(std::make_pair(str[i], pat[i]))
.first->second != pat[i])
return false;
}
return true;
}
//a,a == cat,dog => false
//a,b == cat,dog => true
//a,b == cat,cat => false
//a,b == cat,dog,moo => false
Some code to test
#include <iostream>
#include <string>
#include <map>
#include <vector>
void test(const std::vector<std::string>& pat,
const std::vector<std::string>& str)
{
if (pat.size() > 0) std::cout << pat[0];
for (size_t i = 1; i < pat.size(); ++i)
std::cout << "," << pat[i];
std::cout << " == ";
if (str.size() > 0) std::cout << str[0];
for (size_t i = 1; i < str.size(); ++i)
std::cout << "," << str[i];
std::cout << " => " << std::boolalpha
<< matched(pat, str) << std::endl;
}
int main()
{
typedef std::vector<std::string> array;
test(array({"a", "a"}), array({"cat", "dog"}));
test(array({"a", "b"}), array({"cat", "dog"}));
test(array({"a", "b"}), array({"cat", "cat"}));
test(array({"a", "b"}), array({"cat", "dog", "moo"}));
}
C++ recursive approach just for fun
double powHelper(int x, int y)
{
return y == 1 ? x : x * powHelper(x, y - 1);
}
double pow(int x, int y)
{
// Corner cases and edge cases
if (y == 0 && x < 0) return -1;
if (x == 0 && y < 0) return -1u >> 1; // MAX_INT
if (y == 0) return 1;
if (x == 0) return 0;
// Use separate helper function to avoid
// duplicating corner/edge case tests
if (y > 0)
return powHelper(x, y);
else
return 1.0 / powHelper(x, -y);
}
A basic C++ brute force approach without
abstracting away with STL maps.
bool match(const std::string& pats,
const std::vector<std::string>& strs)
{
if (pats.size() != strs.size) return false;
int count = pattern.size();
for (int i = 0; i < cout; ++i)
{
for (int j = i; j < count; ++j)
{
if (pats[i] == pats[j] && strs[i] != strs[j]) ||
(pats[i] != pats[j] && strs[i] == strs[j])
return false;
}
}
return true;
}
Another C++ solution, but with hash maps for better efficiency.
The style here is to add up the values of each node, then
hash the result and store the node into a map with the hashed
key. The idea is to save time by only comparing trees when
there is a hash collision.
Basic Node structure
struct Node
{
Node* left;
Node* right;
int val;
};
Part 1 - Check if a tree has duplicate sub-trees
bool hasDuplicates(Node* root)
{
if (root == NULL) return false;
bool dupFound = false;
// Multimap allows multiple values with same key
std::unordered_multimap<int, Node*> hashMap;
hashTree(root, hashMap, dupFound);
return dupFound;
}
// Returns recursively calculated hash value
int hashTree(Node* node,
std::unordered_multimap<int, Node*>& hashMap,
bool& dup)
{
if (dup) return; // Kick out of recursion early
if (node == NULL) return 0;
// Get hash value of left tree
int leftHash = hashTree(node->left, map, dup);
if (dup) return; // Kick out of recursion early
// Get hash value of right tree
int rightHash = hashTree(node->right, map, dup);
if (dup) return; // Kick out of recursion early
int hashValue = hash(leftHash + rightHash + node->val);
// Loop through collisions
for (std::unordered_multimap<int, Node*>::iterator collisionMap =
hashMap.find(hashValue);
collisionMap != hashMap.end();
++collisionMap)
{
// Compare due to a hash collision
dup = compareTrees(node, collisionMap->second);
// Return on duplicate found
if (dup) return;
}
// Add the tree to the map
hashMap.insert(std::make_pair(hashValue, node));
}
// Simple hash function
int hash(int key)
{
// Increase number to sacrifice space for time, and vice-versa
return key % 100;
}
// Recursive tree comparison method
bool compareTrees(Node* left, Node* right)
{
if (NULL == left == right) return true;
if (left == NULL || right == NULL) return false;
return left->val == right->val &&
compareTrees(left->left, right->left) &&
compareTrees(left->right, right->right);
}
Part 2 - Return all duplicates
For efficiency, the duplicate list should be passed in by reference
void hasDuplicates(Node* root, std::list<Node*>& duplicates)
{
duplicates.clear(); // Good coding practice
if (root == NULL) return;
// Multimap allows multiple values with same key
std::unordered_multimap<int, Node*> hashMap;
hashTree(root, hashMap, duplicates);
return dupFound;
}
// Returns recursively calculated hash value
int hashTree(Node* node,
std::unordered_multimap<int, Node*>& hashMap,
std::list<Node*>& duplicates)
{
if (node == NULL) return 0;
// Get hash value of left tree
int leftHash = hashTree(node->left, map, dup);
if (dup) return; // Kick out of recursion early
// Get hash value of right tree
int rightHash = hashTree(node->right, map, dup);
if (dup) return; // Kick out of recursion early
int hashValue = hash(leftHash + rightHash + node->val);
// Loop through collisions
for (std::unordered_multimap<int, Node*>::iterator collisionMap =
hashMap.find(hashValue);
collisionMap != hashMap.end();
++collisionMap)
{
// Compare due to a hash collision
if (compareTrees(node, collisionMap->second))
duplicates.push_back(node);
}
// Add the tree to the map
hashMap.insert(std::make_pair(hashValue, node));
}
// Simple hash function
int hash(int key)
{
// Increase number to sacrifice space for time, and vice-versa
return key % 100;
}
// Recursive tree comparison method
bool compareTrees(Node* left, Node* right)
{
if (NULL == left == right) return true;
if (left == NULL || right == NULL) return false;
return left->val == right->val &&
compareTrees(left->left, right->left) &&
compareTrees(left->right, right->right);
}
C++ approach
A basic Node structure
struct Node
{
Node* left;
Node* right;
int val;
};
Part 1 - Check if a tree has duplicate sub-trees
bool hasDuplicates(Node* root)
{
std::vector<Node*> nodesToCheck;
nodesToCheck.reserve(100); // Helps with vector push_back efficiency
Node* node = root;
// Compare the children
while (node != NULL)
{
// Push the right tree onto a list to compare
nodesToCheck.push_back(node->right);
// Compare the each right sub-tree to the left tree
for (int i = 0; i < nodesToCheck.size(); ++i)
{
if (duplicateFound(node->left, nodesToCheck[i]) return true;
}
// Check for duplicates purely within the right trees
if hasDuplicates(node->right) return true;
// Get the next left node to check
node = node->left;
}
return false;
}
// Recursively compare two trees
bool duplicateFound(Node* left, Node* right)
{
if (left == right == NULL) return true;
if (left == NULL && right != NULL) return false;
if (left != NULL && right == NULL) return false;
// Recursive check
if (left->val == right->val &&
compare(left->left, right->left &&
compare(left->right, right->right)
return true;
// The trees are not the same, so check all the right children
if (duplicateFound(left, right->left)) return true;
return duplicateFound(left, right->right));
}
Part 2 - Return all duplicates
With the above code, this isn't too hard. Just replace the main
"return true" with "duplicates.push_back(...);"
std::vector<Node*> hasDuplicates(Node* root)
{
std::vector<Node*> duplicates;
duplicates.reserve(100); // Helps with vector push_back efficiency
std::vector<Node*> nodesToCheck;
nodesToCheck.reserve(100); // Helps with vector push_back efficiency
Node* node = root;
// Compare the children
while (node != NULL)
{
// Push the right tree onto a list to compare
nodesToCheck.push_back(node->right);
// Compare the each right sub-tree to the left tree
for (int i = 0; i < nodesToCheck.size(); ++i)
{
if (duplicateFound(node->left, nodesToCheck[i])
duplicates.push_back(node->left);
}
// Check for duplicates purely within the right trees
hasDuplicates(node->right); // No need for an extra push_back()
// Get the next left node to check
node = node->left;
}
return duplicates
}
// Recursively compare two trees
bool duplicateFound(Node* left, Node* right)
{
if (left == right == NULL) return true;
if (left == NULL && right != NULL) return false;
if (left != NULL && right == NULL) return false;
// Recursive check
if (left->val == right->val &&
compare(left->left, right->left &&
compare(left->right, right->right)
return true;
// The trees are not the same, so check all the right children
if (duplicateFound(left, right->left)) return true;
return duplicateFound(left, right->right));
}
// This solution assumes in-order, though this question could be changed to pre-order or post-order.
// This solution also assumes that a node is a value when it is a leaf, and is an expression otherwise
// Code in C++
struct Node
{
Node* left;
Node* right;
double val;
std::string exp; // --, ++, +, -, *, /
}
bool checkTrees(Node* left, Node* right)
{
if (left == NULL && right != NULL) return false;
if (left != NULL && right == NULL) return false;
return eval(left) == eval(right);
}
double eval(Node* node)
{
if (node->left == node-> right == NULL)
return node->val;
if (node->left == NULL && node-> right != NULL)
return compute(node->right, node->val);
if (node->left != NULL && node-> right == NULL)
return compute(node->left, node->val);
return compute(eval(node->left), node->exp, eval(node->right));
}
double compute(double valu, const std::string& exp)
{
if (exp == "--") return val - 1.0;
if (exp == "++") return val + 1.0;
// ERROR - Invalid tree
return 0.0;
}
double compute(double left, const std::string& exp, double right)
{
if (exp == "+") return left + right;
if (exp == "-") return left - right;
if (exp == "*") return left * right;
if (exp == "/") return left / right;
// ERROR - Invalid tree
return 0.0;
}
A C++ solution
The strategy here is to consider the best displacement in favor of yourself. In other words, consider the profit of the left two choices and the right two choices, which we will call a distance. We choose a side by grabbing the side with the smallest distance.
As for the code, it is done using sliding incides that slowly come together. Note the corner cases and edge cases.
- Josh June 02, 2017