πŸ–₯️
Sunil Notebook
Interview Preparation
  • πŸ“’Notebook
    • What is this about ?
  • System Design
    • πŸ’‘Key Concepts
      • 🌐Scalability
      • 🌐Latency Vs Throughput
      • 🌐Databases
      • 🌐CAP Theorem
      • 🌐ACID Transactions
      • 🌐Rate limiting
      • 🌐API Design
      • 🌐Strong Vs eventual consistency
      • 🌐Distributed tracing
      • 🌐Synchronous Vs asynchronous Communication
      • 🌐Batch Processing Vs Stream Processing
      • 🌐Fault Tolerance
    • πŸ’ŽBuilding Blocks
      • πŸ”ΉMessage
      • πŸ”ΉCache
      • πŸ”ΉLoad Balancer Vs API Gateway
    • πŸ–₯️Introduction to system design
    • ⏱️Step By Step Guide
    • ♨️Emerging Technologies in System Design
    • β˜‘οΈSystem design component checklist
      • πŸ”·Azure
      • πŸ”ΆAWS
      • ♦️Google Cloud
    • 🧊LinkedIn feed Design
    • 🏏Scalable Emoji Broadcasting System - Hotstar
    • πŸ’²UPI Payment System Design
    • πŸ“ˆStock Broker System Design - Groww
    • πŸ§‘β€πŸ€β€πŸ§‘Designing Instagram's Collaborative Content Creation - Close Friends Only
    • 🌳Vending Machines - Over the air Systems
    • Reference Links
  • DSA
    • Topics
      • Introduction
      • Algorithm analysis
        • Asymptotic Notation
        • Memory
      • Sorting
        • Selection Sort
        • Insertion Sort
        • Merge Sort
        • Quick Sort
        • Quick'3 Sort
        • Shell Sort
        • Shuffle sort
        • Heap Sort
        • Arrays.sort()
        • Key Points
        • Problems
          • Reorder Log files
      • Stacks and Queues
        • Stack Implementations
        • Queue Implementations
        • Priority Queues
        • Problems
          • Dijkstra's two-stack algorithm
      • Binary Search Tree
        • Left Leaning Red Black Tree
          • Java Implementations
        • 2-3 Tree
          • Search Operation - 2-3 Tree
          • Insert Operation - 2-3 Tree
        • Geometric Applications of BST
      • B-Tree
      • Graphs
        • Undirected Graphs
        • Directed Graphs
        • Topological Sort
      • Union Find
        • Dynamic Connectivity
        • Quick Find - Eager Approach
        • Quick Find - Lazy Approach
        • Defects
        • Weighted Quick Union
        • Quick Union + path comparison
        • Amortized Analysis
      • Convex Hull
      • Binary Heaps and Priority Queue
      • Hash Table vs Binary Search Trees
  • Concurrency and Multithreading
    • Introduction
    • Visibility Problem
    • Interview Questions
    • References
      • System design
  • Design Patterns
    • ℹ️Introduction
    • πŸ’ Classification of patterns
    • 1️⃣Structural Design Patterns
      • Adapter Design Pattern
      • Bridge Design Pattern
      • Composite Design Pattern
      • Decorator Design Pattern
      • Facade Design Pattern
      • Flyweight Design Pattern
      • Private Class Data Design Pattern
      • Proxy Design Pattern
    • 2️⃣Behavioral Design Patterns
      • Chain Of Responsibility
      • Command Design Pattern
      • Interpreter Design Pattern
      • Iterator Design Pattern
      • Mediator Design Pattern
      • Memento Design Pattern
      • Null Object Design Pattern
      • Observer Design Pattern
      • State Design Pattern
      • Strategy Design Pattern
      • Template Design Pattern
    • 3️⃣Creational Design Patterns
      • Abstract Factory Design Pattern
      • Builder Design Pattern
      • Factory Method Design Pattern
      • Object Pool Design Pattern
      • Prototype Design Pattern
      • Singleton Design Pattern
    • Java Pass by Value or Pass by Reference
  • Designing Data-Intensive Applications - O'Reilly
    • Read Me
    • 1️⃣Reliable, Scalable, and Maintainable Applications
      • Reliability
      • Scalability
      • Maintainability
      • References
    • 2️⃣Data Models and Query Languages
      • Read me
      • References
    • Miscellaneous
  • Preparation Manual
    • Disclaimer
    • What is it all about?
    • About a bunch of links
    • Before you start preparing
    • Algorithms and Coding
    • Concurrency and Multithreading
    • Programming Language and Fundementals
    • Best Practices and Experience
  • Web Applications
    • Typescript Guidelines
  • Research Papers
    • Research Papers
      • Real-Time Data Infrastructure at Uber
      • Scaling Memcache at Facebook
  • Interview Questions
    • Important links for preparation
    • Google Interview Questions
      • L4
        • Phone Interview Questions
      • L3
        • Interview Questions
      • Phone Screen Questions
  • Miscellaneous
    • 90 Days Preparation Schedule
    • My Preparation for Tech Giants
    • Top Product Based Companies
  • Links
    • Github
    • LinkedIn
