ClearTax India Intern

I got placed in ION Trading during campus placements. But I was not satisfied, I wanted to work at some good startup. I started to reach out to people on LinkedIn regarding openings in fast moving startups. Fortunately, I asked one of my seniors who was working in ClearTax and he agreed to share my resume with HR. 

I had one coding round, then code review, problem solving and data structures round and finally, hiring manager round. It was fun interviewing at ClearTax. As I was expecting,  I received a call from HR congratulating me. They wanted me to do an intern before joining as SWE. 

My intern started in mid of Feb 2019. Initially I joined as devops engineer intern. In second week of my intern after discussing it with Director of Engineering I got transferred to e-Filing team where I started working as SWE intern. 

I didn't got any individual project to work on. Some tasks were assigned to me in every sprint. I was working like every other engineer in my team. Everyday in stand-ups I used to tell what I did yesterday and what I am planning to do today like every other person in team. They use to treat me more like an FTE and less like an intern. I met great people there. My mentor was really cool and patient guy. 

Everybody was happy with my work and I received a full time offer from ClearTax for SWE. They were offering a good salary and it was really difficult to decide between ClearTax and Amazon. It was a great experience interning there. It was very different from my experience at Microsoft. Here I had more responsibilities and ownership of the work I was doing.

Cheers!

Read More

Microsoft IDC intern

Oh! It's been a long time.

From the time of my last post, tons of things have happened. Some of those things are, got my first backlog in engineering (that also in my fav subject, surviving in SPPU is tough), interned (SWE) at Microsoft IDC, interned (SWE) at ClearTax India and started working as Software Development Engineer at Amazon India. So, I got a lot to cover, which I will do in 2-3 posts. This post is about Microsoft intern.

It was a great experience interning at Microsoft. I was part of Azure Alert management team. Being a competitive programmer it was my first time working on something which was actually going to make an impact on real world. I can't talk much about the project due to the NDA I signed, but I had an ambiguous and interesting problem to solve. It was fun (and frustrating at times) working on that project. But I am glad, I got a chance to meet cool and smart people during that intern. I got to learn a lot.  

Some people might be interested in how did got this intern. It was an off campus drive, one of my senior referred me. People from different IITs, NITs, IIITs, BITS were there, so initially I was a bit nervous. But after 2nd round I was confident that I will get selected. That was my day and I was feeling it. I was the first guy who got selected that day. It was a real confidence booster. So, If you are interested in getting a software engineering job, work on basics of CS, algos and data-structures and you can crack any interview. Doing CP is the easiest and most interesting way to work on those skills.

I don't know what else to write. 

Cheers! 

  

Read More

MO's ( Query-Sqrt Decomposition) Algorithm on Tree

I was trying hard to solve a problem from July Long Challenge and even after one day of thinking i was not able to solve it. So i decided to solve sub-tasks. For solving sub-tasks, i decided to use MO's algo (aka Query-Sqrt Decomposition).

Prerequisite: MO's algorithm, Euler tour technique (ETT).

So, I needed to do queries on edges (weights) of undirected tree. After searching little bit, i found this article on codeforces. It's a good article. I learnt how to do queries on path for a given tree but the problem was to do queries on edges, not vertices.

After thinking for a while, i came up with a solution. I stored the ETT of the tree in a vector and did all the queries on the ETT. In this method we don't need to find LCA. All we need to do is store the position of first occurrence of each element in an array. For doing query between u and v, we need to do query between firstOccurrence(u) to firstOccurrence(v). While doing query, if an edge occurs twice, we need to remove its contribution from answer. It will be more clear from the following example:

Let us find the sum between u and v for the given tree.

 The ETT for the above example is : { 1, 2, 3, 4, 3, 2, 5, 6, 5, 2, 1, 7, 8, 7, 9, 7, 1}
(How?  open this).

Code for finding ETT:


Now for example i want to do query between 6 to 9.

(Assuming 0-based index)

L = firstOccurrence(6)
R = firstOccurrence(9)

so L = 7  and R = 14

{ 1, 2, 3, 4, 3, 2, 5, 6, 5, 2, 1, 7, 8, 7, 9, 7, 1,}

The answer is (6 -> 5) + (5 -> 2)+ (2 -> 1) + (1 -> 7) + (7 -> 8) -  (8 -> 7) + (7 -> 9), i.e., 8+2+5+4+1-1+6 = 25.
As i mentioned earlier, if an edge comes twice we will delete its contribution to answer, that is why we removed (8->7)'s weight, as it has occurred earlier.

