## Saturday, November 24, 2018

### Cracking the Google Interview | Software Engineer reveals tips & secrets

rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

Hi! Today I will write about some tips, tricks and hacks I have found from my experience in attempting recruitment tests, interviews.

I will begin by giving a brief introduction about myself.
I have done B. Tech. in Electrical Engineering from IIT Roorkee. I have graduated in 2017, and now working in Microsoft for over 18+ months.

I started off competitive programming in 2-2(2nd Year 2nd Semester). So I had around 1.5 years of experience in competitive programming while I was sitting for placement tests. Having a strong background in competitive programming really saves your ass while others keep reading geeksforgeeks to prepare themselves.

You can subscribe to my programming YouTube channel, "Algorithms with Rachit" here.

How to crack the Google interviews and get a decent job?

Here is the YouTube video of 12 mins where I share the complete journey of what exactly happens in a Google Interview, what kind of questions they ask, from where to prepare, and possible mistakes you might be making despite having good skills and getting rejected.

After watching this, you already can see the links in video description. Anyway, if you are lazy, here is what you have to do next.
See the mistakes you will be making despite being good at tech skills and hence getting rejected.

Video: Why Google rejects great coders in Software Interviews?

Now, comes the part about what you have to study. For that have a look at -

Video: Why Google rejects great coders in Software Interviews?

To learn more on how to solve Coding Interview Problems, I launched a playlist where I pickup famous and interesting Interview questions and explain the approach and then the code in C++ to solve them.

Video from that playlist where I teach Graph Theory

Here is a short summary of important data structures and algorithms.
Basic Skill Set (BSS):
1. Quick implementation & debugging (practise questions on codeforces, hackerrank, participate in contests)
2. String Matching (important, KMP, Z-Algorithm, etc)
3. Binary Search, Sorting, STL (sets, maps, unordered set/map, vector, sort) - very very very useful
5. Dynamic Programming - very very important (medium level problems, all companies ask)
6. Binary Trees & BST - super important! (All companies ask this)
7. DFS/BFS questions on Graphs (Dijsktra and flows are rarely asked)
8. DP on Trees (yes, an important topic)
9. Greedy, Backtracking - (Important, can be tricky)
10. Math Concepts like Prime Seive - Not that much important

I think this is enough for cracking through most of the recruitment tests. Though there are always many other topics that can be covered, but I would suggest don't get overwhelmed and focus on these first. Once you are ready with these basics, you should move on to study other Data Structures and Algorithms. Knowing more and in detail will always make you more interesting and awesome.

Many recruitment problems are based on usages of sets, maps.
Do many practise problems based on them. Eg: see this, and the solution.

Tips for recruitment tests:
1. Be fast. Don't just keep on waiting for finding the solution.
2. If stuck on problem, proceed to next. First solve all of those that are easy.
3. At the end, ALWAYS submit the worst brute force solution with no matter what complexity. YES! The test cases are many times weak, and you get pretty high score.
4. You must be familiar with Python inbuilt functions involving combinatorics, permutations and string functionalities too. It can prove to be very beneficial ;)
5. This tip is more of a personal experience. In one of the test, I was getting only a score of 25. I soon realized that the  for loop conditions weren't true and I was simply printing 0. When I corrected it, I got a score of 75. Yes! so I had to basically see that if I am getting a WA in some test case, I need to print 0 there. Finally I used binary search on the values of variables(size of array, first element of array) to identify those test cases, and simply print 0. Basically what I did was used an infinite while loop with some condition like $100<n$ and $n<500$ so that I get the verdict TLE, and I am able to figure out those test cases where I was getting WA.

Tips for interviews:
1. Be humble. Don't give the slightest vibes of overconfidence or arrogance.
2. Never give up. If the problem asked seems difficult at first sight, don't lose out confidence. See what is given, what you have to find, and try doing it for small test cases. Then maybe you will find a pattern.
3. Speak as you think. Don't just keep scribbling on paper. Let the interviewer know about how you are approaching the problem.
4. If problem seems difficult, give the brute force solution and its complexity. Then try optimizing it, maybe using dynamic programming or some greedy solution.

Don't think you don't have time :D
Feel free to write your queries, I am always there to help :)

Important Playlists:
================

Courses Taught by Me
==================
Dynamic Programming: Zero to Hero ► click here

My Code Library
==============
Github ► https://github.com/rachitiitr/DataStructures-Algorithms

==========
Instagram ►https://www.instagram.com/rachitjain2095
Programming Blog ► https://rachitiitr.blogspot.com

