Preguntas de entrevista de mazo de cartas y matriz dispersa [cerrado]

7

Acabo de tener una pantalla técnica del teléfono con una puesta en marcha. Aquí están las preguntas técnicas que me hicieron ... y mis respuestas. ¿Qué piensan de estas respuestas ? Siéntase libre de publicar mejores respuestas :-)

Pregunta 1 : ¿cómo representarías un mazo de 52 cartas estándar (básicamente cualquier idioma)? ¿Cómo barajarías la baraja?

Respuesta : utiliza una matriz que contiene una estructura o clase "Tarjeta". Cada instancia de tarjeta tiene algún identificador único ... ya sea su posición en la matriz o una variable de miembro entero única en el rango [0, 51]. Mezcla las tarjetas atravesando la matriz una vez del índice cero al índice 51. Cambia aleatoriamente la tarjeta con "otra tarjeta" (no recuerdo cómo funciona exactamente este algoritmo de reproducción aleatoria). Tenga cuidado con el uso de la probabilidad misma para cada tarjeta ... eso es un problema en este algoritmo. Mencioné que el algoritmo es de Perlas de programación .

Pregunta 2 : ¿cómo representar una gran matriz dispersa? la matriz puede ser muy grande ... como 1000x1000 ... pero solo un número relativamente pequeño (~ 20) de las entradas no son cero.

Respuesta : condense la matriz en una lista de las entradas que no sean cero. para una entrada dada (i, j) en la matriz ... "mapear" (i, j) a un solo entero k ... luego use k como una clave en un diccionario o tabla hash. Para el mapa de matriz dispersa de 1000x1000 (i, j) para k usando algo como f (i, j) = i + j * 1001. 1001 es solo uno más el máximo de todos los i y j. No recuerdo exactamente cómo funcionó este mapeo ... pero el entrevistador tuvo la idea (creo).

¿Son estas buenas respuestas ? Me pregunto porque, después de terminar la segunda pregunta, el entrevistador dijo: "bueno, eso es todo lo que tengo por ahora".

¡Salud!

    
pregunta MrDatabase 25.02.2011 - 22:36

9 respuestas

4

Es un buen comienzo con las cartas. Esta es mi idea si desea obtener un modelado más realista: debe tener en cuenta el hecho de que una baraja puede contener más o menos de 52 cartas (por ejemplo, si tiene comodines, o si es una baraja de euchre, etc.). Entonces, en lugar de una matriz, tal vez una lista enumerable genérica (como% C_de% de C #). Eso también facilitaría la inserción y eliminación de tarjetas individuales (por ejemplo, para simular transacciones).

Luego, para barajar, puedes dividir esa lista en dos pilas de tamaño arbitrario, sacar las tarjetas de la parte superior y colocarlas en una tercera lista, seleccionando al azar de qué mitad elegir cada vez. Eso sería más realista.

En cuanto a la segunda pregunta, eso me parece razonable.

    
respondido por el Andrew Arnold 25.02.2011 - 22:57
3

Bueno, barajar de forma estadísticamente correcta es sorprendentemente difícil . Ya que sé que es complicado, simplemente lo busco para estar seguro de que lo estoy haciendo correctamente.

Si lo programa usted mismo, asegúrese de dejar que se ejecute unos pocos miles de veces para ver si es correcto. Y señale eso al revisor.

    
respondido por el Carra 26.02.2011 - 00:50
3
  

Pregunta 1: ¿cómo representaría a un   baraja estándar de 52 cartas en (básicamente   cualquier idioma)? ¿Cómo barajarías?   la cubierta?

En Java, usaría:

  1. ArrayList<Card> deck como tipo de datos y nombre.
  2. Collections.shuffle(deck) o Collections.shuffle(deck, myRnd) para barajar la baraja.
  

Pregunta 2: ¿cómo representar una gran matriz dispersa? la matriz puede ser muy grande ... como 1000x1000 ... pero solo un número relativamente pequeño (~ 20) de las entradas no son cero.

En Java, solo almacenaría elementos distintos de cero, en:

  1. HashMap<TupleN, Data> matrix como un tipo de datos en el caso general, donde TupleN es una clase de valor (con una función hash personalizada) y contiene ubicaciones de elementos.
  2. En el caso de 2 dimensiones, las combinaría en el tipo largo HashMap<Long, Data> m y usaría m.get(((Long)i1<<32)+i2); , si necesito un elemento.
respondido por el Margus 26.02.2011 - 02:50
2

No es la mejor técnica para clasificar tarjetas.
Ver Kneuth para más detalles.

Un mejor algoritmo es:

 1) Have a deck of all cards (a)
 2) Have a deck with 0 cards (b)
 3) Pick one card at random from (a) and remove it.
 4) Add picked card to top of (b)
 5) While (a) is not empty goto (3)
 6) (b) is now shuffled.

