SDE - 1

Given an array/list 'ARR' of ‘N’ distinct integers, you are supposed to find the third largest element in the given array 'ARR'.

Given a text and a wildcard pattern of size N and M respectively, implement a wildcard pattern matching algorithm that finds if the wildcard pattern is matched with the text. The matching should cover the entire text not partial text.

The wildcard pattern can include the characters ‘?’ and ‘*’

 ‘?’ – matches any single character 
 ‘*’ – Matches any sequence of characters(sequence can be of length 0 or more)

Aragorn is a great ruler and desires to become the most powerful in the entire world. There are ‘N’ kingdoms, kingdoms are numbered from 0 to 'N' - 1 and form of a tree, you are also given the information about the edges of this tree depicting all the Kingdoms that are adjacent to each other.

The ruler with the most kingdoms is considered the most powerful. You desire to become the greatest ruler without having to fight with Aragorn. Kingdoms are conquered one at a time in turns in order to make the process smooth and less violent.

Aragorn initially rules only the ‘X^th’ kingdom and all other kingdoms are not ruled by anyone. In each turn, a ruler can conquer another kingdom that is adjacent to one of his current kingdoms and is ruled by none of the rulers, the opponent plays the next turn and the process is repeated. The game continues until both the players run out of moves. If a ruler has no available adjacent kingdom to conquer then he passes his turn. In the end, the ruler with more kingdoms under his control wins the game.

Aragorn gives you an advantage in the first turn, letting you choose a kingdom of your choice, but for all other moves, you can only conquer a kingdom adjacent to one of your current kingdoms. If Aragorn plays optimally, determine if it’s possible for you to win by becoming the most powerful or not, print “true” if you can become more powerful than Aragorn, else return “false”.

For Example :

If N = 7, X = 2 and Edges = { {0, 1}, {0, 2}, {1, 4}, {1, 5}, {2, 3}, {4, 6} }

Then the tree is: 

Here N = 7 depicts that there are seven kingdoms (numbered from 0 to 6). Edges depict that kingdom-0 and kingdom-1 are adjacent, kingdom-0 and kingdom-2 are adjacent, and so on. And Aragorn initially controls kingdom-2.
Then in this case, if you select kingdom-1 in your first then, then Aargon will select kingdom-0 in the next turn, as both rulers play optimally, therefore in the end Aargon will be ruling kingdom-0, kingdom-2 and kingdom-3 and the remaining four kingdoms will be ruled by you. Hence you will be able to win the game and therefore we will print “true”.

You are the manager of a hotel having 10 floors numbered 0-9. Each floor has 26 rooms [A-Z]. You will be given a sequence of strings of the room where ‘+’ suggests the room is booked and ‘-’ suggests the room is freed. You have to find which room is booked the maximum number of times.

Note:

You may assume that the sequence is always correct, i.e., every booked room was previously free, and every freed room was previously booked.

In case, 2 rooms have been booked the same number of times, you have to return Lexographically smaller room.

A string 'a' is lexicographically smaller than a string 'b' (of the same length) if in the first position where 'a' and 'b' differ, string 'a' has a letter that appears earlier in the alphabet than the corresponding letter in string 'b'. For example, "abcd" is lexicographically smaller than "acbd" because the first position they differ in is at the second letter, and 'b' comes before 'c'.

For Example :

n = 6, Arr[] = {"+1A", "+3E", "-1A", "+4F", "+1A", "-3E"}

Now in this example room “1A” was booked 2 times which is the maximum number of times any room was booked. Hence the answer is “1A”.

You are given a ‘Binary Tree’.

Return the level-order traversal of the Binary Tree.

Example:

Input: Consider the following Binary Tree:

Output: 
Following is the level-order traversal of the given Binary Tree: [1, 2, 3, 5, 6, 4]

You are given two sparse vectors ‘vec1’ and ‘vec2’. You have to compute the dot product of these two vectors and print the final answer.

Implement class :

Sparse Vector: Initialize the vector.

dotProduct(vec2): Implement the dot product between vector ‘sparseVector’ and ‘vec2’.

For Example :

‘N’ = 6, ‘vec1’ = {2, 4, 0, 0, 1, 0}, ‘vec2’ = {0, 0, 3, 0, 5, 0}

Now in this example, the dot product of these two vectors is (2 * 0) + (4 * 0) + (0 * 3) + (0 * 0) + (1 * 5) + (0 * 0) = 5. Hence the final answer is 5.