PenChief
BAN USER- 0of 0 votes
AnswersGiven K sorted (ascending) arrays. Write an iterator class that iterate over the arrays and returns the next element. Duplicate are allowed. What is the complexity to iterate the entire arrays? what is the complexity for each iteration?
Example:arr1 = {1,2,3,4,7,9} arr2 = {3,5,6,8,10}
The iterator should return:
1,2,3,3,4,5,6,7,8,9,10
Extension:
Don't return duplicates, so the above iterator should return:
- PenChief in Israel1,2,3,4,5,6,7,8,9,10
| Report Duplicate | Flag | PURGE
Facebook - 1of 1 vote
AnswersGiven a binary tree that complies to the following rule:
The parent node value is always the the result of the AND operator of its children values.
You modify one of the LEAF nodes value (e.g. if it was 1 it is now 0). Write a function that fixes the tree
so it complies with the above rule.
- PenChief in Israel// // 0 1 // / \ / \ // 1 0 =====> 1 1 // / \ / \ / \ / \ // 1 1 0 1 1 1 1 1 // // The parent node value is always children value's LOGICAL AND // & //
| Report Duplicate | Flag | PURGE
Facebook Algorithm - 0of 0 votes
AnswersGiven an array of integers, return the index of the max value in this array.
Note:
If the max value appears more than once, the function should return one the indexes, but make it so that the next call will return different index.
Important: you are not allowed to store state between calls
Example: given this input array// 0 -1 6 4 5 6 6 // | | | // 2,1/3 5,1/3 6,1/3
Function signature:
int getIndex(const std::vector<int>& numbers);
Example output:
2 5 6 5 2
Extension:
What if you knew how many times the max value appears in the array, can you improve the function performance?
So using the given example array, the function signature is now:
- PenChief in Israelint getIndex(const std::vector<int>& numbers, int maxCount);
| Report Duplicate | Flag | PURGE
Facebook Algorithm
1. If unpark was called, keep track of the parking space in priority queue where floor>length>width
2. Allocate new parking space
#include <iostream>
#include <queue>
using namespace std;
struct Location {
size_t length = -1;
size_t width = -1;
size_t floor = -1;
void Print()
{
if(IsOk()) { cout << "(" << length << ", " << width << ", " << floor << ")" << endl; }
}
bool operator>(const Location& other) const
{
// the order of comparison matters
if(this->floor > other.floor) return true;
if(this->floor < other.floor) return false;
// same floor, compare length
if(this->length > other.length) return true;
if(this->length < other.length) return false;
// same floor & length, just compare the width
return this->width > other.width;
}
bool IsOk() const { return length != string::npos; }
};
; // Min heap
class ParkingLot
{
size_t m_length = 0;
size_t m_width = 0;
size_t m_floor = 0;
size_t m_nextLen = 0;
size_t m_nextWidth = 0;
size_t m_nextFloor = 0;
bool m_isFull = false;
priority_queue<Location, vector<Location>, greater<Location>> Q;
protected:
/**
* @brief find next parking space. return false if the parking lot is full
*/
bool FindLocation(Location& loc)
{
loc = { string::npos, string::npos, string::npos };
if(!Q.empty()) {
// reuse parking spot
loc = Q.top();
Q.pop();
return true;
}
if(m_isFull) { return false; }
loc = { m_nextLen, m_nextWidth, m_nextFloor };
// Allocate new spot
if(m_nextWidth + 1 < m_width) {
// progress the width, this keeps lowest available length / floor
++m_nextWidth;
} else {
// m_nextWidth is at its max, reset it back to 0
m_nextWidth = 0;
// attempt to increase the length first, since floor has highest priority
if(m_nextLen + 1 < m_length) {
++m_nextLen;
} else {
m_nextLen = 0;
if(m_nextFloor + 1 < m_floor) {
++m_nextFloor;
} else {
// full
m_isFull = true;
return true;
}
}
}
return true;
}
public:
ParkingLot(int length, int width, int floor)
: m_length(length)
, m_width(width)
, m_floor(width)
{
}
Location Park()
{
Location loc;
if(!FindLocation(loc)) { cout << "parking lot is full" << endl; }
return loc;
}
void Unpark(size_t len, size_t width, size_t floor) { Q.push({ len, width, floor }); }
};
ParkingLot P(3, 3, 3);
void Park()
{
Location loc = P.Park();
loc.Print();
}
void Unpark(int len, int width, int floor) { P.Unpark(len, width, floor); }
We approach this problem as a topological sorting problem:
We traverse the graph checking for circular dependencies while marking all nodes visited
The traverse yields 2 results: the execution order + all the possible starting points ("sub graphs"):
#include <exception>
#include <iostream>
#include <set>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
struct Task {
typedef std::vector<Task*> Vec_t;
size_t id = 0;
size_t duration = 0;
Vec_t depends;
std::string ToString() const
{
std::stringstream ss;
ss << id;
return ss.str();
}
};
Task::Vec_t G;
#define NODE_MARKER_TEMP 1
#define NODE_MARKER_DONE 2
void Visit(Task* t, std::unordered_map<size_t, size_t>& M, Task::Vec_t& runOrder)
{
if(M.count(t->id) && M[t->id] == NODE_MARKER_TEMP) { throw std::logic_error("circular loop found"); }
if(M.count(t->id) && M[t->id] == NODE_MARKER_DONE) { return; }
// Visit the children
M[t->id] = NODE_MARKER_TEMP;
for(Task* dep : t->depends) { Visit(dep, M, runOrder); }
M[t->id] = NODE_MARKER_DONE;
// add the task to the start
runOrder.push_back(t);
}
void GetStartingPoints(Task::Vec_t& S)
{
std::unordered_map<size_t, size_t> M; // Node markers
Task::Vec_t runOrder;
size_t maxExecutionTime = 0;
for(Task* t : G) {
if(M.count(t->id)) { continue; }
runOrder.clear();
Visit(t, M, runOrder);
// print the runOrder
size_t tempMaxExecutionTime = 0;
for(Task* dep : runOrder) {
std::cout << dep->ToString();
tempMaxExecutionTime += dep->duration;
}
maxExecutionTime = std::max(tempMaxExecutionTime, maxExecutionTime);
std::cout << std::endl;
}
std::cout << "Total time needed to execute the tasks: " << maxExecutionTime << std::endl;
}
void CalcMinExecutionTime()
{
// Build some test graph
Task t1{ 1, 5 };
Task t2{ 2, 7 };
Task t3{ 3, 8 };
Task t4{ 4, 20 };
Task t5{ 5, 1 };
Task t6{ 6, 1 };
// Create dependencies
t1.depends.push_back(&t2);
t2.depends.push_back(&t3);
t4.depends.push_back(&t5);
G.push_back(&t1);
G.push_back(&t2);
G.push_back(&t3);
G.push_back(&t4);
G.push_back(&t5);
G.push_back(&t6);
// Build sub graphs
Task::Vec_t S;
try {
GetStartingPoints(S);
} catch(std::logic_error& e) {
std::cerr << e.what() << std::endl;
}
}
The above code results with:
321
54
6
Total time needed to execute the tasks: 21
This means: we have 3 starting points (i.e. three separate processes), which needs 21 time units for execution (we simply sum and keep track of the longest sequence)
- PenChief April 24, 2019There are two ways to solve this:
The first approach is naive: use hash to mark all busy points in time. Whenever we want to check if a program can be added, we simply loop over its range (start -> start + duration) and checking if any of the points is already marked in the hash. The complexity is O(k) where k is the duration. One problem (major one): if a program is set to work indefinitely , the performance is poor :)
A better approach:
use set (ordered set, insert is o(log n), then use binary search to find the first elements that starts *after* the program that we want to add starting point and check if this program or the one before it (if any) are conflicting
The complexity: is o(log n) - where n is the number programs we have in the set
#include <iostream>
#include <set>
#include <sstream>
#include <stdio.h>
using namespace std;
struct Program {
int start = -1;
int duration = -1;
int GetDuration() const { return duration; }
int GetStartTime() const { return start; }
int GetEndTime() const { return start + duration; }
bool InRange(int t, bool checkingStartTime) const
{
if(checkingStartTime) {
// t is the start time
return t >= GetStartTime() && t < GetEndTime();
} else {
// t is the end time
return t > GetStartTime() && t < GetEndTime();
}
}
bool Conflicts(const Program& p) const
{
return InRange(p.GetStartTime(),
true) || // The starting point of P is conflicting with the exeuction of this program
InRange(p.GetEndTime(), false) || // The ending point of P is conflicting with the exeuction of this program
(p.GetStartTime() <= GetStartTime() &&
p.GetEndTime() >=
GetEndTime()); // P execution time starts before this program and ends after (i.e p contains this)
}
// Required by std::set
bool operator<(const Program& p) const { return GetStartTime() < p.GetStartTime(); }
std::string ToString() const
{
std::stringstream ss;
ss << "[" << GetStartTime() << ", " << GetDuration() << "]";
return ss.str();
}
};
bool AddIfPossible(const Program& p, set<Program>& T)
{
// empty T? just add the program
if(T.empty()) {
T.insert(p);
return true;
}
// end should point to the first element that its starting time is greater than or p.GetStartTime()
auto end = T.lower_bound(p);
// No program that start after this one?
if(end == T.end()) {
// get the last element and check if it conflicts with p
auto it = T.rbegin();
if(!it->Conflicts(p)) {
T.insert(p);
return true;
} else {
cout << "Program: " << p.ToString() << " conflicts with " << it->ToString() << endl;
}
} else {
// end starts after p
auto start = T.end();
if(end != T.begin()) { start = --end; }
if(!end->Conflicts(p) && (start != T.end() && !start->Conflicts(p))) {
T.insert(p);
return true;
} else if(end->Conflicts(p)) {
cout << "Program: " << p.ToString() << " conflicts with " << end->ToString() << endl;
} else if(start != T.end()) {
cout << "Program: " << p.ToString() << " conflicts with " << start->ToString() << endl;
}
}
return false;
}
int main(int argc, char** argv)
{
Program P1{ 10, 5 };
Program P2{ 25, 15 };
Program P3{ 18, 7 };
Program P4{ 12, 10 };
Program P5{ 28, 2 };
set<Program> T;
AddIfPossible(P1, T);
AddIfPossible(P2, T);
AddIfPossible(P3, T);
AddIfPossible(P4, T);
AddIfPossible(P5, T);
return 0;
}
I would use
std::lower_bound
and
std::upper_bound
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
void search_closest_number(const std::vector<int>& numbers, int search_number)
{
if(numbers.empty()) {
return;
}
std::vector<int>::const_iterator lower_iter = std::lower_bound(numbers.begin(), numbers.end(), search_number);
std::vector<int>::const_iterator upper_iter = std::upper_bound(numbers.begin(), numbers.end(), search_number);
if(upper_iter != numbers.end() && lower_iter != numbers.end()) {
int diffUpper = abs(search_number - (*upper_iter));
if(lower_iter != numbers.begin()) {
lower_iter--;
}
int diffLower = abs(search_number - (*lower_iter));
std::cout << ((diffUpper < diffLower) ? (*upper_iter) : (*lower_iter)) << std::endl;
} else if(upper_iter == numbers.end() && lower_iter != numbers.end()) {
std::cout << *lower_iter << std::endl;
} else if(lower_iter == numbers.end() && upper_iter != numbers.end()) {
std::cout << *upper_iter << std::endl;
} else {
std::cout << numbers.back() << std::endl;
}
}
int main(int argc, char** argv)
{
std::vector<int> numbers = { 4, 5, 5, 8, 8, 9 };
search_closest_number(numbers, 4); // 4
search_closest_number(numbers, 5); // 5
search_closest_number(numbers, 11); // 9
search_closest_number(numbers, 6); // 5
search_closest_number(numbers, 1); // 4
return 0;
}
Using a custom Trie like tree (not really a trie, since a single node can hold multiple words - this is because of the sorting)
As @ChrisK pointed out, sorting the input and the dictionary is the way to go:
My solution is basically @ChrisK solution that actually compiles :)
* The trie here is case-insensitive
* Only A-Z words are allowed
#include "CommonHeader.h"
static inline int char_to_num(char ch) { return ch - 'a'; }
class Trie
{
Trie* m_children[26];
std::unordered_set<std::string> m_words;
private:
/**
* @brief find a node for a given char, create it if it does not exist
* this function is used by "insertSorted" method
*/
Trie* getOrCreateNode(char ch)
{
int offset = char_to_num(ch);
if(m_children[offset] == nullptr) {
m_children[offset] = new Trie();
}
return m_children[offset];
}
public:
/**
* @brief find node for a given char, return null if it does not exist
*/
inline Trie* findNode(char ch) { return m_children[char_to_num(ch)]; }
public:
Trie() { memset(m_children, 0, sizeof(m_children)); }
virtual ~Trie() {}
/**
* @brief get all words for this node (there can be multiple words)
*/
void getWords(std::unordered_set<std::string>& words) const
{
if(!m_words.empty()) {
words.insert(m_words.begin(), m_words.end());
}
}
/**
* @brief add word to the trie
*/
void insertSorted(const std::string& word)
{
std::string sortedWord = word;
std::transform(sortedWord.begin(), sortedWord.end(), sortedWord.begin(), ::tolower);
std::sort(sortedWord.begin(), sortedWord.end());
Trie* node = this;
for(size_t i = 0; i < sortedWord.size(); ++i) {
char ch = sortedWord[i];
node = node->getOrCreateNode(ch);
}
// but we store the original word (unsorted)
node->m_words.insert(word);
}
};
void findInDictionary()
{
Trie trie;
trie.insertSorted("a");
trie.insertSorted("car");
trie.insertSorted("aca");
trie.insertSorted("art");
trie.insertSorted("rac");
trie.insertSorted("rac");
trie.insertSorted("tr");
trie.insertSorted("bar");
trie.insertSorted("aaa");
// Sort the result
std::string filter = "acrat";
std::sort(filter.begin(), filter.end()); // aacrt
std::unordered_set<std::string> words; // the result
std::queue<std::pair<Trie*, std::string> > q;
q.push({ &trie, filter });
while(!q.empty()) {
std::string w = q.front().second;
Trie* t = q.front().first;
q.pop();
t->getWords(words);
while(t && !w.empty()) {
Trie* child = t->findNode(w[0]);
w.erase(w.begin());
if(child) {
q.push({ child, w });
}
}
}
std::for_each(words.begin(), words.end(), [&](const std::string& w){
std::cout << w << std::endl;
});
}
Assumptions:
* I am using integer arithmetic here (6/10=0)
* No multiplication precedence
* The order of the numbers is fixed. only the operators are changing
#include "CommonHeader.h"
typedef std::tuple<int, std::vector<int>, std::string> QueueElement;
bool isEqual42(std::vector<int> numbers)
{
if(numbers.size() != 5) return false;
std::queue<QueueElement> q;
int num = numbers[0];
numbers.erase(numbers.begin());
q.push(std::make_tuple(num, numbers, std::to_string(num)));
while(!q.empty()) {
QueueElement e = q.front();
q.pop();
int currentValue = std::get<0>(e);
std::vector<int> currentNumbers = std::get<1>(e);
std::string strOperation = std::get<2>(e);
if(currentNumbers.empty() && (currentValue == 42)) {
std::cout << "42=" << strOperation << std::endl;
return true;
} else if(currentNumbers.empty()) {
continue;
}
num = currentNumbers[0];
currentNumbers.erase(currentNumbers.begin());
q.push(std::make_tuple(currentValue + num, currentNumbers, strOperation + "+" + std::to_string(num)));
q.push(std::make_tuple(currentValue * num, currentNumbers, strOperation + "*" + std::to_string(num)));
if(num > 0) {
// division by zero
q.push(std::make_tuple(currentValue / num, currentNumbers, strOperation + "/" + std::to_string(num)));
}
q.push(std::make_tuple(currentValue - num, currentNumbers, strOperation + "-" + std::to_string(num)));
}
return false;
}
void checkIfEqual42(std::vector<int> numbers)
{
if(numbers.size() != 52) {
return;
}
// Pick 5 unique numbers
std::vector<int> fiveNumbers;
for(size_t i = 0; i < 5; ++i) {
int index = (rand() % numbers.size());
fiveNumbers.push_back(numbers[index]);
numbers.erase(numbers.begin() + index);
}
isEqual42(fiveNumbers);
}
We maintain 2 hashes:
* First hash keep track of voters - this is to check for fraud
* Second hash: candidate->voters-count - we keep track of the number of votes for each candidate
In addition we use a class that keep maps between: votes=>hash of candidates
Every time we add a vote, we go and update this class
The below solution is a bit complicated because it assumes that the number of candidates can be the same as the number of voters...
If we could assume that the number of candidates is small we could simply sort the candidates array at the end (using priority_queue where the "voters-count" is the priority) and just pop the first top 5 from the queue:
Complex code, assuming number of candidates can be the same as the number of voters:
#include "CommonHeader.h"
#define TOP_LIST_MAX 5
// Unique hash to remember voters ID - insert/find O(1)
static std::unordered_set<int> VotersHash;
// Hash table to keep track for each candidate voters count
static std::unordered_map<int, int> Candidates;
struct TopCandidates {
// voters:{candidate-hash}
// We use "map" here because it uses BST (balanced) so the key is always sorted in ascending order
std::map<int, std::unordered_set<int> > _topVotes;
// Candidates in the top 5 list. There can be more than 5, since some candidates might get the same number of votes
std::unordered_set<int> _candidates;
/**
* @brief try to add candidate to the top 5 list
*/
void addCandidate(int candidateID, int voters)
{
if(_candidates.count(candidateID)) {
// already in the top 5.
// Move it from _topVotes[voters-1] -> _topVoters[voters]
_topVotes[voters - 1].erase(candidateID);
if(_topVotes[voters - 1].empty()) {
_topVotes.erase(voters - 1);
}
_topVotes[voters].insert(candidateID);
// If the top-5-list exceeds the maximum entries (i.e. 5)
// remove the entry with the least votes (and since we use std::map
// we know it's the first entry _topVotes.begin() )
if(_topVotes.size() > TOP_LIST_MAX) {
_topVotes.erase(_topVotes.begin());
}
} else if(_candidates.empty()) {
// No entries in list, just add it
_topVotes[voters].insert(candidateID);
_candidates.insert(candidateID);
} else {
// first time we see this candidate. this means that "voters" is 1
int minVotersInTheMap = _topVotes.begin()->first;
if((minVotersInTheMap == 1) || _topVotes.size() < TOP_LIST_MAX) {
_topVotes[voters].insert(candidateID);
_candidates.insert(candidateID);
}
}
}
void print()
{
std::for_each(
_topVotes.rbegin(), _topVotes.rend(), [&](const std::map<int, std::unordered_set<int> >::value_type& vt) {
const std::unordered_set<int>& candidates = vt.second;
std::cout << "Votes: " << vt.first << ", Candidates:";
std::for_each(
candidates.begin(), candidates.end(), [&](int candidateID) { std::cout << " " << candidateID; });
std::cout << std::endl;
});
}
};
static TopCandidates topCandidates;
bool addVote(int candidateID, int voterID)
{
if(VotersHash.count(voterID)) {
std::cout << "Voter ID: " << voterID << " already voted !! Fraud detected!!" << std::endl;
return false;
}
VotersHash.insert(voterID);
if(Candidates.count(candidateID) == 0) {
// first time
Candidates.insert(std::make_pair(candidateID, 0));
}
int& voters = Candidates[candidateID];
++voters;
topCandidates.addCandidate(candidateID, voters);
return true;
}
If we can assume that the number of candidates is small, we can remove the class TopCandidates class and use priority queue:
std::priority_queue<std::pair<int, int> > Q;
std::for_each(Candidates.begin(), Candidates.end(), [&](const std::pair<int, int>& p) {
// "p" contains: candidate-id:voter
// we want to to add the queue voters:candidate-id
std::pair<int, int> qentry = p;
std::swap(qentry.first, qentry.second);
Q.push(qentry);
});
size_t i = 0;
int prevVoters = INT_MAX;
while(!Q.empty() && i < TOP_LIST_MAX) {
const std::pair<int, int>& qentry = Q.top();
if(prevVoters != qentry.first) {
prevVoters = qentry.first;
++i;
}
std::cout << "#" << i << " candidate-id: " << qentry.second << " with " << qentry.first << " votes"
<< std::endl;
Q.pop();
}
The fastest solution: O(N).
Loop the array and keep each number visited in an hash table. For each number in the array check the hash if we have in the hash sum-currentnumber, if we do, we are done.
std::pair<int, int> findNumbersSumEqual(const std::vector<int>& numbers, int sum)
{
std::unordered_set<int> visited;
for(size_t i=0; i<numbers.size(); ++i) {
// search the diff in the map
int secondNumber = sum - numbers[i];
if(visited.count(secondNumber)) {
// we already saw this number before in the array
return {numbers[i], secondNumber};
} else {
// Keep this number in the hash
visited.insert(numbers[i]);
}
}
return {INT_MAX,INT_MAX}; // No match was found
}
The trick here is to find the prefix, the prefix requires a loop: we divide the number by 10 until we hit a single digit result - this is our prefix. The suffix is a simple modulo by 10.
We do some optimizations so won't be calculating the prefix until we actually met all the other conditions:
// Stub (given function)
bool isPrime(int number) { return true; }
bool isSuperPrime(int number)
{
if(!isPrime(number)) return false;
if(number < 10) return true; // Single digit number, no need to test further
// Get the suffix (its faster without loop required)
if(!isPrime(number % 10)) return false;
// so far, we have met both conditions, suffix and prime
// time to get the prefix
int prefix = (number / 10);
while(prefix > 9) {
prefix /= 10;
}
return isPrime(prefix);
}
We use BFS to scan the tree. We only need to keep track of the following:
- Current level being scanned
- Current level sum so far
- Min level found so far
- Min sum found so far
This solution has O(N) complexity with minimum space
#include "CommonHeader.h"
struct Node {
int value;
std::vector<Node*> children;
Node(int v, Node* parent = nullptr)
: value(v)
{
if(parent) {
parent->children.push_back(this);
}
}
};
std::pair<int, int> getMinSumLevel(Node* root)
{
std::queue<std::pair<Node*, int> > q; // node:level
q.push({ root, 1 });
int curlevel = 1;
int minLevel = 1;
int minSumSoFar = INT_MAX;
int curlevelSum = 0;
while(!q.empty()) {
Node* n = q.front().first;
int level = q.front().second;
q.pop();
if(curlevel != level) {
// we completed this level
if(curlevelSum < minSumSoFar) {
minSumSoFar = curlevelSum;
minLevel = curlevel;
}
curlevel = level;
curlevelSum = 0;
}
curlevelSum += n->value;
std::for_each(n->children.begin(), n->children.end(), [&](Node* child) { q.push({ child, curlevel + 1 }); });
}
return { minLevel, minSumSoFar };
}
void test_min_level_sum()
{
Node n01(50);
Node n11(6, &n01), n12(2, &n01);
Node n21(30, &n11), n22(80, &n11), n23(7, &n12);
std::pair<int, int> res = getMinSumLevel(&n01);
std::cout << "Level is: " << res.first << ", Sum: " << res.second << std::endl;
}
@ChrisK I fixed my code with the following logic: instead of moving one element at a time, I "merge" two intervals if they are adjacent so the comparison is done on two intervals: {0,13} and {2,12}
Here is the updated code:
class Interval2
{
public:
int start;
int end;
Interval2()
: start(0)
, end(0)
{
}
Interval2(const std::pair<int, int>& p)
: start(p.first)
, end(p.second)
{
}
/**
* @brief return true if merge took place
*/
bool mergeIfAdjacent(const Interval2& other)
{
if(isAdjacent(other)) {
this->end = other.end;
return true;
}
return false;
}
/**
* @brief adjacent means that this interval ends exactly where the "other" interval starts
*/
bool isAdjacent(const Interval2& other) const { return (this->end + 1) == other.start; }
bool intersects(const Interval2& other) const
{
return (other.start > start && other.start < end) || (other.end > start && other.end < end);
}
static Interval2 createIntersection(const Interval2& a, const Interval2& b)
{
Interval2 i;
i.start = std::max(a.start, b.start);
i.end = std::min(a.end, b.end);
return i;
}
std::string toString() const { return "(" + std::to_string(start) + "," + std::to_string(end) + ")"; }
};
void mergeAndIntervals(const std::vector<std::pair<int, int> >& v1, const std::vector<std::pair<int, int> >& v2)
{
// v1 and v2 are sorted
std::vector<Interval2> andV;
std::vector<std::pair<int, int> >::const_iterator iter1 = v1.begin();
std::vector<std::pair<int, int> >::const_iterator iter2 = v2.begin();
while((iter1 != v1.end()) && (iter2 != v2.end())) {
Interval2 interval1 = *iter1;
while((iter1 + 1) != v1.end() && interval1.mergeIfAdjacent(*(iter1 + 1))) {
++iter1;
}
Interval2 interval2 = *iter2;
while((iter2 + 1) != v2.end() && interval2.mergeIfAdjacent(*(iter2 + 1))) {
++iter2;
}
if(interval1.intersects(interval2)) {
andV.push_back(Interval2::createIntersection(interval1, interval2));
}
// Advance the lowest interval
(interval1.start < interval2.start) ? ++iter1 : ++iter2;
}
// Print the merged result
std::cout << "Intersections:" << std::endl;
std::for_each(
andV.begin(), andV.end(), [&](const Interval2& interval) { std::cout << interval.toString() << std::endl; });
std::cout << "Intersections___END:" << std::endl;
}
@xyz, he might be a Facebook employee? (maybe from HR...). Just a thought :)
Now, about the question:
- Create a class named Interval
- Since the lists are sorted, we can start the beginning of each list.
** If we find an intersection, we add the result vector the intersection and advance both lists
** If no intersection is found, we advance the iterator of the *lower* interval (i.e. the one with the lowest "start" point)
The worst case complexity is O(N+M) (where N and M is the number of elements in the arrays)
Here is the C++ implementation:
class Interval2
{
public:
int start;
int end;
Interval2()
: start(0)
, end(0)
{
}
Interval2(const std::pair<int, int>& p)
: start(p.first)
, end(p.second)
{
}
bool intersects(const Interval2& other) const
{
return (other.start > start && other.start < end) || (other.end > start && other.end < end);
}
static Interval2 createIntersection(const Interval2& a, const Interval2& b)
{
Interval2 i;
i.start = std::max(a.start, b.start);
i.end = std::min(a.end, b.end);
return i;
}
std::string toString() const { return "(" + std::to_string(start) + "," + std::to_string(end) + ")"; }
};
void mergeAndIntervals(const std::vector<std::pair<int, int> >& v1, const std::vector<std::pair<int, int> >& v2)
{
// v1 and v2 are sorted
std::vector<Interval2> andV;
std::vector<std::pair<int, int> >::const_iterator iter1 = v1.begin();
std::vector<std::pair<int, int> >::const_iterator iter2 = v2.begin();
while((iter1 != v1.end()) && (iter2 != v2.end())) {
const Interval2& interval1 = *iter1;
const Interval2& interval2 = *iter2;
if(interval1.intersects(interval2)) {
andV.push_back(Interval2::createIntersection(interval1, interval2));
++iter1;
++iter2;
} else {
// Advance the lowest interval
(interval1.start < interval2.start) ? ++iter1 : ++iter2;
}
}
// Print the merged result
std::for_each(
andV.begin(), andV.end(), [&](const Interval2& interval) { std::cout << interval.toString() << std::endl; });
}
Use sliding window with the size of the anagram on the input string
then compare each substring using characters counting.
#include "CommonHeader.h"
class Anagram
{
int chars[256];
size_t length = 0;
public:
Anagram(const std::string& str)
{
memset(chars, 0, sizeof(chars));
length = str.size();
for(size_t i = 0; i < str.size(); ++i) {
chars[(int)str[i]]++;
}
}
/**
* @brief check if this represents an anagram of the string represented between start and end iterators
* This function assumes that the string represented between start-end has the same legnth as the string
* created this object
*/
bool isAnagram(std::string::const_iterator start, std::string::const_iterator end) const
{
int tmp_chars[256];
memcpy(tmp_chars, chars, sizeof(chars));
while(start != end) {
int index = (int)(*start);
tmp_chars[index]--;
if(tmp_chars[index] < 0) {
return false;
}
++start;
}
return true;
}
/**
* @brief check if str contains an anagram of this object, we do this by using a sliding window
*/
bool isSubAnagramOf(const std::string& str) const
{
if(str.size() < length) return false;
// Use sliding window to check for anagram
std::string::const_iterator start;
std::string::const_iterator end;
for(size_t i = 0; i <= (str.size() - length); ++i) {
start = str.begin() + i;
end = str.begin() + i + length;
if(isAnagram(start, end)) {
return true;
}
}
return false;
}
};
bool is_sub_anagram(const std::string& sanag, const std::string& strfull)
{
Anagram ang(sanag);
return ang.isSubAnagramOf(strfull);
}
@ChrisK I guess that this approach would work if the intervals are small. Given the following example:
v1 = {1,1000},{1100,2000}
v2 = {600,900},{10,000-50,000}
I would rather compare each element in v1 against elements in v2 (O(2^2))
So your solution should be considered for small intervals only
Here is the full code (forgot to copy it entirely...):
#include "CommonHeader.h"
class Interval
{
public:
int start;
int end;
Interval()
: start(0)
, end(0)
{
}
Interval(const std::pair<int, int>& p)
: start(p.first)
, end(p.second)
{
}
bool contains(const Interval& other) const
{
return (other.start >= start && other.start <= end) || (other.end >= start && other.end <= end);
}
void merge(const Interval& other)
{
start = std::min(start, other.start);
end = std::max(end, other.end);
}
int range() const { return end - start; }
bool operator>(const Interval& other) const
{
if(start > other.start) return true;
if(start < other.start) return false;
return range() > other.range();
}
std::string toString() const { return "(" + std::to_string(start) + "," + std::to_string(end) + ")"; }
};
void mergeOrIntervals(const std::vector<std::pair<int, int> >& v1, const std::vector<std::pair<int, int> >& v2)
{
std::priority_queue<Interval, std::vector<Interval>, std::greater<Interval> > q;
std::for_each(v1.begin(), v1.end(), [&](const std::pair<int, int>& p) {
Interval interval(p);
q.push(interval);
});
std::for_each(v2.begin(), v2.end(), [&](const std::pair<int, int>& p) {
Interval interval(p);
q.push(interval);
});
std::vector<Interval> orV;
while(!q.empty()) {
const Interval& interval = q.top();
if(orV.empty()) {
orV.push_back(interval);
} else {
Interval& lastInterval = orV.back();
if(lastInterval.contains(interval)) {
lastInterval.merge(interval);
} else {
orV.push_back(interval);
}
}
q.pop();
}
// Print the merged result
std::for_each(
orV.begin(), orV.end(), [&](const Interval& interval) { std::cout << interval.toString() << std::endl; });
}
use min-heap to store all the intervals from both ranges N(logN) + M(logM)
Next we loop over all elements in the queue.
We sort the intervals by the starting position and the range size (end-start).
The loop is Nlog(N)
Here is the "OR" function:
void mergeOrIntervals(const std::vector<std::pair<int, int> >& v1, const std::vector<std::pair<int, int> >& v2)
{
std::priority_queue<Interval, std::vector<Interval>, std::greater<Interval> > q;
std::for_each(v1.begin(), v1.end(), [&](const std::pair<int, int>& p) {
Interval interval(p);
q.push(interval);
});
std::for_each(v2.begin(), v2.end(), [&](const std::pair<int, int>& p) {
Interval interval(p);
q.push(interval);
});
std::vector<Interval> orV;
while(!q.empty()) {
const Interval& interval = q.top();
if(orV.empty()) {
orV.push_back(interval);
} else {
Interval& lastInterval = orV.back();
if(lastInterval.contains(interval)) {
lastInterval.merge(interval);
} else {
orV.push_back(interval);
}
}
q.pop();
}
// Print the merged result
std::for_each(
orV.begin(), orV.end(), [&](const Interval& interval) { std::cout << interval.toString() << std::endl; });
}
Pretty straight forward. The only thing to remember here is that when using "stack" we should push the "right" node before we push the "left" node (stack is FILO)
#include "CommonHeader.h"
class TreeNodeR
{
public:
TreeNodeR* left = nullptr;
TreeNodeR* right = nullptr;
int value = 0;
TreeNodeR() {}
TreeNodeR(int v)
: value(v)
{
}
};
static void doLevelOrderBottomRecurse(TreeNodeR* node, size_t depth, std::vector<std::vector<size_t> >& res)
{
if(res.size() < (depth + 1)) {
res.push_back({});
}
res[depth].push_back(node->value);
if(node->left) {
doLevelOrderBottomRecurse(node->left, depth + 1, res);
}
if(node->right) {
doLevelOrderBottomRecurse(node->right, depth + 1, res);
}
}
std::vector<std::vector<size_t> > levelOrderBottomRecurse(TreeNodeR* root)
{
std::vector<std::vector<size_t> > res;
doLevelOrderBottomRecurse(root, 0, res);
std::reverse(res.begin(), res.end());
return res;
}
std::vector<std::vector<size_t> > levelOrderBottomStack(TreeNodeR* root)
{
std::vector<std::vector<size_t> > res;
std::stack<std::pair<TreeNodeR*, size_t> > s;
s.push({ root, 0 });
while(!s.empty()) {
std::pair<TreeNodeR*, size_t> p = s.top();
s.pop();
size_t depth = p.second;
TreeNodeR* node = p.first;
if(res.size() < (depth + 1)) {
res.push_back({});
}
res[depth].push_back(node->value);
// Since we are using "stack", we need to push the "right" element first
// stack is FILO
if(node->right) {
s.push({ node->right, depth + 1 });
}
if(node->left) {
s.push({ node->left, depth + 1 });
}
}
std::reverse(res.begin(), res.end());
return res;
}
static void print_result(const std::vector<std::vector<size_t> >& res)
{
std::for_each(res.begin(), res.end(), [&](const std::vector<size_t>& v) {
std::for_each(v.begin(), v.end(), [&](size_t v) { std::cout << " " << v; });
std::cout << std::endl;
});
}
// Test
void printReverseOrderTree()
{
std::unordered_map<int, TreeNodeR> G;
G[3] = TreeNodeR(3);
G[9] = TreeNodeR(9);
G[20] = TreeNodeR(20);
G[15] = TreeNodeR(15);
G[7] = TreeNodeR(7);
G[3].left = &G[9];
G[3].right = &G[20];
G[20].left = &G[15];
G[20].right = &G[7];
std::vector<std::vector<size_t> > res1 = levelOrderBottomRecurse(&G[3]);
print_result(res1);
std::vector<std::vector<size_t> > res2 = levelOrderBottomStack(&G[3]);
print_result(res2);
}
We could use a hash to remember the sums of the elements we visited so far:
void findTriplet(std::vector<int>& numbers)
{
std::sort(numbers.begin(), numbers.end()); // O(NlogN)
std::unordered_map<int, std::pair<int, int>> Sums; // Keep track of the sums we visited so far
for(size_t i = 0; i < numbers.size(); ++i) {
if(Sums.count(numbers[i])) {
// We already found a pair that matches this sum
std::cout << numbers[i] << "=" << Sums[numbers[i]].first << "+" << Sums[numbers[i]].second << std::endl;
break;
} else {
for(size_t j = 0; j < i; ++j) {
Sums[numbers[j] + numbers[i]] = { numbers[i], numbers[j] };
}
}
}
}
EDIT: updated the solution to support cases such as [7,4,3]
- PenChief October 02, 2017We use BFS to traverse the tree while keeping track on each child's parent
The same can be coded using recursion. As the question stated: this method fixes only one broken node (it can be adjusted to continue and scan for more double links):
#include "CommonHeader.h"
class BSTNode
{
public:
std::string label;
std::vector<BSTNode*> children;
BSTNode(const std::string& n)
: label(n)
{
}
BSTNode() {}
};
static std::unordered_map<std::string, BSTNode> G;
// Our test tree
// (a)
// / \
// / \
// (b) (c)
// | /
// | /
// (d)
BSTNode* makeTestTree()
{
G["a"] = BSTNode("a");
G["b"] = BSTNode("b");
G["c"] = BSTNode("c");
G["d"] = BSTNode("d");
G["a"].children.push_back(&G["b"]);
G["a"].children.push_back(&G["c"]);
G["c"].children.push_back(&G["d"]); // double parent
G["b"].children.push_back(&G["d"]); // double parent
return &G["a"];
}
void fixDoubleParentNode()
{
BSTNode* bst = makeTestTree();
// Keep track of the parents
std::unordered_map<BSTNode*, BSTNode*> Parents;
// Use BFS with Queue (we can apply the same logic with recursion)
std::queue<BSTNode*> q;
q.push(bst);
Parents[bst] = nullptr;
while(!q.empty()) {
BSTNode* node = q.front();
q.pop();
for(size_t i = 0; i < node->children.size(); ++i) {
BSTNode* child = node->children[i];
if(Parents.count(child)) {
// already visited this child
node->children.erase(node->children.begin() + i);
std::cout << "Found duplicate parenting for node: " << child->label
<< " faulty parent: " << node->label << " is removed" << std::endl;
return;
} else {
Parents[child] = node;
q.push(child);
}
}
}
}
@Alex I took your code and improved it a bit. I added a "m_totalChars" counter to Hash class. There is no need to "operator==" - you simply check if "m_totalChars" is equal to 0
So the logic for "ContainsAnagram" is now like this:
* Construct a Hash class for the substring
* Loop over the second string, for each char call sub_s_hash.RemoveChar (which reduces the total counter by 1)
* We return sub_s_hash.isEmpty() if its true this means its an anagram
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
class Hash
{
private:
std::vector<int> m_charCounts;
size_t m_totalChars;
private:
void AddChar(char c)
{
++m_charCounts[c];
++m_totalChars;
}
public:
Hash(const std::string& str)
: m_totalChars(0)
{
m_charCounts.resize(256, 0);
std::for_each(str.begin(), str.end(), [&](char ch) { AddChar(ch); });
}
void RemoveChar(char c)
{
if(m_totalChars == 0) return;
if(m_charCounts[c]) {
--m_charCounts[c];
--m_totalChars;
}
}
bool isEmpty() const { return m_totalChars == 0; }
};
bool ContainsAnagram(const std::string& s, const std::string& sub_s)
{
if(sub_s.empty()) return false;
if(sub_s.size() > s.size()) return false;
Hash h(sub_s);
for(size_t i = 0; i < s.size(); ++i) {
h.RemoveChar(s[i]);
if(h.isEmpty()) break;
}
// If we "consumed" all the characters from the string itself, than "sub_s is" contained in "s"
return h.isEmpty();
}
int AnagramCasesCount(const std::vector<std::string>& strings)
{
int count = 0;
for(size_t i = 0; i + 1 < strings.size(); ++i) {
if(ContainsAnagram(strings[i + 1], strings[i])) {
++count;
}
}
return count;
}
int main()
{
std::cout << AnagramCasesCount({ "ab", "ab", "abc", "bca" }) << std::endl;
std::cout << AnagramCasesCount({ "ab", "aqb" }) << std::endl;
return 0;
}
I believe that this is the fastest solution using "binary" counter to get all subsets. No recursion is needed, no duplicates
#include "CommonHeader.h"
typedef std::vector<int> IntVec_t;
#define CHECK_BIT(var, pos) (var & (1 << pos))
std::vector<IntVec_t> findSubsets(const IntVec_t& numbers, int target)
{
// Number of subsets is 2^N where N is the number of elements (including empty set)
// we look at the problem as binary counter, for example:
// { 1, 3, 4, 5, 6, 15 }
// 0 0 0 0 0 1 (1 dec) {15}
// 0 0 0 0 1 0 (2 dec) {6}
// 0 0 0 0 1 1 (3 dec) {6, 15}
// ...
std::vector<IntVec_t> result;
int noSets = pow(2, numbers.size());
for(int i = 0; i < noSets; ++i) {
int sum = 0;
IntVec_t subset;
for(size_t j = 0; j < numbers.size(); ++j) {
if(CHECK_BIT(i, j)) {
sum += numbers[j];
subset.push_back(numbers[j]);
}
}
if(sum == target) {
result.push_back(subset);
}
}
return result;
}
I recursively create subgroups of the initial int array and sum their values.
* If the value is greater than the target value - we keep on recursing
* If the value is less than the target value, we stop the current recursion branch
* In order to avoid duplicates, we keep a set of all the visited subgroups (we do this by creating a unique string key out of the current int array and keep track of it in a hash table)
* This code can be coded without recursion (use queue instead)
* One thing that can be done better here: instead of using a string, use some kind of function to generate unique ID per int array
I have come up with the following code
#include "CommonHeader.h"
static std::unordered_set<std::string> V;
static std::string makeKeyFromVector(const std::vector<int>& numbers)
{
std::string k;
std::for_each(numbers.begin(), numbers.end(), [&](int n) { k += std::to_string(n); });
return k;
}
static void findSubgroupsForTargetInternal(
const std::vector<int>& numbers, int target, std::vector<std::vector<int> >& result)
{
// If we already visited this branch, skip it
std::string k = makeKeyFromVector(numbers);
if(V.count(k)) return;
V.insert(k);
int sum = 0;
std::for_each(numbers.begin(), numbers.end(), [&](int n) { sum += n; });
if(sum == target) {
// An exact match - add it to the result vector and return
result.push_back(numbers);
return;
} else if(sum < target) {
// No need to continue
return;
}
// The result is gt than the target, try removing one element and try again
std::vector<int> nextSetOfNumbers = numbers;
for(size_t i = 0; i < nextSetOfNumbers.size(); ++i) {
int numberToRemove = nextSetOfNumbers[i];
nextSetOfNumbers.erase(nextSetOfNumbers.begin() + i);
findSubgroupsForTargetInternal(nextSetOfNumbers, target, result);
nextSetOfNumbers.insert(nextSetOfNumbers.begin() + i, numberToRemove);
}
}
std::vector<std::vector<int> > findSubgroupsForTarget(const std::vector<int>& numbers, int target)
{
std::vector<std::vector<int> > result;
findSubgroupsForTargetInternal(numbers, target, result);
return result;
}
@ChrisK Yes, I am aware that my initial code was wrong, I deleted as soon I posted it (this site does not delete it immediately, this is why you were able to view it)
Here is a working solution that also print the groups found in a more human readable form which uses queue:
int countDecodingOptions(const std::vector<int>& numbers)
{
// The result
int options = 0;
// For visualization, we also keep track of the prefix this is why I use here std::pair
std::queue<std::pair<std::vector<int>, std::string> > q;
q.push(std::make_pair(numbers, ""));
while(!q.empty()) {
std::pair<std::vector<int>, std::string> e = q.front();
std::vector<int> v = e.first;
std::string prefix = e.second;
q.pop();
if(v.empty()) {
// All numbers processed successfully, increase the options counter and print the group found
++options;
std::cout << prefix << std::endl;
continue;
}
int n0 = v[0];
if(n0 != 0) {
// Single digit branch
v.erase(v.begin());
q.push(std::make_pair(v, prefix + std::to_string(n0) + " "));
if(!v.empty()) {
int n1 = v[0];
int tmp = (n0 * 10 + n1);
if(tmp < 27) {
// Two digit branch
v.erase(v.begin());
q.push(std::make_pair(v, prefix + std::to_string(tmp) + " "));
}
}
}
}
return options;
}
Example execution:
countDecodingOptions({ 1, 2, 2, 1 });
12 21
1 2 21
1 22 1
12 2 1
1 2 2 1
countDecodingOptions({ 2, 1, 1, 1 });
21 11
2 1 11
2 11 1
21 1 1
2 1 1 1
Here is a better solution that still uses O((M+N)/2) complexity but with minimal space:
#include "CommonHeader.h"
double findMedian(const std::vector<int>& arr1, const std::vector<int>& arr2)
{
// Sanity
size_t arr1Index = 0;
size_t arr2Index = 0;
size_t maxMergedSize = arr1.size() + arr2.size();
bool isOdd = ((maxMergedSize % 2) != 0);
// We need to merge both arrays and return the median
// Incase the merged array size is odd we need to merge halfway and return the last element in the merged array
// otherwise, we return the avg of the two last elements of the merged array
size_t minMergedSize = isOdd ? (maxMergedSize / 2) : ((maxMergedSize / 2) + 1);
size_t elementsToKeep = isOdd ? 1 : 2;
size_t counter = 0;
// We use queue to keep the values of the last 2 elements (or 1, depends on the total number of numbers of both arrays)
std::queue<int> q;
while(true) {
int a = arr1[arr1Index];
int b = arr2[arr2Index];
if(a < b) {
q.push(a);
if(q.size() > elementsToKeep) q.pop();
arr1Index++;
} else {
q.push(b);
if(q.size() > elementsToKeep) q.pop();
arr2Index++;
}
++counter;
if(counter == minMergedSize) break;
}
if(isOdd) {
// return the last number in the array
return (double) q.front();
} else {
// we cast to double to allow decimal points
double a = q.front(); q.pop();
double b = q.front(); q.pop();
return (a + b) / 2.0;
}
}
Merge both arrays and return the median.
However, we don't need to fully merge the arrays only O((M+N)/2) where M and N are the array sizes.
#include "Common.h"
double findMedian(const std::vector<int>& arr1, const std::vector<int>& arr2)
{
size_t arr1Index = 0;
size_t arr2Index = 0;
size_t maxMergedSize = arr1.size() + arr2.size();
bool isOdd = ((maxMergedSize % 2) != 0);
// We need to merge both arrays and return the median
// Incase the merged array size is odd we need to merge halfway and return the last element in the merged array
// otherwise, we return the avg of the two last elements of the merged array
size_t minMergedSize = isOdd ? (maxMergedSize / 2) : ((maxMergedSize / 2) + 1);
std::vector<int> mergedArray;
while(true) {
int a = arr1[arr1Index];
int b = arr2[arr2Index];
if(a < b) {
mergedArray.push_back(a);
arr1Index++;
} else {
mergedArray.push_back(b);
arr2Index++;
}
if(mergedArray.size() == minMergedSize) break;
}
if(isOdd) {
// return the last number in the array
return (double)mergedArray[mergedArray.size() - 1];
} else {
// we cast to double to allow decimal points
return (double)(mergedArray[mergedArray.size() - 1] + mergedArray[mergedArray.size() - 2]) / 2.0;
}
}
O(N) solution:
#include "CommonHeader.h"
// O(N) solution
bool isSubstring(const std::string& str, const std::string& sub)
{
std::string tmpSub = sub;
size_t i = 0;
while(!tmpSub.empty()) {
char ch = tmpSub.front();
for(; i < str.length(); ++i) {
if(str[i] == ch) {
tmpSub.erase(tmpSub.begin());
break;
}
}
if(i < str.length()) {
// we got more chars to scan in the input string
continue;
} else {
// we scanned the entire input string
// break and return true if we found all characters in "sub"
// false otherwise (i.e. return tmpSub.empty())
break;
}
}
return tmpSub.empty();
}
Here is the solution I gave to the interviewer:
#include "CommonHeader.h"
struct TreeNode {
TreeNode* parent;
TreeNode* left;
TreeNode* right;
bool value;
TreeNode() : parent(NULL), left(NULL), right(NULL) {}
/**
* @brief return true if this node value was actually fixed. False otherwise
* @return
*/
bool updateValue() {
bool oldValue = this->value;
this->value = this->left && this->right; // same as LOGICAL AND
return oldValue != this->value;
}
};
void fixTree(TreeNode* node) {
node->value = !node->value;
TreeNode* cur = node->parent;
while(cur) {
if(!cur->updateValue())
break;
cur = cur->parent;
}
}
The key here is to maintain a hash table with previously computed variables:
#include "Common.h"
static std::unordered_map<std::string, int> Variables;
static bool is_number(const std::string& str)
{
if(str.empty())
return false;
else
return (str.find_first_not_of("0123456789") == std::string::npos);
}
struct ASTNode
{
enum eOperator { kNone, kPlus, kMin, kStar, kDiv, kAssign, kReturn };
eOperator _operator = kNone;
ASTNode* _left;
ASTNode* _right;
std::string _value;
ASTNode(eOperator oper, ASTNode* left, ASTNode* right)
: _operator(oper)
, _left(left)
, _right(right)
{
}
ASTNode(const std::string& value)
: _left(NULL)
, _right(NULL)
, _value(value)
{
}
bool isLeaf() const { return (_left == NULL) && (_right == NULL); }
int processValue()
{
switch(_operator) {
case kNone:
if(Variables.count(_value)) {
return Variables[_value];
}
if(!is_number(_value)) throw std::string("Leaf node is not a number. " + _value);
return atoi(_value.c_str());
case kPlus:
return _left->processValue() + _right->processValue();
case kStar:
return _left->processValue() * _right->processValue();
case kMin:
return _left->processValue() - _right->processValue();
case kDiv:
return _left->processValue() / _right->processValue();
case kAssign: {
int rv = _right->processValue();
Variables[_left->_value] = rv;
return rv;
}
default:
case kReturn: {
return _right->processValue();
}
}
}
};
void compute_tree()
{
{
ASTNode* l = new ASTNode("2");
ASTNode* r = new ASTNode("3");
ASTNode* op = new ASTNode(ASTNode::kPlus, l, r);
ASTNode* xNode = new ASTNode("x");
ASTNode* assign = new ASTNode(ASTNode::kAssign, xNode, op);
std::cout << "x=2+3=" << assign->processValue() << std::endl;
}
{
ASTNode* l = new ASTNode("5000");
ASTNode* r = new ASTNode("30");
ASTNode* op = new ASTNode(ASTNode::kMin, l, r);
ASTNode* xNode = new ASTNode("y");
ASTNode* assign = new ASTNode(ASTNode::kAssign, xNode, op);
std::cout << "y=5000-30=" << assign->processValue() << std::endl;
}
{
ASTNode* l = new ASTNode("50");
ASTNode* r = new ASTNode("x");
ASTNode* op = new ASTNode(ASTNode::kStar, l, r);
ASTNode* xNode = new ASTNode("z");
ASTNode* assign = new ASTNode(ASTNode::kAssign, xNode, op);
std::cout << "z=50*x=" << assign->processValue() << std::endl;
}
{
ASTNode* l = new ASTNode("1");
ASTNode* r = new ASTNode("y");
ASTNode* op1 = new ASTNode(ASTNode::kStar, l, r);
ASTNode* z = new ASTNode("z");
ASTNode* op2 = new ASTNode(ASTNode::kMin, z, op1);
// for the "return" node , we only compute the right node
ASTNode* assign = new ASTNode(ASTNode::kReturn, NULL, op2);
std::cout << "z-(1*y)=" << assign->processValue() << std::endl;
}
}
Use shiftxor algorithm to generate a random number:
#include "CommonHeader.h"
// Generate RNG numbers.
// The below initialises the seed to pre-determined number
// To get a TRNG (True-Random-Number-Generator) one should initialise the
// seed with a true random number (e.g. capture the mouse current point and use it as the seed)
static size_t s_seed = 940983058;
void setSeed(int seed) { s_seed = seed; }
size_t rng()
{
size_t x = s_seed;
x ^= x << 17;
x ^= x >> 19;
x ^= x << 13;
s_seed = x;
return x;
}
size_t rng(size_t min, size_t max)
{
if(min >= max) return std::string::npos;
if(min == max) return min;
size_t x = s_seed;
x ^= x << 17;
x ^= x >> 19;
x ^= x << 13;
s_seed = x;
// apply the limits
x = (x % (max - min)) + min;
return x;
}
The idea here:
* Each transaction is identified by a string "Payer->Payee"
* Before we insert the this transaction to our ledger ("G" in the code) with the given amount, we check if we have a reversed transaction "Payee->Payer"
** If we do have such a transaction, we subtract the amount.
*** If the updated amount is negative, we remove the reversed transaction ("Payee->Payer") and insert "Payer->Payee" with the diff amount.
*** If the updated amount is zero - remove the reversed transaction and move on to the next transaction
*** Else (the reversed transaction is bigger than the current transaction) so just update the reverse transaction amount and continue
This is done in roughly o(n)
#include "CommonHeader.h"
static std::unordered_map<std::string, int> G;
static std::string make_key(const std::string& payer, const std::string& payee) { return payer + "->" + payee; }
static int& GetPayment(const std::string& key)
{
if(G.count(key) == 0) {
G[key] = 0;
}
return G[key];
}
static bool HasPayment(const std::string& key)
{
if(G.count(key) == 0) return false;
return true;
}
void ProcessPayments(const std::vector<std::tuple<std::string, std::string, int> >& transcations)
{
// Build the payment matrix
for(size_t i = 0; i < transcations.size(); ++i) {
const std::tuple<std::string, std::string, int>& paymentInfo = transcations[i];
const std::string& payee = std::get<0>(paymentInfo);
const std::string& payer = std::get<1>(paymentInfo);
int amount = std::get<2>(paymentInfo);
std::string key = make_key(payer, payee);
std::string reverse_key = make_key(payee, payer);
// Check to see if we have a reversed payment
if(HasPayment(reverse_key)) {
int& reversedAmount = GetPayment(reverse_key);
reversedAmount -= amount;
if(reversedAmount < 0) {
// Remove the reversed payment and add the current payment
int& tmpAmount = GetPayment(key);
tmpAmount += abs(reversedAmount);
// The erase must come *after* we update the new value of else we might get an invalid pointer
G.erase(reverse_key);
} else if(reversedAmount == 0) {
G.erase(reverse_key);
} else {
// nothing to be done here
}
} else {
int& tmpAmount = GetPayment(key);
tmpAmount += amount;
}
}
// Print the transcations
std::for_each(G.begin(), G.end(), [&](const std::unordered_map<std::string, int>::value_type& vt) {
std::cout << vt.first << ":" << vt.second << std::endl;
});
}
Simple array loop with hash contains the visited indexes comes to mind:
void checkCircularArray(const std::vector<int>& arr)
{
std::unordered_set<int> VisitedIndex;
int index = -1;
for(size_t i = 0; i < arr.size(); ++i) {
if(index == -1) {
index = arr[0];
} else {
index = arr[index];
}
if(VisitedIndex.count(index)) {
std::cout << "Circular found!" << std::endl;
return;
}
VisitedIndex.insert(index);
}
std::cout << "No dependency found!" << std::endl;
}
Using hash, no recursive functions:
* Store all the movies using std::map using int (movie-start-time) as the key and the value is std::unordered_set (hash-table) containing the movies that start at that time
NOTE: I used std::map because the underlying implementation is red-black tree, i.e. the items will be sorted based on the key (i.e. the start-time)
We then iterate over the map and print the possibilities (eliminating duplication as much as we can, we dont want to watch the same movie twice...)
void ScheduleMovies(const std::vector<std::pair<std::string, std::vector<int> > >& movies)
{
// Create a map based on the start time as key
std::map<int, std::unordered_set<std::string> > M;
std::for_each(movies.begin(), movies.end(), [&](const std::pair<std::string, std::vector<int> >& p) {
const std::string& name = p.first;
const std::vector<int>& movieHours = p.second;
for(size_t i = 0; i < movieHours.size(); ++i) {
if(M.count(movieHours[i]) == 0) {
M[movieHours[i]] = std::unordered_set<std::string>();
}
std::unordered_set<std::string>& moviesList = M[movieHours[i]];
moviesList.insert(name);
}
});
// Print the first option that has no conflict
while(true) {
std::vector<std::string> Plan;
std::unordered_set<std::string> Watched;
std::for_each(M.begin(), M.end(), [&](std::map<int, std::unordered_set<std::string> >::value_type& vt) {
// get the first movie from the list that we didn't watch yet
int movieHour = vt.first;
std::unordered_set<std::string>& possibleMovies = vt.second;
std::unordered_set<std::string>::const_iterator iter = std::find_if(possibleMovies.begin(),
possibleMovies.end(), [&](const std::string& name) { return (Watched.count(name) == 0); });
if(iter == possibleMovies.end() && !possibleMovies.empty()) {
// Could not find a match, pick the first movie
Plan.push_back(*(possibleMovies.begin()) + " " + std::to_string(movieHour));
Watched.insert(*(possibleMovies.begin()));
possibleMovies.erase(possibleMovies.begin());
} else if(iter != possibleMovies.end()) {
Plan.push_back(*(iter) + " " + std::to_string(movieHour));
Watched.insert(*iter);
possibleMovies.erase(iter); // Remove it
}
});
if(Plan.empty()) {
break;
}
std::for_each(Plan.begin(), Plan.end(), [&](const std::string& item) { std::cout << item << " "; });
std::cout << std::endl;
Plan.clear();
}
}
Example:
ScheduleMovies({ { "Shining", { 14, 15, 16 } }, { "Kill Bill", { 14, 15 } }, { "Pulp Fiction", { 14, 15 } } });
Input array - return maximum number
The array elements can be re-order
#include <algorithm>
#include <vector>
int best_operator_result(int a, int b)
{
int tmp;
int opt1 = a * b;
int opt2 = a + b;
tmp = std::max(opt1, opt2);
int opt3 = a / b;
tmp = std::max(tmp, opt3);
int opt4 = b / a;
tmp = std::max(tmp, opt4);
int opt5 = a / b;
tmp = std::max(tmp, opt5);
int opt6 = a - b;
tmp = std::max(tmp, opt6);
int opt7 = b - a;
tmp = std::max(tmp, opt7);
return tmp;
}
int best_match(int n, const std::vector<int>& numbers, size_t& index)
{
int maxVal = 0;
for(size_t i = 0; i < numbers.size(); ++i) {
int tmp = best_operator_result(n, numbers[i]);
if(i == 0) {
maxVal = tmp;
index = 0;
} else if(tmp > maxVal) {
maxVal = tmp;
index = i;
}
}
return maxVal;
}
int getMaxNumber(const std::vector<int>& numbers)
{
int res = 0;
// Empty list - return 0
if(numbers.empty()) return 0;
// 1 element in the list, return that element
if(numbers.size() == 1) return numbers[0];
// Loop over the array trying every pair combination
std::vector<int> modNumbers = numbers;
while(!modNumbers.empty()) {
int n = modNumbers[0];
modNumbers.erase(modNumbers.begin());
size_t where = std::string::npos;
res = best_match(n, modNumbers, where);
modNumbers.erase(modNumbers.begin() + where);
if(modNumbers.empty()) break;
modNumbers.insert(modNumbers.begin(), res);
}
return res;
}
Examples:
getMaxNumber({ 2, 1, 1, 1, 9 }); // 21=2*9+1+1+1
@ChrisK i think that we only disagree on the initial matrix traverse time. You ignore it, while I take it into consideration. If you ignore this step, then yes, this is a traveling salesman problem. I think that we can't ignore the initial matrix traverse time (and this is what my code does). This debate can be solved only by asking the interviewer these kind of questions...
FYI: I also notice that other people assumed the same assumption as I did
Mimic the multiplication process as you would do by hand:
Multiple each digit from the second string with the first string and sum up the results (taking into consideration the "carried")
#include "CommonHeader.h"
// Convert ASCII char to number (0 ASCII is 48)
static int char_to_num(char ch) { return ch - 48; }
std::string MultipleHelper(const std::string& num, int multipleBy, size_t depth)
{
int carried = 0;
std::string resString = std::string(depth, '0');
for(size_t i = num.length() - 1; i != std::string::npos; --i) {
int res = (char_to_num(num[i]) * multipleBy) + carried;
int n = res % 10;
carried = res / 10;
resString.insert(0, std::to_string(n));
}
if(carried != 0) {
resString.insert(0, std::to_string(carried));
}
return resString;
}
void MultipleStrings(const std::string& num1, const std::string& num2)
{
if(num1.empty()) return;
if(num2.empty()) return;
int depth = 0;
std::vector<std::string> arr;
size_t maxStrLen = 0;
for(size_t i = (num2.length() - 1); i != std::string::npos; --i) {
arr.push_back(MultipleHelper(num1, char_to_num(num2[i]), depth));
maxStrLen = arr.back().length();
depth++;
}
// Pad the strings so they will have the same length
std::string outputString;
int carried = 0;
for(size_t i = (maxStrLen - 1); i != std::string::npos; --i) {
int curSum = 0;
for(size_t j = 0; j < arr.size(); ++j) {
std::string& curstr = arr[j];
if(curstr.length() != maxStrLen) {
curstr.insert(0, std::string(maxStrLen - curstr.length(), '0'));
}
curSum += char_to_num(curstr[i]);
}
int n = curSum % 10 + carried;
carried = curSum / 10;
outputString.insert(0, std::to_string(n));
}
if(carried != 0) {
outputString.insert(0, std::to_string(carried));
}
std::cout << num1 << " * " << num2 << " = " << outputString << std::endl;
}
int main(int argc, char** argv)
{
MultipleStrings("4385", "345"); // an example
return 0;
}
@ChrisK not really a travelling salesman: all the steps have the same weight (one step for each direction), you don't know the locations of the cheeses, so you must visit each cell once. Notice that in my code I am using this condition:
if(!adj->_visited && (adj->_value != BLOCKED_PATH))
i.e. we don't visit each cell more than once.
The solution is O(m*n)
RepIsotherm provides the best roof insulation products in Cape Town, South Africa. We offer insulation products for roofs, water pipes ...
Rep
RepFannieRamirez, Accountant at A9
I am a technically skilled Payroll bookkeeper responsible for the full charge bookkeeping function. My expertise includes knowledge of accepted ...
We start from 0 and keeping track of the current sum of the current subarray (of len 1)
* If the cursum < sum => add next element to the end of the subarray (while updating the cursum)
* If the cursim > sum => start removing elements from the start of the subarry (while updating the cursum)
* If the cursum matches sum - return true
O(N) solution.
Here is the C++ implementation:
- PenChief May 01, 2019