I hope, you guys find it helpful and interesting!

Read More

AGGRCOW - Aggressive cows SOLUTION

AGGRCOW - Aggressive cows is a good question based on Binary Search! (It took me an hour to figure out, how to crack this nut using binary search :P )

My solution's complexity is O(n logn).

If you haven't done a lot of problems based on binary search, then this problem will make you learn something good!

Now let us talk about the question. In the problem statement it is given that N (2 <= N <= 100,000) and
x1,...,xN (0 <= xi <= 1,000,000,000). This makes one thing very obvious that the maximum possible ans is  1,000,000,000 and the minimum possible answer is 1.

We have got our upper and lower limits, and now we have to find the answer, which exist between them.

But the question arises, why binary search? It is very clear that, for a value 'x', if it is not possible to keep all the cows in the stalls with the minimum distance between any two cows as 'x', then it will not be possible for all y > x  , and hence answer<x. This is the point which gives entry to binary search in the scene!

Now, we will do binary search for answer, with i as upper and j as lower limit, mid is the middle element. For each mid we will see if it is possible to fit all the cows in stalls with mid as the minimum distance between any two cows. Further we can decide if we have to search for the answer in the upper or lower half of the mid!

If you find any difficulty in coding part, refer to the following code!

Happy Coding! :) 

Read More

ACM ICPC Asia Chennai regional 2016

Today, i am going to write something off-topic, which is not related to "SPOJ solutions". Well, this is pretty clear from the title that i am going to talk about my experience of ACM ICPC Asia Chennai regional. Overall it was a good experience, but it would have been better if our team would have performed good in contest!

The contest was hosted on codechef, and the problemssetters were previous years ACM ICPC finalists/contestants. There were total 10 problems, and top 4 teams solved 6 of them. We solved just 2 very easy problems. The third problem was based on extended euclidean algorithm. We spend 4 hours trying to solve that problem, but due to lack of knowledge we were not able to solve it.
After a long struggle of 4 hours, we moved on to next problem, which was based on "trie". That problem was solvable, but by the time we started solving that problem it was too late! We had only 14 minutes left to implement "trie". We weren't able to solve this problem too. It was a bad contest for us. We didn't expected that we will perform this bad, but we were happy as we competed with great coders, like Atanu Chakraborty, Rajat de.

What we got to know from that contest was, the biggest difference between small colleges like ours and colleges like IIT Kanpur or IIITH is "coding culture". We don't have that coding culture. There are many more points like our maths club and programming club are two different things, our programming club focuses mainly on first year students, and two major points are, negligible interaction with seniors and we are not that hardworking!

It was a good experience! I hope next year we'll perform better!

Read More

CODERE3 - Coder Express 3!! - SOLUTION

CODERE3 - Coder Express 3!! is very easy DP problem.

I've solved this problem in O(n^2), but there is a better solution also, which runs in O(n(logn)) time complexity.

This problem is based on longest increasing sub-sequence (link for n*logn recursive DP for LIS).

There are two arrays, l[] and r[]. ith index of l[] tells the longest increasing sub-sequence till ith element, and same is for r[].

For finding longest increasing sub-sequence, we will traverse i 0 to n, and j from i+1 to n, and will check following conditions:

if (a[i] < a[j] && l[j] < l[i] + 1)

                    l[j] = l[i] + 1

And by doing same thing in reverse order, we can get r[].

After calculating l[] and r[], we will find the point where l[i] + r[i] is max. 

This was explanation for O( n^2 ), now try to think solving this problem in   O(n(logn)). 

If you find any difficulty in coding part, refer to the following code: 

Read More

IAPCR2F - Summer Trip - SOLUTION

IAPCR2F - Summer Trip is an easy DSU problem. If you don't know what Disjoint set union is, then you should first understand DSU then try solving this problem!

I've solved this problem using breadth first search (BFS).

There are T test cases, and each test case contains 'n', which denotes the number of students who are going for trip, and 'm'  denotes the number of relations between them.

Next line contains 'n' integers, which denotes the money for ith student, and next 'm' lines tells relationship between students.

After understanding the problem statement it is very clear that we need to form disjoint sets, and find money for each disjoint set.

This can be easily done by applying BFS to each such node, which is not yet visited. If we choose any node and apply BFS, we will visit all the nodes reachable from that node, and we can easily count money for each node, present in that disjoint set.

I think, now its easy to code for this problem. If you find any difficulty in coding part, refer to the following code:

Read More

FRNDCIRC - FRIEND CIRCLE - SOLUTION

