When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

codenationtest's blog

By codenationtest, history, 5 years ago, In English

Codenation test was conducted on Hackerrank on 15th July. There were 3 questions in the hiring contest.

Q1) Given a NxM (NxM <= 1e5) matrix with each cell having a value mod(Aij) <= 1e9. Job is to rank each element by the following rules:

1) Ranks start from 1.
2) Equal elements in the same row or same column should have the same rank.
3) Greater elements in the same row or same column should have a greater rank.
4) Maximum Rank should be minimized.

Print the final rank matrix.

Q2) N employees are given, you have to divide them into teams of two. If n is odd the last person will form a one man team. Problem is all employees are not compatible with each other. and if both are compatible with each other then only a team can be formed.

Aij ='C' if employee i is compatible with employee j, Aij = 'X' otherwise.
Aii ='C' if employee i can work as one man team, Aii = 'X' otherwise.

find the maximum no of valid teams that can be formed. constraints: T <=20, N<=18.

Q3) Given a Directed graph with N nodes and M edges. each node has a population Ai. you have to open outlets in some or all nodes following the conditions in decreasing priority:

1) Every Node must have access to some outlet either directly or through some path.
2) Maximize the average sales per outlet. sales are linearly proportional to the no of people that visit that 
   location. Average sales per outlet = (sum of all outlet sales)/(total number of outlets)
3) Minimize the number of outlets.

Print how many outlets will you open and in which node. Constraints : T <= 100, N <= 1e3, M <= min( 1e5, N(N-1)), Ai <= 1e3.

Please share your approach on how you solved each of them.

  • Vote: I like it
  • +47
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

2)for this we can simply do dp with bitmasking by updating 2 bits at a time,also for case of odd numbers we can update all dp state with one set bit to 1 initially. 3)i guess we can calculate total no. of connected components in the graph and any one point from each component can be taken as position for outlet though didnt do that in contest :')but i think this is the correct approch.u can use dsu for this

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    In 3rd question, to maximize the 'average' number of sales and to minimise the number of outlets, isn't it always better to choose the most populated node(only one) in each connected component and not 'any random node' as you said ?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if they are saying every node should have a rechable outlet. i assume total sales of the outlet is total population of the conected component it is in and no.of outlets ofc is no. of components. i dont exactly remember the sample test possibly that could clarify the dilemma

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We need to output only the number of outlet. So the answer would be number of connected components.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what you are saying is true, may be the question is asking something different or some different formula for average mean , also when edges are directed , talking about connected components doesn't make sense, so let's think of strongly connected components so now after we find SCC(strongly connected components) treat each group of SCC as a single node , so finally we will get a DAG(directed acyclic graph) where each node is a SCC.

      for eg: if suppose our final dag comes out to be a chain like structure with edges pointing in same direction it's better to place the outlet at the tail node(outdegree=0), if u place outlet at every node in a single SCC node the mean decreases .

      so i feel like we should be placing outlet's at places where the outdegree of that node is zero , just return the count of them.Iam not sure of this because i have no proof that this is maximum mean case, because sometimes placing an extra outlet in outdegree zero node increases the numerator of average sales high which overcomes the denominator and finally increasing the mean.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 6   Vote: I like it +6 Vote: I do not like it

        If we call the nodes in this DAG 'SCC nodes', each SCC node having an outdegree of 0 must contain atleast 1 outlet due to the first condition. Among the nodes in that SCC, it is optimal to make a node with the largest population an outlet.

        If an SCC node's outdegree is not 0, it can access an SCC node whose outdegree is 0. So no other nodes are required to be made an outlet due to the first condition alone.

        Among the nodes which aren't outlets, go on making a node with the largest population an outlet as long as it increases the average.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution to 1st Question of matrix.. it may be right.. https://ideone.com/Bs911f initialize 2d matirx with -ve infinity. first of all I sorted the 2d Matrix in ascending order while maintaining index then, suppose the first element is (i,j) pos in sorted then,find max rank in that ith row and in jth col then assign the maximum rank+1,if if element is equal to prev element then asign previous rank.. nlogn complexity with segment Tree.

  • »
    »
    5 years ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    we can solve it in another way using binary search . firstly do a co-ordinate compression to map those values inside the matrix to some small set of values then we will build a graph over the relation < , for each row/column after we sort individually&independently then we add edges to this directed graph as follows if u<v in a row/col then we add an edge from v to u . Note that we don't need to add edge for every u<v just add edge from largest u which is less than v from v , also note that this graph is acyclic(no cycles ). after u have built this graph do binary search over the max value. the check function/process would be like this ,here we consider all nodes which have indegree zero as source one by one and do a dfs from it and assigned it rank K , and rank K-1 to it's child , if u find any discrepancy after this process answer this return false else true.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain your solution more clearly, especially the co-ordinate compression part? Thanks in advance.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        as matrix values can be around 1e9 , we do co-ordinate compression(google it ) , so that we map those large values to small values , now why should we do it , because to keep our graph vertices small. around 1e5.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      What about this case?

      2 5
      2 3 1 1 1
      1 1 1 3 4
      

      (IMHO, the optimum cost is here 3.) I haven't thought much about this but I imagine that the correct solution should (in a clever way) create a graph over all cells of the matrix and not over the distinct values.

»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

My Approach to ques_3
Step 1 — Create an adjacency list of the graph where for each directed edge (u,v), you have an edge from v to u.
Step 2 — Place an outlet for all the nodes whose oudegree is 1 (size of adj[node] is 0)
Step 3- Compute the avg of the currently placed outlets based on the number of people from that node where outlet is placed. Let it be alpha.
Step 4 — Now for all the nodes without any outlet, sort their sales in descending order and traverse linearly till the avg is increasing. Compute the new avg taking into account the increase in the sales for placing outlet.
Step 5 — Output the resultant number
I couldnt solve it during the contest:/ but i believe this should work.

»
5 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

The second problem can be solved using bitmask dp.
Construct an undirected graph $$$n$$$ vertices and edges $$$(i, j) \in E$$$

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]


Let's assume $$$n$$$ is even.
We have to count the number of perfect matchings for this graph.
Define

Unable to parse markup [type=CF_MATHJAX]

as the number of perfect matchings for the subgraph $$$mask$$$.

Unable to parse markup [type=CF_MATHJAX]


Unable to parse markup [type=CF_MATHJAX]

, such that

Unable to parse markup [type=CF_MATHJAX]

is the first set bit in $$$mask$$$

When $$$n$$$ is odd, simply iterate over each vertex assuming it to be single, and solve for even case for the rest vertices.

Edit
It seems like I understood the problem differently (that every employee of N must belong to some team for the distribution to be valid).
If we can select any employees, then the problem is just to find the maximum matching in the above graph, which can be solved using Blossom Algorithm.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I couldn’t log in to the test that day but here is my solution for Project Allocation https://pastebin.com/kisKNzEx . Explanation: dp[i][j][k] where maximum groups till ith person with current status as j and k = 0 => no single group yet, 1 => one single group.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

did anyone receive interview calls for hiring ? / when will the results be declared ?