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
We use Topological sorting here:
#include <stdio.h>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <string.h>
#include <queue>
#include <functional>
struct N {
enum eState { kNone, kTemp, kPerm };
eState marker;
std::string name;
std::vector<N*> adjacents;
N()
: marker(kNone)
{
}
};
static std::unordered_map<std::string, N> G; // The graph
static std::vector<N*> L; // Contains the result
static N* GetNodeCreateIfNeeded(const std::string& name)
{
if(G.count(name) == 0) {
N node;
node.name = name;
G[name] = node;
}
return &G[name];
}
void Visit(N* node)
{
if(node->marker == N::kPerm) return;
if(node->marker == N::kTemp) throw std::string("Loop found!");
node->marker = N::kTemp;
std::for_each(node->adjacents.begin(), node->adjacents.end(), [&](N* adj) { Visit(adj); });
node->marker = N::kPerm;
L.insert(L.begin(), node);
}
void TopoSort(const std::vector<std::pair<std::string, std::string> >& items)
{
L.clear();
G.clear();
std::for_each(items.begin(), items.end(), [&](const std::pair<std::string, std::string>& p) {
N* node = GetNodeCreateIfNeeded(p.first); // PluginSDK
N* dependency = GetNodeCreateIfNeeded(p.second); // libCodeLite
dependency->adjacents.push_back(node);
});
try {
std::for_each(G.begin(), G.end(), [&](std::unordered_map<std::string, N>::value_type& vt) {
if(vt.second.marker == N::kNone) {
Visit(&(vt.second));
}
});
} catch(std::string& e) {
std::cout << "Error: " << e.c_str() << std::endl;
}
// Print the build order
std::for_each(L.begin(), L.end(), [&](N* node) { std::cout << node->name << std::endl; });
}
int main(int argc, char** argv)
{
// std::vector<int> numbers = { 48, 20, 1, 3, 4, 6, 9, 24, 7, 8 };
// // std::sort(numbers.begin(), numbers.end(), [](int a, int b) { return a > b; });
// int minArrSize = getNumbers(numbers);
// std::cout << "The best match leaving us with an array of size: " << minArrSize << std::endl;
// return 0;
// calculate_steps(10, 20, { { 5, 3 }, { 4, 3 }, { 7, 11 } }, { { 7, 19 }, { 4, 4 }, { 5, 5 }, { 3, 9 } }, { 8, 17
// });
TopoSort({ { "master", "ubuntu" }, { "numpy", "master" }, { "tensorflow", "numpy" } });
TopoSort({ { "python", "numpy" }, { "numpy", "python" }, { "tensorflow", "ubuntu" } });
return 0;
}
And the output:
ubuntu
master
numpy
tensorflow
Error: Loop found!
ubuntu
tensorflow
And here is a C++ implementation of the above description:
#include <stdio.h>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <string.h>
#include <queue>
#include <functional>
#define CAN_MOVE 0
#define BLOCKED_PATH 1
#define CHEESE 2
#define OTHER_PERSON 3
struct DimNode {
int _x;
int _y;
int _value;
std::string _key;
std::vector<DimNode*> _adjacents;
DimNode* _origin;
bool _visited;
DimNode() {}
DimNode(int x, int y)
: _x(x)
, _y(y)
, _value(CAN_MOVE)
, _key(std::to_string(x) + "," + std::to_string(y))
, _origin(NULL)
, _visited(false)
{
}
};
std::unordered_map<std::string, DimNode> G;
DimNode* GetNode(int x, int y)
{
std::string key = std::to_string(x) + "," + std::to_string(y);
if(G.count(key) == 0) {
G.insert(std::make_pair(key, DimNode(x, y)));
}
return &G[key];
}
std::vector<DimNode*> GetAdjacents(DimNode* node, int m, int n)
{
int x = node->_x;
int y = node->_y;
std::vector<DimNode*> result;
if((x + 1) < m) {
// valid index
result.push_back(GetNode(x + 1, y));
}
if((x - 1) >= 0) {
// valid index
result.push_back(GetNode(x - 1, y));
}
if((y - 1) >= 0) {
// valid index
result.push_back(GetNode(x, y - 1));
}
if((y + 1) < n) {
// valid index
result.push_back(GetNode(x, y + 1));
}
return result;
}
enum eState { kNormal, kOtherPersonFound };
void calculate_steps(int m, int n, const std::vector<std::pair<int, int> >& cheeseCells,
const std::vector<std::pair<int, int> >& blockedCells, const std::pair<int, int>& otherPerson)
{
// build m*n graph
for(int x = 0; x < m; ++x) {
for(int y = 0; y < n; ++y) {
DimNode* node = GetNode(x, y);
node->_adjacents = GetAdjacents(node, m, n);
}
}
std::for_each(blockedCells.begin(), blockedCells.end(),
[&](const std::pair<int, int>& coords) { GetNode(coords.first, coords.second)->_value = BLOCKED_PATH; });
std::for_each(cheeseCells.begin(), cheeseCells.end(),
[&](const std::pair<int, int>& coords) { GetNode(coords.first, coords.second)->_value = CHEESE; });
GetNode(otherPerson.first, otherPerson.second)->_value = OTHER_PERSON;
// Now that we have the graph, loop over it
std::queue<DimNode*> q;
q.push(GetNode(0, 0));
GetNode(0, 0)->_visited = true;
int cheesCounter = 0;
eState state = kNormal;
std::string otherPersonCoords;
int steps = 0;
DimNode* currentNode = NULL;
while(!q.empty()) {
currentNode = q.front();
q.pop();
steps++;
switch(currentNode->_value) {
case CAN_MOVE:
// Traverse
break;
case CHEESE:
// Increase the cheese counter
cheesCounter++;
break;
case OTHER_PERSON:
// Found the other person cell, start tracking to this location
state = kOtherPersonFound;
otherPersonCoords = currentNode->_key;
break;
default:
break;
}
std::for_each(currentNode->_adjacents.begin(), currentNode->_adjacents.end(), [&](DimNode* adj) {
if(!adj->_visited && (adj->_value != BLOCKED_PATH)) {
q.push(adj);
adj->_visited = true;
if(state == kOtherPersonFound) {
adj->_origin = currentNode;
}
}
});
}
std::cout << "Found " << cheesCounter << " cheese caked" << std::endl;
std::cout << "Other person is found at " << otherPersonCoords << std::endl;
if(currentNode) {
DimNode* runner = currentNode;
std::cout << "Path from last position to other-person:" << std::endl;
while(runner) {
steps++;
std::cout << runner->_key << " ";
runner = runner->_origin;
}
std::cout << std::endl;
}
std::cout << "Total steps walked: " << steps << std::endl;
}
int main(int argc, char** argv)
{
calculate_steps(10, 20, { { 5, 3 }, { 4, 3 }, { 7, 11 } }, { { 7, 19 }, { 4, 4 }, { 5, 5 }, { 3, 9 } }, { 8, 17 });
return 0;
}
This will output:
Found 3 cheese caked
Other person is found at 8,17
Path from last position to other-person:
9,19 9,18 9,17
Total steps walked: 199
This sounds like the Knight Chess problem. To solve this:
* Build a graph. Each cell is connected to its adjacent cells marked with 0 or 2 (we can't move to 1s).
* Use BFS to traverse the *entire* graph (we don't know where the cheeses are located nor how many we have, so we need to check them all).
* When we hit the other person cell we keep track for how many steps we needed to get from him to the end of the maze.
So in theory its O(m*n)
At first glance, the solution seems simple (when assuming: no duplicate numbers in the array). Even when adding duplicate entries, this is still solvable with not much of change.
The idea here is to visit each permutation (per target number) only once. We keep on recursing on the array until we find the lowest result.
Running the example numbers will yield 5 possible solutions, from which we pick the least one (which is one)
std::unordered_set<int> all_numbers;
std::unordered_set<std::string> visited_matches;
std::string make_key(const std::vector<int>& numbers, int target)
{
std::string key;
for(int i = 0; i < (int)numbers.size(); ++i) {
key += std::to_string(numbers[i]);
}
key += std::to_string(target);
return key;
}
bool is_equal(const std::vector<int>& numbers, int target)
{
int res = 0;
std::string k = make_key(numbers, target);
if(visited_matches.count(k)) {
return false;
}
visited_matches.insert(k);
for(int i = 0; i < (int)numbers.size(); ++i) {
res += numbers[i];
}
if(res == target) {
// remove these numbers from the set
for(int i = 0; i < (int)numbers.size(); ++i) {
std::cout << numbers[i] << " ";
all_numbers.erase(numbers[i]);
}
std::cout << " => " << target << std::endl;
all_numbers.erase(target);
return true;
} else if(res < target) {
return false;
}
// recurse
for(int i = 0; i < (int)numbers.size(); ++i) {
std::vector<int> v = numbers;
v.erase(v.begin() + i); // remove the i-th entry to create a new subset and try again
if(is_equal(v, target)) {
return true;
}
}
return false;
}
int search_subset_groups(const std::vector<int>& numbers)
{
std::cout << "--------------------------------------------" << std::endl;
// initialize the hash
all_numbers.clear();
all_numbers.insert(numbers.begin(), numbers.end());
bool cont = false;
while(true) {
// create the list of numbers to work on
// We copy it from the hash
std::vector<int> numbersLeft;
std::for_each(all_numbers.begin(), all_numbers.end(), [&](int n) { numbersLeft.push_back(n); });
// sort the list in desc order
std::sort(numbersLeft.begin(), numbersLeft.end(), [](int a, int b) { return a > b; });
// And try to find matches
for(int i = 0; i < (int)numbersLeft.size(); ++i) {
std::vector<int> v = numbersLeft;
int target = numbersLeft[i];
v.erase(v.begin() + i);
if(is_equal(v, target)) {
cont = true;
break;
}
}
if(cont) {
cont = false;
continue;
}
break;
}
std::cout << "==> we are left with array of size " << all_numbers.size() << std::endl;
std::for_each(all_numbers.begin(), all_numbers.end(), [&](int n) { std::cout << " " << n << std::endl; });
return all_numbers.size();
}
int getNumbers(const std::vector<int>& numbers)
{
int size = search_subset_groups(numbers);
if(size == 0) return 0;
while(size < (int)numbers.size()) {
int newIterSize = search_subset_groups(numbers);
if(newIterSize == (int)numbers.size()) {
break;
}
if(newIterSize < size) size = newIterSize;
if(newIterSize == size) continue;
}
return size;
}
///------------------------------------------------------
/// Main
///------------------------------------------------------
int main(int argc, char** argv)
{
std::vector<int> numbers = { 48, 20, 1, 3, 4, 6, 9, 24 };
// std::sort(numbers.begin(), numbers.end(), [](int a, int b) { return a > b; });
int minArrSize = getNumbers(numbers);
std::cout << "The best match leaving us with an array of size: " << minArrSize << std::endl;
return 0;
}
Here is the C++ solution for this problem:
1. We build the graph
2. Then we traverse the graph from the starting node ("keypad key") to each node and sum its adjacent count (we do this recursively). Then we do this for each adjacent recursively
struct KeypadNode {
int number;
std::vector<int> adjacents;
KeypadNode(int num, const std::vector<int>& adj)
: number(num)
, adjacents(adj)
{
}
};
std::unordered_map<int, KeypadNode> build_keypad_graph()
{
// 1 2 3
// 4 5 6
// 7 8 9
// 0
std::unordered_map<int, KeypadNode> g;
g.insert(std::make_pair(0, KeypadNode(0, { 4, 6 })));
g.insert(std::make_pair(1, KeypadNode(1, { 8, 6 })));
g.insert(std::make_pair(2, KeypadNode(2, { 7, 9 })));
g.insert(std::make_pair(3, KeypadNode(3, { 4, 8 })));
g.insert(std::make_pair(4, KeypadNode(4, { 3, 9, 0 })));
g.insert(std::make_pair(5, KeypadNode(5, {})));
g.insert(std::make_pair(6, KeypadNode(6, { 1, 7, 0 })));
g.insert(std::make_pair(7, KeypadNode(7, { 2, 6 })));
g.insert(std::make_pair(8, KeypadNode(8, { 1, 3 })));
g.insert(std::make_pair(9, KeypadNode(9, { 2, 4 })));
return g;
}
void get_keypad_knight_path_count(
const std::unordered_map<int, KeypadNode>& G, int initialDigit, int length, int& pathCount)
{
if(length == 0) return;
const KeypadNode& key = G.find(initialDigit)->second;
pathCount += key.adjacents.size();
std::for_each(key.adjacents.begin(), key.adjacents.end(),
[&](int adj) { get_keypad_knight_path_count(G, adj, length - 1, pathCount); });
}
int main(int argc, char** argv)
{
// print_task_order();
{
std::unordered_map<int, KeypadNode> G = build_keypad_graph();
int pathCount = 0;
get_keypad_knight_path_count(G, 6, 2, pathCount);
std::cout << "There are " << pathCount << " possible paths" << std::endl;
}
}
Here is the C++ version of this solution:
#define COOLDOWN_INTERVAL 2
void print_task_time_slots()
{
std::vector<int> tasks{ 1, 1, 2, 1, 2 }; // initial tasks list
std::unordered_map<int, int> timers; // keep track of all the timers per task type
size_t timeSlots = 0;
while(!tasks.empty()) {
// Execute the tasks if there is no timer for it
int taskType = tasks[0];
if(timers.count(taskType) == 0) {
// we can execute this task, since we have no timer for it
// add timer for this task type and remove the task from the queue
timers.insert(
std::make_pair(taskType, COOLDOWN_INTERVAL + 1)); // +1 we will decrease it by one few lines below
tasks.erase(tasks.begin());
}
// always increase the timeslots counter
timeSlots++;
// reduce the counters for all the task types. If a counter hits 0 we remove it from the map
std::unordered_map<int, int> tmpTimers;
std::for_each(timers.begin(), timers.end(), [&](std::unordered_map<int, int>::value_type& p) {
int type = p.first;
int counter_value = p.second;
--counter_value;
if(counter_value > 0) {
tmpTimers.insert(std::make_pair(type, counter_value));
}
});
timers.swap(tmpTimers);
}
std::cout << "we need " << timeSlots << " time units to run this tasks list" << std::endl;
}
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 ...
I wrote another solution based on my previous solution. A bit more elegant (this time using queue (vector based)
The code:
- PenChief September 10, 2017