SDE - Intern

You are given two strings STR1 and STR2. You need to check whether STR2 can be formed from the characters of STR1. Both the strings can contain any characters.

For example:

If STR1 = “codingninjas” and STR2 = “sing”. We can form the second string using the characters of the first string. This is because “s”, “i”, “n”, “g” are present in the string STR1.

You are given an 'N * N' matrix of integers where each row and each column is sorted in increasing order. You are given a target integer 'X'.

Find the position of 'X' in the matrix. If it exists then return the pair {i, j} where 'i' represents the row and 'j' represents the column of the array, otherwise return {-1,-1}

For example:

If the given matrix is:
[ [1, 2, 5],
  [3, 4, 9],
  [6, 7, 10]] 
We have to find the position of 4. We will return {1,1} since A[1][1] = 4.

You are given an array ‘ARR’ of size ‘N’ and an integer ‘K’. Your task is to find the total number of distinct elements present in every ‘K’ sized window of the array. A ‘K’ sized window can also be viewed as a series of continuous ‘K’ elements present in the sequence.

Note:

1. The size of ‘ARR’ will always be greater than or equal to the ‘K’.
2. Here window refers to a subarray of ‘ARR’. Hence ‘K’ sized window means a subarray of size ‘K’.
3. You are not required to print the output explicitly. It has already been taken care of. Just implement the function and return an array of the count of all distinct elements in the ‘K’ size window.

Example

Consider ARR = [ 1, 2, 1, 3, 4, 2, 3 ] and K = 3.

As per the given input, we have a sequence of numbers of length 7, and we need to find the number of distinct elements present in all the windows of size 3.

Window-1 has three elements { 1, 2, 1 } and only two elements { 1, 2 } are distinct because 1 is repeating two times.
Window-2 has three elements { 2, 1, 3 } and all three elements are distinct { 2, 1, 3 }.
Window-3 has three elements { 1, 3, 4 } and all three elements are distinct { 1, 3, 4 }.
Window-4 has three elements { 3, 4, 2 } and all three elements are distinct { 3, 4, 2 }.
Window-5 has three elements { 4, 2, 3 } and all three elements are distinct { 4, 2, 3 }.

Hence, the count of distinct elements in all K sized windows is { 2, 3, 3, 3, 3 }.

You are given two sorted linked lists. You have to merge them to produce a combined sorted linked list. You need to return the head of the final linked list.

Note:

The given linked lists may or may not be null.

For example:

If the first list is: 1 -> 4 -> 5 -> NULL and the second list is: 2 -> 3 -> 5 -> NULL

The final list would be: 1 -> 2 -> 3 -> 4 -> 5 -> 5 -> NULL

Two questions of operating systems were asked: -

1. What is thrashing?
2. Explain the Round Robin Scheduling algorithm?