Powered by GitBook
On this page
  • Algorithms
  • What you need to know
  • Notes
  • Advice
  • Books
  • Links and Articles
  • Coding
  • What you need to be able to
  • What you need to know
  • Advice
  • Books

Was this helpful?

Edit on GitHub
  1. Preparation Manual

Algorithms and Coding

Priority: P0

PreviousBefore you start preparingNextConcurrency and Multithreading

Last updated 3 years ago

Was this helpful?

Algorithms

What you need to know

Please note here that if I write that I need to know "Linked lists", for example, then I will not list every algorithm related to this topic. But it is understood that you need to independently study which he has operations and practice writing delete, insert and other important things.

The second important thing is that if you are short on time and do not have time to cover all topics, then choose those that you are more likely to meet. For example, it is better to study graphs and trees, than encryption algorithms. But if you have the opportunity, try to study everything, at least for the level of understanding of Wikipedia.

  • Basic things

    • Algorithm complexity - what is it and how is it counted? The complexity is temporary and spatial

    • Working with bits - tables AND, OR, XOR. This also includes a binary notation, and degrees deuces

    • Fundamentals of Probability Theory

    • Basics of combinatorics and counting the number of different combinations

    • Fundamentals of Euclidean geometry - for example, how to check if points lie on the same straight, on one or different sides of a straight

    • Fundamentals of Cryptography

    • Computer Security Fundamentals

  • Basic Data Structures

    • Strings

      • ASCII, UNICODE

      • How Strings are implemented in your programming langauge ( for example does it have maximum length )

      • Search for substrings (for example, the Rabin-Karp algorithm)

      • Regular expressions

    • Arrays

      • Implementation details in your programming language. For example, for C ++ you need to know the implementation using pointers, and the vector. For a vector too you need to know, for example, what it resize periodically, and other similar details.

    • Linked Lists

      • Single Linked List

      • Double Linked List

      • Less common types are listed in page

    • Stacks and Queues

    • Trees

      • DFS , BFS

      • Adding and removal of elements

      • Less common tree types (eg, red black trees, B-trees) - what are they, how they

        differ from the binary trees, basic complexities, and how they are used. No need to know all the rotations in the RB-tree, for example.

      • Tries

    • Heaps

      • Heap sort

      • Using heaps for tracking top-K

      • Allocating elements on a heap vs on a stack - what does it mean?

    • Graphs

      • DFS, BFS

      • Topological search

      • Shortest path

    • Hash

      • Hash functions

      • Universal hash

  • Algorithms

    • Sorting

      • Especially make sure you know heapsort, mergesort and quicksort.

    • Searching

      • Binary search

      • Searching in linked lists, arrays, trees, graphs, dictionaries

    • Dynamic Programming

    • Greedy Algorithms

    • Recursion

  • Other Mastering algorithms

    • Master theorem

    • NP Complete Problems

    • Discrete Math

Notes

  • You need to understand the trade offs of each task. For example, searching in a HashMap is usually faster sort, but it needs additional memory. So in cases where the speed is not critical, but memory, yes, it may be better to sort.

  • For more rare data structures - eg, trie, B-tree, red black tree - it is not necessary to remember all rotations for deleting and inserting an element, but you need to understand how these structures work and where they are used.

  • Learn standard problem solving techniques. For example, a heap of size K can be

use top-K for large array for linear complexity. Remember these tricks are worked out by solving problems.

Advice

When learning algorithms, ask yourself the questions yourself. This is the easiest way to deepen own knowledge. For example, when the complexity of the algorithm is log (n), then on what basis is log and why? Or what is better to buy to speed up your code - a sea of RAM or more smart processor? Why?

Books

Links and Articles

  • http://visualgo.net - many visualizations of algorithms and data structures

  • Video from the author of "Cracking the coding interview":

Coding

             I regularly see candidates for the hiring committee who know how to solve problems, everyone knows well algorithms, but cannot write code for them. Surprising but true! Such a candidate finds the most the optimal solution, can tell you well why it is optimal, and in general, brilliant copes with the task in the plane of theory. But when it comes to writing to the task code, he gets a gag, and he writes for a long time, with mistakes, and does not have time to finish the interview. So we refuse candidates with the words " _They are, of course, smart and with potential, but it is immediately clear that you need to develop some coding skills._ "

In general, don't be like that candidate. Be sure to practice writing code for tasks. Necessarily! You should be able to write a binary search or quicksort there without coming to consciousness, if I wake you up in the middle of the night!