Programming Profiles:
===================
CodeForces ► http://www.codeforces.com/profile/rachitjain
CodeChef ► http://www.codechef.com/users/rachitiitr

## Saturday, October 6, 2018

### This is why you are FAILING at Interviews

Hi,
Here is another video from my side: "This is why you are failing at Coding Interviews"

If you have not subscribed to my YouTube channel, now is the right time as its all about making you ready to get your dream job. I share tips, lectures(like dp, dp on trees, graphs, squareroot decomposition), and the right mindset needed to crack coding interviews.
Rachit, an IIT Roorkee Alumnus and Software Engineer at Microsoft shares the major issues that people overlook while they are failing at Coding Interviews, despite being good at technical skills.
Subscribe to see more of me. Let me know if this helped. Go get a job at your dream company!
Cheers!

## Saturday, September 29, 2018

### If you are preparing for Coding Interviews, WATCH THIS!

Hi,
Here is another video from my side: "If you are preparing for Coding Interviews, WATCH THIS!"

If you have not subscribed to my YouTube channel, now is the right time as its all about making you ready to get your dream job. I share tips, lectures(like dp, dp on trees, graphs, squareroot decomposition), and the right mindset needed to crack coding interviews.
In this video, I share what is the story behind the present hiring process for companies like Microsoft, Amazon, Goldman Sachs and then I share what are the various topics you need to study to prepare for them.
Subscribe to see more of me. Let me know if this helped. Go get a job at your dream company!
Cheers!

## Saturday, April 7, 2018

### How to excel at Competitive Programming | ft. FFAO from Codeforces

Hi guys! ✋
rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

I got the opportunity to talk to one of my favorite coders. I remember I used to read comments by ffao and just see how great his rating curve is and how soon he came red on Codeforces.

So I made a video on YouTube where ffao answered a lot many questions about competitive programming and how one can excel in this field.

My screencast software got some issues and we got a poor video quality and I sincerely apologize to ffao and the audience.

I can't ask ffao the time to again record with me, and I was almost sure of not uploading the video. But the audio is great, and I decided to have it on my YouTube channel.

You can watch the video here.

You can also refer this blog post to have a summary of what we discussed in the video.
• ffao: I have a five-year bachelor’s degree in Computer Engineering from Instituto Tecnológico de Aeronáutica (ITA), a Brazilian university
• When did you start programming?
• ffao: I wrote my first program when I was 13, as with a lot of people that happened because I really liked video games and wanted to know more about making them (spoiler: turns out it’s actually quite time-consuming). At that point I could only make very simple programs, like “type in a number and the program tells you if it’s even or not”, but I picked up more as I went along.
• Why does math background help?
• ffao: I can’t even pinpoint where the math ends and the programming starts! Functions, recursive relations, geometry, transforming algebraic expressions – these are all things you do routinely in math and these are all things you do routinely in competitive programming. Just as math helped me with programming, studying for programming also helped me do better at math, so these things are quite tightly coupled.
• Should students prefer math over computer science for graduation?
• ffao: There isn’t an objectively correct answer to this question – graduation choice should be influenced by the student’s tastes and what they intend to do with their life, so my best advice would be to research what graduates at each of these fields tend to do and go towards the one that has the choices that appeal to you the most. Getting into a programming job in general is easier with a computer science degree, but I have heard of jobs that hire mathematicians due to their usual analytical skills.
• ffao: Sure, I believe everyone’s experiences in their whole life matter - I’ve always liked math, so I didn’t have trouble with those parts. I also did a bit of programming, so I did not have to struggle with learning what ifs and whiles do since I already struggled with it before.
• How can intermediate coders excel and reach the next target?
• ffao: Just keep at it – do every competition you can, and you’ll struggle with a problem or two; those should be the problems a bit above your skill level so make sure you understand why you couldn’t solve the problem you couldn’t solve. Could you have approached the problem in a different way to get to the solution faster? Is there a technique you can generalize to solve a class of similar problems if they show up?

