Join UsSite Message
Only Premium Users can view the Question
Entering edit mode
There were a total of 3 questions in the coding round of increasing difficulty. <br/> Total Time: 90 minutes <br/>
<h3>Q1 : 50 points</h3>
A binary string consisting of 0's & 1's is given, along with a number X. We have to output the total number of substring having no of 1's >= X. <br/>
Eg:<br/> S = "1010", X = 2 <br/> Ans = 2 ("101", "1010") <br/>
<h3>Q2: 75 points</h3>
There are a total of N questions given to you. K out of this N questions are mandatory.<br/> Every question has some dependency i.e for example we have question 1 and it has dependencies 2,3,4 this means before solving 1 we need to solve 2,3 and 4. <br/> Find the minimum no. of questions that need to done such that we can do those k mandatory questions.<br/>
<h3>Q3: 100 points</h3>
You are given a graph. You have to assign a value to each vertex.<br/> The value should be a prime number less than 100 and the values need to be assigned in such a way that no two adjacent vertex should be prime. <br/> Find the total number of unique ways possible to assign the values.<br/>
Entering edit mode
Problem 3
> Observation 1 : There are roughly 25 prime numbers between 2-100.
> Observation 2 : Each node can choose any of these 25 prime numbers (similar to how we can make 2 choices in knapsack problem)
We can come up with a Dynamic Programming solution. ( contains number of ways to assign under its subtree )
dp[node][prime] , prime = { 2 . . . 97 } , isPrime = Boolean map for prime lookup.
Run dfs from root of the tree and solve the problem bottom-up.
Base Case : when we reach leaf node ,
for all i <= 25 , dp[curNode][prime[i]] = 1
Normal Case : We assign prime[i] and add valid subtrees with child having prime[j] as its root.
for all (i , j ) <= 25 , dp[curNode][prime[i]] += dp[child][prime[j]] ( isPrime[prime[i] + prime[j]] == true)
> Time complexity = N*(25x25) == O(N)
Quick Solution Sketches
Problem 1 There are multiple ways to solve this. One approach is to mantain sliding window and do basic counting to compute answer.
Problem 2 Construct a graph, where each question is a node and there exists and edge from question X to question Y iff X is required to be solved in order to solve Y. Now, you can do usual "Topological Sorting" to process nodes. Keep track of how many K compulsory questions you have solved, stop toposort as soon as you have solved those K problems.
Problem 3 Beautiful solution mentioned below by @Gigaliths