SDE - 1

Given an infinite supply of Indian currency i.e. [1, 2, 5, 10, 20, 50, 100, 500, 1000] valued coins and an amount 'N'.

Find the minimum coins needed to make the sum equal to 'N'. You have to return the list containing the value of coins required in decreasing order.

For Example

For Amount = 70, the minimum number of coins required is 2 i.e an Rs. 50 coin and a Rs. 20 coin.

Note

It is always possible to find the minimum number of coins for the given amount. So, the answer will always exist.

You have been given an integer ‘X’ and a non-decreasing sorted doubly linked list with distinct nodes.

Your task is to return the number of triplets in the list that sum up to the value ‘X’.

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)

You are given a square matrix ‘NxN’ rows and columns. The matrix is sorted, meaning all rows and columns of the matrix are sorted in ascending order. You are also given an integer ‘K’, and your task is to find the ‘K’th smallest element in the sorted order.

For example:

You are given ‘mat’ = [[1, 2, 2,], [3, 3, 4], [5, 6 ,7]]] and ‘K’ = 5, the elements of the matrix are [1, 2, 2, 3, 3, 4, 5, 6, 7], the 5th smallest element in the matrix is 3. Hence the answer is 3.

You are given a string ‘expression’ consists of characters ‘+’, ‘-’, ‘*’, ‘/’, ‘(‘, ‘)’ and ‘0’ to ‘9’, that represents an Arithmetic Expression in Infix Notation. Your task is to evaluate this Arithmetic Expression.

In Infix Notation, operators are written in-between their operands.

Note :

1. We consider the ‘/’ operator as the floor division.

2. Operators ‘*’ and ‘/’ expression has higher precedence over operators‘+’ and ‘-’ 

3. String expression always starts with ‘(‘ and ends with ‘)’.

4. It is guaranteed that ‘expression’ represents’ a valid expression in Infix notation.

5. It is guaranteed that there will be no case that requires division by 0.

6. No characters other than those mentioned above are present in the string. 

7. It is guaranteed that the operands and final result will fit in a 32-bit integer.

For example :

Consider string ‘expression’ = ‘((2+3)*(5/2))’. 
Then it’s value after evaluation will be ((5)*(2)) = 10. 

You are given two numbers, ‘X’ and ‘Y’. Your task is to find the greatest common divisor of the given two numbers.

The Greatest Common Divisor of any two integers is the largest number that divides both integers.

For Example:

You are given ‘X’ as 20 and ‘Y’ as 15. The greatest common divisor, which divides both 15 and 20, is 5. Hence the answer is 5.

You are given a Binary Tree of 'n' nodes.

The Top view of the binary tree is the set of nodes visible when we see the tree from the top.

Find the top view of the given binary tree, from left to right.

Example :

Input: Let the binary tree be:

Output: [10, 4, 2, 1, 3, 6]

Explanation: Consider the vertical lines in the figure. The top view contains the topmost node from each vertical line.

Given a binary tree, return the vertical order traversal of the values of the nodes of the given tree.

For each node at position (X, Y), (X-1, Y-1) will be its left child position while (X+1, Y-1) will be the right child position.

Running a vertical line from X = -infinity to X = +infinity, now whenever this vertical line touches some nodes, we need to add those values of the nodes in order starting from top to bottom with the decreasing ‘Y’ coordinates.

Note:

If two nodes have the same position, then the value of the node that is added first will be the value that is on the left side.

For example:

For the binary tree in the image below.

The vertical order traversal will be {2, 7, 5, 2, 6, 5, 11, 4, 9}.

What are semaphores? (Learn)
What is virtual memory? (Learn)

What are ACID properties? (Learn)

What are joins? (Learn)