public static AlluxioURI findLowestCommonAncestor(Collection<AlluxioURI> paths) {
    if (paths == null || paths.isEmpty()) {
      return null;
    }
    String[] matchedComponents = null;
    int matchedLen = 0;
    for (AlluxioURI path : paths) {
      String[] pathComp = path.getPath().split(AlluxioURI.SEPARATOR);
      if (matchedComponents == null) {
        matchedComponents = pathComp;
        matchedLen = pathComp.length;
        continue;
      }

      for (int i = 0; i < pathComp.length && i < matchedLen; ++i) {
        if (!matchedComponents[i].equals(pathComp[i])) {
          matchedLen = i;
          break;
        }
      }
      // here, either matchedComponents or pathComp is the prefix of one another,
      // if pathComp is the prefix of matchedComponents (e.g. pathComp: ["", "a"]
      // matchedComponents: ["", "a", "b"]), then the lowest common ancestor of
      // pathComp and current matchedComponents is pathComp (the shorter one).
      if (matchedLen > pathComp.length) {
        matchedLen = pathComp.length;
      }
    }
    return new AlluxioURI(PathUtils.concatPath(AlluxioURI.SEPARATOR,
        Arrays.copyOf(matchedComponents, matchedLen)));
  }
@Test
  public void findLowestCommonAncestor() {
    assertNull(PathUtils.findLowestCommonAncestor(null));
    assertNull(PathUtils.findLowestCommonAncestor(Collections.EMPTY_LIST));

    ArrayList<AlluxioURI> paths = new ArrayList<>();

    paths.add(new AlluxioURI("/"));
    assertEquals("/", PathUtils.findLowestCommonAncestor(paths).getPath());

    paths.clear();
    paths.add(new AlluxioURI("/"));
    paths.add(new AlluxioURI("/a/b/c/d"));
    paths.add(new AlluxioURI("/a/b/c/d/e/f"));
    assertEquals("/", PathUtils.findLowestCommonAncestor(paths).getPath());

    paths.clear();
    paths.add(new AlluxioURI("/a"));
    paths.add(new AlluxioURI("/a/b"));
    paths.add(new AlluxioURI("/aaa/b"));
    assertEquals("/", PathUtils.findLowestCommonAncestor(paths).getPath());

    paths.clear();
    paths.add(new AlluxioURI("/a/b/"));
    assertEquals("/a/b", PathUtils.findLowestCommonAncestor(paths).getPath());

    paths.clear();
    paths.add(new AlluxioURI("/a/b/c"));
    paths.add(new AlluxioURI("/a"));
    paths.add(new AlluxioURI("/a/b/c/d"));
    assertEquals("/a", PathUtils.findLowestCommonAncestor(paths).getPath());

    paths.clear();
    paths.add(new AlluxioURI("/a"));
    assertEquals("/a", PathUtils.findLowestCommonAncestor(paths).getPath());

    paths.add(new AlluxioURI("/a/b"));
    assertEquals("/a", PathUtils.findLowestCommonAncestor(paths).getPath());

    paths.clear();
    paths.add(new AlluxioURI("/a/c"));
    paths.add(new AlluxioURI("/a/d/"));
    assertEquals("/a", PathUtils.findLowestCommonAncestor(paths).getPath());

    paths.add(new AlluxioURI("/b/a/"));
    assertEquals("/", PathUtils.findLowestCommonAncestor(paths).getPath());

    paths.clear();
    paths.add(new AlluxioURI("/a/b/c"));
    paths.add(new AlluxioURI("/a/b/d"));
    paths.add(new AlluxioURI("/a/b/e"));
    assertEquals("/a/b", PathUtils.findLowestCommonAncestor(paths).getPath());

    paths.clear();
    String prefix = "/a/b/c";
    for (int i = 0; i < 10; i++) {
      for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 10; k++) {
          paths.add(new AlluxioURI(String.format("%s/%d/%d/%d", prefix, i, j, k)));
        }
      }
    }
    assertEquals(prefix, PathUtils.findLowestCommonAncestor(paths).getPath());
  }