| A guide to be better software Engineer wherever you are | competetive-programming-using-java

Repo to hold all competitive programming questions and manuals

To get up to speed with respect to how and what to prepare, please find below certain materials/links which will be extremely useful to you. Do have a thorough look at them.

| Overall process:

| Recruiter Prescreen → Onsite Interview (5 sessions) → Hiring Committee Review → Offer Review → Offer Delivery (Woohoo!)

| Step 1. Refresh yourself with CS fundamentals:

We do expect you to know a lot about algorithms and data structures and especially be able to implement them into your solutions - there is a great bigocheatsheet that may also help you!

Steve Yegge’s Blog

Google Style Guides (C++, Python, Java; Android, Javascript)

Geek for Geeks - Study algorithms and data structure

| System Design resources:

System design interview tip!

Hired in Tech

| Step 2. Coding Practice + CS review

When you practice, do not use an IDE. You need to be able to write legible, compilable code without help with regards to layout, or spelling of standard library class/method names. I suggest solving similar style algorithmic/ DS problems on a google document or on paper to simulate a real interview. Several sites that provide similar problems to those typically asked in the interview are:

• Leetcode

• Code Jam Kickstart

great practice to get a glimpse of Google coding and algorithm questions. Code Jam hosts online Kickstart rounds that give participants the opportunity to test and grow their coding abilities! Participate in one—or join them all! You can also learn how to solve those problems by reading our analysis

• Codeforces

• HackerRank

• Topcoder

• ACM-ICPC

• Code Jam

Additional Notes/ Optional Studies:

| Study Materials:

• Courses: can choose one of below

• • Coursera - Algorithms, Part 1
• • Coursera - Algorithms, Part 2
• • Udacity - Intro to Algorithms
• • MIT Open courseware - Introduction to Algorithms (not efficient)

• Youtube Channels:

• • Tushar Roy - Coding made Simple
• • Interview Prep
• • Google Recruiters Share Technical Interview Tips (30 min)
• • Google Technical Interview Workshop - Singapore (2 hours)

| Books:

• Beautiful code

• Elements of Programing Interview

• Coding Interview University

• Cracking the Coding Interview

| Understand Google Interview Process

• Ask a Google Engineer — What is the Interview Process at Google? (2 min)

• How to prepare for a Google Engineering Interview (7 min)

• Candidate Coaching Session for Technical Interviewing (45 min)

• Example of a Coding Interview (24 min)

| Interview behaviors to note

• Talk through your thought process about the questions you are asked. In all of Google's interviews, our engineers are evaluating not only your technical abilities but also how you approach problems and how you try to solve them.

• Ask clarifying questions if you do not understand the problem or need more information. Many of the questions asked in Google interviews are deliberately underspecified because our engineers are looking to see how you engage the problem. In particular, they are looking to see which areas leap to your mind as the most important piece of the technological puzzle you've presented.

• Think about ways to improve the solution you'll present. In many cases, the first answer that springs to mind isn't the most elegant solution and may need some refining. It's definitely worthwhile to talk about your initial thoughts to a question, but jumping immediately into presenting a brute force solution will be received less well than taking time to compose a more efficient solution.

• Access to a computer at the time of interview is required as you will be requested to write and share code. Interviewers use Google Docs to facilitate coding in real time.

| ## Please focus on the points below to appear for TPS.

| Technical Tips:

• Algorithm Complexity: You need to know Big-O, time and space complexity. Identify edge cases independently, and distinguish between average case/worst case runtime. The goal is to reach the most optimized solution at the end of the interview, and to have a complete working solution.

• Coding: We look for clean, bug-free and concise solutions, and well-structured code with good use of variable and method names. You should know the coding language, constructs and library functions well and make good use of it’s features. Note that coding speed is very important, and the code should be production ready. Optimize, check for boundary conditions and debug as much as possible.

• Sorting: Know how to sort. Don't do bubble-sort. You should know the details of at least one n*log(n) sorting algorithm, preferably two (say,quicksort and merge sort). Merge sort can be highly useful in situations where quicksort is impractical, so take a look at it.

• Hash tables: You should know this data structure and how they work. Be able to implement one using only arrays in your favorite language, in the space of one interview.

• Trees: Know about trees; basic tree construction, traversal and manipulation algorithms. Familiarize yourself with binary trees, n-ary trees, and trie-trees. Be familiar with at least one type of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree,and know how it's implemented. Understand tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder.

• Graphs: Graphs are really important at Google. There are 3 basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list); familiarize yourself with each representation and its pros & cons. You should know the basic graph traversal algorithms: breadth-first search and depth-first search. Know their computational complexity, their trade offs, and how to implement them in real code. If you get a chance, try to study up on fancier algorithms such as Dijkstra and A*.

