Senior Software Engineer

1) Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will

a) Always decrease the number of page faults
b) Always increase the number of page faults
c) Some times increase the number of page faults
d) Never affect the number of page faults

2) In which one of the following page replacement policies, Belady’s anomaly may occur?

(A) FIFO
(B) Optimal
(C) LRU
(D) MRU

Out of all the 2-digit integers between 1 and 100, a 2-digit number has to be selected at random. What is the probability that the selected number is not divisible by 7?

a) 13/90
b) 12/90
c) 78/90
d) 79/90

1) Predict output of following:

#include 
using namespace std;

int main()
{
int a = b = c = 0;
cout << a << "*" << b << "*" << c;
return 0;
}

2) Predict output of following:

#include 
using namespace std;

class A
{
int id;
public:
A (int i) { id = i; }
void print () { cout << id << endl; }
};

int main()
{
A a[2];
a[0].print();
a[1].print();
return 0;
}

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 a sequence of only digits in the form of a string 'DIGIT_PATTERN', your task is to find the first repeating digit. If no digit is repeating you should return -1.

Example:

Given string of digits is 123456325. Now starting from the left, the first digit which is repeating is 3 as till 2nd 3 every digit is encountered 1st time and thus our answer for this input will be 3.

Given a linked list having two pointers in each node. The first one points to the next node of the list, however, the other pointer is random and can point to any node of the list or null. The task is to create a deep copy of the given linked list and return its head. We will validate whether the linked list is a copy of the original linked list or not.

A deep copy of a Linked List means we do not copy the references of the nodes of the original Linked List rather for each node in the original Linked List, a new node is created.

For example,

Random pointers are shown in red and next pointers in black.

You are given a linked list having ‘n’ nodes and an integer ‘k’.

You have to rotate the linked list to the right by ‘k’ positions .

Example :

Input: linked list = [1 2 3 4] , k = 2

Output: 3 4 1 2

Explanation:
We have to rotate the given linked list to the right 2 times. After rotating it to the right once it becomes 4->1->2->3. After rotating it to the right again, it becomes 3->4->1->2.