Блог пользователя codenationtest

Автор codenationtest, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +47
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        Rev. 6   Проголосовать: нравится +6 Проголосовать: не нравится

        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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      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 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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