Q1) Given a binary string (represented by B and G for boys and girls in question), find the least number of switches (switching position of B and G from any index counts as 2) that maximizes the number of adjacent characters that are not the same.
Q2) Ways to partition an array (consisting of 1,2,3,…,n) into less than or equal to k sub arrays such that for any two sub arrays A and B, there are no elements a,c ∈ A and b,d ∈ B such that a<b<c<d.
Q3) Given a tree with bidirectional weighted edges. Pair nodes such that the sum of distances between each pair is minimized.
Q4) Lexicographically reorder all arrays whose individual elements add up to 1, 2, 3, so on. That is, the reordered list will be: ,[1,1],,[1,1,1],[1,2],[2,1], … and so on. Find the sum of the digits in the 10^6th element of list and product of the digits in the 10^9th element in the list.
These questions are a summarized version and I have skipped over a few details/story-setting.