TheJobOverflow | Sprinklr Coding Round Oncampus 2022

Question: Sprinklr Coding Round Oncampus 2022

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/>

ADD COMMENT • link

Entering edit mode

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

ADD REPLY • link 2.4 years ago

mod2 870

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  &lt;= 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 ) &lt;= 25 , dp[curNode][prime[i]] += dp[child][prime[j]] ( isPrime[prime[i] + prime[j]] == true)

> Time complexity = N*(25x25) == O(N)

ADD COMMENT • link 2.4 years ago Gigaliths 570