Dies ist eine Frage zu einem Google-Interview. Hier finden Sie einen Youtube-Link.

Die Aufgabe:

Suchen Sie aus einer ungeordneten Liste nach 2 Ganzzahlen, die sich zu einer bestimmten Ganzzahl summieren.

1. Suchen Sie bei einer ungeordneten Liste von Ganzzahlen nach 2 Ganzzahlen, die sich zu einem bestimmten Wert summieren, geben Sie diese 2 Ganzzahlen aus und geben Sie den Erfolg an (Exit 0). Sie müssen keine bestimmten Zahlen sein (dh die ersten 2 Ganzzahlen, die zur richtigen Zahl summieren). Jedes Paar, das den Wert summiert, funktioniert.
2. Eine ganze Zahl ist positiv und größer als Null.
3. Eine Liste von Ganzzahlen kann sich in jeder Datenstruktur befinden, einschließlich einer Datei mit Ganzzahlen - eine Ganzzahl pro Zeile.
4. Wenn keine ganzen Zahlen gefunden werden können, geben Sie einen Fehler an (Ausgang 1).
5. Es müssen zwei Ganzzahlen an verschiedenen Positionen in der Liste zurückgegeben werden. (dh Sie können nicht zweimal dieselbe Nummer von derselben Position zurückgeben)

(Hinweis: Im Video sind dies nicht genau die Anforderungen. Der 'Interviewer' hat seine Angaben mehrmals geändert.)

z.B.

sum2 8 <<EOF
1
7
4
6
5
3
8
2
EOF

Drucke 3und 5und Beenden Status ist 0. Beachten Sie, dass in diesem 1,7und 2,6würde auch Ergebnisse erlaubt sein.

sum2 8 <<EOF
1
2
3
4

Gibt den Exit-Status 1 zurück, da keine Kombination möglich ist. 4,4ist nicht erlaubt, gemäß Regel 5.

Bash, 84 Bytes

Meine Implementierung von (ungefähr) Googles Engineer-Lösung unter Verwendung von Bash und eines Eingabestreams - nicht meine Lösung, das zählt also nicht.

while read V;do((V<$1))&&{ ((T=R[V]))&&echo $T $V&&exit;((R[$1-V]=V));};done;exit 1

Methode

während wir die Ganzzahl V aus dem Eingabestream lesen können, wenn sie kleiner als das Ziel $ 1 ist, dann, wenn sie bereits $ 1-V gesehen hat, $ 1-V und V ausgeben und 0 beenden (sonst), um den Kandidaten für die Eingabe $ 1-V, Exit 1, zu speichern

Brachylog , 9 Bytes

h⊇Ċ.+~t?∧

Probieren Sie es online!

Vorausgesetzt, ich habe die Herausforderung richtig verstanden ...

Erläuterung

h⊇Ċ          Ċ ('couple') has two elements, and is a subset of the head of the input
  Ċ.         Output = Ċ
   .+~t?     The sum of the elements of the Output is the tail of the Input
        ∧    (disable implicit unification)

Perl 6 , 59 Bytes

$_=get;put lines().combinations(2).first(*.sum==$_)//exit 1

Probieren Sie es aus Versuchen
Sie es ohne mögliches Ergebnis

Erweitert:

$_ = get;            # get one line (the value to sum to)

put                  # print with trailing newline
    lines()          # get the rest of the lines of input
    .combinations(2) # get the possible combinations
    .first(          # find the first one
      *.sum == $_    # that sums to the input
    )
  //                 # if there is no value (｢Nil｣)
    exit 1           # exit with a non-zero value (｢put｣ is not executed)

JavaScript ES6, 58 70 68 64 Bytes

a=>b=>{for(i in a)if(a.includes(b-a[i],i+1))return[a[i],b-a[i]]}

Gibt ein Zahlenpaar in Form eines Arrays zurück, wenn es gefunden wird. undefinedAnderenfalls wird ein falscher Wert zurückgegeben.

f=a=>b=>{for(i in a)if(a.includes(b-a[i],i+1))return[a[i],b-a[i]]}

console.log(f([1,7,4,6,5,3,8,2])(8));
console.log(f([1,2,3,4,5,6,7,8])(8));
console.log(f([1,2,3,4])(8));
console.log(f([2,2])(4));

