Given a matrix mat of size N x M where every element is either ‘O’ or ‘X’.
Replace all ‘O’ with ‘X’ that are surrounded by ‘X’.
A ‘O’ (or a set of ‘O’) is considered to be by surrounded by ‘X’ if there are ‘X’ at locations just below, just above, just left and just right of it.
Imagine you have a special keyboard with the following keys:
- Key 1: Prints ‘A’ on screen
- Key 2: (Ctrl-A): Select screen
- Key 3: (Ctrl-C): Copy selection to buffer
- Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.
Find maximum numbers of A’s that can be produced by pressing keys on the special keyboard N times.
Allocate minimum number of pages
You are given N number of books. Every ith book has Ai number of pages.
You have to allocate contiguous books to M number of students. There can be many ways or permutations to do so. In each permutation, one of the M students will be allocated the maximum number of pages. Out of all these permutations, the task is to find that particular permutation in which the maximum number of pages allocated to a student is the minimum of those in all the other permutations and print this minimum value.
Each book will be allocated to exactly one student. Each student has to be allocated at least one book.
Note: Return -1 if a valid assignment is not possible, and allotment should be in contiguous order (see the explanation for better understanding).
Given an array Arr[] of N positive integers. The task is to find the maximum of j - i subjected to the constraint of Arr[i] <= Arr[j].
Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)
Assignment Problem에 cost 주는 문제들은 Mcmf로 모델링 해서 푸는게 쉬운거 같다. 단순 이분 매칭일때 최대 매칭을 찾는 알고리즘은 헝가리안 알고리즘이 조금 더 간단하긴 함.
IPL 2021 Finals are here and it is between the most successful team of the IPL Mumbai Indians and the team striving to garb their first trophy Royal Challengers Banglore. Rohit Sharma, captain of the team Mumbai Indians has the most experience in IPL finals, he feels lucky if he solves a programming question before the IPL finals. So, he asked the team’s head coach Mahela Jayawardene for a question. Question is, given a string S consisting only of opening and closing parenthesis ‘ie ‘(‘ and ‘)’, the task is to find out the length of the longest valid parentheses substring.
NOTE: The length of the smallest valid substring ( ) is 2.
Given a matrix cost of size n where cost[i][j] denotes the cost of moving from city i to city j. Your task is to complete a tour from the city 0 (0 based index) to all other cities such that you visit each city atmost once and then at the end come back to city 0 in min cost.
A Hamiltonian path, is a path in an undirected or directed graph that visits each vertex exactly once. Given an undirected graph the task is to check if a Hamiltonian path is present in it or not.
Given a string s and a dictionary of words dict of length n, add spaces in s to construct a sentence where each word is a valid dictionary word. Each dictionary word can be used more than once. Return all such possible sentences.
Follow examples for better understanding.
Maximum absolute difference between sum of two contiguous sub-arrays
Given an array of integers, find two non-overlapping contiguous sub-arrays such that the absolute difference between the sum of two sub-arrays is maximum.