📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 32744| 回复: 25
跳转到指定楼层
上一主题 下一主题
收起左侧

[题目讨论] 请教一道亚麻最近高频的OOD linux find题目

 
全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
亚麻这道linux find的题目最近考得特别多,但是面经里面的描述和信息很有限, 想请教一下地里的大神们,指导一下这道的解题思路和相关代码实现。在此先谢过了!

评分

参与人数 4大米 +7 收起 理由
LeonChen + 2 好问题!
woyaoshuati + 2 很有用的信息!
高渐离击筑高歌 + 1 赞一个
的萨菲 + 2 给你点个赞!

查看全部评分


上一篇:网上找的系统设计资料
下一篇:再来一道系统设计题

本帖被以下淘专辑推荐:

推荐
magicsets 2019-3-10 07:03:17 | 只看该作者
全局:
最近有点时间我来稍微写一下这个问题..

Linux的find命令其实还是相当复杂的一个命令,参数种类很多,官方文档在这里:https://www.gnu.org/software/fin ... _mono/find.html#Top

文档里在序章的1.3节介绍了find命令的四大类参数:
options:affect overall operation rather than the processing of a specific file;
tests:return a true or false value, depending on the file's attributes;
actions:have side effects and return a true or false value; and
operators:connect the other arguments and affect when and whether they are evaluated.

这个分类方法稍微有点土,毕竟find是很早以前设计的工具了。现在来看的话find命令本质上是一个针对文件系统的查询引擎(Query Engine)。Options相当于全局的configuration,tests(各种过滤器)和 operations(“与或非”逻辑联结词)可以合称为谓词(predicate,类似于SQL中的where语句),而actions则是一些side effect操作

总体设计上:
(1) 首先要设计对所存储数据的access path,也就你怎么访问/遍历这些数据 —— 对应文件系统就是简单粗暴的walk file tree
(2) 然后需要将各种参数转化为一定的中间表示(IR,intermediate representation),比如说上面提到的option,predicate和action都可以是一个抽象类,然后针对每个参数继承其中一个并实现相应功能
(3) 得到了中间表示,还可以设计优化器对其进行优化。比如说Linux find是可以启动优化功能的(-O1或者-O2或者-O3),会reorder过滤条件的执行顺序。举个简单例子,考虑过滤条件“找到文本中包含Hello world并且后缀为.cpp的文件”,那么我们肯定希望先执行后缀名.cpp的这个过滤,然后在满足后缀的文件中再查找Hello wolrd关键词
(4) 最后需要生成一个执行器,根据优化后的中间表示(一般称为执行计划Execution Plan),walk file tree并且执行相应的filter和action。

关于OOP的部分,首先问一个最根本的问题:我们为什么需要OOP,或者说OOP可以做到什么?

其实OOP好处还是挺多的.. 但最重要的用处之一就是系统的可扩展性(extensibility)。比如说现在系统支持了若干种过滤器,那么当我们想要添加一个新的过滤器的时候,是否需要修改很多处已有的代码?还是只需要在某个地方独立地实现一下该过滤器的逻辑,然后将其注册到过滤器列表(registry)中? —— 我们肯定希望的是后者,并可以通过OOP的继承与动态绑定机制实现。

还有一点题外话.. OOP不是表达抽象、实现多态的唯一/最好的机制,具体要看应用场景。函数式以及C++模板元编程(静多态)都有其非常适用的场景。

