Python Challenge aus dem Vorstellungsgespräch - Zwei Zahlen addieren, die als Liste gespeichert sind

Heute sehen wir uns eine Frage aus einem Python Job Interview an - könnt ihr sie lösen? * *Meine Website mit allen anderen Kanälen und Newsletter* *:

_Discord:_

_Unterstützt mich - Danke!:_

[Basicx]

Bei deiner Lösung könnte der Übertrag an der letzten Stelle verloren gehen. Wegen der Abbruchbedingung kann die Ergebnisliste nie länger sein als die Eingabelisten. Das ist aber z.B. bei 5+5 = 10 notwendig.

[BRLN]

Deine Hausaufgabe: add recursive in place und das ohne Memory waste

[janga]

Ich finde deine Denkweise Interessant: Du machst im Grunde eine Schriftliche Addition. Allerdings frage ich mich, ob es nicht klüger wäre zuerst die Zahl zu bilden und die fertigen Zahlen zu addieren - oder ist das "gegen die Regel"?

Generatoren machen hier doch wunderbar Sinn?
Hier die Lösung für den Loop inkl. Generator. Habe eine verschachtelte Funktion genutzt, mache ich ganz gerne wenn die Funktion nur an einer Stelle innerhalb einer anderen Funktion aufgerufen werden soll und nirgendwo anders Sinn macht:

class Add:

def get_number_by_iterating(n):
def looper(current_node, unit):
while current_node.next:
current_node = current_node.next
unit *= 10
yield current_node.foo * unit

value = n.foo
looper = looper(current_node=n, unit=1)
for loop in looper:
value += loop
return value

@classmethod
def add(cls, zahl1, zahl2):
n1 =
n2 =
return n1 + n2

[johnbow]

Meine iterative Lösung:

def add_iterative(self, zahl1, zahl2):
zero = Node(0)
result = Node((zahl1.foo + zahl2.foo) % 10)
c = (zahl1.foo + zahl2.foo) // 10
node1 = zahl1.next if zahl1.next else zero
node2 = zahl2.next if zahl2.next else zero
node3 = result
while True:
a = node1.foo
b = node2.foo
val = a + b + c
node3.next = Node(val % 10)
c = val // 10
node3 = node3.next
if not (node1.next or node2.next):
return result
node1 = node1.next if node1.next else zero
node2 = node2.next if node2.next else zero

[THEMithrandir]

Für floor division gibts in python den // operator ;)

[progfix]

habe mich auch kurz daran probiert :P

class Add:
def add(self, zahl1, zahl2):
l = Node((zahl1.foo + zahl2.foo) % 10)
carry = (zahl1.foo + zahl2.foo) // 10
tmp = l
while 1:
if zahl1.next and zahl2.next:
zahl1 = zahl1.next
zahl2 = zahl2.next
tmp.next = Node((zahl1.foo + zahl2.foo + carry) % 10)
carry = (zahl1.foo + zahl2.foo + carry) // 10
elif zahl1.next:
zahl1 = zahl1.next
tmp.next = Node((zahl1.foo + carry) % 10)
carry = (zahl1.foo + carry) // 10
elif zahl2.next:
zahl2 = zahl2.next
tmp.next = Node((zahl2.foo + carry) % 10)
carry = (zahl2.foo + carry) // 10
else:
if carry: tmp.next = Node(carry)
break
tmp = tmp.next
return l

[eliasauer]

Tolles Video wie immer, mach weiter so 😬😁

[jannikweiss]

Python:

def add(z1, z2):
res = Node(0) # zum iterieren
res_start = res # referenz auf start behalten
carry = 0
while (z1, z2) != (None, None):
for z in (z1, z2):
if z != None:
carry += z.foo
res.foo = carry % 10
carry = carry // 10
z1 = z1.next if z1 != None else None
z2 = z2.next if z2 != None else None
# nächste Node, falls noch was kommt
if (z1, z2) != (None, None):
res.next = Node(0)
res = res.next
if carry > 0:
res.next = Node(carry)
return res_start

[maikfriemel]

//Hier meine Lösung in C++ :

#include<list>
#include<iostream>


std::list<int> add(const std::list<int>&, const std::list<int>&);
void print_list (const std::list<int>&);

int main(int argc, char* argv[]){

// gegeben
std::list<int>
l1{7, 3, 3, 1},
l2{5, 4};

// Ausgabe der Summe
print_list(add(l1, l2));

return 0;
}

/* Summenfunktion für 2 Listen
* erwartet 2 Listen mit Ziffern 0-9,
* die eine Dezimalzahl darstellen,
* deren Potenz mit jedem Listenelement steigt
* und gibt deren Summe als Dezimalzahl
* im selben Format zurück
*/
std::list<int> add(const std::list<int>& zahl1, const std::list<int>& zahl2){
std::list<int> summe;
auto stelle_zahl1 = zahl1.begin();
auto stelle_zahl2 = zahl2.begin();
bool zahl1_ende = stelle_zahl1 == zahl1.end();
bool zahl2_ende = stelle_zahl2 == zahl2.end();
int merke = 0;

while( !zahl1_ende || !zahl2_ende ){

if (!zahl1_ende){
merke += *stelle_zahl1;
zahl1_ende = ++stelle_zahl1 == zahl1.end();
}

if (!zahl2_ende){
merke += *stelle_zahl2;
zahl2_ende = ++stelle_zahl2 == zahl2.end();
}

summe.push_back(merke % 10);
merke /= 10;
}
if (merke){
summe.push_back(merke);
}

return summe;
}

