Experiencia de entrevista de Samsung R&D Bangalore | Contratación lateral (experiencia de 6 meses)

Fue una prueba de codificación de nivel profesional, donde nos dieron 4 horas para resolver un problema.

Hay una carretera que tiene daños en N (4<=N<=100) ubicaciones. Cada ubicación de daño está representada por un número a (0<=a<=10000). Necesitas reparar estos daños con Asphalt. El daño se repara con estas reglas:

1. El asfalto se puede esparcir en la calzada con un tramo mínimo de K (1<=K<=10000) es decir, cada vez que ponga asfalto, se esparcirá en k lugares consecutivos. p.ej. si el daño está en las ubicaciones 2, 5 y K=3, entonces la primera aplicación de asfalto es de 0-2 o 1-3 o 2-4 y la segunda es de 3-5 o 4-6 o 5-7.
2. Debe esparcir asfalto mínimo para reparar todas las ubicaciones dañadas de la carretera. Para el ejemplo anterior, el asfalto mínimo requerido es de 4 unidades (2-4 y 3-5) porque 3-4 se superpone.

Ejemplos de casos de prueba:

Aporte:-

NK

A[0] A[1] …….. A[N-1]

Producción:-

Área mínima de asfalto para reparar todos los daños.

1.

10 2

0 10 2 12 4 14 6 16 8 18

salida: 15

2.

4 3

3 9 11 8

salida: 7

3.

8 3

2 7 20 5 19 9 6 22

salida: 12

¡Por favor, avíseme si hay alguna confusión en la pregunta!