Contest Experience : GeeksforGeeks Mega Job-A-Thon [05-07-23]
About Contest:
- This contest consists of 4 parts:
- 3 DSA coding problems
- 5 MCQ on programming logic
- 5 MCQ on logical reasoning
- 5 MCQ on quantitative aptitude
- This contest is held to shortlist programmers by specific companies based on their own criteria.
- Languages supported for the DSA problems were C++, Java, and Python.
- There was also 5% penalty for each wrong submission.
- Link of the contest !!
Coding problems:
There was total 3 coding problems, all of them based on DSA.
Overview Table:
Problem Name |
Difficulty |
Pre-requisite |
Approx. time to solve |
Number of Submissions |
---|---|---|---|---|
Magic and Toy shop |
Easy |
Greedy |
5-8 mins |
1 |
Count beautiful Strings |
Medium-Hard |
Hashing |
20- 25 mins |
3 (2 TLE) |
Maximum good length |
Medium |
Binary Search ,Pre-sum |
15- 20 mins |
1 |
Question 1 : Magic and toy shop
Observations:
It was an easy problem in which we just have to think about in which index we have to perform the operation first to get most benefit , after some observation we can easily find out the greedy approach will work just fine.
Approach :
- Calculate the sum of magical_price for all elements.
- if it is greater than M than it is not possible to buy all the toys so returning -1.
- Else create a priority queue of in which we store = ‘ price[i] – magical_price[i] ‘
- It will store the maximum profitable element we can get , at the front after the operation.
- Calculate the current total price.
- while our sum of current total price is greater than M we do the following:
- We increase the operation count.
- We decrease the current total price by front element and pop that element from queue.
- Return the operation count.
Result : Accepted!!
Question 2 : Count beautiful Strings
Observations:
This was a very good problem , Initially my thought was we can always select two strings having same odd characters and merge them it will create a string having all characters with even frequencies , but how should I find out that one odd occurring character ? after some thought I have the idea about:
Brute force Approach [TLE] :
Well I saw the problem and thought of a fairly easy brute force approach which was:
- find every pair in the string and check weather we can make a beautiful string with the help of them or not.
Obviously it will work but it will surely give us TLE because of constraints.
Optimized Approach :
- Create a 26 size vector for each string and store the even or odd frequency of the characters , and store it in a map.
- Initialize the answer variable = 0
- Traverse through the map and for each time increase the value of answer by:
- ans = ans + freq*(freq-1)/2 . // taking two vectors of same kind of character appears odd times and create a new string.
- where freq = number of times that perticular vector occur .
- ans = ans + freq*(freq-1)/2 . // taking two vectors of same kind of character appears odd times and create a new string.
- Till now we have calculated the strings having all characters even times.
- Now for “atleast one character is odd” :
- iterate through all the vectors in map and check for each lowercase alphabet , weather it can be that odd character or not ?
- if we have already present a vector in map where all other characters parity are same [ odd and even ] only the current characters parity is different then we can make a string by selecting these two strings also so :
- update the answer by multiplication of those two vectors frequency .
- return the answer.
Result: TLE … again !! But why ??
Reason: we are searching the vector again and again in the map which causes this problem … now how can we improve it ??
Improved Optimized Approach:
- In this approach we are doing same thing as above just replacing the vector for each string by a number .
- Idea :
- We will traverse in the string and if any character present odd times we will set the i-th bit of that number where i will be index of the character in the English alphabet [ like: a->0 , b->1 ,c->2 … z->25].
- ex if string is : S = “abc” then our number will be : (111)2 -> 7.
- now we will store these values in map and do the operation just like above and we will save a lot of time by converting the vector into a number .
- in the end return the answer.
Result: Accepted!!
Question 3 : Maximum Good Length
Observations:
Because we have to tell the maximum size of L for which has atleast one L*L submatrix having minimum value >= L . And most of the maximum of minimum problems can be solved by Binary Search , So I applied it.
Approach :
- Apply binary search on the Length ‘L’ and for each L we calculate the following:
- make a temporary_matrix and store its value matrix[i][j] >= L ? 1 : 0 .
- and do the 2D pre-sum , it will help us to find out a valid submatrix in O(n*m) time.
- Store the value of L in the answer and update value of low and high accordingly.
- In the end return the answer .
Result: Accepted !!
Contact Us