MockQuestions

Python Beginner Level Linked Lists Mock Interview

To help you prepare for your Python Beginner Level Linked Lists interview, here are 9 interview questions and answer examples.

Get More Information About Our Python Beginner Level Linked Lists Interview Questions

Question 1 of 9

Add two numbers from two separated singly-linked lists.

This interview question focuses on Python linked lists and values along with constraints.

You are given two numbers that are represented as two singly-linked lists. Each node of the linked list represents a digit in the number. The digits are stored in reverse order. That is, the unit-place digit is the head of the linked list. Your task is to find the sum of the two numbers and return the result in the form of a linked list.

/*Example*/

Let two numbers are 123 and 456
so given linked lists will be
	3 -> 2 -> 1
and	6 -> 5 -> 4

The sum of the numbers is 579
So the expected result will be
	9 -> 7 -> 5
Constraints:  The numbers of nodes in each given linked lists will be between 1 and 100

Solution:

The first solution that comes to mind is to get the value numbers from given linked lists. Then add them, and then create a linked list from the result again.

But the number of the digits in the list is up to 100, which means the range of the numbers is [1, 10100], which is too large for storing numbers directly in their bit forms in a computer.

What we can do is take digits one by one from the linked lists and add them. If it is smaller than 10, directly append it to the resultant list; if it is greater than 10, then append its unit place to the list and forward carry 1 to the next digits as we do in pen-paper while adding two numbers.

More formally,
Let, a and b are the linked lists and res be result list.
ai and bi are digits stored in the ith node.

ri = ai + bi + ci - 1 // take carry from last calculation
resi = ri % 10 // store the unit place i.e. remainder by 10
ci = floor(ri / 10) // forward carry, if any

class ListNode:
	def __init__(self, val=0):
		self.val = val
		self.next = None

def addTwoNumbers(l1,l2):
	newLL = ListNode()
	remainder = 0

	temp = newLL
	while l1 or l2:
		digit1 = l1.val if l1 else 0
		digit2 = l2.val if l2 else 0
		value = digit1 + digit2 + remainder
		node = ListNode(value % 10)
		remainder = value // 10
		
		# move to next pointers
		l1 = l1.next
		l2 = l2.next
		temp.next = node
		temp = temp.next

	if remainder:
		temp.next = ListNode(remainder)

	return newLL.next

Time complexity - O(max(n, m)) // n and m are length of the two digits
Space complexity - O(1)

Written by on May 21st, 2021

Next Question

9 Python Beginner Level Linked Lists Interview Questions & Answers

Below is a list of our Python Beginner Level Linked Lists interview questions. Click on any interview question to view our answer advice and answer examples. You may view six answer examples before our paywall loads. Afterwards, you'll be asked to upgrade to view the rest of our answers.

  • 1. Add two numbers from two separated singly-linked lists.

  • 2. Return the middle node of a given linked list.

  • 3. Remove elements from linked list that are equal to target.

  • 4. Delete the node in a singly-linked list.

  • 5. Merge two sorted lists.

  • 6. Can you remove nodes between indices from list1 and replace them with list2 nodes?

  • 7. Create a deep copy of the special-linked list.

  • 8. Does the list contain a cycle?

  • 9. How do you rotate the list?