JavaScript (ES6), 61 57 56 Bytes

Nimmt das Array von Ganzzahlen aund die erwartete Summe sin die aktuelle Syntax auf (a)(s). Gibt ein Paar übereinstimmender Ganzzahlen als Array zurück oder undefinedwenn kein solches Paar vorhanden ist.

a=>s=>(r=a.find((b,i)=>a.some(c=>i--&&b+c==s)))&&[r,s-r]

Formatiert und kommentiert

a =>                      // given an array of integers (a)
  s => (                  // and an expected sum (s)
    r = a.find((b, i) =>  // look for b at position i in a such that:
      a.some(c =>         //   there exists another c in a:
        i-- &&            //     - at a different position
        b + c == s        //     - satisfying b + c == s
      )                   //   end of some()
    )                     // end of find(): assign the result to r
  ) &&                    // if it's not falsy:
  [r, s - r]              // return the pair of integers

Prüfung

let f =

a=>s=>(r=a.find((b,i)=>a.some(c=>i--&&b+c==s)))&&[r,s-r]

console.log(f([1,7,4,6,5,3,8,2])(8))
console.log(f([1,2,3,4])(8))

Gelee , 14 Bytes

ŒcS=⁹$$ÐfḢṄo⁶H

Probieren Sie es online!

Dies ist eine Funktion (kein vollständiges Programm), die als Standardausgabe ausgegeben wird. (Der TIO-Link verfügt über einen Wrapper, der eine Funktion ausführt und ihren Rückgabewert ignoriert.)

Dieses Programm könnte 4 Byte kürzer sein, wenn der Exit-Code nicht benötigt wird. Einen Exit-Code von 1 in Jelly zurückzugeben ist ziemlich schwierig. (Es ist möglich, dass es einen genaueren Weg gibt, den ich verpasst habe.)

Erläuterung

ŒcS=⁹$$ÐfḢṄo⁶H
Œc                All pairs of values from {the first argument}
       Ðf         Take only those which
  S=⁹               sum to {the second argument}
     $$           Parse the preceding three builtins as a group
         Ḣ        Take the first result (0 if there are no results)

          Ṅ       Output this result (plus a newline) on standard output
           o⁶     If this value is falsey, replace it with a space character
             H    Halve every element of the value

Wir können jede ganze Zahl in einem Paar gut halbieren, und das o⁶Hwird nichts tun, wenn wir ein Ergebnis finden, außer einen nutzlosen Rückgabewert zurückzugeben, der ohnehin nicht relevant ist (das Ṅdient als bequeme Einzelbyte-Methode, um die Rückgabe der Funktion zu bestimmen Wert früh, nach PPCG-Regeln). Wenn wir jedoch kein Ergebnis gefunden haben, versuchen wir letztendlich, ein Leerzeichen zu halbieren, eine Operation, die so bedeutungslos ist, dass der Jelly-Interpreter abstürzt. Glücklicherweise erzeugt dieser Absturz einen Exit-Code von 1.

Perl 5 , 51 Bytes

46 Byte Code + für 5 Byte -pliFlags.