• Other data structures: You should study up on as many other data structures and algorithms as possible. You should especially know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise. Find out what NP-complete means.

• Mathematics: Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other companies because we are surrounded by counting problems, probability problems, and other Discrete Math 101 situations. Spend some time before the interview refreshing your memory on (or teaching yourself) the essentials of combinatorics and probability. You should be familiar with n-choose-k problems and their ilk the more the better. Google interviews focus very heavily on algorithms and data structures.

• Operating Systems: Know about processes, threads and concurrency issues. Know about locks and mutexes and semaphores and monitors and how they work.Know about deadlock and livelock and how to avoid them. Know what resources a process needs, and a thread needs, and how context switching works, and how it's initiated by the operating system and underlying hardware. Know a little about scheduling. The world is rapidly moving towards multi-core, so know the fundamentals of "modern" concurrency constructs.

| Important Areas of Assessment:-

• 1.Coding - Good code quality (No IDE. Fully functional code. Take care of syntax, good language constructs, clean and concise code) & coding fast(you can code in Codechef timed challenges to practise coding under time pressure)

• 2.Good communication - Talk out loud, explain your thought process to the interviewer

• 3.Attitude - Being independent, lead/drive the discussion forward while being receptive to hints from interviewers and integrating it in your solution

• 4.Speed of solving the question (Ideally 20 mins per question)

| Strategy for Success (Framework):-

• Step 1: Clarify the problem

• Step 2: Define your approach

• Step 3: Propose a solution before coding > feel free to say that your first solution will be refined later > Run through at least one or two examples to check for correctness > Use reasonable variable names or clean up the code after the first pass > Ask if the interviewer has any questions before refinement.

• Step 4: Propose an alternative solution.

• Step 5: Implementation.

| Interview Preparation Plan (created by Google Software Engineers):

• 1. Revise all concepts on data structures & algorithms- you can also use this gitHub link https://github.com/jwasham/google-interview-university/blob/master/README.md#google-interview-university on CS fundamentals that can serve as a checklist while preparing. This Big O cheat sheet <http://bigocheatsheet.com/ http://bigocheatsheet.com/>could help you as well!*

• 2. *Structured Revision plan *on the topics that to cover (Eg.hashtable, hashmaps, trees, arrays, strings, graphs, dynamic programming and more)

• 3.Practise per category: Practice up to a level that you reach competency - Solve the question in 20/40 minutes (for medium and hard problems respectively) and come up with the optimal solutions

• *Practice Problem Identification by picking random problems and practicing identifying “Which category does this problem belong to? Backtracking/Dynamic programming? Solution/Algorithmic design?”.

• 4. Practice coding without an IDE, be familiar with the differences in how you should write code in Google Docs. Do practise coding in Google Docs within a set time frame and getting comfortable talking while coding.

• In summary: Practise a wide variety of questions, and simulate actual Interview conditions! You can also run mock interviews here at pramp.com

| Frequently asked topics (in no particular order)

Binary search, BFS/DFS/Flood fill, Tree traversals, Hash tablesLinked list, stacks, queues, two pointers/sliding window, Binary heaps, Dynamic programming, Union find, Ad hoc/string manipulations

Other good to know topics: Trie, segment trees/fenwick trees, bitmask.

Google Interview Style Guides

https://google.github.io/styleguide/cppguide.html,C++

https://google.github.io/styleguide/pyguide.html, Python

https://google.github.io/styleguide/javaguide.html; Java

https://google.github.io/styleguide/javascriptguide.xml)Javascript

You'll be expected to know and apply: lists, maps, stacks, priority queues, binary trees, graphs, bags, and sets.

For algorithms you'll want to know greedy algorithms, divide and conquer, dynamic programming, recursion, and brute force search.

You'll definitely want to be conversant with big­ O notation,time­-space complexity, and real world performance of all of this.

What we are assessing for Data Structures & Algorithms

Can you implement the most optimized data structure and algorithm for the question? Can you explain the tradeoffs between the data structure/solution? Can you explain why you choose a data structure for implementation? Can you explain and analyze the time and space complexity correctly? Can you translate the algorithm to code well?

| MORE Resources :

How to setup leetcode in vs code editor for free questions (GREAT HACK!! for free leetcoding!!).

Competetive Programming Essentials :-

If you are coding in java make sure that you are using FastReader and PrintWriter for fast I/O. As fast input/output can be a diffrentiator in getting as AC or TLE. Please make sure to amend this and dont get disheartned by the whole process of it.

It will all finally make sense once you have started practising.

General guidelines you want to contribute to this repo

create your named folder at the root of the project.

Do as much code as you can

Raise a pull request against master.