/* benötigt eine Liste aus Integern,
* die einer Dezimal-Zahl in umgekehrter Reinfolge,
* also von der niedrigsten Stelle zur höchsten Stelle entspricht
* und gibt die Dezimalzahl aus
*/
void print_list (const std::list<int>& liste){
for (auto ziffer = liste.crbegin(); ziffer != liste.crend(); ++ziffer){
std::cout << *ziffer;
}
std::cout << std::endl;

}

[derpruefer]

Hey danke dass du immer so tolle viedeos machst!!! Hab mit dir python gelernt danke!!!

[koenigluki]

Iterative Java Lösung:
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

int carry = 0;
int val1 = 0;
int val2 = 0;

if (l1 != null) val1 = l1.val;
else val1 = 0;
if (l2 != null) val2 = l2.val;
else val2 = 0;

int add = val1 + val2;

if (add >= 10) {
add %= 10;
carry = 1;
}

ListNode node = new ListNode(add);
ListNode ret = node;
l1 = l1.next;
l2 = l2.next;


while (l1 != null || l2 != null) {

if (l1 != null) val1 = l1.val;
else val1 = 0;
if (l2 != null) val2 = l2.val;
else val2 = 0;


add = val1 + val2 + carry;
if (add >= 10) {
add %= 10;
carry = 1;
} else carry = 0;
node.next = new ListNode(add);
node = node.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (carry == 1) node.next = new ListNode(1);

return ret;
}

[jimknopf]

def tree_to_int(node):
token = str(node.foo)
if node.next is None:
return str(node.foo)
else:
return tree_to_int(node.next) + token

res = sum([int(tree_to_int(a)) for a in [l1, l2]])

Der Rest ist Boilerplate

[orange_tie]

Kann man theoritisch auch die beiden Start zahlen immer mit entsprechenden Potenzen von 10 multiplizieren und so in "normale" integer umwandeln und diese dann addieren. Um das ganze im entsprechenden Format auszugeben würde ich das Ergebnis in einen string umwandeln und durch die Stellen iterieren.
Würde mich sehr interessieren ob das auch geht. Deshalb würde ich mich über eine Antwort freuen 😊

Edit: nach einem Test hat sich bestätigt dass es durchaus möglich ist aber die Ausgabe in einem verschachtelten node objekt ist (für mich) extrem kompliziert gewesen Ich bin mir aber sicher dass man mit mehr Erfahrung meine Probleme leicht umschiffen kann.

[ProJayfy]

Hier meine iterative Lösung.

class Node(object):
def __init__(self, x):
self.foo = x
self.next = None

class Add:
def add(self, zahl1, zahl2):
start = Node((zahl1.foo + zahl2.foo) % 10)
carry = (zahl1.foo + zahl2.foo) // 10
tmp = start

while zahl1.next or zahl2.next or carry:
value1 = value2 = 0

if zahl1.next:
zahl1 = zahl1.next
value1 = zahl1.foo

if zahl2.next:
zahl2 = zahl2.next
value2 = zahl2.foo

tmp.next = Node((value1 + value2 + carry) % 10)
carry = (value1 + value2 + carry) // 10
tmp = tmp.next

return start

l1 = Node(7)
l1.next = Node(3)
l1.next.next = Node(3)
l1.next.next.next = Node(1)

l2 = Node(5)
l2.next = Node(4)

result = Add().add(l1, l2)
while result:
print(result.foo)
result = result.next

[xXNoRespectXx]

Ich les nur "Node" und bekomm direkt n Nervenzusammenbruch hahaha weil ich gerade n Projekt im Studium machen muss, bei dem es um BinHeaps geht und ich da nicht weiterkomme

[paul]

Du hast den Fall vergessen wenn die hoechste Stelle eine Zehnerueberschreitung hat. Also z.B. 90 + 20 wird zwar zwar 110 zurueckgeben, aber intern ware die Darstellung 11<-0 anstatt 1<-1<-0, oder? Und du kannst die drei Rekusiven Aufrufe auf einen verringern, indem du in jedem Fall den Nodes ohne succesor einen succesor gibst. Der Basisfall waere dann erreicht wenn fuer beide nodes gilt nodes.foo = 0 und der counter auch 0 ist. Wenn du 5 und 5 addierst, wird dein Programm 0 zurueckgeben.

[koenigluki]

das ist Leetcode problem 2 - Add Two Numbers oder?

[donaldduck]

Spit(str, "<-"), addieren und "join(sum, "<-")

[ronnybluthgen]

In Java gibt es keine Pointer! Und soweit ich weiß, gibt es in Python auch Pointer, aber da lasse ich mich gerne belehren.

[qqww]

Achja, einfach verkettete Listen, hab ich erst in C++ gelernt