|
|---|
|
|
|
|
|
|
c****a
发帖数: 50 | 1 题目有点长，求大牛赐一个漂亮点的解法
面试要求可以在eclipse等工具下完成，可以上网用google等
ProgA
System Dependencies
Components of computer systems often have dependencies--other components
that must be installed before they will function properly. These
dependencies are frequently shared by multiple components. For example, both
the TELNET client program and the FTP client program require that the TCP/
IP networking software be installed before they can operate. If you install
TCP/IP and the TELNET client program, and later decide to add the FTP client
program, you do not need to reinstall TCP/IP.
For some components it would not be a problem if the components on which
they depended were reinstalled; it would just waste some resources. But for
others, like TCP/IP, some component configuration may be destroyed if the
component was reinstalled.
It is useful to be able to remove components that are no longer needed. When
this is done, components that only support the removed component may also
be removed, freeing up disk space, memory, and other resources. But a
supporting component, not explicitly installed, may be removed only if all
components which depend on it are also removed. For example, removing the
FTP client program and TCP/IP would mean the TELNET client program, which
was not removed, would no longer operate. Likewise, removing TCP/IP by
itself would cause the failure of both the TELNET and the FTP client
programs. Also if we installed TCP/IP to support our own development, then
installed the TELNET client (which depends on TCP/IP) and then still later
removed the TELNET client, we would not want TCP/IP to be removed.
We want a program to automate the process of adding and removing components.
To do this we will maintain a record of installed components and component
dependencies. A component can be installed explicitly in response to a
command (unless it is already installed), or implicitly if it is needed for
some other component being installed. Likewise, a component, not explicitly
installed, can be explicitly removed in response to a command (if it is not
needed to support other components) or implicitly removed if it is no longer
needed to support another component.
Input
The input will contain a sequence of commands (as described below), each on
a separate line containing no more than eighty characters. Item names are
case sensitive, and each is no longer than ten characters. The command names
(DEPEND, INSTALL, REMOVE and LIST) always appear in uppercase starting in
column one, and item names are separated from the command name and each
other by one or more spaces. All appropriate DEPEND commands will appear
before the occurrence of any INSTALL dependencies. The end of the input is
marked by a line containing only the word END.
Command Syntax Interpretation/Response
DEPEND item1 item2 [item3 ...] item1 depends on item2 (and item1 depends
on item3 ...)
INSTALL item1 install item1 and those on which it depends
REMOVE item1 remove item1, and those on whch it depends, if possible
LIST list the names of all currently-installed components
Output
Echo each line of input. Follow each echoed INSTALL or REMOVE line with the
actions taken in response, making certain that the actions are given in the
proper order. Also identify exceptional conditions (see Expected Output,
below, for examples of all cases). For the LIST command, display the names
of the currently installed components. No output, except the echo, is
produced for a DEPEND command or the line containing END. There will be at
most one dependency list per item.
Sample Input
DEPEND TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND BROWSER TCPIP HTML
INSTALL NETCARD
INSTALL TELNET
INSTALL foo
REMOVE NETCARD
INSTALL BROWSER
INSTALL DNS
LIST
REMOVE TELNET
REMOVE NETCARD
REMOVE DNS
REMOVE NETCARD
INSTALL NETCARD
REMOVE TCPIP
REMOVE BROWSER
REMOVE TCPIP
LIST
END
Output for the Sample Output
DEPEND TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND BROWSER TCPIP HTML
INSTALL NETCARD
Installing NETCARD
INSTALL TELNET
Installing TCPIP
Installing TELNET
INSTALL foo
Installing foo
REMOVE NETCARD
NETCARD is still needed.
INSTALL BROWSER
Installing HTML
Installing BROWSER
INSTALL DNS
Installing DNS
LIST
HTML
BROWSER
DNS
NETCARD
foo
TCPIP
TELNET
REMOVE TELNET
Removing TELNET
REMOVE NETCARD
NETCARD is still needed.
REMOVE DNS
Removing DNS
REMOVE NETCARD
NETCARD is still needed.
INSTALL NETCARD
NETCARD is already installed.
REMOVE TCPIP
TCPIP is still needed.
REMOVE BROWSER
Removing BROWSER
Removing HTML
Removing TCPIP
REMOVE TCPIP
TCPIP is not installed.
LIST
NETCARD
foo
END | w*r
发帖数: 72 | 2 我觉得类似SmartPointer的reference counting， 如果你回写smart_pointer， 应该
不会很难，我用了3个小时左右才写对，最后处理何时可以dereference花了很多时间。 | I*******g
发帖数: 7600 | 3 saleforce question
both
install
client
【在 c****a 的大作中提到】
: 题目有点长，求大牛赐一个漂亮点的解法
: 面试要求可以在eclipse等工具下完成，可以上网用google等
: ProgA
: System Dependencies
: Components of computer systems often have dependencies--other components
: that must be installed before they will function properly. These
: dependencies are frequently shared by multiple components. For example, both
: the TELNET client program and the FTP client program require that the TCP/
: IP networking software be installed before they can operate. If you install
: TCP/IP and the TELNET client program, and later decide to add the FTP client
| l*********u
发帖数: 19053 | 4 是否有?
DEPEND A B C
DEPEND C D
both
install
client
【在 c****a 的大作中提到】
: 题目有点长，求大牛赐一个漂亮点的解法
: 面试要求可以在eclipse等工具下完成，可以上网用google等
: ProgA
: System Dependencies
: Components of computer systems often have dependencies--other components
: that must be installed before they will function properly. These
: dependencies are frequently shared by multiple components. For example, both
: the TELNET client program and the FTP client program require that the TCP/
: IP networking software be installed before they can operate. If you install
: TCP/IP and the TELNET client program, and later decide to add the FTP client
| n********n
发帖数: 529 | | n********n
发帖数: 529 | 6 这是我当时写的，1个半小时左右吧。
/////////////////////////////////////////////////////
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.HashMap;
import java.util.HashSet;
public class TestForSalesforce {
// Variable to track the dependencies
HashMap> deps = new HashMap
String>>();
// Variable to track the installed commands
HashMap ins = new HashMap();
public boolean processFile(File inputFile) {
try {
// Open the file for read. Output error message if file can not
be opened.
FileReader fr = new FileReader(inputFile);
BufferedReader br = new BufferedReader(fr);
String line = "";
// Read the file line by line
while((line = br.readLine()) != null) {
// Handle the empty line
if(line.trim().equals("")) {
continue;
}
// Separate the input to String array
String[] commands = line.trim().split("\s+");
//System.out.println(Arrays.toString(commands));
System.out.println(line);
processCommand(commands);
}
br.close();
} catch (Exception e) {
System.out.println("Error: Can not process file correcly, " +
inputFile.toPath());
//e.printStackTrace();
return false;
}
return true;
}
// function to process the commands in the line
private boolean processCommand(String[] commands) {
// consider corner condition in case other people is calling this
// private function in other function inside this class.
if(commands == null || commands.length == 0) {
return false;
}
String relation = commands[0];
switch (relation) {
case "DEPEND":
if(commands.length < 3) {
return false;
}
String command = commands[1];
HashSet depency = new HashSet();
for(int i=2; i
depency.add(commands[i]);
}
deps.put(command, depency);
break;
case "INSTALL" :
if(commands.length < 2) {
return false;
}
for(int i=1; i
if(ins.containsKey(commands[i])) {
System.out.println("\t" + commands[i] + " is already
installed.");
} else {
installCommand(commands[i]);
}
}
break;
case "REMOVE" :
if(commands.length < 2) {
return false;
}
for(int i=1; i
if(!ins.containsKey(commands[i])) {
System.out.println("\t" + commands[i] + " is not
installed.");
} else {
if(checkDependency(commands[i])) {
System.out.println("\tRemoving " + commands[i]);
ins.remove(commands[i]);
// Look for all the dependencies. Remove the
dependents is possible.
removeDependency(commands[i]);
} else {
System.out.println("\t" + commands[i] + " is
still needed.");
}
}
}
break;
case "LIST" :
for(String s : ins.keySet()) {
System.out.println("\t" + s);
}
break;
default :
}
return true;
}
// Remove dependent commands.
private boolean removeDependency(String command) {
if(deps.containsKey(command)) {
HashSet set = deps.get(command);
for(String s : set) {
if(checkDependency(s)) {
System.out.println("\tRemoving " + s);
ins.remove(s);
}
}
}
return true;
}
// Install the giving command. Use deep-first algo to install the
dependencies firsts.
private boolean installCommand(String command) {
if(deps.containsKey(command)) {
HashSet set = deps.get(command);
for(String s : set) {
if(ins.containsKey(s)) {
continue;
} else {
installCommand(s);
}
}
}
System.out.println("\tInstalling " + command);
ins.put(command, true);
return true;
}
/* check the dependency for giving command.
return true if there is no dependency.
return false if there is dependency.
*/
private boolean checkDependency(String command) {
for(String s : ins.keySet()) { // look for all the installed
commands
if(deps.containsKey(s)) {
HashSet set = deps.get(s);
for(String depency : set) {
// return false if an installed command depends on the
giving one.
if(depency.equals(command)) {
return false;
}
}
}
}
return true;
}
public static void main(String[] args) {
File file = new File("C:\test1_input.dat");
TestForSalesforce test = new TestForSalesforce();
test.processFile(file);
}
} | p****w
发帖数: 90 | 7 nn【在 cuptea (cuptea)的大作中提到：】n：题目有点长，求大牛赐一个漂亮点的解
法n：面试要求可以在eclipse等工具下完成，可以上网用google等n：n：n：ProgAn：
System Dependencies n：Components of computer systems often have
dependencies--other components n……nn--n[发自未名空间Android客户端] | s**********s
发帖数: 1 | 8 说实话，他的参考答案是错的。这家公司似乎不大靠普。
上面的解法也是错的，有两个算法上的根本性错误。
试试下面的测试资料：
//TEST 1
DEPEND A B
DEPEND C A B
INSTALL C
REMOVE C
//TEST 2
DEPEND B A
DEPEND C B A
INSTALL C
REMOVE C
//TEST 3
DEPEND B A
DEPEND C B
INSTALL C
REMOVE C
有时候，错反而被认为是对，因为刚好符合错的标准答案。 | p****w
发帖数: 90 | 9 nn【在 cuptea (cuptea)的大作中提到：】n：题目有点长，求大牛赐一个漂亮点的解
法n：面试要求可以在eclipse等工具下完成，可以上网用google等n：n：n：ProgAn：
System Dependencies n：Components of computer systems often have
dependencies--other components n……nn--n[发自未名空间Android客户端] | h**********c
发帖数: 4120 | | h**********c
发帖数: 4120 | 11 jenkins 上有depency graph
怎么画的， open source
不过要检查dependency diamond， avoid infinite loop是非常困难的，光画图可以
bfs,dfs不难 |
|
|
|
|
|
|
|