下面是一份Java写的参考代码:
  1. import java.io.FileNotFoundException;
  2. import java.io.IOException;
  3. import java.io.PrintWriter;
  4. import java.nio.file.FileSystems;
  5. import java.nio.file.FileVisitOption;
  6. import java.nio.file.FileVisitResult;
  7. import java.nio.file.FileVisitor;
  8. import java.nio.file.Files;
  9. import java.nio.file.Path;
  10. import java.nio.file.PathMatcher;
  11. import java.nio.file.Paths;
  12. import java.nio.file.attribute.BasicFileAttributes;
  13. import java.util.ArrayList;
  14. import java.util.EnumSet;
  15. import java.util.HashMap;
  16. import java.util.Stack;
  17. import java.util.Map;

  18. // 需要通过命令行提供参数,可以先打包成jar文件然后通过命令行执行
  19. // 例如:
  20. // java -jar find.jar . -name data.txt
  21. // java -jar find.jar . -name \*.txt
  22. // java -jar find.jar /Some/Path -maxdepth 3 -name \*.h -or -name \*.cpp
  23. // java -jar find.jar /Some/Path \( -name \*.h -or -name \*.cpp \) -and -size +100K
  24. public class Main {
  25.   public static void main(String[] args) throws IOException {
  26.     Executor exec = new ExecutionGenerator().generateExecutor(args);
  27.     exec.Execute();
  28.   }
  29. }

  30. ////////////////////////////////////////////////////////////////////////////////
  31. ///////////////////////////////////// 执行器 ////////////////////////////////////
  32. ////////////////////////////////////////////////////////////////////////////////
  33. class Executor {
  34.   private Path startPath;
  35.   private ArrayList<Option> options;
  36.   private Predicate filterPredicate;
  37.   private ArrayList<Action> actions;
  38.   private ExecutionContext context;

  39.   // 这里利用了Java本身提供的Files.walkFileTree()方法以及FileVisitor回调接口
  40.   // 参考这里的介绍:[url]https://docs.oracle.com/javase/tutorial/essential/io/walk.html[/url]
  41.   private class NodeVistor implements FileVisitor<Path> {
  42.     private FileVisitResult visitFileOrDirectory(Path fileOrDir, BasicFileAttributes attr) {
  43.       // 检查是不是Symbolic link
  44.       if (attr.isSymbolicLink() && !context.shouldFollowSymbolicLink()) {
  45.         return FileVisitResult.SKIP_SUBTREE;
  46.       }
  47.       context.setFilePath(fileOrDir);
  48.       context.setBasicFileAttributes(attr);
  49.       // 谓词(predicate,类似SQL中where语句)求值
  50.       // 如果值为false的话表示当前文件不满足用户设定的过滤条件,那么跳过当前文件
  51.       if (filterPredicate != null && !filterPredicate.evaluate(context)) {
  52.         return FileVisitResult.CONTINUE;
  53.       }
  54.       // 满足过滤条件,首先打印当前路径
  55.       System.out.println(fileOrDir.toString());
  56.       // 然后执行所有actions
  57.       for (Action action : actions) {
  58.         action.invoke(context);
  59.       }
  60.       return FileVisitResult.CONTINUE;
  61.     }
  62.    
  63.     // 访问每一个文件时的回调
  64.     @Override
  65.     public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) {
  66.       return visitFileOrDirectory(file, attrs);
  67.     }
  68.     // 访问每一个目录之前的回调
  69.     @Override
  70.     public FileVisitResult preVisitDirectory(Path dir, BasicFileAttributes attrs) {
  71.       return visitFileOrDirectory(dir, attrs);
  72.     }
  73.     // 访问每一个目录之后的回调
  74.     @Override
  75.     public FileVisitResult postVisitDirectory(Path dir, IOException exc) {
  76.       return FileVisitResult.CONTINUE;
  77.     }
  78.     // 遇到错误时的回调
  79.     @Override
  80.     public FileVisitResult visitFileFailed(Path file, IOException exc) throws IOException {
  81.       return FileVisitResult.CONTINUE;
  82.     }
  83.   }
  84.   
  85.   // 构造函数
  86.   public Executor(Path startPath, ArrayList<Option> options,
  87.                   Predicate filterPredicate, ArrayList<Action> actions) {
  88.     this.startPath = startPath;
  89.     this.options = options;
  90.     this.filterPredicate = filterPredicate;
  91.     this.actions = actions;
  92.   }

  93.   public void Execute() throws IOException {
  94.     context = new ExecutionContext();
  95.     // 首先用options初始化context(例如maxdepth参数)
  96.     for (Option option : options) {
  97.       option.setup(context);
  98.     }
  99.     // 然后初始化actions(例如打开输出文件)
  100.     for (Action action : actions) {
  101.       action.initialize();
  102.     }
  103.     // Walk file tree,利用NodeVistor处理回调
  104.     Files.walkFileTree(startPath, EnumSet.of(FileVisitOption.FOLLOW_LINKS),
  105.                        context.getMaxDepth(), new NodeVistor());
  106.     // actions的完结处理(例如flush并关闭输出文件)
  107.     for (Action action : actions) {
  108.       action.finalize();
  109.     }
  110.   }
  111. }

  112. ////////////////////////////////////////////////////////////////////////////////
  113. //////////////////////////////////// 执行上下文 //////////////////////////////////
  114. ////////////////////////////////////////////////////////////////////////////////
  115. class ExecutionContext {
  116.   // Options
  117.   private int maxDepth = Integer.MAX_VALUE;
  118.   private boolean followSymbolicLink = false;

  119.   // Runtime attributes
  120.   private Path filePath;
  121.   private BasicFileAttributes fileAttr;

  122.   // Getters and setters
  123.   public void setMaxDepth(int maxDepth) {
  124.     this.maxDepth = maxDepth;
  125.   }
  126.   public int getMaxDepth() {
  127.     return maxDepth;
  128.   }
  129.   public void setFollowSymbolicLink() {
  130.     followSymbolicLink = true;
  131.   }
  132.   public boolean shouldFollowSymbolicLink() {
  133.     return followSymbolicLink;
  134.   }
  135.   public void setFilePath(Path filePath) {
  136.     this.filePath = filePath;
  137.   }
  138.   public Path getFilePath() {
  139.     return filePath;
  140.   }
  141.   public void setBasicFileAttributes(BasicFileAttributes fileAttr) {
  142.     this.fileAttr = fileAttr;
  143.   }
  144.   public BasicFileAttributes getBasicFileAttributes() {
  145.     return fileAttr;
  146.   }
  147. }

  148. ////////////////////////////////////////////////////////////////////////////////
  149. /////////////////////////////// 解析参数并生成执行器 //////////////////////////////
  150. ////////////////////////////////////////////////////////////////////////////////
  151. class ExecutionGenerator {
  152.   private static Map<String, OptionParser> optionParserRegistry = new HashMap<>();

  153.   private static void Register(OptionParser parser) {
  154.     optionParserRegistry.put(parser.getName(), parser);
  155.   }

  156.   // 在这里注册所有的OptionParser子类
  157.   static {
  158.     Register(new MaxDepthOptionParser());
  159.     Register(new FollowSymbolicLinkOptionParser());
  160.     Register(new FileTypeFilterParser());
  161.     Register(new FileNameFilterParser());
  162.     Register(new FileSizeFilterParser());
  163.     Register(new WriteToFileActionParser());
  164.   }

  165.   private Stack<String> tokens;

  166.   // 给定输入参数,生成执行器
  167.   // 这里包含了一个简易的LL(1) recursive descent parser
  168.   public Executor generateExecutor(String[] args) {
  169.     tokens = new Stack<String>();
  170.     for (int i = args.length - 1; i >= 0; --i) {
  171.       tokens.push(args[i]);
  172.     }
  173.    
  174.     if (tokens.empty()) {
  175.       throw new RuntimeException("Requires at least one path argument");
  176.     }
  177.     final Path filePath = Paths.get(tokens.pop());

  178.     ArrayList<Option> options = new ArrayList<>();
  179.     ArrayList<Predicate> predicates = new ArrayList<>();
  180.     ArrayList<Action> actions = new ArrayList<>();
  181.    
  182.     while (!tokens.empty()) {
  183.       PlanNode node = parseOr();
  184.       switch (node.getKind()) {
  185.         case OPTION: options.add((Option)node); break;
  186.         case PREDICATE: predicates.add((Predicate)node); break;
  187.         case ACTION: actions.add((Action)node); break;
  188.         default:
  189.           throw new RuntimeException("Unsupport enum value " + node.getKind().name());
  190.       }
  191.     }
  192.    
  193.     Predicate filterPredicate = null;
  194.     if (predicates.size() == 1) {
  195.       filterPredicate = predicates.get(0);
  196.     } else if (predicates.size() > 1) {
  197.       filterPredicate = new LogicalAnd(predicates);
  198.     }
  199.    
  200.     tokens = null;
  201.     return new Executor(filePath, options, filterPredicate, actions);
  202.   }

  203.   // 解析 "... -or ..." 这样的输入
  204.   private PlanNode parseOr() {
  205.     ArrayList<PlanNode> operands = new ArrayList<>();
  206.     operands.add(parseAnd());
  207.     while (nextTokenIs("-or") || nextTokenIs("-o")) {
  208.       tokens.pop();
  209.       operands.add(parseAnd());
  210.     }
  211.     if (operands.size() == 1) {
  212.       return operands.get(0);
  213.     }
  214.     ArrayList<Predicate> predicates = new ArrayList<>();
  215.     for (PlanNode node : operands) {
  216.       if (node.getKind() != PlanNodeKind.PREDICATE) {
  217.         throw new RuntimeException("Logical OR can only be applied to predicates");
  218.       }
  219.       predicates.add((Predicate)node);
  220.     }
  221.     return new LogicalOr(predicates);
  222.   }

  223.   // 解析 "... -and ..." 这样的输入
  224.   private PlanNode parseAnd() {
  225.     ArrayList<PlanNode> operands = new ArrayList<>();
  226.     operands.add(parseNot());
  227.     while (nextTokenIs("-and") || nextTokenIs("-a")) {
  228.       tokens.pop();
  229.       operands.add(parseNot());
  230.     }
  231.     if (operands.size() == 1) {
  232.       return operands.get(0);
  233.     }
  234.     ArrayList<Predicate> predicates = new ArrayList<>();
  235.     for (PlanNode node : operands) {
  236.       if (node.getKind() != PlanNodeKind.PREDICATE) {
  237.         throw new RuntimeException("Logical AND can only be applied to predicates");
  238.       }
  239.       predicates.add((Predicate)node);
  240.     }
  241.     return new LogicalAnd(predicates);
  242.   }

  243.   // 解析 "-not ..." 这样的输入
  244.   private PlanNode parseNot() {
  245.     boolean negate = false;
  246.     if (nextTokenIs("-not") || nextTokenIs("-n")) {
  247.       tokens.pop();
  248.       negate = true;
  249.     }
  250.     PlanNode operand = parseAtom();
  251.     if (!negate) {
  252.       return operand;
  253.     }
  254.     if (operand.getKind() != PlanNodeKind.PREDICATE) {
  255.       throw new RuntimeException("Logical NOT can only be applied to a predicate");
  256.     }
  257.     return new LogicalNot((Predicate)operand);
  258.   }

  259.   // 解析括号表达式 "( ... )" 或者是基础的 Option / Filter / Action
  260.   private PlanNode parseAtom() {
  261.     if (nextTokenIs("(")) {
  262.       tokens.pop();
  263.       PlanNode node = parseOr();
  264.       if (!nextTokenIs(")")) {
  265.         throw new RuntimeException("Unmatched parenthesis");
  266.       }
  267.       tokens.pop();
  268.       return node;
  269.     }
  270.     if (tokens.isEmpty()) {
  271.       throw new RuntimeException("Unexpected end of input stream");
  272.     }
  273.     if (!tokens.peek().startsWith("-")) {
  274.       throw new RuntimeException("Unexpected token " + tokens.peek());
  275.     }
  276.     // 这个name就是参数名,例如-type的"type",-size的"size"
  277.     final String name = tokens.pop().substring(1);
  278.     // 在registry中找到与参数名对应的parser
  279.     final OptionParser parser = optionParserRegistry.get(name);
  280.     if (parser == null) {
  281.       throw new RuntimeException("Unrecognized option " + name);
  282.     }
  283.     // Parser各自的parse()方法用于解析参数的arguments
  284.     // 例如 -size +1M,那么"size"所对应的parser应当知道如何解析"+1M"
  285.     return parser.parse(tokens);
  286.   }

  287.   private boolean nextTokenIs(String value) {
  288.     return !tokens.isEmpty() && value.equals(tokens.peek());
  289.   }
  290. }

  291. ////////////////////////////////////////////////////////////////////////////////
  292. ////////////////////// Option/ Predicate / Action 的抽象 ////////////////////////
  293. ////////////////////////////////////////////////////////////////////////////////

  294. // 这边是OOP设计比较重要的部分

  295. enum PlanNodeKind {
  296.   OPTION, PREDICATE, ACTION
  297. }

  298. // Option/Predicate/Action的基类
  299. abstract class PlanNode {
  300.   public abstract PlanNodeKind getKind();
  301. }

  302. // 继承这个类以添加一个新的Option
  303. abstract class Option extends PlanNode {
  304.   // 每个Option需要实现setup()方法以配置ExecutionContext
  305.   public abstract void setup(ExecutionContext context);
  306.   @Override
  307.   public PlanNodeKind getKind() {
  308.     return PlanNodeKind.OPTION;
  309.   }
  310. }

  311. // 继承这个类以添加一个新的Predicate
  312. abstract class Predicate extends PlanNode {
  313.   // 每个Predicate需要实现evaluate()方法以过滤当前访问的文件或目录
  314.   public abstract boolean evaluate(ExecutionContext context);
  315.   @Override
  316.   public PlanNodeKind getKind() {
  317.     return PlanNodeKind.PREDICATE;
  318.   }
  319. }

  320. // 继承这个类以添加一个新的Action
  321. abstract class Action extends PlanNode {
  322.   // 每个Action需要实现invoke()方法以针对当前访问的文件或目录作出对应操作
  323.   public abstract void invoke(ExecutionContext context);
  324.   public void initialize() {}
  325.   public void finalize() {}
  326.   @Override
  327.   public PlanNodeKind getKind() {
  328.     return PlanNodeKind.ACTION;
  329.   }
  330. }

  331. // Filter也就是GNU find官方文档上所说的"tests"
  332. // 例如:
  333. //   -name a.txt
  334. //   -size +1MB
  335. //   -type f
  336. // 这些都是Filter
  337. // 继承这个类以添加一个新的Filter
  338. abstract class Filter extends Predicate {}

  339. // Option/Filter/Action的解析器基类
  340. abstract class OptionParser {
  341.   // 该解析器所处理的参数名,例如"maxdepth","type","size"
  342.   public abstract String getName();
  343.   // 解析逻辑的实现
  344.   public abstract PlanNode parse(Stack<String> args);
  345. }

  346. ////////////////////////////////////////////////////////////////////////////////
  347. ///////////////////// 逻辑联结词 And/Or/Not (与/或/非) 的实现 //////////////////////
  348. ////////////////////////////////////////////////////////////////////////////////

  349. // 逻辑“与”
  350. class LogicalAnd extends Predicate {
  351.   private ArrayList<Predicate> operands;
  352.   public LogicalAnd(ArrayList<Predicate> operands) {
  353.     this.operands = operands;
  354.   }
  355.   // “与”操作返回true当且仅当所有子谓词都返回true
  356.   @Override
  357.   public boolean evaluate(ExecutionContext context) {
  358.     for (final Predicate operand : operands) {
  359.       if (!operand.evaluate(context)) {
  360.         return false;
  361.       }
  362.     }
  363.     return true;
  364.   }
  365. }

  366. // 逻辑“或”
  367. class LogicalOr extends Predicate {
  368.   private ArrayList<Predicate> operands;
  369.   public LogicalOr(ArrayList<Predicate> operands) {
  370.     this.operands = operands;
  371.   }
  372.   // “或”操作返回true当且仅当任意一个子谓词返回true
  373.   @Override
  374.   public boolean evaluate(ExecutionContext context) {
  375.     for (final Predicate operand : operands) {
  376.       if (operand.evaluate(context)) {
  377.         return true;
  378.       }
  379.     }
  380.     return false;
  381.   }
  382. }

  383. // 逻辑“非”
  384. class LogicalNot extends Predicate {
  385.   private Predicate operand;
  386.   public LogicalNot(Predicate operand) {
  387.     this.operand = operand;
  388.   }
  389.   // “非”操作返回true当且仅当子谓词返回false
  390.   @Override
  391.   public boolean evaluate(ExecutionContext context) {
  392.     return !operand.evaluate(context);
  393.   }
  394. }

  395. ////////////////////////////////////////////////////////////////////////////////
  396. //////////////////////// Option/ Filter / Action 的子类 /////////////////////////
  397. ////////////////////////////////////////////////////////////////////////////////

  398. // 添加一个新的Filter / Action大部分情况下只需要继承并实现相应的基类以及OptionParser基类
  399. // 添加一个新的Option可能还需要修改ExecutionContext并在Executor中做对应修改

  400. // 查找时的最大深度,例如:
  401. // -maxdepth 10
  402. class MaxDepthOption extends Option {
  403.   private int maxDepth;
  404.   public MaxDepthOption(int maxDepth) {
  405.     this.maxDepth = maxDepth;
  406.   }
  407.   @Override
  408.   public void setup(ExecutionContext context) {
  409.     context.setMaxDepth(maxDepth);
  410.   }
  411. }
  412. class MaxDepthOptionParser extends OptionParser {
  413.   @Override
  414.   public String getName() {
  415.     return "maxdepth";
  416.   }

  417.   @Override
  418.   public PlanNode parse(Stack<String> args) {
  419.     return new MaxDepthOption(Integer.parseInt(args.pop()));
  420.   }
  421. }

  422. // 是否处理symbolic link:
  423. // -L
  424. class FollowSymbolicLinkOption extends Option {
  425.   @Override
  426.   public void setup(ExecutionContext context) {
  427.     context.setFollowSymbolicLink();
  428.   }
  429. }
  430. class FollowSymbolicLinkOptionParser extends OptionParser {
  431.   @Override
  432.   public String getName() {
  433.     return "L";
  434.   }
  435.   @Override
  436.   public PlanNode parse(Stack<String> args) {
  437.     return new FollowSymbolicLinkOption();
  438.   }
  439. }

  440. // 设定查找的是文件还是目录,例如:
  441. // -type f
  442. // -type d
  443. class FileTypeFilter extends Filter {
  444.   public enum FileType {
  445.     DIRECTORY, FILE
  446.   }
  447.   private FileType targetFileType;
  448.   public FileTypeFilter(FileType targetFileType) {
  449.     this.targetFileType = targetFileType;
  450.   }
  451.   @Override
  452.   public boolean evaluate(ExecutionContext context) {
  453.     switch (targetFileType) {
  454.     case FILE:
  455.       return context.getBasicFileAttributes().isRegularFile();
  456.     case DIRECTORY:
  457.       return context.getBasicFileAttributes().isDirectory();
  458.     }
  459.     throw new RuntimeException("Unsupported enum value: " + targetFileType.name());
  460.   }
  461. }
  462. class FileTypeFilterParser extends OptionParser {
  463.   @Override
  464.   public String getName() {
  465.     return "type";
  466.   }
  467.   @Override
  468.   public PlanNode parse(Stack<String> args) {
  469.     final String param = args.pop();
  470.     switch (param) {
  471.     case "f":
  472.       return new FileTypeFilter(FileTypeFilter.FileType.FILE);
  473.     case "d":
  474.       return new FileTypeFilter(FileTypeFilter.FileType.DIRECTORY);
  475.     }
  476.     throw new RuntimeException("Unsupport file type: " + param);
  477.   }
  478. }

  479. // 设定文件名glob pattern,例如:
  480. // -name a.txt
  481. // -name \*.txt
  482. // -name \*data\*.txt
  483. // 注意命令行下不能直接写-name *.txt,否则glob会把*.txt展开为当前目录下的所有match的文件
  484. class FileNameFilter extends Filter {
  485.   private PathMatcher pathMatcher;
  486.   public FileNameFilter(PathMatcher pathMatcher) {
  487.     this.pathMatcher = pathMatcher;
  488.   }
  489.   @Override
  490.   public boolean evaluate(ExecutionContext context) {
  491.     final Path filePath = context.getFilePath();
  492.     return pathMatcher.matches(filePath) ||
  493.            pathMatcher.matches(filePath.getFileName());
  494.   }
  495. }
  496. class FileNameFilterParser extends OptionParser {
  497.   @Override
  498.   public String getName() {
  499.     return "name";
  500.   }
  501.   @Override
  502.   public PlanNode parse(Stack<String> args) {
  503.     return new FileNameFilter(FileSystems.getDefault().getPathMatcher("glob:" + args.pop()));
  504.   }
  505. }

  506. // 过滤文件size,例如:
  507. // -size 1MB
  508. // -size +1KB
  509. // -size -1GB
  510. class FileSizeFilter extends Filter {
  511.   public enum OpType {
  512.     EQUAL, GREATER_EQUAL, LESS_EQUAL
  513.   }

  514.   private long targetFileSize;
  515.   private OpType op;

  516.   public FileSizeFilter(OpType op, long targetFileSize) {
  517.     this.op = op;
  518.     this.targetFileSize = targetFileSize;
  519.   }
  520.   @Override
  521.   public boolean evaluate(ExecutionContext context) {
  522.     long fileSize = context.getBasicFileAttributes().size();
  523.     switch (op) {
  524.     case EQUAL:
  525.       return fileSize == targetFileSize;
  526.     case GREATER_EQUAL:
  527.       return fileSize >= targetFileSize;
  528.     case LESS_EQUAL:
  529.       return fileSize <= targetFileSize;
  530.     }
  531.     throw new RuntimeException("Unsupported enum value: " + op.name());
  532.   }
  533. }
  534. class FileSizeFilterParser extends OptionParser {
  535.   @Override
  536.   public String getName() {
  537.     return "size";
  538.   }
  539.   @Override
  540.   public PlanNode parse(Stack<String> args) {
  541.     String param = args.pop();
  542.     FileSizeFilter.OpType op = FileSizeFilter.OpType.EQUAL;
  543.     int digitStart = 0;
  544.     if (param.startsWith("+")) {
  545.       op = FileSizeFilter.OpType.GREATER_EQUAL;
  546.       digitStart = 1;
  547.     } else if (param.startsWith("-")) {
  548.       op = FileSizeFilter.OpType.LESS_EQUAL;
  549.       digitStart = 1;
  550.     }
  551.     int digitEnd = digitStart;
  552.     while (digitEnd < param.length() && Character.isDigit(param.charAt(digitEnd))) {
  553.       ++digitEnd;
  554.     }
  555.     if (digitEnd == digitStart) {
  556.       throw new RuntimeException("Invalid file size specification: " + param);
  557.     }
  558.     long targetFileSize = Long.parseLong(param.substring(digitStart, digitEnd));
  559.     if (digitEnd != param.length()) {
  560.       final String unit = param.substring(digitEnd);
  561.       switch (unit.toLowerCase()) {
  562.       case "k":
  563.       case "kb":
  564.         targetFileSize *= 1024;
  565.         break;
  566.       case "m":
  567.       case "mb":
  568.         targetFileSize *= 1024 * 1024;
  569.         break;
  570.       case "g":
  571.       case "gb":
  572.         targetFileSize *= 1024 * 1024 * 1024;
  573.         break;
  574.       default:
  575.         throw new RuntimeException("Invalid file size unit: " + unit);
  576.       }
  577.     }
  578.     return new FileSizeFilter(op, targetFileSize);
  579.   }
  580. }

  581. // 将结果写到某个文件中,例如:
  582. // -writetofile output.txt
  583. class WriteToFileAction extends Action {
  584.   private String fileName;
  585.   private PrintWriter pw;
  586.   public WriteToFileAction(String fileName) {
  587.     this.fileName = fileName;
  588.   }
  589.   @Override
  590.   public void initialize() {
  591.     try {
  592.       pw = new PrintWriter(fileName);
  593.     } catch (FileNotFoundException e) {
  594.       throw new RuntimeException(e);
  595.     }
  596.   }
  597.   @Override
  598.   public void finalize() {
  599.     pw.close();
  600.   }
  601.   @Override
  602.   public void invoke(ExecutionContext context) {
  603.     pw.println(context.getFilePath());
  604.   }
  605. }
  606. class WriteToFileActionParser extends OptionParser {
  607.   @Override
  608.   public String getName() {
  609.     return "writetofile";
  610.   }
  611.   @Override
  612.   public PlanNode parse(Stack<String> args) {
  613.     return new WriteToFileAction(args.pop());
  614.   }
  615. }
