ChitreshApte's blog

Infosys Contest Questions
By ChitreshApte, history, 4 years ago, In English

Hi everyone, Infosys conducted the Hackwithinfy contest which just concluded yesterday. I found some questions very interesting but was not able to figure out solutions for those. Please share possible approaches or solutions for these. Any help will be appreciated.

Question 1

You are given 2 numbers N and M and an array of sizes N. A triplet is defined if it satisfies ANY ONE of the following conditions:

  1. All numbers in the triplet are the same (Eg. {1, 1, 1})

  2. The numbers are consecutive (Eg. {1, 2, 3})

Given the array, find the maximum number of triplets that can be formed. All elements in the array are <= M.

NOTE: Each element of the array can only be part of 1 triplet.

Constraints:
1 <= N <= 10^5
1 <= M <= 10^4
1 <= arr[i] <= M

Sample Input : 
4 2
1 2 2 2
Output : 1
Explanation: Only one triplet can be formed {2,2,2}

Question 2

You are given an array A of N elements. You need to divide the array into 4 non-empty contiguous subsequences B, C, D, E by making 3 cuts to it. Let P, Q, R, S be the sum of elements in the new arrays B, C, D, E.

Your task is to find the minimum possible absolute difference of the (maximum and minimum among P, Q, R, S)

Constraints:
4 <= N <= 10^5
1 <= A[i] <= 10^4

Sample Input : 
10
10 71 84 33 6 47 23 25 52 64
Output: 36

Question 3

(I am presenting the simplified form) We are given K arrays which are all permutations of numbers from 1 to N. The ith array represents the order of N people coming to a theatre on some ith day (1 <= i <= K). You have to find the maximum size of the group of people that come to the theatre in the same sequence each of the K days.

Constraints:
1 <= N <= 1000
1 <= K <= 10
1 <= a[i][j] <= N

Sample Input:
4 (this is N)
3 (this is K)
1 3 2 4 (day 1)
1 3 2 4
1 4 3 2 (day k)

Sample Output:
3
Explanation:
We can see people 1, 3, 2, they come in the same sequence all the days. So the answer is 3.

Note: This is a compilation of questions that were asked to different participants.

Thank You.

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

Comments Comments (48)
| Write comment?
»
4 years ago, # |
← Rev. 4   Vote: I like it +17 Vote: I do not like it

Problem 1 is similar to this: Jongmah

Problem 3 is similar to this: Gargari and Permutations

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

    Thank You

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Someone knows how to solve b ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      Iterate for the 2nd cut. Let's say the second cut is at the ith index. Now using binary search on prefix sum array, find the best cut for array[0:i] and using binary search on suffix sum array, find the best cut for array[i:n]. For each i from 0 to n-1, we use binary search two times, so the total time complexity is O(nlogn).

      Do comment if you feel something is wrong.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        find the best cut for array[0:i] what condition will you use to find the best j in the prefix ?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it -9 Vote: I do not like it

          Choose the prefix whose sum is closest to sum(array[0:i])/2

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +2 Vote: I do not like it

            I can not understand, like doing so will minimize the difference between P and Q. And if we do the same with the suffix. Like chose the closest to sum(array[i + 1 : n]). Then this will minimize the difference between R and S. But how does this minimizes the difference between max{P, Q, R, S} and min{P, Q, R, S}. P, Q, R, S is the individual sum of array partition as mention in the problem.

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

              Let the best cut for the left array according to my algorithm be P and Q. Let the actual best cut be P' and Q'. Let P <= Q and P' <= Q'. We can show that |P-Q| <= |P'-Q'|. Using P+Q = P'+Q' and |P-Q| <= |P'-Q'|, we can conclude P' <= P and Q' >= Q. Now whatever be the value of R and S, max{P, Q, R, S}-min{P, Q, R, S} <= max{P', Q', R, S}-min{P', Q', R, S}.

              Not a proper proof but hope it helps

              → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how did you find this

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

2) I'm a bit skeptical about this, but it seems like a 3-pointers problem.