FRNDCIRC - FRIEND CIRCLE is an easy DSU problem. If  DSU is an "alien" term for you, I recommend you to, understand Disjoint set union first and then try solving this problem!

If you want to solve easier problem based on DSU, try solving FOXLINGS. If you find difficulty in solving this problem you can refer to the tutorial.

In this problem, in each test case, we are given 'n' , number of  new friendships. For each such new forming friendship, we need to find the total number of people in their friend circle!

So, for each query, if the new friends were already in the same friend circle, their friendship will not affect the size of friend circle. But if they were not friends before, we will perform union operation on their friend circles, and the new size of friend circle will be, friend1_cirlce_size + friend2_cirlce_size.

I know, now you can code solution for this problem easily, isn't it?
More hint? You need to use STL (unordered_map) to solve this problem.

If you find any problem in solving this question, refer to the following code:

Read More

HERDING - Herding - SOLUTION

HERDING - Herding is an easy DSU problem. If you are not familiar with term DSU, I suggest you to first of all understand DSU, then try solving this problem.

In this problem, we are give a n*m array and  each block of array contains 'N','S','W' or 'E'. 'N' is for north, 'S' for south, 'W' for west and 'E' for east, and they represents the direction of movement of cat if it is on that block.

So, if a cat is present on a block, there is a specific path, which it will follow. If we keep trap at the end of that path, and cat is present anywhere in the path, it will end up in the trap!

So, all we need to do is to find the number of paths, which do not intersect at any point. And we will set traps at the end of every path.

For example:

Input:
3 4
SWWW
SEWN
EEEN

Output:
2

                                                 

There are two paths, one is shown by yellow color and second one by blue.
If we set a trap at any of the yellow block, then all cats which are at yellow path, will end up in that trap, and same for the blue path!

The thing you should notice is, there is only one way possible from each block. So, if we traverse whole n*m map, and connect each block to the next block (according to the given direction), we can find all paths!

So, our answer will be the number of disjoint paths!

Easy, isn't it? Now try implementing this code bye yourself or refer to the following code:

 

Read More

GCPC11J - Time to live - SOLUTION

GCPC11J - Time to live is an easy BFS problem, which can be solved by applying BFS twice. If you are not familiar with the term Breadth First Search (BFS), then i suggest you to first of all understand BFS, then try solving this problem.

In this problem, our job is to minimize the number of TTL we need to send from the router to the farthest computer. So all we need to do is find a node, at which we can keep our router so that, it needs to send minimum number of TTLs to the farthest computer.

This can be done by finding the longest path in given graph, and we can keep our router at the center of the longest path (longest distance b/w two computers). By applying BFS twice, we can find the longest path easily.

If you want to understand, how we gonna find longest path, please see this blog, otherwise continue reading!

In the first BFS we will apply BFS from a random node, I chose 1 for this purpose. And our bfs(1) will return the farthest node from '1'. Then we will apply second BFS from the farthest node selected in bfs(1). This time the farthest distance from selected node will be the longest path in the graph!

That's all you need to do, easy, isn't it? 

Now, 

if(n%2==0) print (longest path length)/2 

else print (longest path length +1)/2

I hope you can implement the code for this problem yourself otherwise refer to the following code:

Read More

FOXLINGS - Foxlings - SOLUTION

I am assuming that you have already understood the problem statement otherwise go back and read the problem statement once again: PROBLEM STATEMENT

If you are not familiar with DSU and path compression, I suggest you to go and read this post first.

There are total N Foxlings , and if one foxling gets a cracker he divides it and give it to his friend too, in this way, if only one member of each friend circle receives a cracker, indirectly whole group will have crackers !

Input contains N the number of foxlings and M, the number of friendships.
Next M lines contains  A B , which means A is friend of B, and B is friend of A.

Initially, there is no friendship, so everyone is their own friend, and there are total N groups. Let us store number of groups in a variable co, i.e., co = N .
So, what we can do is , using union operation at each of the M queries, i.e., finding the root of A and B , and if root(A) ! = root (B) we will do union of them. And every time we do union, we will reduce value of co by one. After all queries the remaining value of co will be our answer!

I hope you can implement the code for this problem yourself otherwise refer to the following code:

Read More

ONEZERO - Ones and zeros -SOLUTION

ONEZERO - Ones and zeros is an easy BFS + Modular Arithmetic problem.

I am assuming that you have already understood the problem statement, otherwise go back and read the problem statement again.

If you are not familiar to the term BFS, i suggest you to first read basics of BFS.

