Add Two Numbers – II

By | | , , ,
Leave a comment

Let’s discuss a very interesting problem add two numbers represented by linked lists.

Problem Statement –

Given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and least significant digit comes last. Each of the linked list node contain a single digit.

We have to write a code to add the two numbers and return it as a linked list.

Both the numbers do not contain any leading zero, except the number 0 itself.

NOTE: Reversing a linked list is not allowed.

For Example –

List 1 : 7 -> 2 -> 4 -> 3 -> NULL

List 2 : 5 -> 6 -> 4 -> NULL

Result : 7 -> 8 -> 0 -> 7 -> NULL

Explanation : The first linked list is representing the number 7243 and the second linked is representing the number 564. If we add these two numbers we get 7807, which we have to return in the form of a linked list.

→

Majority Element II | N/3 Repeated Number

By | | , ,
Leave a comment

In this tutorial, I am going to discuss a very interesting problem find N/3 repeated number in an array.

Given an array of size n, Write a code to find all the elements that appear more than n/3 times.

NOTE: We have to solve this problem in linear time and in O(1) space.

Example 1:

Input : [3, 2, 3]

Output: 3

In this example, The size of this array is 3. We have to find all the numbers which occurred more than n/3 where n is the size of the array. The number 3 appears more than 1 times.

Example 2:

Input: [1, 1, 1, 3, 3, 2, 2, 2]

Output:[1, 2]

→

Recover Binary Search Tree

By | | , , ,
Leave a comment

In this problem, we have given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Write a code to recover binary search tree without changing its structure.

The solution using O(n) space is pretty straight forward. Can you solve this problem using constant space?

→