Tenga en cuenta que al implementar esto, puede usar una sola plataforma. El secreto es que una vez que se ha seleccionado una carta, nunca se vuelve a seleccionar (es decir, una vez que se mueve a la baraja barajada no se toca).

    
respondido por el Martin York 26.02.2011 - 00:14
2

En la segunda pregunta, me habría preguntado qué operaciones queríamos optimizar en la matriz. La mejor implementación de una matriz dispersa parece depender de las operaciones que se realizan.

    
respondido por el Winston Ewert 26.02.2011 - 00:42
1

Yo diría que para ser honesto, ya que sé que hay personas más inteligentes que yo que ya han resuelto un problema como ese, y como nunca he pasado mucho tiempo pensando en ello en particular porque no aparece con frecuencia En la programación de red integrada, comenzaría por buscar algoritmos publicados o bibliotecas de terceros. ¿Quieres que me tome un par de minutos para hacer una búsqueda, o simplemente te digo lo mejor que puedo hacer por mi cuenta?

El "mejor que pueda encontrar por mi cuenta" es muy similar al tuyo, aunque podría entrar en más detalles de la aplicación, como las estructuras de datos necesarias para garantizar que una tarjeta no se duplique entre las manos, "vista" de una tarjeta versus "modelo", etc.

    
respondido por el Karl Bielefeldt 26.02.2011 - 04:04
1

La respuesta a ambas preguntas realmente es "Depende de lo que quieras hacer con él".

Una carta de juego se puede considerar como un elemento del producto cartesiano de valores y trajes y se puede implementar como un par que compone dos enums. Ideal para clases de OO a nivel escolar. Pero si está implementando, digamos, la evaluación de la mano de póquer optimizada para un sistema con memoria limitada (es decir, no puede usar un FSM de 2GB), entonces esa no es una representación útil. Cuando hice esto (en parte por el problema relevante del Proyecto Euler, en parte porque un amigo expresó interés), utilicé un int per card de 64 bits con representación de bits 23456789TJQKA00200300400500600700800900T00J00Q00K00A00C00D00H00S porque el bit fiddling puede obtener una gran cantidad de propiedades muy rápido.

Para matrices dispersas, realmente tienes que pensar qué tipo de matrices estás implementando y qué quieres hacer con ellas. Las matrices diagonales, por ejemplo, son susceptibles de una implementación muy especializada.

    
respondido por el Peter Taylor 26.02.2011 - 00:29
0

¿Esto no garantizaría que no vuelvas a tocar un elemento ya colocado?

for (i = 51; i >= 2; i--) {
  swap(arr[i], arr[rand() % i]);
}

swap(arr[0], arr[1]); //just to be safe.

(refiriéndose a Cuidado, use la misma probabilidad para cada tarjeta ... eso es un problema en este algoritmo).

    
respondido por el waka-waka 08.05.2013 - 03:57
-1

Básicamente, la mezcla de medios significa que el resultado final debe ser lo más aleatorio posible (nadie debería poder adivinar la secuencia resultante, dada la secuencia original).

Me gusta el enfoque simple de Martin, solo que tu función rand () debería ser buena.

Por cierto, incluso si uso swap algo (sin ninguna restricción en la revisión), eso también debería ser un buen enfoque. la iteración debe ser > = 52/2 = 26 veces.

    
respondido por el Munish Goyal 11.05.2011 - 12:13

Lea otras preguntas en las etiquetas