Software Engineer

Given a matrix where every element is either 1 or 0(zero), replace 0 with 1 if surrounded by 1. A 0 (or a set of 0s) is considered to be surrounded by 1 if there are 1 at locations just below, just above, just left and just right of it.

See the sample input.

You are given an infinite supply of coins of each of denominations D = {D0, D1, D2, D3, ...... Dn-1}. You need to figure out the total number of ways W, in which you can make a change for value V using coins of denominations from D. Print 0, if a change isn't possible.

You are given an array 'arr' containing 'n' non-negative integers.

Your task is to partition this array into two subsets such that the absolute difference between subset sums is minimum.

You just need to find the minimum absolute difference considering any valid division of the array elements.

Note:

1. Each array element should belong to exactly one of the subsets.

2. Subsets need not always be contiguous.
For example, for the array : [1, 2, 3], some of the possible divisions are 
   a) {1,2} and {3}
   b) {1,3} and {2}.

3. Subset-sum is the sum of all the elements in that subset. 

Example:

Input: 'n' = 5, 'arr' = [3, 1, 5, 2, 8].

Ouput: 1

Explanation: We can partition the given array into {3, 1, 5} and {2, 8}. 
This will give us the minimum possible absolute difference i.e. (10 - 9 = 1).

Given a string (STR) of length N, you have to create a new string by performing the following operation:

Take the smallest character from the first 'K' characters of STR, remove it from STR and append it to the new string.

You have to perform this operation until STR is empty.

 Note:

The input string(STR) will not contain any spaces.

Assume that all characters in STR are lower case letters.

If characters less than 'K' remain, then append them in a sorted way to the new string.

Example:

Let the input string be "edcba" with K = 4.

Let the new string to be formed is initially empty, newString = "".
The first set of 4 characters are, ('e', 'd', 'c', 'b')
Out of these 4 characters, the smallest one is 'b' and hence we add it to the newString and it becomes, 
newString = "b"

The next set of 4 characters are, ('e', 'd', 'c', 'a')
Out of these 4 characters, the smallest one is 'a' and hence we add it to the newString and it becomes, 
newString = "ba"

Now we are left with "edc" and since we can't get a window of size 4, we sort them in the increasing order and append them to the newString.

Hence, newString thus formed will be "bacde".

Create a stack data structure that allows operations such as push (adding an element), pop (removing the top element), top (retrieving the top element), and also provides a way to retrieve the minimum element in constant time.

Implement the following public functions :

1. push(data) :
This function should take one argument of type integer. It pushes the element into the stack and returns nothing.

2. pop() :
It pops the element from the top of the stack and returns nothing.

3. top() :
It returns the element being kept at the top of the stack.

4.  getMin() :
It returns the smallest element present in the stack.

Operations Performed on the Stack:

Query-1(Denoted by an integer 1): Pushes integer data to the stack. (push function)

Query-2(Denoted by an integer 2): Pops the data kept at the top of the stack. (pop function)

Query-3(Denoted by an integer 3): Fetches and returns the data being kept at the top of the stack. (top function)

Query-4(Denoted by an integer 4): Returns the smallest element present in the stack. (getMin() function)

You are given an array containing ‘N’ integers. You need to find the number of subsequences of length 3 which are in Geometric progression with common ratio ‘R’.

A geometric progression (GP), also called a geometric sequence, is a sequence of numbers that differ from each other by a common ratio. For example, the sequence 2,4,8,16,… is a geometric sequence with common ratio 2.

Note:

As the answer can be very large you need to return the answer in mod 10^9+7.

What are the conditions for a deadlock to occur?

You have been given an array/list of strings 'inputStr'. You are supposed to return the strings as groups of anagrams such that strings belonging to a particular group are anagrams of one another.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase. We can generalize this in string processing by saying that an anagram of a string is another string with the same quantity of each character in it, in any order.

Note:

The order in which the groups and members of the groups are printed does not matter.

For example:

inputStr = {"eat","tea","tan","ate","nat","bat"}
Here {“tea”, “ate”,” eat”} and {“nat”, “tan”} are grouped as anagrams. Since there is no such string in “inputStr” which can be an anagram of “bat”, thus, “bat” will be the only member in its group.

You are given an array of integers 'ARR' of size 'N' and another integer 'K'.

Your task is to find and return 'K'th smallest value present in the array.

Note: All the elements in the array are distinct.

Example

If 'N' is 5 and 'K' is 3 and the array is 7, 2, 6, 1, 9

Sorting the array we get 1, 2, 6, 7, 9

Hence the 3rd smallest number is 6.

Given a singly linked list of 'N' nodes. The objective is to determine the middle node of a singly linked list. However, if the list has an even number of nodes, we return the second middle node.

Note:

1. If the list is empty, the function immediately returns None because there is no middle node to find.
2. If the list has only one node, then the only node in the list is trivially the middle node, and the function returns that node.