Iuri Covalisin
BAN USERIt can be done also via data structure - ternary tree with the following properties:
1. left node must have both properties less
2. right node must have both properties greater
3. mid node doesn't meet first two criterias
4. the node height is maximum of (left.height + 1, mid.height, right.height + 1)
In case we'll build this ternary tree with weight and height properties - the root node height will be the maximum human tower height. Here's the code:
#include <iostream>
#include <vector>
/**
* Calculate maximum human tower height, where next person
* to be shorter and ligther than a person below
*/
struct TernaryNode {
size_t height{0};
size_t weight{0};
size_t maxHeight{0};
TernaryNode *left{nullptr};
TernaryNode *mid{nullptr};
TernaryNode *right{nullptr};
bool operator<(const TernaryNode &other) {
return this->height < other.height &&
this->weight < other.weight;
}
bool operator>(const TernaryNode &other) {
return this->height > other.height &&
this->weight > other.weight;
}
};
TernaryNode* buildTTree(std::vector<std::pair<size_t, size_t> > &staff,
size_t index = 0) {
TernaryNode *node = new TernaryNode();
node->height = staff[index].first;
node->weight = staff[index].second;
if(index == staff.size() - 1) {
return node;
}
TernaryNode *subNode = buildTTree(staff, index + 1);
if(*subNode < *node) {
node->left = subNode;
node->maxHeight = std::max(node->maxHeight, subNode->maxHeight + 1);
} else if(*subNode > *node) {
node->right = subNode;
node->maxHeight = std::max(node->maxHeight, subNode->maxHeight + 1);
} else {
node->mid = subNode;
node->maxHeight = std::max(node->maxHeight, subNode->maxHeight);
}
}
size_t calcMaxTowerHt(std::vector<std::pair<size_t, size_t> > &staff) {
TernaryNode *node = buildTTree(staff);
return node->maxHeight;
}
int main()
{
std::vector<std::pair<size_t, size_t> > circusStaff{{60, 230}, {50, 130}, {56, 240},
{52, 220}, {57, 200}, {53, 160},
{58, 210}, {51, 140}, {55, 180},
{59, 220}};
std::cout << calcMaxTowerHt(circusStaff);
return 0;
}
I think the key here is to improve time second time via "unlimited memory". Means interviewer tried to get better complexity second time. It's possible to achieve O(1) complexity second time if we use enourmous ammount of memory, by allocating an array with type max value size, for int that would be 0xffffffff, which is ~16GB at 32 bit machine which is impossible to address. But we have unlimited memory, so here's the code. The way to make it real is use bitset for cache, as we need only 5 bits to store bits count for 32 bit type.
size_t cache[0xffffffff] = {0};
size_t countBits(unsigned int i) {
if(i == 0) return 0;
// cache lookup in O(1)
size_t count = 0;
if(cache[i] != 0)
return cache[i];
// calculate
while(i > 0) {
i &= i - 1;
count++;
}
// and cache the result
cache[i] = count;
return count;
}
it's worth mentioning this is existing algorithm for Hamming weight problem.
- Iuri Covalisin November 08, 2013could you explain why shifting the number right is logn complexity? worst case you'll shift all bits, which is O(n)
- Iuri Covalisin November 08, 2013In the perfect case the posed problem would be resolved with a graph and searching for Hamiltonian path, which is NP-complete, so I avoided graph and did a brute-force solution: build all combinations of strings recursively and return false if it fails to build the combination at any level, here's working code:
bool validChain(std::vector<std::string*> &newChain) {
if(newChain.size() <= 1) return true;
for(int i = 1; i < newChain.size(); ++i) {
std::string *prevString = newChain[i-1];
if((*newChain[i])[0] != (*prevString)[prevString->size() - 1]) {
return false;
}
}
return true;
}
bool isChainable(std::vector<std::string*>::iterator start,
std::vector<std::string*>::iterator end,
std::vector<std::vector<std::string*>> &chains) {
if(std::distance(start, end) == 1) {
std::vector<std::string*> singleChain({*start});
chains.push_back(singleChain);
return true;
}
std::string *head = *start;
std::vector<std::vector<std::string*>> tmpChains;
if(isChainable(++start, end, tmpChains)) {
for(std::vector<std::string*> chain : tmpChains) {
for(int i = 0; i <= tmpChains.size(); ++i) {
std::vector<std::string*> newChain(chain.size() + 1);
newChain[i] = head;
std::copy(chain.begin(), chain.begin() + i, newChain.begin());
std::copy(chain.begin() + i, chain.end(), newChain.begin() + i + 1);
if(validChain(newChain)) chains.push_back(newChain);
}
}
}
return chains.size() > 0;
}
bool isChainable(std::vector<std::string*> arr) {
std::vector<std::vector<std::string*>> chains;
return isChainable(arr.begin(), arr.end(), chains);
}
int main()
{
std::string str1("abc"), str2("feg"), str3("cef");
std::cout << isChainable(std::vector<std::string*>({&str1, &str2, &str3}));
return 0;
}
@memo
you are right - this is Hamiltonian path problem, not Eulerian, because last allows same vertex to be visited twice, which is not acceptable solution.
This is NP-Complete problem and seems all combinations have to be verified in worst case.
I wonder if this problem can be converted to another, not NP-Complete so we'll have better complexity.
what if it has cycles? topological sort assumes you always find an element that has no incoming edges, and little modification of original example breaks the topological sort possibility ("S ← Set of all nodes with no incoming edges" will not do anything):
first string=sdfd
second string=dfgs
third string=dhjhs
The worst case complexity to build a ticket hashmap is O(N^2), because in the worst case hashmap degrades to a linked list.
- Iuri Covalisin November 06, 2013First create hash map having destination as a key, pass current location (trip destination), hashmap and reference to path vector.
The total complexity is O(N^2) where N is number of tickets and square time is spent while creating a hashmap, while the method itself has O(N + 1) complexity:
bool reconstructPath(std::string ¤tLoc,
std::unordered_map<std::string, std::string> &tickets,
std::vector<std::string> &path) {
path.resize(tickets.size() + 1);
path[0] = currentLoc;
for(int i = 1; i < path.size(); ++i) {
auto it = tickets.find(path[i - 1]);
if(it == tickets.end()) {
return false;
} else {
path[i] = it->second;
}
}
return true;
}
"Each ticket contains *just* the start location and the end location"
- Iuri Covalisin November 06, 2013right, memmove is O(n) while being in T(n) cycle, so overall is O(n^2).
- Iuri Covalisin November 01, 2013I can seemany people propose a table/map while that's just an alphabet and is already part of the language, just calculate the offset.
To avoid "z" trap (z to right) and down to "z" empty string you need to rotate clockwise - you'll always have max 2 directions out of 4, and never get stuck if doing that clockwise.
void printPath(std::string &word) {
assert(word.size() != 0);
std::transform(word.begin(), word.end(), word.begin(), ::tolower);
char position = 'a';
for(const char &c : word) {
assert(c >= 'a' && c <= 'z');
char diffX = ((c - 'a') % 5) - ((position - 'a') % 5);
char diffY = ((c - 'a') / 5) - ((position - 'a') / 5);
for(int i = diffX; i < 0; ++i) std::cout << "LEFT" << std::endl;
for(int i = diffY; i < 0; ++i) std::cout << "UP" << std::endl;
for(int i = 0; i < diffX; ++i) std::cout << "RIGHT" << std::endl;
for(int i = 0; i < diffY; ++i) std::cout << "DOWN" << std::endl;
std::cout << "OK" << std::endl;
position = c;
}
}
This is reservoir sampling where k == 0
int singleReservoirSampling(std::vector<int> &arr) {
int result = arr[0]; // use single var instead of array as k == 0
for(int i = 1; i < arr.size(); ++i) {
int r = std::rand() % i;
if(r == 0) { // replacing r <= k with r == 0
result = arr[i]; // probability to be set is 1 to i
}
}
return result;
}
Here's the C++ (11) solution with symbol table storing counts, it successfully validates concatenated words also:
bool validate(std::string &str) {
std::list<std::pair<std::string::value_type, int>>
symbolTable {{'h', 0}, {'i', 0}, {'r', 0}, {'e', 0}};
int strPos = 0;
auto symIt = symbolTable.begin();
auto symEnd = symbolTable.end();
auto currSym = symIt;
while(strPos <= str.size() - 1) {
if(currSym == symEnd) {
// reached sym table end, go to beginning
currSym = symIt;
} else {
if(currSym->first == str[strPos]) {
// matched symbol, inc counter
++strPos; // go to next char in the string
currSym->second++; // and increase counter
} else {
// current string char and sym table mismatch
if(currSym != symIt) {
// not 1st position in sym table
// compare current and previous counters
auto prev = currSym;
--prev;
if(currSym->second != prev->second) {
// counters at n and n - 1 not equal
return false;
}
}
// move to next position in sym table
++currSym;
}
}
}
// iterate over the map and check all counts match
int checkSum = symIt->second;
for(auto it = ++symIt; it != symEnd; ++it) {
if(checkSum != it->second) return false;
}
return true;
}
Here's the implementation, it's quite clear what has to be done - print all duplicates, so if you have 1, 1, 1, 2, 2, 3 you'd print 1, 1, 2, because 2nd and 3rd ones are duplicates of 1st one in the array. Here's the code in C++:
bool exists(std::vector<char> &duplicates, short val) {
size_t index = val / 8 + ((val % 8) ? 1 : 0);
char valByte = duplicates[index];
valByte <<= 7 - val % 8;
return valByte >> 7;
}
void put(std::vector<char> &duplicates, short val) {
size_t index = val / 8 + ((val % 8) ? 1 : 0);
char valByte = duplicates[index];
valByte |= (1 << val % 8);
duplicates[index] = valByte;
}
void printDups(std::vector<short> &array) {
std::vector<char> duplicates = {0};
duplicates.resize(4000); // 32000bit
for(auto it = array.begin(); it != array.end(); ++it) {
if(exists(duplicates, *it)) {
std::cout << *it << std::endl;
} else {
put(duplicates, *it);
}
}
}
int main()
{
std::vector<short> array = {1, 1, 2, 2, 32000, 32000, 32000, 15000, 16000, 16001, 16001};
printDups(array);
return 0;
}
@Kirk
this is iterating over every bit in a number, look you have 5 iterations for 6 bits. which is O(N), while O(lg N) would require up to 2 iterations.
This is O(n) worst case, imagine you'd have 11111110 instead of 10000101, means you'll have 8 iterations == O(n)
- Iuri Covalisin October 25, 2013
O(1) insert and O(1) history retrieve:
- Iuri Covalisin November 21, 2013