2016-07-14 50 views
5

Ho ricevuto una domanda di intervista e il mio algoritmo ha superato solo casi di test esemplificativi e non ha superato tutti i casi di test.Somma di array unica minima

Domanda: Dato un array intero ordinato, restituisce la somma dell'array in modo che ogni elemento sia univoco aggiungendo alcuni numeri per duplicare gli elementi in modo tale che la somma di elementi univoci sia minima.

I.e., se tutti gli elementi dell'array sono univoci, restituire la somma. Se alcuni elementi sono duplicati, incrementali per assicurarti che tutti gli elementi siano univoci in modo che la somma di questi elementi univoci sia minima.

Alcuni esempi:

  • input1[] = { 2, 3, 4, 5 } =>return 19 = 2 + 3 + 4 + 5 (tutti gli elementi sono unici, quindi basta sommare)
  • input2[] = { 1, 2, 2 } =>return 6 = 1 + 2 +3 (indice 2 è duplicato, così incrementarlo)
  • input3[] = { 2, 2, 4, 5 } =>return 14 = 2 + 3 + 4 + 5 (indice 1 è duplicato, così incrementarlo)

Questi tre sono esempi nella domanda, il mio semplice algoritmo è il seguente e ha passato i tre esempi forniti, ma non ha superato altri casi in cui non sono riuscito a vedere gli input.

static int minUniqueSum(int[] A) { 
    int n = A.length; 


    int sum = A[0]; 
    int prev = A[0]; 

    for(int i = 1; i < n; i++) { 
     int curr = A[i]; 

     if(prev == curr) { 
      curr = curr+1; 
      sum += curr; 
     } 
     else { 
      sum += curr; 
     } 
     prev = curr; 
    } 

    return sum; 
} 

non ho potuto vedere gli altri ingressi che questo algoritmo non è riuscita. Quello che mi viene in mente altri esempi di ingresso sono

{1, 1, 1, 1} --> {1, 2, 3, 4} 
{1, 1, 2, 2, 3, 3, 3} --> {1, 2, 3, 4, 5, 6, 7} 

{1, 2, 4, 4, 7, 7, 8} --> I think this should be {1, 2, 3, 4, 6, 7, 8} and my algorithm fails in this example because my algorithm has {1, 2, 4, 5, 7, 8, 9} whose sum is not minimum 

Quali sono alcuni altri casi di test e un algoritmo che può passare tutti i casi?

Alcune persone si lamentano che la domanda non è chiara. Vorrei farti sapere del problema. Non c'era una chiara descrizione del numero aggiunto se sarà permesso solo positivo, positivo o negativo. Dati tre esempi con input e output e altri casi di input e output che non è possibile vedere, scrivere un programma per passare anche tutti gli altri casi di input/output non visti. Questa era la domanda.

+0

Nel tuo ultimo test-case, si sta rimuovendo 1 dal 2 ° indice. Tuttavia, nella tua domanda dici che puoi renderlo unico solo aggiungendo "numeri minimi se duplicati". – MathBunny

+0

In che modo '{1, 2, 4, 7, 7, 8}' diventa '{1, 2, 3, 4, 6, 7, 8}' se è permesso solo aggiungere ai numeri? –

+0

Quindi è possibile aggiungere numeri negativi purché l'array rimanga ordinato? – stark

risposta

3

l'algoritmo fallirà nei casi con valori più ripetuti, per esempio

2, 2, 2

Otterreste 7 invece di 9.

una correzione minima utilizzando il tuo algoritmo sarebbe:

static int minUniqueSum(int[] A) { 
    int n = A.length; 

    int sum = A[0]; 
    int prev = A[0]; 

    for(int i = 1; i < n; i++) { 
     int curr = A[i]; 

     if(prev >= curr) { 
      curr = prev+1; 
     } 
     sum += curr; 
     prev = curr; 
    } 

    return sum; 
} 

* Come sottolineato nei commenti, no bisogno di ordinare una matrice già ordinata.

+1

Inoltre, la matrice è già ordinata quando viene immessa. L'ordinamento di nuovo non è necessario. – MathBunny

+0

@MathBunny - questo non è garantito nella domanda – Amit

+1

"Domanda: Dato un array intero ordinato, ..." –

0

È possibile aggiungere valori negativi a qualsiasi input, quindi il minimo è solo il numero triangolare Nth dove N è il numero di elementi nell'array. (Suppongo che si tratti solo di numeri positivi per l'array corretto poiché altrimenti potremmo renderlo arbitrariamente piccolo (negativo)

Quindi l'algoritmo è solo una questione di ricerca di un paio di numeri consecutivi valori ugualiSe non trovato, restituire la somma N * (N + 1)/2.


Se invece è vero che solo duplicato elementi può essere regolato, allora l'approccio è quello di trovare buchi tra elementi consecutivi e riempirli con precedenza "in coda" valori. I valori effettivi degli elementi "in coda" sono irrilevanti e solo un contatore è necessario. Di seguito è riportata una soluzione C# in cui presumo che gli aggiustamenti agli elementi debbano essere valori positivi. Ciò significa che non possiamo andare indietro e riempire buchi inutilizzati che semplificano il problema.

