semantics - sentences - ¿Qué significa "en el lugar"?
syntax definition (3)
Invierta las palabras en una cadena (las palabras están separadas por uno o más espacios). Ahora hazlo en el lugar.
¿Qué significa in situ?
Debe cambiar el contenido de la cadena original a la inversa sin utilizar una variable de almacenamiento temporal para mantener la cadena.
En el lugar significa que debe actualizar la cadena original en lugar de crear una nueva.
Dependiendo del lenguaje / framework que estés usando, esto podría ser imposible. (Por ejemplo, las cadenas son inmutables en .NET y Java, por lo que sería imposible realizar una actualización in situ de una cadena sin tener que recurrir a algunos ataques maliciosos).
Los algoritmos en el lugar solo pueden usar O(1) espacio adicional, esencialmente. La inversión de matrices (esencialmente a lo que se reduce la pregunta de la entrevista) es un ejemplo clásico. Lo siguiente está tomado de Wikipedia:
Supongamos que queremos revertir una matriz de n elementos. Una forma simple de hacer esto es:
function reverse(a[0..n]) allocate b[0..n] for i from 0 to n b[n - i] = a[i] return bDesafortunadamente, esto requiere
O(n)espacio adicional para crear la matrizb, y la asignación es a menudo una operación lenta. Si ya no necesitamosa, podemos sobrescribirla con su propia inversión utilizando este algoritmo in situ:
function reverse-in-place(a[0..n]) for i from 0 to floor(n/2) swap(a[i], a[n-i])
A veces hacer algo in situ es MUY DIFÍCIL. Un ejemplo clásico es la transposición general de matriz no cuadrada.