ChitreshApte's blog

By ChitreshApte, history, 4 days ago, In English

We are given N words. We have to divide the words into groups. Each word can go into a single group. In a group, any two words taken should be related.

Let us say we have two words. Let the set of unique alphabets in these words be A and B respectively. The words are related if the difference between sets A and B is at most one.

The difference of at most 1 means
- 1 unique character of A missing in B. Example A = ['a', 'b', 'c'] and B = ['a', 'b']
- 1 unique character of B missing in A. Example A = ['a', 'b'] and B = ['a', 'b', 'c']
- 1 unique character of A replaced by another unique character in B. Example A = ['a', 'b', 'c'] and B = ['a', 'b', 'd']

Find the minimum number of groups required to group all the words.

Constraints:
10 Testcases
1 <= N <= 10^4
1 <= len(word) <= 30
the words contain only lowercase alphabets
Sample Input:
4
aabcd
abc
efg
eert

Sample Output:
3

We need 3 groups [aabcd, abc],[efg],[eert]

A related question: What can be the maximum-sized group that we can form?

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By ChitreshApte, history, 7 weeks 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.

Read more »

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