What you need to be able to

  1. Quickly and without errors write the code of the standard algorithm (binary search, sorting, depth-first search, breadth-first search, removing an element from a linked list ...)

  2. Quickly and without errors, write the code for your solution to the algorithmic problem in the interview. it means that if you combine several data structures, for example (well, you never know :), store the nodes of the graph in a linked list and do something with them in the search process, then you should completely calmly write the code for the graph, and the code for the linked list, and the code for search.

  3. Write code that compiles (avoid pseudocode if possible).

  4. Write code that works with corner cases: null, empty lines, zero, negative numbers

  5. Write code that doesn't just work, but works efficiently. For example for C ++, if

    you need to pass a string as a parameter to the function, it will be correct to write

    f (const string & s), instead of f (string s).

  6. Test your code without being reminded and find all errors yourself. Better right away

    start with test cases, at least in the simplest form: that is, you have been assigned a task - write an example (or several) of input and output data before writing the actual code. In this way, you are not just setting the stage for further debugging your code, but also make sure that you correctly understand the task set by the interviewer.

  7. When testing, try to cover all the code - so that the code coverage is 100%.

What you need to know

Advice

  1. Keep in mind that the most important thing here is practice, not reading books and articles. In the context of the process preparation for the interview, you can write the code for the solution, and then look at other people's solutions the same task and compare how much the best of them are better than yours and what your decision. Close someone else's solution and rewrite yours to make it more "elegant". Do this with each task until your solution looks like one of the best among the rest.It is better to rewrite the problem using someone else's solution on the next day, then you will be sure that you really understand how a faster solution works, and not just copied the code seen from the head.

  2. Speak your train of thought. The interviewer doesn't know what's going on in your head if you silently look at the board for five minutes. Maybe you have already thought through and discarded 5 different approaches, but the interviewer may think that your head is empty. Therefore, we must speak. For most people, this is unnatural. Practice with a friend.

  3. If you can't immediately come up with the optimal solution to the problem, start with brute force solutions. Tell me that you understand that it is not the best, but you want to start with it, in order to further improve and optimize. Perhaps the interviewer will "push" you in the right direction, but even if not, then it is better to do at least something than look at clean board and look like a complete idiot. 🀨

  4. You probably won't be given an IDE to write code. And without Code Insight, write much more difficult. You may be asked to write the code on the board with a marker, on paper with a pencil, or Alternatively, if it's a remote phonescreen, go to Google Doc. Practice writing code on paper with a friend, and then let him give you feedback on how it looked.

  5. Nobody will require you to remember all the methods of all library classes and all parameters of all methods, but you should at least in general terms remember the syntax. Have in mind that writing with a marker on a blackboard is in some respects even more difficult than writing with a pen on paper - because although you can erase your code, markers are usually very thick and on the boards quickly runs out of space. (In some sources, therefore, even it is advised to bring your markers to the interview, thinner. Just don't bring indelible, otherwise you will definitely remain in the interviewer's memory for a long time, but not in the better context! 🀨

The advice to practice not alone, but with someone is one of the most difficult to implement, and accordingly, one of the most overlooked. The trouble is that he is also one of the most significant. Believe me, solve the problem yourself and solve it under the watchful eye interviewer, under stress and limited time - these are two big differences. if you there is absolutely no one to ask and no one to cooperate with to evaluate your interview - at worst end, record yourself on camera. Then review and rate. ( I repeat that this is an option really without fish, that is, in the case when you really have absolutely no one ask, or you are so shy that before you ask someone, you need practice alone.)

Books

You need to understand the limitations of each task. For example, searching for an element in an array cannot be done in less than O (n) time. Or that in general the complexity sorting, which uses a comparison elements,

What is NP completeness. This is the type of problem that can only be solved by exhaustive search options. Know what tasks are -

Another good answer to the "What you need to know" question on Stackexchange:

, - Courses Stanford algorithms

- a course at Princeton

- one course at Princeton

Write neat, which reads well. The fewer lines the better but not at the expense of readability. If you have several options - for example, more efficient code, which, however, is less readable, then discuss these options with interviewer.

Standard libraries of your programming language. For example, you should know how or without looking at the documentation. For C ++ it means knowing quite a lot things from STL and std.

wikipedia
can not be less than O (n log n)
NP-complete
Which algorithms / data structures should I β€œrecognize” and know by name?
Introduction to algorithms
The Algorithm Design Manual
Discrete Mathematics for Computing
Algorithms (4th edition)
Essential Algorithms by Rod Stephens
Big-About Cheat Sheet
Algorithms: Design and Analysis, Part 1 (Stanford)
Part 2
Algorithms, Part I of (The Princeton)
an Analysis of Algorithms (The Princeton)
Intro to Algorithms (Udacity)
How Companies Evaluate Technical Interviews
How to Approach Behavioral Questions
7 Steps to Solve Algorithm Problems
3 Algorithm Strategies
The Mastering the Software Engineering of Interview on Coursera
elegant code
remove an element from the middle of the array
find elements of a set that are not in another the set
"Clean Code: A Handbook of Agile Software Craftsmanship"
"Code Craft: The Practice of Writing Excellent Code"
"The Clean Coder: A Code of Conduct for Professional Programmers (Robert C. Martin Series)"
"Beautiful Code: Leading Programmers Explain How They Think"
Effective Java (2nd Edition) 2nd Edition by Joshua Bloch