复制代码

评分

参与人数 33大米 +102 收起 理由
sas鹰uke + 1 给你点个赞!
wljfrost + 1 很有用的信息!
JerryWuX + 3 给你点个赞!
mela3 + 1 很有用的信息!
ddii + 2 很有用的信息!

查看全部评分

回复

使用道具 举报

推荐
magicsets 2019-4-20 13:36:32 | 只看该作者
全局:
多shy一girl 发表于 2019-4-19 23:15
您好楼主,您写的代码很好看,讲解的很透彻,但是有一些点没看懂想请教下,在generateExecutor 处理token ...

or/and/not的优先级(结合性)是依次升高的,就和加减乘除一样,一个表达式不一定是从左往右计算。比如说 A -or B -and C 的运算顺序是 A -or ( B -and C ),而不是 (A -or B) -and C

现在我们要写一个parser来正确地解析A -or B -and C这样的表达式,那么这个parser其实有若干种写法:
--
(1) 可以用解LeetCode上计算器题目的那种stack的方法,其本质上是一个下推自动机(但是扩展性不好不适合处理复杂情况)
(2) 可以写一个LR parser,主要是构造并使用一个shift-reduce跳转表
(3) 可以写一个LL parser,也叫“递归下降解析器”,主要是写一堆递归方法层层调用..
--

