Context: There's a network of

Interview Question

0

of 0 votes

4
Answers
Context:
There's a network of computers. Each computer accepts connections at certain incoming port numbers and can make outgoing connections to a possibly different set of outgoing port numbers. Some computers are connected through cables to each other. Computer A can directly transmit data to computer B if and only if:
there is a direct cable connection between computer A and B,
there exists a port number X, that is an outgoing port on computer A and an incoming port on computer B.
Some of the computers are connected directly to the outside, unsafe network. If there is a way to connect to computer Z either directly or indirecly from the outside network, that computer Z is "at risk". If there is no way to connect to computer Z from outside network, that computer is "safe".
Question:
Write a program that given:
computers (each computer has incoming and outgoing port numbers),
cable connections between computers (a pair of computers),
computers accessible from outside network,
Print out all "safe” computers and all possible ways to access a specific computer from outside network.
- codercoder July 19, 2014 in United States | Report Duplicate | Flag | PURGE
Trees and Graphs

Email me when people comment.

An error occurred in subscribing you.

Country: United States

Email me when people comment.

An error occurred in subscribing you.

Comment hidden because of low score. Click to expand.

of 0 vote

Suppose we have to access a particular computer F. But it is not accessible from the outside world. Whereas computer A is accessible from outside and it is connected to computer F by having outgoing ports on A and incoming ports on F from A.
1. We can think of all computers as nodes and the port connections as edges in a graph.
2. Then we can find out the shortest possible distance from computer A to computer F by using Dijkistra's algorithm. And to access some other computer we can think of the same solution

- vgeek July 20, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

The question already marks its a graph algo, I think quick optimization is once unsafe computer list is parsed, do a BFS for 1 node and mark all unsafe computers. Remove these computers from further parsing of rest of the unsafe computers

- R July 20, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

1. U = Set of computers connected to outside, V = Set of all computers
2. For every node in U, do a BFS to add connected computers in set V.
3. Remove visited nodes from U and V, if present.
4. Remaining nodes in V are the 'safe' computers.

- loverisk July 22, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

Build a min spanning tree. While building if you see any system which can be accessed from the outside then all the nodes in the min spanning tree can be termed unsafe. The same can be done again on remaining set of nodes (computers) until no further unsafe computers are found.

- brk August 31, 2014 | Flag Reply

CareerCup

Interview Question

Books

Videos

Resume Review

Mock Interviews