SDE - 1

You are given an integer ‘N’, your task is to find and return the N’th Fibonacci number using matrix exponentiation.

Since the answer can be very large, return the answer modulo 10^9 +7.

Fibonacci number is calculated using the following formula:

F(n) = F(n-1) + F(n-2), 
Where, F(1) = F(2) = 1.

For Example:

For ‘N’ = 5, the output will be 5.

You are given two Singly Linked Lists of integers, which may have an intersection point.

Your task is to return the first intersection node. If there is no intersection, return NULL.

Example:-

The Linked Lists, where a1, a2, c1, c2, c3 is the first linked list and b1, b2, b3, c1, c2, c3 is the second linked list, merging at node c1.

Given a sequence of numbers ‘ARR’. Your task is to return a sorted sequence of ‘ARR’ in non-descending order with help of the merge sort algorithm.

Example :

Merge Sort Algorithm -

Merge sort is a Divide and Conquer based Algorithm. It divides the input array into two-parts, until the size of the input array is not ‘1’. In the return part, it will merge two sorted arrays a return a whole merged sorted array.

The above illustrates shows how merge sort works.

Note :

It is compulsory to use the ‘Merge Sort’ algorithm.

Design and implement a data structure for Least Recently Used (LRU) cache to support the following operations:

1. get(key) - Return the value of the key if the key exists in the cache, otherwise return -1.

2. put(key, value), Insert the value in the cache if the key is not already present or update the value of the given key if the key is already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting the new item.

You will be given ‘Q’ queries. Each query will belong to one of these two types:

Type 0: for get(key) operation.
Type 1: for put(key, value) operation.

Note :

1. The cache is initialized with a capacity (the maximum number of unique keys it can hold at a time).

2. Access to an item or key is defined as a get or a put operation on the key. The least recently used key is the one with the oldest access time.

You are given a directed acyclic graph. Your task is to find any topological sorting of the graph.

A directed acyclic graph is a directed graph with no directed cycles.

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge from u to v, vertex u comes before v in the ordering.

For example-

For the given DAG-

One of the possible topological sort will be-
1  2  3

A code was given that essentially counts the sum of the digits of a number. We need to determine its time complexity.