$\="$_ $v"if$h{$v=$^I-$_};$h{$_}=1}{$\||exit 1

Probieren Sie es online!

Die Idee ist, in der Eingabeliste zu iterieren: Wenn wir zuvor eine Zahl x( $_) gesehen haben n-x( $^I-$_), haben wir gefunden, wonach wir gesucht haben, und $\diese beiden Werte ( "$_ $v") festgelegt. Am Ende, wenn $\nicht gesetzt, dann wir exit 1, sonst wird es implizit gedruckt.

Röda , 60 56 Bytes

f s,a{seq 1,s|{|x|[[x,s-x]]if[x in a,s-x in a-x]}_|pull}

Probieren Sie es online!

Dieser Code löst einen Fehler aus, wenn keine Antwort vorliegt. Es werden alle möglichen Paare erzeugt, die die Summe bilden können s, dh. 1, s-1, 2, s-2, 3, s-3, ... Dann prüft sie , ob beide Zahlen im Array sind aund wenn ja, sie an den Strom schiebt. pullLiest einen Wert aus dem Stream und gibt ihn zurück. Wenn der Stream keine Werte enthält, wird ein Fehler ausgegeben. a-xGibt das Array amit dem xentfernten zurück.

Python 2, 60 Bytes

Diese kurzen, bis Regeln beim Verlassen mit Code 1 geklärt sind. Jetzt wird mit Fehler beendet, wenn nichts gefunden wird.

-5 Bytes dank @Peilonrayz

-4 Bytes dank @Rod

Probieren Sie es online aus

a,s=input()
while a:
 x=a.pop()
 if s-x in a:r=s-x,x
print r

C ++ 133 Bytes (kompiliert mit clang 4 und gcc 5.3 -std = c ++ 14)

#include <set>
auto f=[](auto s,int v,int&a,int&b){std::set<int>p;for(auto i:s)if(p.find(i)==end(p))p.insert(v-i);else{a=v-i;b=i;}};

C 108 Bytes

void f(int*s,int*e,int v,int*a,int*b){do{int*n=s+1;do if(v-*s==*n){*a=*s;*b=*n;}while(++n<e);}while(++s<e);}

Haskell , 34 Bytes

(n:v)#s|elem(s-n)v=(n,s-n)|1<2=v#s

Probieren Sie es online!

Diese Funktion prüft für jedes Element der Liste, ob sich (Summenelement) im folgenden Teil der Liste befindet. Gibt das erste gefundene Paar zurück. Wenn die Funktion das Ende der Liste erreicht, wird ein Fehler "Nicht erschöpfende Muster" ausgegeben und mit Code 1 beendet.

Power Shell, 109 97 Byte

param($i,$a)($c=0..($a.count-1))|%{$c-ne($f=$_)|%{if($a[$f]+$a[$_]-eq$i){$a[$f,$_];exit}}};exit 1

Hat einen 12-Byte-Deal abgeschlossen, den AdmBorkBork angeboten hat

Erläuterung

# Get the parameter passed where $i is the addition target from the array of numbers in $a
param($i,$a)

($c=0..($a.count-1))|%{
    # We are going to have two loops to process the array elements.
    # The first loop element will be held by $f
    $f=$_
    # Create a second loop that will be the same as the first except for the position of $f to
    # prevent counting the same number twice. 
    $c|?{$_-ne$f}|%{
        # Check if the number at the current array indexes add to the target value. If so print and exit.
        if($a[$f]+$a[$_]-eq$i){$a[$f],$a[$_];exit}        
    }

}
# If nothing was found in the loop then we just exit with error.
exit 1

Die aktuellen Regeln suchen nach Exit-Code. Diese könnten entfernt werden und nur überprüfen, ob Nummern zurückgegeben werden und ob sie falsch sind.

Beispielnutzung

Wenn der obige Code als Funktion gespeichert wurde s

s 8 @(1,2,3,4)
s 8 @(1,7,4,6,5,3,8,2) 

R, 49 Bytes

function(x,y){r=combn(x,2);r[,colSums(r)==y][,1]}

Dies findet alle 2-Kombinationen von xund gibt eine Matrix zurück. Dann summiert nach Spalten und findet alle Summen, die gleich sind y(ohne den [,1]Teil am Ende werden alle Kombinationen gedruckt, deren Summen gleich sind y).

Japt , 9 Bytes

Dank @ETHproductions viele Bytes gespart

à2 æ_x ¥V

Probieren Sie es online!

Erläuterung

à2 æ_x ¥V
à2         // Creates all combinations of the input, length 2
   æ       // Returns the first item where:
    _x     //     The sum of the two items in each set
       ¥V  //     == Second input   

Beispiel

Input:        [1,2,3], 4
à2         // [[1,2],[1,3],[2,3]]
   æ_x     // [3,    4,    5    ]
       ¥V  //  3!=4, 4==4 ✓
Output:    //  1,3

Javascript, 114 96 86 84 Bytes

a=>b=>{c=b.length;for(x=0;x<c;x++)for( y=x;++y<c;)if(b[x]+b[y]==a)return[b[x],b[y]]}

1 Byte dank @Cyoce und weitere 8 Byte dank @ETHProductions gespeichert

Dies gibt ein Tupel mit der ersten Kombination von Listenelementen zurück, die die angegebene Eingabe ergeben, oder nichts für keine Übereinstimmung. Ich habe das vars in der Funktion entfernt; REPL.it stürzt ohne sie ab, aber die Chrome Dev Console erledigt dies in Ordnung ...

Probieren Sie es online!

Clojure, 77 Bytes

#(first(mapcat(fn[i a](for[b(drop(inc i)%):when(=(+ a b)%2)][a b]))(range)%))

Liefert das erste solche Paar oder nil.

Haskell, 62 Bytes

r=return;s#[]=r 1;s#(a:b)|elem(s-a)b=print(a,s-a)>>r 0|1<2=s#b

Ich weiß immer noch nicht, was die Herausforderung erlaubt und was nicht. Ich gehe für eine Funktion, die ein Paar von Zahlen druckt und 0 zurückgibt, wenn es eine Lösung gibt, und nichts druckt und 1 zurückgibt, wenn es keine Lösung gibt. Da Drucken E / A ist, muss ich die Rückgabewerte in die E / A-Monade (über return) heben und die tatsächliche Art der Funktion ist Num a => IO a.

Anwendungsbeispiel (mit Rückgabewert, der von der Replik ausgegeben wird):

*Main> 4 # [2,2]
(2,2)
0

Probieren Sie es online! .

Wenn das Auslösen von Ausnahmen zulässig ist, failwerden einige Bytes (insgesamt 51) gespeichert:

s#[]=fail"";s#(a:b)|elem(s-a)b=print(a,s-a)|1<2=s#b

Gelee , 9 Bytes

ŒcS=¥ÐfḢZ

Jelly hat keine Möglichkeit, den Exit-Code auf beliebige Werte zu setzen. Daher wird ein TypeError für die Eingabe ohne gültige Lösung erstellt, wodurch der übergeordnete Interpreter mit Exit-Code 1 beendet wird .

Probieren Sie es online!

Wie es funktioniert

ŒcS=¥ÐfḢZ  Main link. Argument: A (array of integers), n (integer)

Œc         Yield all 2-combinations of different elements of A.
     Ðf    Filter by the link to the left.
    ¥        Combine the two links to the left into a dyadic chain.
  S            Take the sum of the pair.
   =           Compare the result with n.
       Ḣ   Head; extract the first pair of the resulting array.
           This yields 0 if the array is empty.
        Z  Zip/transpose the result.
           This doesn't (visibly) alter pairs, but it raise a TypeError for 0.

Nova , 101 Bytes

q(Int[] a,Int x)=>a{if(Int y=a.firstWhere({a.contains(x-a.remove(0))}))return [y,x-y];System.exit(1)}

Eine schöne Sache am Codegolf ist, dass es mir hilft, Fehler in meiner Sprache zu finden. zB der Platzbedarf zwischenreturn und[y,x-y] .

Sobald ich Array.nova Push / Pop-Funktionen hinzufüge und die Rückgabe behebe, wären das 96 Bytes:

q(Int[] a,Int x)=>a{if(Int y=a.firstWhere({a.contains(x-a.pop())}))return[y,x-y];System.exit(1)}

Verwendung:

class Test {
    static q(Int[] a,Int x)=>a{if(Int y=a.firstWhere({a.contains(x-a.remove(0))}))return [y,x-y];System.exit(1)}

    public static main(String[] args) {
        Console.log(q([1, 2, 3, 4, 5], 8)) // [5, 3]
        Console.log(q([1, 2, 3, 4, 5], 5)) // [1, 4]
        Console.log(q([1, 2, 3, 4], 8)) // exit code 1
    }
}

Bearbeiten: Auch gibt es diesen Weg bei 73 Bytes (69 mit Pop) auch:

q(Int[] a,Int x)=>[Int y=a.firstOrThrow({a.contains(x-a.remove(0))}),x-y]

firstOrThrow löst eine Exception aus, die nicht abgefangen wird und somit das Programm letztendlich mit Exit-Code 1 beendet.;)

