Follow Learning Algorithms with Rachit Jain on Feedspot
Continue with Google
Continue with Facebook
or
Not now
Learning Algorithms with Rachit Jain
.+Add.Feed Info1000FOLLOWERS
This is my blog dedicated to competitive programming. I write about interesting data structures, algorithms and beautiful problems that have awesome analysis and thus offer great learning.
Tags: google, google job,placement, interviews, data-structures, algorithms
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.
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.
Software Engineer talks about cracking Google Interviews | Story & Tips for Job at Google - YouTube
Video: Software Engineer talks about cracking Google | Tips & Story of cracking Google
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.
Data Structures and Algorithms You Must Know in Coding Interviews - YouTube
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 -
Why Google rejects great coders in Software Job Interviews? MUST WATCH! - YouTube
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.
"Famous Coding Interview Problems and their Solutions" - click here
Graph Theory for beginners - How Splitwise work behind the Scenes? - YouTube
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 4. Data Structures - (Linked Lists, stacks, queues, BIT useful, Segment Tree - asked in Google) 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 11. Bitmask DP - sometimes asked in interviews, cover it later.
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 Just start doing already! Feel free to write your queries, I am always there to help :)
Important Playlists: ================ Famous Interview Questions You Must Know ►click here Tips & Tricks for Success in Career ►click here How to Improve at Data Structures ► click here OOPS Interview Questions ► click here Gaurav Challenges Rachit ► click here How to use Codeforces for Improving ► click here Math Problems with Interesting Analysis ► click here
Courses Taught by Me ================== Dynamic Programming: Zero to Hero ► click here Dynamic Programming on Trees ► click here Graph Theory for Beginners ► click here SquareRoot Decomposition for Beginners ► click here Segment Trees ► click here
So the Hackerrank Codesprint 11 ended, and here is the question that I will talk about today: you are given a directed graph, and you will be given 2 types of queries: introduce a new node with an edge from/to the existing nodes, or answer whether there is a path from node $x_i$ to node $y_i$.
If it were a undirected graph, DSU would have nailed it. Anyway, this is a standard technique used for connectivity in directed graphs. As for now, forget the type of query that modifies the graph structure. 1. Find all the SCCs in the directed graph. 2. Form a new graph, a DAG by compressing the SCCs and adding edges between the SCCs. 3. Now for each SCC $A$, maintain the list$(reach[A])$ of all the SCCs it can reach. 4. For given nodes $x$ and $y$, there is a path from $x$ to $y$ iff the SCC component $Y$ is present in $reach[X]$, where $X,Y$ refer to the SCC that contain $x,y$ respectively.
Note that this takes $O(n^2)$ because of step $3$. We can do it faster by using BITSETS. Click the above link which excellently outshows the applications of bitsets in C++. So we replace the list $reach[A]$ by the bitset $bit[A]$.
So we now do this in $O(\frac{N^2}{32})$. This is pretty fast to pass the TL.
Now notice that queries modifying the structure of graph won't affect our algorithm much. We first build the complete graph and then finally answer the queries. The only thing that one can worry about is that there might be some case for which the answer to present query is "No" but since we have built the complete graph, we might get a "Yes". So if answer for $x,y$ is "No", then this means that till now there isn't a path from $x$ to $y$. Notice that as we continue to modify the graph, we always bring a NEW node inside the structure and it's never possible in this way to add a path from $x$ to $y$. Wow!
As usual, here is the code implementing the above idea. I've seen similar questions in past hackerrank contest too(can't recall it). So I learnt that using bitsets is a standard technique for connectivity queries on directed graphs.
This blog post is just to inspire people about life and saying goodbye to worries.
We all have aims and goals in our lives. There is a necessity for them. For example, I cannot live a life with no goals and watch tv series, sleep 10 hours a day. Though this looks fine for a day, 3 days, a week, enough! But this makes me carry unnecessary burden on my mind. Also due to lack of social circle, many people fall under depression and live life in despair.
In today's life, we worry way too much. But in reality that worry is not the worth. Constantly worrying causes depression, irritation, frustration, and bad mental health. I have adapted to the following 3 steps to stay away from these:
Step 1: Think about the worst possible outcome of the present situation. Step 2: Accept it. Step 3: See the possible actions you can do to make the outcomes less unfavorable.
On one side there is Napolean Bonaparte who had fame, power and money but couldn't recollect even six happy days of his life. On the other hand we have Hellen Keller, who was dumb and deaf but described life as the most beautiful thing.
We must keep ourselves engaged in some activities. Keep yourself busy. Just make sure that they are productive, require focus and enhance your creativity. For people who aren't that fond of reading(Look who's talking), they must give it a shot! Its worth it. Their have been 1000s of generations that have passed and have left their experiences. Its very good to read about random stuff daily.
This was what I learnt from my mother this December. She was noticing my behavior and finally made me realized where I was going wrong. I will definitely try to live by this and make my life much much stress-free. Following is the video she whatsapped me.
HOW TO STOP WORRYING AND START LIVING (HINDI)- HOW TO REDUCE STRESS,DEPRESSION,ANXIETY,WORRIES - YouTube
Pro Tip: We must remember the people who are close to us and make us happy. I feel thankful to my parents and close ones for being my moral support and feel blessed to have a perfectly complete life. :) No matter in how much trouble I am, there are people who will stand besides me. Trust is the most beautiful thing after love. Give it to people and never break it.
I personally found the implementation given in the above GeeksForGeeks link very long. The aim of this post is simply to provide a short and efficient implementation of min and max heap in C++. This helps me to revise just before the placement interviews too. :P
Advantage: 1. Short and efficient code. 2. Works as both max-heap as well as min-heap.
Why Google rejects great coders in Software Job Interviews? MUST WATCH! - YouTube
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!
Data Structures and Algorithms You Must Know in Coding Interviews - YouTube
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!
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 2 months back, and now working in Microsoft for over a month.
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.
How to crack the interviews and get a decent job? So, the organizations will be coming in many colleges soon, and conduct their shortlisting tests. Now, I will be talking very short and to the point. Each point is important.
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 4. Data Structures - (Linked Lists, stacks, queues, BIT useful, Segment Tree - asked in Google) 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 11. Bitmask DP - sometimes asked in interviews, cover it later.
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.
People who don't do CP should immediately do the following: 1. Need to improve implementation, debugging skills. 2. Learn the basic set of data structures and algorithms as mentioned above. 3. Begin by doing all 37 problems on GeeksForGeeks under array category. 4. Move on to DP on GeeksForGeeks. 5. For sets, maps I think problems on CodeForces like I mentioned above will be better. 6. Cover other topics like greedy, dfs/bfs from GeeksForGeeks. 7. Linked list, binary trees and their traversals. (Important!)
This should take around 2 weeks. I don't think people who are consistently doing CP would face the need of doing linked list, stacks, etc from geeksforgeeks. But its good if you give it a fast skimming read.
What next? Now start off at interviewbit and solve problems there so that you familiarize yourself with verdicts like WA, AC, etc and also how to respond in case of TLE or WA. This will improve your implementation and debugging skills. This will clearly help you understand the various concepts like DP, trees, etc.
You must also participate in the ongoing challenges on sites like Codechef, Codeforces, Hackerrank, etc.
Once you are stable blue on CF around 1700, you can easily clear the recruitment tests. Then all you have to do is brush up your explanation skills so that you can clear the interview rounds too.
NOTE: Speed is important. Many times people fail by 10-15 mins to implement the algorithm correctly. This will really turn you off. So keep practicing everyday!
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 Just start doing already! Feel free to write your queries, I am always there to help :)