Comment hidden because of low score. Click to expand.
0
of 0 vote

The question obviously points to a Graph solution.
Starting from the root C, we should implement BFS using a queue and a "visited" matrix. We can also keep a "parent" matrix to remember the different paths.
To find the turning off order, we can do the topological sort of the graph.

Comment hidden because of low score. Click to expand.
0

topological sort is useless here since its not DAG, its undirected graph.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Given a computer at (row, col) put it into the processing queue.
Then, take first element to process and:
2. If it is a computer, print it and put its row (row, 0) and column (0, col) for processing.
3. If it is a row, find all computers in that row and put for processing.
4. If it is a column, find all computers in that column and put for processing.
Assumption: indices start from 1, while 0 denotes the entire row/column.

``````#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <vector>

class Node
{
public:
int row;
int col;
class CompareByRow
{
public:
bool operator()(const Node* x, const Node* y) { return x->row < y->row; }
};
class CompareByCol
{
public:
bool operator()(const Node* x, const Node* y) { return x->col < y->col; }
};
bool operator<(const Node& o) const { return row < o.row || row == o.row && col < o.col; }
};

int main()
{
std::vector<Node> computers = { {1, 1}, {2, 2}, {4, 4}, {4, 1} };
std::vector<const Node*> comp_by_row;
std::vector<const Node*> comp_by_col;
for (const Node& n : computers)
{
comp_by_row.push_back(&n);
comp_by_col.push_back(&n);
}
std::sort(comp_by_row.begin(), comp_by_row.end(), Node::CompareByRow());
std::sort(comp_by_col.begin(), comp_by_col.end(), Node::CompareByCol());

std::list<Node> processing_queue;
std::set<Node> processed_nodes;
processing_queue.push_back(computers[0]);
while (!processing_queue.empty())
{
Node& n = processing_queue.front();
if (processed_nodes.insert(n).second)
{
if (n.row != 0 && n.col != 0)
{
std::cout << "Node (" << n.row << ", " << n.col << ") added." << std::endl;
processing_queue.push_back({ n.row, 0 });
processing_queue.push_back({ 0, n.col });
processed_nodes.insert(n);
}
else
{
if (n.row == 0)
{
auto b = std::lower_bound(comp_by_col.begin(), comp_by_col.end(), &n, Node::CompareByCol());
auto e = std::upper_bound(comp_by_col.begin(), comp_by_col.end(), &n, Node::CompareByCol());
while (b != e)
{
processing_queue.push_back(**b);
b++;
}
}
if (n.col == 0)
{
auto b = std::lower_bound(comp_by_row.begin(), comp_by_row.end(), &n, Node::CompareByRow());
auto e = std::upper_bound(comp_by_row.begin(), comp_by_row.end(), &n, Node::CompareByRow());
while (b != e)
{
processing_queue.push_back(**b);
b++;
}
}
}
}
else
{
std::cout << "Node (" << n.row << ", " << n.col << ") skipped (already processed)." << std::endl;
}
processing_queue.pop_front();
}
return 0;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.