Simplificando un camino -- java campo con algorithm campo con interview-questions camp codereview Relacionados El problema

Simplifying a path


7
vote

problema

Español

Por favor, sea super brutal y trate esto como una entrevista técnica principal.

El peor análisis de caso: $ O (n) $ (confirme)

complejidad espacial: $ O (n) $

problema:

Dada una ruta absoluta para un archivo (estilo unix), simplifícelo.

Por ejemplo:

  path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c"   

Casos de esquina: ¿Consideró el caso donde la ruta = 9988777665544334 ? En esto Caso, debe devolver / . Otra caja de la esquina es el camino. Contiene múltiples barras / JUNTOS, como /home//foo/ . En esto Caso, debe ignorar las barras redundantes y devolver /home/foo .

Mi intento:

  private static String simplifyPath(String path) {     Deque<String> pathDeterminer = new ArrayDeque<String>();     String[] pathSplitter = path.split("/");     StringBuilder absolutePath = new StringBuilder();     for(String term : pathSplitter){         if(term == null || term.length() == 0 || term.equals(".")){             /*ignore these guys*/         }else if(term.equals("..")){             if(pathDeterminer.size() > 0){                 pathDeterminer.removeLast();             }         }else{             pathDeterminer.addLast(term);         }     }     if(pathDeterminer.isEmpty()){         return "/";     }     while(! pathDeterminer.isEmpty()){         absolutePath.insert(0, pathDeterminer.removeLast());         absolutePath.insert(0, "/");     }     return absolutePath.toString();  }   
Original en ingles

Please be super brutal, and treat this as a top technical interview.

Worst case analysis: \$O(n)\$ (please confirm)

Space complexity: \$O(n)\$

Problem:

Given an absolute path for a file (Unix-style), simplify it.

For example:

path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" 

Corner Cases: Did you consider the case where path = /../? In this case, you should return /. Another corner case is the path might contain multiple slashes / together, such as /home//foo/. In this case, you should ignore redundant slashes and return /home/foo.

My attempt:

private static String simplifyPath(String path) {     Deque<String> pathDeterminer = new ArrayDeque<String>();     String[] pathSplitter = path.split("/");     StringBuilder absolutePath = new StringBuilder();     for(String term : pathSplitter){         if(term == null || term.length() == 0 || term.equals(".")){             /*ignore these guys*/         }else if(term.equals("..")){             if(pathDeterminer.size() > 0){                 pathDeterminer.removeLast();             }         }else{             pathDeterminer.addLast(term);         }     }     if(pathDeterminer.isEmpty()){         return "/";     }     while(! pathDeterminer.isEmpty()){         absolutePath.insert(0, pathDeterminer.removeLast());         absolutePath.insert(0, "/");     }     return absolutePath.toString();  } 
        
       
       

Lista de respuestas

7
 
vote
vote
La mejor respuesta
 

Dentro de los límites de las instrucciones, esta es una buena solución, pero podría hacer con algunos ajustes.

Empezaría con desafiar un poco las suposiciones. Incluso si no manejas los casos extraños, todavía los mencionaría. Las cosas en las que piensan, cuando escucho ", dado un camino absoluto para un archivo (estilo de unix)" son:

  • barras escapadas path/to/file/with/slash.in.name
  • Bueno, eso es todo, en realidad ... otros casos especiales similares a los Unix probablemente no afectarían a este código.

Entonces, probablemente manejaría la barra posterior escapada, probablemente con un aspecto negativo en el regulador SPLIT 9988776655544335 ....

Luego, no me gusta el insert(0, ...) Uso del StringBuilder. Porque conozco a los internos de StringBuilder, sé que es más rápido anexar. Yo trataría a The StringBuilder de manera diferente a usted de 2 maneras:

  1. Configurar el tamaño inicial:

      StringBuilder absolutePath = new StringBuilder(path.length());   
  2. Anexar valores del otro extremo del deque

      while(! pathDeterminer.isEmpty()){     absolutePath.append("/");     absolutePath.append(0, pathDeterminer.removeFirst()); }           

Porque su código utiliza el mecanismo de StringBuilder.insert (0, ...), y debido a que es una operación $ O (N) $ (porque tiene que mover todos los otros caracteres que vienen después del valor insertado ), la complejidad general del Código no es $ O (N) $, pero más bien $ O (n ^ 2) $. Cambiar a un Anexo para recuperar el código (más cerca) a $ O (n) $, donde cada personaje se copia solo una vez ...

ver las diferencias entre:

  • stringbuilder.append ()
  • stringbuilder.insert (0, ...)
 

Within the limits of the instructions, this is a good solution, but could do with some tweaks.

I would start with challenging the assumptions a little bit. Even if you don't handle the odd cases, I would still mention them. The things I am think of, when I hear "Given an absolute path for a file (Unix-style)" are:

  • escaped slashes path/to/file\/with\/slash.in.name
  • well, that's about it, actually... other unix-like special cases probably would not affect this code.

So, I would probably handle the escaped-backslash, probably with a negative-look-behind on the split regex path.split("(?!\\\\)/")....

Then, I dislike the insert(0, ...) use of the StringBuilder. Because I know the internals of StringBuilder, I know that it is faster to append. I would treat the StringBuilder differently to you in 2 ways:

  1. Set the initial size:

    StringBuilder absolutePath = new StringBuilder(path.length()); 
  2. Append values from the other end of the Deque

    while(! pathDeterminer.isEmpty()){     absolutePath.append("/");     absolutePath.append(0, pathDeterminer.removeFirst()); }         

