HackWithInfy 2019 Round 2 Experience with Questions.

Sharing my Hackwithinfy 2019 Round 2 along with questions and other useful tips.

Introduction

In my previous blog I shared the questions and my experience for HackWithInfy Round 1. So if you haven't read that yet then check it out first.

In this one, I'll be sharing my experience from round 2 for which around 7,500 students were qualified.

So let's get started with the questions first.

Questions

Again the same as Round 1, we have 3 questions that are to be solved in 3 hours.

Question 1 - Peaks and Troughs

Expected Time Complexity - O(n)

Problem Statement

A function generates values that can be plotted as a line graph.

Peaks are points at which the function output changes from increasing to decreasing and troughs are points at which the function output changes from decreasing to increasing.

The first or last value in the graph is either a peak or trough depending on whether it is greater than or lesser than its neighboring value. If it is equal, it is neither a peak nor a trough.

Given the output of this function, find the maximum distance between any two consecutive peaks or two consecutive troughs.

Note: distance is the difference in the index at which the value occurs

Function Description

Input Format:

The first line contains an integer, n, where n denotes the number of values generated.

Each line i of the n subsequent lines ( where 0 <= i < n ) contains the ith value generated by the function.

Output Format:

Print a single integer denoting the maximum distance between any two consecutive peaks or two consecutive troughs.

Constraints

• 1 <= n <= 105

• 1 <= values generated by the function <= 105

• It is guaranteed that there will only be one key with the worst time. Input Format For Custom Testing

Sample Input

8 
5 
10
5
7
3
2
4
5

Sample Output

4

Explanation:

The peaks are 10, 7 and 5. Troughs are 5, 5 and 2.

The maximum distance is between 7 and 5 which is 4.

Question 2 - Max Gapping

Expected Time Complexity - O(nlogn)

Problem Statement

A program is required to find certain patterns in modeling data that has been provided in the form of an array.

The program is looking for a non-continuous monotonically decreasing pattern in the data.

Example: Assume that in an array A,

A[1] >= A[5] >= A[7] holds true

Then, these three elements form one such pattern.

You are provided the input data for this program.

What is the maximum possible difference in the index of two elements of any such pattern found by the program?

Function Description

Input Format:

The first line contains an integer, n, denoting the number of data elements in the array.

Each line i of the n subsequent lines ( where 0 <= i < n ) contains an integer describing the ith element in the array

Output Format:

Print one line denoting the maximum difference.

Constraints

• 1 <= n <= 105

• 1 <= A[i] <= 105

Sample Input

6
10
3
5
6
8
8

Sample Output

5

Explanation:

One of the patterns can be 10, 8 for which the difference between the elements is 5. This is the maximum possible difference in the given input

Question 3 - Science Exhibition

Problem Statement

Charlie is dropping off his nephew Jake at the Science Museum in Malibu.

Charlie tells Jake that he'll be back to pick Jake up after exactly x minutes.

Since Jake does not want to waste any time, he decides to utilize all the x minutes ( neither more nor less ).

There are n exhibition tours going on in the museum, connected by corridors. The entry into the museum is free, but each exhibition tour has a cost.

When walking around the museum, Jake will never skip an exhibition when walking past it, even if he has visited it before. He can also visit an exhibition more than once back to back since he's fond of them.

It is given that walking through the corridors from one exhibition to another takes a given amount of time.

Find the minimum amount that has to be spent by Jake while visiting the exhibitions.

NOTE: Jake always starts and ends at exhibition 1, since the entrance is located there

Function Description

Input Format:

The first line contains 4 integers x, n, m, t that are used to represent the following:

x: number of minutes which Jake has to spend at the museum

n: number of exhibitions

m: number of corridors

t: number of minutes it takes to walk through a corridor, from one exhibition to another

This is followed by n lines, where the ith line contains two integers t' and c, where t' denotes the time taken to tour the ith exhibition and c denotes the cost of attending the ith exhibition.

This is followed by m lines, each containing two integers u and v, denoting that there is a corridor from exhibition u to exhibition v.

Output Format:

An integer denoting the minimum cost required to spend x minutes or print "NOT POSSIBLE" ( without quotes ) if it is not possible to stay for exactly x minutes.

Constraints

• 1 <= x <= 1000

• 1 <= n <= 1000

• 1 <= m <= 1000

• 1 <= t <= 1000

• 1 <= time taken to tour any exhibition, cost spent while touring any exhibition <= 1000

• 1 <= u <= n

• 1 <= v <= n

Sample Input

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

Sample Output

5

Explanation:

Jake first goes to exhibition 1, then to exhibition 2 and finally revisits exhibition 1 and exits.

Thus, time taken = 1 ( Tour ex1 ) + 1 ( Go to ex2) + 2 ( Tour ex2 ) + 1 (Go back to ex1 ) + 1 ( Tour ex1 ) = 6

Amount spent = 2 ( Cost of ex1 ) + 1 ( Cost of ex2 ) + 2 ( Cost of ex1 )

My Experience

Personally, for me Round 2 was far much better than Round 1 of HackWithInfy.

Question 1 was very simple and I solved it quickly with the O(n) solution directly.

Question 2 was nice, I tried the brute force approach first with O(n2) complexity and was able to solve 6 test cases. However, after spending some time on it, I was able to solve the question in O(nlogn) time complexity which helped me clear all the test cases.

So, by far I had solved 2 questions completely with all test cases which was way better than my round 1. So I was quite positive when I moved to the third question.

Unfortunately, It was a Graph question and I was not very confident with Graph data structures at that time.

But I had like around an hour left, so I started thinking of the solution. I understood the question and tried implementing the solution but could not come up with any solution to test and submit.

Conclusion

So I can conclude by saying that I was quite happy with my performance in Round 2.

Now let's talk about the results.

I was not selected for the final round which is the on-site hackathon at the Pune campus. A total of 109 students were selected for the final phase of HackWithInfy in 2019.

But wait!!

There was a silver lining for me, I was given an opportunity for the pre-placement interview for the Power Programmer Role (CTC 8LPA).

Although Infosys never disclosed the exact ranking for the participants, it was written on their website that the top 300 or 500 (I don't remember exactly) are given the chance to get a pre-placement interview for power programmer.

So solving 2 questions didn't help me to reach in the top 109 candidates but it did help me to reach in the top 300 or 500.

Now what happened in the interview can be a topic for another blog.

So this was my experience with HackWithInfy 2019 competition.

If you have any doubts or queries then let me know in the comment section below.

See you in the next one 👋

Share it with One Tap 📤

Did you like it? Why don't you try also...