然后上面代码用的方法是(3)。至于为什么是parseOr()里面调用parseAnd(),然后parseAnd()里面调用parseNot().. 这和LL文法的结构有关,可以参考一下这篇知乎文章:
https://zhuanlan.zhihu.com/p/31271879

里面提到了一个算数表达式的例子(也就是计算器了)可以仔细看一下,+/* 本质上和 or/and 是一样的处理

评分

参与人数 4大米 +5 收起 理由
pengchaoandy + 1 很有用的信息!
leecx22 + 1 很有用的信息!
風行烈 + 1 给你点个赞!
多shy一girl + 2 感谢~

查看全部评分

回复

使用道具 举报

推荐
laomao2021 2021-7-1 07:19:29 | 只看该作者
全局:
这道题确实是很高频的香蕉题,我拿这道题面过一些人,也曾经在同一个interview loop里看到别人面这道题。诉求(assigned competencies)不一样,对candidate的期待也不同。尤其是当assigned competency里还有deal with ambiguity的时候,大家都会把题面弄得一样,可实际上,如果candidate直接假定了面试官大概期待什么,最后八成要挂。

所以说,具体面试官期待怎样的答案是需要candidate通过沟通来发现的。建议先问面试官如下问题再开始设计和码代码:

1. 我对Linux的command line不熟悉,你能不能举例说明?
2. 还是不太明白题目的要求,能不能提供main函数,这样我能感受一下调用的过程?
3. 这个命令看起来很powerful,能不能举例看看我要优先实现哪些功能?
4. 我能不能假设有一些API是可以用的,比如说,输入是一个路径,输出是路径下所有文件?
5. 我能不能假设软链接的情况不存在?
6. 在做类的架构之前,能不能具体说说该功能的用户未来可能需要哪方面的扩展呢?

评分

参与人数 2大米 +3 收起 理由
xiaoyu20 + 1 很有用的信息!
Myron2017 + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
jackli31742 2019-1-20 20:41:19 | 只看该作者
全局:
这不就是用命令吗,还能怎么考…
回复

使用道具 举报

🔗
IamForrest 2019-2-28 00:59:25 | 只看该作者
本楼:
全局:
同问同问!
回复

使用道具 举报

🔗
redemptionnuo 2019-2-28 01:16:55 | 只看该作者
全局:
类似 Trie,练习recursive, 不放心再看看 linux find 的source code
回复

使用道具 举报

🔗
joezie 2019-3-1 01:47:35 | 只看该作者
全局:
我找到了这个网站,估计可以解答楼主的问题吧~
https://www.mkyong.com/java/sear ... y-for-file-in-java/
最后求一波大米嘻嘻

补充内容 (2019-3-1 01:48):
还想问一下楼主申的fulltime还是intern呀

评分

参与人数 3大米 +6 收起 理由
孙行者 + 1 给你点个赞!
的萨菲 + 2 很有用的信息!
IamForrest + 3 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
airicaruss 2019-4-18 01:13:50 | 只看该作者
全局:
Thanks for sharing!
回复

使用道具 举报

本楼:
全局:
谢谢分享
回复

使用道具 举报

🔗
多shy一girl 2019-4-19 23:15:56 | 只看该作者
全局:
magicsets 发表于 2019-3-10 07:03
最近有点时间我来稍微写一下这个问题..

Linux的find命令其实还是相当复杂的一个命令,参数种类很多,官 ...

您好楼主,您写的代码很好看,讲解的很透彻,但是有一些点没看懂想请教下,在generateExecutor 处理token的时候,为啥是先call pareOr() 然后在看到-or token的时候再parseAnd()在parseAnd 时候看到not call parseNot()。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表