int F() 
{ 
    int[] a = {2, 2, 2, 3, 8, 9}; // sorted list 

    int n = 0; /* num */ int p = 0; /* prev; zero is an invalid value in the list */ 
    int q = 0; /* queue */ int s = 0; /* sum */ 

    for (int i = 1; i < a.Length; i++) 
    { 
     n = a[i]; 
     if (n == p) 
      q++; // increment queue on duplicate number 
     else 
     { 
      // for every hole between array values, decrement queue and add to the sum 
      for (int j = 1; q > 0 && j < n - p; j++, q--) 
       s += p + j; 
      s += (p = n); 
     } 
    } 
    // flush the queue 
    for (; q > 0; q--) 
     s += ++n; 

    return s; 
} 

Si esempio {1, 2, 4, 4, 7, 7, 8} suggerisce che l'ipotesi precedente non è valido. Così sono andato avanti e ho scritto una versione che utilizza una coda per memorizzare i buchi saltati per il riempimento successivo. Non è poi così doloroso, ed è molto simile nella struttura, ma potrebbe essere ancora troppo per la maggior parte delle interviste.

using System.Collections.Generic; 
int F2() 
{ 
    int[] a = {1, 1, 8, 8, 8, 8, 8}; // sorted list 

    int n = 0; /* num */ int p = 0; // prev; zero is an invalid value in the list 
    int q = 0; /* queue */ int s = 0; // sum 
    Queue<int> h = new Queue<int>(); // holes 

    for (int i = 1; i < a.Length; i++) 
    { 
     n = a[i]; 
     if (n == p) 
      q++; // increment queue on duplicate number 
     else 
     { 
      for (int j = 1; j < n - p; j++) 
       if (h.Count <= q + a.Length - i) // optimization 
        h.Enqueue(p + j); 
      s += (p = n); 
     } 
    } 
    // flush the queue 
    for (; q > 0; q--) 
     s += h.Count > 0 ? h.Dequeue() : ++n; 

    return s; 
} 

entrambi provare qui: http://rextester.com/APO79723

+0

Hai ragione, la domanda non specifica cosa un 'numero' è, quindi possiamo ad esempio supponete che sia negativo (cosa avete fatto) e aggiungete per es. l'IEEE 754 'infinito negativo' o il più piccolo doppio reale o - se limitato a valori positivi - aggiunge la differenza al più piccolo float successivo ecc. La tua risposta tuttavia è errata in quanto se ci fossero, per es. solo un numero ripetuto '[1,5,5,9]' puoi modificare solo uno degli elementi '5' che non permetteranno di riempire gli altri 'buchi' e la somma non può essere' N * (N + 1)/2'. –

+0

@le_m La domanda non specifica quali valori sono consentiti per la modifica. "aggiungere alcuni numeri" è un po 'poco chiaro e ho effettivamente affermato questa ipotesi nella mia risposta – shawnt00

+0

IMHO la domanda è precisa qui: "aggiungendo alcuni numeri per duplicare gli elementi" - beh, si potrebbe sostenere che solo uno o entrambi gli elementi duplicati possono essere modificato, ma ancora, non potremmo garantire la tua assunzione sopra il minimo. somma. –

0
int a[] = {1,2,2,3,5,6,6,6,6 }; So what would be elements in array for sum 
As per above problem statement it would be {1,2,3,4,5,6,7,8,9 } 

Solution 
public static void uniqueSum(){ 
     int a[] = {1,2,2,3,5,6,6,6,6 }; 
     int n = a.length; 
     int sum = a[0]; 
     int prv=a[0]; 
     for(int i=1; i<n;i++){ 
      int cur = a[i]; 
      if(cur==prv){ 
       cur = cur+1; 
       sum+= cur; 
       System.out.print("--"+cur); 
      }else{ 
       if(cur<prv){ 
        cur = prv +1; 
       } 
       sum += cur; 
      } 
      prv = cur; 
     } 
     System.out.println("===================== "+sum); 
    } 
0

si può provare il codice qui sotto.

int a[] = {1, 1 , 1}; 
ArrayList<Integer> arr = new ArrayList<Integer>(); 
HashMap hash = new HashMap(); 
for(int i=0;i<a.length;i++){ 
    arr.add(a[i]); 
} 
int sum = 0; 
hash.put(0, arr.get(0)); 
sum = (int) hash.get(0); 
for(int i=1;i<arr.size();i++){ 
    for(int j=1;j<=a.length;j++){ 
     if(hash.containsValue((arr.get(i)))){ 
      arr.set(i, arr.get(i)+1); 
     }else{ 
      hash.put(i, arr.get(i)); 
      sum += (int) hash.get(i); 
      break; 
     } 
    } 
} 

System.out.println(sum); 

PS: Anche io ho avuto questa domanda nella mia intervista, il codice di cui sopra ha superato tutti i casi di test.

+0

La tua mente spiega le tue motivazioni insieme al tuo codice? –

0

public static int minSum (int arr []) {

for(int i=0; i<arr.length-1;i++){ 

     if(arr[i]==arr[i+1]){ 

      arr[i+1]= arr[i+1]+1; 
     } 
    } 

    int sum=0; 

    for(int i=0; i<arr.length;i++){ 

     sum=sum+arr[i]; 
    } 

    System.out.println("sum: "+sum); 
    return sum; 
}