0 like 0 dislike
4,933 views
| 4,933 views

0 like 0 dislike

There were 4 questions to solve in 90 minutes.
Platform: Glider.ai

1.

General Problem: Boolean Parenthesization Problem.
Original Question: Given a boolean expression with following symbols.
Symbols:
'T' ---> true
'F' ---> false
And following operators filled between symbols
Operators:
& ---> boolean AND
| ---> boolean OR
^ ---> boolean XOR
Count the number of ways we can parenthesize the expression so that the value of expression evaluates to true.
Let the input be in form of two arrays one contains the symbols (T and F) in order and other contains operators (&, | and ^}
Examples:
Input: symbol[] = {T, F, T}
operator[] = {^, &}
Output: 2
The given expression is "T ^ F & T", it evaluates true
in two ways "((T ^ F) & T)" and "(T ^ (F & T))"
Input: symbol[] = {T, F, F}
operator[] = {^, |}
Output: 2
The given expression is "T ^ F | F", it evaluates true
in two ways "( (T ^ F) | F )" and "( T ^ (F | F) )".

2.

General Problem: Partition a set into two subsets such that the difference of subset sums is minimum.
Original Question: Given N chocolate bags containing some chocolates (ith bag contains arr[i] chocolates).
Distribute these bags between two people such that the absolute difference in the total number of chocolate each one gets, is minimum.

3.

General Problem: Find Maximum number possible by doing at-most K swaps.
Original Question: Given a string S of digits and a number K, output the largest number possible by performing swap operations on the digits of S at most K times.

4.

General Problem: Collect the balls between two roads.
Original Question: There are two parallel roads, each containing N and M buckets, respectively. Each bucket may contain 0 or more coins. The coins in first road are given in an array A and coins in the second road in an array B. The buckets on both roads are kept in such a way that they are sorted according to the number of coins in them (either ascending or descending). Both roads are sorted in the same order. You start from the end of the road which has the bucket with a lower number of coins(i.e. if buckets are sorted in increasing order, then you will start from the left side of the road).

• You can choose any road to start.
• You can change the road only at the point of intersection(which means, buckets with the same number of coins on two roads, not necessarily at the same distance from the start.).
• If you choose to switch roads, you'll collect from only one of the two buckets that you switched between.
Output the maximum possible coins that you can collect.
by Expert (113,040 points)