Dieser Weg scheint auch lesbarer zu sein.

Pyth, 12 Bytes

hfqsThQ.ceQ2

Erläuterung

       .ceQ2   Get all pairs from the second input
 fqsThQ        Find the ones whose sum is the first input
h              Take the first (exits with error code 1 if there aren't any)

PHP, 88 Bytes

for($i=1;$a=$argv[$k=++$i];)for(;$b=$argv[++$k];)if($a+$b==$argv[1])die("$a $b");die(1);

Nimmt Eingaben von Befehlszeilenargumenten entgegen, summiere zuerst. Laufen Sie mit-nr .

Zum Glück die/ exitAusgänge mit , 0wenn Sie ihm einen String als Parameter geben.

_{Ich habe versucht, die Schleifen zu einer zusammenzuführen. Diesmal ist jedoch eine längere Initialisierung und ein Test erforderlich.}

Mathematica, 76 Bytes

f::e="1";If[(l=Cases[#~Subsets~{2},x_/;Tr@x==#2])=={},Message@f::e,First@l]&

Ziemlich einfach: #~Subsets~{2}erhält dann alle 2-Element-Teilmengen der ListeCases[...,x_/;Tr@x==#2] wählt nur die aus, deren Summe die gewünschte Zahl ist. Wenn es keine davon gibt,If[l=={}, Message@f::e,First@l] die Fehlermeldung gedrucktf::e : 1 zuvor definierte (da ich keine Ahnung habe, was "Exit-Status 1" für Mathematica bedeuten könnte). Andernfalls wird der erste Eintrag in der Liste der Paare zurückgegeben, die die korrekte Summe ergeben.

Wenn wir einen Falsey-Wert zurückgeben dürfen, anstatt diese seltsame Exit-Status-Sache auszuführen, hat der folgende Code 58 Bytes:

If[(l=Cases[#~Subsets~{2},x_/;Tr@x==#2])=={},1<0,First@l]&

Scala, 55 41 Bytes

(l,n)=>l combinations 2 find(_.sum==n)get

Gibt eine Liste der beiden Zahlen zurück, wenn sie existieren, und löst andernfalls einen Fehler aus. Wird dieser Fehler nicht abgefangen, wird der Beendigungsstatus 1 angezeigt.

Ruby, 53 48 Bytes

->a,s{p(a.combination(2).find{|x,y|x+y==s})?0:1}

Eingabe: a ist die Liste, s ist die erwartete Summe.

Wenn die 2 Zahlen gefunden wurden, drucken Sie sie aus und geben Sie 0 zurück, andernfalls 1, wie in der Spezifikation angegeben.

TI-Basic, 59 Bytes

Prompt L1
Prompt X
While 1
L1(1→B
seq(L1(C),C,2,dim(L1→L1
If sum(not(X-L1-B
Then
Disp B,X-B
Return
End
End

Erläuterung:

Prompt L1               # 4 bytes, input array like "{1, 2, 3}"
Prompt X                # 3 bytes, Input target sum
While 1                 # 3 bytes, until the list is empty
L1(1→B                  # 7 bytes, try the first element (now B)
seq(L1(C),C,2,dim(L1→L1  # 18 bytes, remove first element from list
If sum(not(X-L1-B       # 10 bytes, if any element in the list plus B is the target
Then                    # 2 bytes, then...
Disp B,X-B              # 7 bytes, print it and it's "complement"
Return                  # 2 bytes, and exit gracefully
End                     # 2 bytes
End                     # 1 byte

Wenn das Programm nicht ordnungsgemäß beendet wurde, wird ein Fehler verursacht, wenn die Liste nicht genügend Elemente enthält, um fortzufahren.

CJam, 23 Bytes

l~_,1>{e!2f<::+#)}{;;}?

Eingabe ist sum numbers . Beispielsweise:6 [3 2 3] . Hinterlässt eine positive Zahl für wahr und eine leere Zeichenfolge oder eine 0 für falsch.

Erläuterung:

l~    e# Read input and evaluate:  | 7 [3 2 3]
_     e# Duplicate:                | 7 [3 2 3] [3 2 3]
,     e# Take the length:          | 7 [3 2 3] 3
1>{   e# If more than 1:           | 7 [3 2 3]
  e!  e#   Unique permutations:    | 7 [[2 3 3] [3 2 3] [3 3 2]]
  2f< e#   Slice each to length 2: | 7 [[2 3] [3 2] [3 3]]
  ::+ e#   Some each:              | 7 [5 5 6]
  #   e#   Index:                  | -1
  )   e#   Increment:              | 0
}{    e# Else:                     | 7 [3 2 3]
  ;   e#   Pop                     | 7
  ;   e#   pop                     |
}?    e# Endif
e# Implicit output: 0