How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Add two big integers from digit lists | Google Interview Question

Q: Add two big integers from digit lists

This question evaluates algorithmic skills in manipulating linked lists or arrays to perform addition of large integers, focusing on carry propagation, handling differing lengths, and analysis of time and space complexity.

You are given two non-empty singly linked lists (or arrays) representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit from 0 to 9.

Your task is to add the two numbers and return the sum as a new linked list, also in reverse order.

You may assume:

Each list has at least one node.
The integers do not contain leading zeros, except the number 0 itself.

Example

Input:

List 1: 2 → 4 → 3 (represents the integer 342)
List 2: 5 → 6 → 4 (represents the integer 465)

Output:

7 → 0 → 8 (represents the integer 807, since 342 + 465 = 807)

Another example

Input:

List 1: 9 → 9 → 9 (represents 999)
List 2: 1 (represents 1)

Output:

0 → 0 → 0 → 1 (represents 1000)

Constraints

Let n be the length of the first list and m be the length of the second list.
1 ≤ n, m ≤ 10^5.
Each node value is an integer in the range [0, 9].

Task: Describe an algorithm to perform this addition and construct the resulting linked list in O(n + m) time and O(1) additional space (excluding the space for the output list).

You are given two non-empty singly linked lists (or arrays) representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit from 0 to 9.

Your task is to add the two numbers and return the sum as a new linked list, also in reverse order.

You may assume:

Each list has at least one node.
The integers do not contain leading zeros, except the number 0 itself.

Example

Input:

List 1: 2 → 4 → 3 (represents the integer 342)
List 2: 5 → 6 → 4 (represents the integer 465)

Output:

7 → 0 → 8 (represents the integer 807, since 342 + 465 = 807)

Another example

Input:

List 1: 9 → 9 → 9 (represents 999)
List 2: 1 (represents 1)

Output:

0 → 0 → 0 → 1 (represents 1000)

Constraints

Let n be the length of the first list and m be the length of the second list.
1 ≤ n, m ≤ 10^5.
Each node value is an integer in the range [0, 9].

Task: Describe an algorithm to perform this addition and construct the resulting linked list in O(n + m) time and O(1) additional space (excluding the space for the output list).

Add two big integers from digit lists

Quick Overview

Example

Another example

Constraints

Comments (0)

Add two big integers from digit lists

Quick Overview

Example

Another example

Constraints

Comments (0)