In this problem, we have a made a queue which contains pairs, and each pair consists of a string (as number may exceed the integer limit) and an integer.

Now let us talk about the modular arithmetic concept we are going to use in this problem, let us take an example, we have to find 356 % 8, which is equal to 4. Now let us try to find this in the following way:

3 % 8 = 3
now multiply 3 to 10 and add next digit = 3*10+5 = 35

35 % 8= 3
now multiply 3 to 10 and adding next digit = 3 * 10 + 6= 36

36 % 8 =4

By using this method you can be sure that your answer will not be wrong due to integer overflow.

In this problem we will start from 1 and will check if 1 is divisible by n or not, if not then we add 11 and 10 to the queue, and now we know that the remainder of 11 will be ((1 % n) * 10 + 1) % n and for 10 it will be ((1 % n) * 10 + 0) % n at next step, same thing will happen with 11 and 10, and 110, 111, 101, 100 will be added to the queue and so on....

We will repeat this till we didn't find or answer, we can reduce the execution time of code by using visit array.

I hope you can implement the code for this problem yourself otherwise refer to the following code:

Read More

MCOINS - Coins Game - Solution

MCOINS - Coins Game is an easy bottom-up DP problem.

I am assuming that you have already understood the problem statement, otherwise go back and read the problem statement again.

In this problem, we have made an array b[] which contains height of different towers, and we have to print a string containing A and B, who's ith element represent the player who will win for the ith tower. Now we have to print A if first player wins and B if second player wins.

Now, we have an array a[], which contains result of all towers.

Each player can choose 1,K or L to remove from tower, so if there is a tower with height 1, first player will win. So, we keep a[1] = 1

Now, for every i, A can win only if
a[i-1] = 0 or a[i-K] = 0 or a[i-L] = 0

otherwise B will win.

I hope you can implement the code for this problem yourself otherwise refer to the following code:

Read More

FARIDA - Princess Farida - SOLUTION

This is an easy DP problem, which can be solved using bottom-up DP.

Let us take an array a[] which keeps the number of coins ith monster keeps.

Lets make a new array dp[]

dp[0]=0;

and further for every index i

dp[i] = max(a[i] + dp[i-2], dp[i-1])

I hope you can implement the code yourself or refer to the following code:

Read More

LOSTNSURVIVED - Lost and survived - SOLUTION

I am assuming that you have already understood the problem statement otherwise go back and read the problem statement once again: PROBLEM STATEMENT

If you are not familiar with DSU and path compression, I suggest you to go and this post first.

There are 'N' survivors and  'Q' queries in each test case.
In each query two survivors become friends uniting their respective groups into a larger group. And after each query you have to tell the difference between the group size of largest group and smallest group, for this purpose we will use STL, we can use SET, MULTISET, or MAP, which will keep the group size of each group.
As set, multiset and map keeps the data sorted, for difference between smallest and biggest group you can subtract the first element from last element.

We are keeping a 'parent' array which keeps parent of each survivor, i.e., parent[A] store the parent of Ath survivor. Intially every body is their own parent :P

For all the group members we will find root using root function. Suppose A,B,C,D and E are in a group and parent[A]=A, parent[B]=A, parent[C]=B, parent[D]=C and parent[E]=D.
Then root(A) = root(B) =  root(C) = root(D) = root(E).

After every query we will do union operation if and only if their roots are not equal. After every union we will add group1_size + group2_size into the multiset and will remove group2_size from multiset.

I hope you can implement the code for this problem yourself otherwise refer to the following code:

Read More

CORNET - Corporative Network - SOLUTION

I' am assuming that you've already understood the problem otherwise go back and read the problem once again : PROBLEM STATEMENT.

If you are not familiar with DSU, I suggest you to go and read this article first: DSU

It is a simple DSU problem in which whenever a query starts with 'I' you have to do union of A and B, where A is always a server, but B may be or may not be a server. And at every union you have to set distance from A to B = |A-B|%1000.

Now let us talk about the queries starting with 'E'. At every query starting with 'E' you have to tell the distance of that enterprise from its server. It is also possible that the given building is server itself, then the difference will be equal to '0'. We have kept an array 'd' which is storing distance of ith enterprise from its server.
Assume that the query is 'E A' and the enterprise serving to A is D in the following manner:
A -> B -> C -> D
While finding the distance from A to D we will update all distances of enterprises from A to D, i.e., we will update d[A], d[B] and d[C].

While telling the distance from server to that  enterprise you don't need to do any %1000 thing!

Now, I hope you can implement the code yourself or refer to the following code:

Read More