3) I believe that this is just the longest common subsequence of all $$$a_i$$$. That should run in $$$O(KN^2) \approx 10^7$$$.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your slot was yesterday? My slot was on 7th May and problem 1 on my set was exactly same as yours. That's so unfair to those who had the earlier slots.

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

    It was not unfair. That problem is from the 7th May slot only, not from yesterday.

    → Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Giving problems of rating 2200+ srsly? Infosys? .. ;(

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone tell the algorithm for solving problem 3? I currently have $$$O(KN^K)$$$ solution.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 5   Vote: I like it -16 Vote: I do not like it

    3rd Problem could be done in O(K*N*N)

    Let's Define a matrix Pos[i][j] which will tell the position of Number 'j' in array 'i'.

    Now we will find the number of pairs (a,b) such that 'a' occurs before 'b' in all K arrays. Let this count be Cnt.

    The above could be achieved using Naive approach i.e., iterate for each pair (a,b) [this would take O(N*N) ] and then check for each array 'i' if Pos[i][a] < Pos[i][b]. If this is true for all 'i' in [1,K], then increment Cnt.

    Now upon observing we can realize that Cnt >= (ans*(ans-1))/2. So just find the closest 'ans' such that above equation is satisfied.

    Please Let me know if the above approach is incorrect.

    UPDATE : It's incorrect

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can't we just fix an array among all given k arrays, let say the first one.

      Then we find out LCS with all the remaining k-1 arrays in O(N*N).

      And the minimum LCS will be the answer?

      I am just asking if it can work or it will fail?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        I don't think your approach using LCS is correct

        Case : N = 4, K = 3

        Array 1 : 1 2 3 4

        Array 2 : 1 4 2 3

        Array 3 : 2 3 4 1

        Your approach would give 3 but correct answer is 2.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Consider this test case:

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

      Clearly the answer is 2[1, 4]. However, Cnt = 3,[(1, 4), (2, 4) and (3, 4)]. So, from your logic, answer should be 3. So, this is also wrong.

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

        But can't we do one thing we find out lcs of first two then Find lcs of the previous lcs and next array

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      After getting the matrix of positions, we can consider it as tree edges and then try to find the height of the tree for every number x as the root of the tree. The maximum of all the heights will be the answer.

      Generating the root has N options and doing a depth traversal from each chosen root to find tree height will be O(N), so the time complexity (for this tree process) will be O(N²). However the matrix creation takes O(K*N²) time.

      The overall complexity will be O(K*N²).

      Please let me know if this is incorrect.

      Update: I just found out that this problem is already available here and has the similar solution as what I tried to convey.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    (https://ideone.com/iLQvgv)

    Link to my code

    → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Isn't problem 3 LCS?

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

    Yes, it is LCS, but we have multiple arrays of which we want LCS.

    → Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I wonder, what does Infosys want to prove by giving 2000+ rated problems in the contest. It isn't like they are going to give some 20 lpa. They would give a mere 5-7 LPA and they want red coders in their company lol.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    .

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    yeah i dont get it either, wallmart labs, microsoft, etc had easier questions, i went through some of the questions my friend told me after her assessment and it was a day before op's assessment and boy was i shocked, it was definitely 2200+ questions, i dont get why would anyone who can solve such questions join infosys xD

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You should keep in mind that it wasn't a placement round, it was a HACKATHON !!, and hackathons are meant to be challenging.

    → Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

wtf is this??.. If someone can solve question of rating 2200 ,why will they go to infosys?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I had different questions. Did someone get the matrix question in which we had to throw out garbage?

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I solved problem 2 but I am not sure if it is correct or not.

pre[i][0] = sum of subarray elements starting from o to l where(l < i)

pre[i][1]= sum of subarray elements starting from l + 1 to i

such that absolute difference between pre[i][0] and pre[i][1] is minimum.

also calculated suf[i][0], suf[i][1] for subarray from i to n — 1.

link to my code

→ Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

2 is direct copy of this AtCoder problem (they even used the same variables lmao)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
My Problems 10 May, 2021
→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

ANY HELP WILL BE APPRECIATED, THANKS IN ADVANCE :)

ANOTHER QUESTION FROM HACKWITHINFY 2020

Problem DIFFRENT ARRAYS
→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

The question are worth more value than the company itself xD.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    The irony is that they don't even make these questions. Just Copy, Paste, and Edit.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Bro which company in the world gives 2200 rating questions for a 8 LPA (in Indian Rupees) job??

      That too after taxes and all idk how much people get in-hand salary.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with this problem asked in infytq link .

It would be great if author can add it to the post.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain me the DP approach of Qn1? I could not understand the editorial.1110D - Jongmah

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hii, for hackwithinfy i was using firefox and the timer wasn’t running but i was able to view and submit problems and after one hour i switched back to chrome will they disqualify me? Also will i get call for PP , I wad able to solve 2 problems full and 1 problem 78% .

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

    Switching the browser is not a problem.

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

      Thanks man, actually i asked the same question on codechef forum and someone replied that 90% chances are of disqualification :(

      → Reply