Other Questions that students requested:
• How to understand hard and tough concepts easily for example FFT , centroid decomposition etc.
• ffao: This sounds like the wrong question to ask. To be honest, FFT/centroid are not that useful and I didn’t learn about them for a very long time (I think I only knew about those things for a few months?) The best thing is to just go doing full competitions, without trying to learn specific techniques, until one of them comes up. But if you really want to know, my generic way to learn things when they do come up is: look up an explanation from someone who knows the subject well (there are a lot of bad tutorials, so you might have to search a lot to find a good one), try to do the most basic possible thing with the technique, then solve a few problems to see potential alternative ways to use it, then go back to solving random problems until it comes up naturally again.
• How to select problems for practice? Ladders in A2OJ sort problems by tag and number of submissions which are not that great.
• ffao: If you are training for a certain competition A, an obvious choice is to do previous editions of that competition for training. There are a lot of ICPC Regionals available online, also other competitions with quality problems like topcoder and codeforces. There isn’t a perfect answer to this and you’ll eventually find problems that are not helpful, the important thing is just to keep at it and eventually you’ll come across something interesting. I went to the Google Code Jam finals in 2014 and another finalist asked me how to find good problems, so I guess none of us really know. 😊
• Tackling DP and understanding the states to be defined and how this though process goes inside his head so rapidly.!
• What ffao said is exactly told in one of my videos to Introduction to Dynamic Programming that you can watch here.

Dynamic Programming: How to think of states?

If you liked the video, please hit the like button 👍, subscribe and share the videos among your college :D

Have a good day! 😆

## Wednesday, September 6, 2017

### [Tutorial] SquareRoot Decomposition + Dynamic Programming in Competitive Programming

Hi guys! ✋
rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

You are going to learn how Square Root Decomposition and DP can be mixed to generate harder problems.

This is an awesome math problem on Matrices. It is based on DP + Data Structures(Fenwick Tree/SquareRoot Decomposition). Its a counting problem from CSAcademy Junior Challenge 2017.

You are given a matrix $M$ with $N,M( \le 2000)$ rows and columns, and you have to count the no of special square submatrices. A square matrix is special if it has all $1s$ on its borders and principal diagonal(top-left to bottom-right). The rest of the matrix can be filled with either $0s$ and $1s$.
In beginning, the problem seems to be solvable using only DP, but the solution is simply mind-blowing, jaw-dropping and beautiful.

The trick here is to iterate on diagonals which are $O(N+M)$ in number. Then for each diagonal, count the number of special square submatrices that lie on current diaognal i.e their principal diagonal lies on the current diagonal that we are iterating.

Lets pick any two points on the diagonal that we are currently at.
Using DP, we do some preprocessing. Then the question is transformed to given two arrays $L,R$, find the number of pairs $(i, j)$ such that following 3 conditions are met:
1. $i\le j$
2. $L_j \le i$
3. $R_i \ge j$

We iterate on $j$, and use square root decomposition to solve this problem :)

The video tutorial is divided into 2 parts:

1. Part1: Approaching the problem and building our solution

2. Part2: The Square Root Decomposition part

Refer the Video Description to find the links to problem link and other relevant information.
If you liked my efforts, please hit the like button 👍, subscribe and share the videos among your college :D

Have a good day! 😆

## Wednesday, August 30, 2017

### An Interesting Math + Data Structure Problem from Codeforces (Round #430)

Hi guys! ✋
rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

This is a data structure(TRIE) + math based problem from Codeforces Round #430.
You are given an array $A$ of size $N$, and you have to perform $M$ operations on it.
In each operation, you are given an integer $x$, and you perform XOR operation of every element of the array with $x$. Note that the array is updated after every operation and subsequent operations are performed on modified array. At end of every operation, you need to print the mex value of the updated array.

NOTE: mex of a set $A$ is the least whole number ( $\ge 0$ ) which is not present in $A$.
Check out the following video where I've described the solution:
CodeForces Round 430 - Problem D Tutorial (Number Theory, Trie)

Refer the Video Description to find the links to source code and problem link.
If you liked my efforts, please hit the like button 👍, subscribe and share the videos among your college :D

Have a good day! 😆

## Tuesday, August 29, 2017

### An Interesting Number Theory Problem from CSAcademy(Round #43)

Hi guys! ✋
rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

This is a greedy, math problem from CSAcademy Round #43.
You are given two integers $N,K$ and you are required to print an array of $N$ distinct integers $<10^6$ such that there are exactly $K$ pairs $(a[i], a[j])$ with their gcd as $1$.
Check out the following video where I've described the solution:
CSAcademy Round 43 - Coprime Pairs Tutorial (Number Theory)

Refer the Video Description to find the links to source code and problem link.
The family 💓 has grown to 600+ subscribers and I thank you guys for the love and support :)

If you liked my efforts, please hit the like button 👍, subscribe and share the videos among your college :D

Have a good day! 😆

### Cracking the Google Interview | Software Engineer reveals tips & secrets

rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain micr...