Because your code uses the StringBuilder.insert(0, ...) mechanism, and because that is an \$O(n)\$ operation (because it has to move all the other characters that come after the inserted value), the overall complexity of the code is not \$O(n)\$, but rather \$O(n^2)\$. Changing to an append will bring the code back (closer) to \$O(n)\$, where each character is copied only once....

See the differences between:

  • StringBuilder.append()
  • StringBuilder.insert(0, ...)
 
 
     
     
6
 
vote

En general, es muy fácil de leer y entender su código. Creo que toma buenas opciones de estructuras de datos.

Algunas cosas:

  • No estoy muy aficionado a su formato de espaciado, pero al menos eres consistente, lo que hace que este sea un problema menor. Yo prefiero, y las convenciones de estilo Java son, 9988777665544339

  • int foo(){ for{ //... } } 0 nunca sucederá. Como int foo(){ for{ //... } } 1 es una matriz de cadena adquirida a partir de usar int foo(){ for{ //... } } 2 en una cadena regular, no habrá entradas nulas en la matriz.

  • int foo(){ for{ //... } } 3 int foo(){ for{ //... } } 4 - Use int foo(){ for{ //... } } 5 en su lugar.

  • int foo(){ for{ //... } } 6 Utilizaría un 99887776655443317 Para que sea más claro que realmente deben ignorarse, o usar esto:

      int foo(){     for{          //...        } } 8  

Con respecto a las complejidades: Sí, estoy de acuerdo en que esos son $ O (N) $.

 

Overall, it is very easy to read and understand your code. I think that you make good choices of data structures.

A few things:

  • I'm not very fond of your spacing formatting, but at least you're consistent which makes this a minor issue. I prefer, and the Java styling conventions is, while (!pathDeterminer.isEmpty()) {

  • if(term == null will never happen. As pathSplitter is a String array acquired from using .split on a regular string, there will be no null entries in the array.

  • term.length() == 0 and if(pathDeterminer.size() > 0){ - use .isEmpty() instead.

  • /*ignore these guys*/ I would use a continue; to make it more clear that they really should be ignored, or use this:

    if (term.equals("..")) {     if (!pathDeterminer.isEmpty())         pathDeterminer.removeLast(); } else if (!term.isEmpty() && !term.equals(".")) {     pathDeterminer.addLast(term); } 

Regarding the complexities: Yes, I agree that those are \$O(n)\$.

 
 
2
 
vote

Espero que la función funcione con caminos absolutos o relativos. Si lo paso un camino relativo como un parámetro, espero que haya vuelto una ruta relativa.

 

I would expect the function to work with either absolute or relative paths. If I pass it a relative path as a parameter, I expect a relative path returned.

 
 

Relacionados problema

1  Cuenta las precipitaciones acumuladas en una cadena de montaña 2D  ( Count the accumulated rainfall in a 2d mountain range ) 
desafío: cuenta cuánta lluvia se recogerá en los valles entre los picos de una cordillera en un mundo 2D. La gama de montaña se define por una única ...

3  Tarea de entrevista de juego de blackjack  ( Blackjack game interview task ) 
Como parte de una entrevista reciente, me asignaron escribir un pequeño programa de blackjack. Después de enviar la solución, recibí una respuesta que "la sol...

2  Contando un ciclo  ( Counting a cycle ) 
Una pregunta de entrevista que tengo - Cada elemento de un int Matriz puntos al otro elemento, eventualmente creando un ciclo. A partir de array[0] , ...

2  Cola de bloqueo delimitada  ( Bounded blocking queue ) 
¿Puede alguien por favor revise este código para mí? No he implementado todos los métodos para la simplicidad. NSUSerDefaults1 Preguntas abiertas: l...

3  Codificación de longitud de ejecución  ( Run length encoding ) 
Dada una cadena de entrada, escriba una función que devuelva la longitud de ejecución Cadena codificada para la cadena de entrada. Por ejemplo, si la cad...

5  Compruebe si dos cadenas son permutaciones entre sí  ( Check if two strings are permutations of one another ) 
Estoy trabajando en mi camino a través de "Cracking The Coding Entrevistion" problemas y ha terminado de implementar esta pregunta: "Dadas, dos cuerdas, escri...

8  Escriba un método para reemplazar todos los espacios en una cadena con% 20  ( Write a method to replace all spaces in a string with 20 ) 
He implementado una solución a este agrietamiento la pregunta de la entrevista de codificación: Escriba un método para reemplazar todos los espacios en una ...

18  Invirtiendo una cadena  ( Reversing a string ) 
Tuve esto como una pregunta de entrevista, y el entrevistador señaló esto. Esto es lo que escribí: //C# Syntax here public string Reverse(string s) { c...

3  Invertir un mapa de puntuación de letras de Scrabble  ( Inverting a scrabble letter score map ) 
Pregunta: El sistema antiguo almacenó una lista de letras por puntaje: 1 punto: "A", "E", "I", "O", "U", "L", "N", "R", "S", "T", 2 puntos: "D", "G", ...

11  Optimizando el corrector de anagramas Java (comparar 2 cadenas)  ( Optimizing java anagram checker compare 2 strings ) 
Un anagrama es como una mezcla de las letras en una cadena: pots es un anagrama de detener wilma es un anagrama de ilwma Estoy pasando por el ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos