SDE - 1

Given two strings S and T consisting of lower case English letters. The task is to count the distinct occurrences of T in S as a subsequence.

A subsequence is a sequence generated from a string after deleting some or no characters of the string without changing the order of the remaining string characters. (i.e. “ace” is a subsequence of “abcde” while “aec” is not).

For example, for the strings S = “banana” and T=”ban”, output is 3 as T appears in S as below three subsequences.

[ban], [ba n], [b an ]

There are 'N' persons standing in a circular queue. There is a number written on the back of the shirts of every person. One person among them has a ball in his hands and the number written on his shirt's back is 1. The number written on the shirt of every other person is 1 more than the number written on the shirt of the person standing to the left of him. We have also been provided with an integer 'K' denoting the jump parameter. They start playing a game. The game proceeds as follows:

1. If there is only one person remaining in the game then the game stops immediately and the person is declared the winner.
2. The player who currently has the ball in its hand passes the ball to the person standing to his right. 
3. Step 2 happens exactly 'K'-1 times.
4. The game pauses here and the person who has the ball in his hand currently has to pass the ball to the person standing on his right and has to leave the game.
5. Again the game resumes with the remaining players.

You have been provided with positive integers 'N' and 'K'. Your task is to find the number written on the back of the winner when the game is played with 'N' members using the jump parameter 'K'.

For example:

N=4, K=2 -> K-1=1

The game starts with Person 1. He passes the ball to person 2. The game pauses here. Person 2 passes the ball to person 3 and leaves the game. Then the game resumes. Person 3 passes the ball to person 4. The game pauses here. Person 4 passes the ball to person 1 and leaves the game. Then the game resumes with person 1 having the ball in his hand. He passes the ball to person 3. The game pauses here. Person 3 passes the ball to person 1 and leaves the game. Now only person 1 remains and the game stops here.

Note

You are not required to print anything, just implement the given function and return the number written on the shirt of the winner of the game.

You are given an integer 'N'. For a given 'N' x 'N' chessboard, find a way to place 'N' queens such that no queen can attack any other queen on the chessboard.

A queen can be killed when it lies in the same row, or same column, or the same diagonal of any of the other queens. You have to print all such configurations.

You are given a reference/address of a node in a connected undirected graph containing N nodes and M edges. You are supposed to return a clone of the given graph which is nothing but a deep copy. Each node in the graph contains an integer “data” and an array/list of its neighbours.

The structure of the graphNode class is as follows:

class graphNode 
{  
    public:
        int data;
        vector<graphNode*> neighbours;
}

Note :

1. Nodes are numbered from 1 to N.

2. Your solution will run on multiple test cases. If you are using global variables make sure to clear them.

Introduce yourself
How will you react if you are asked to work overtime at the same pay?
How will you handle conflict in your colleagues?
Are you willing to relocate?
What do you know about the work culture here in our organisation?