Catalan number wiki article

May 8, 2017

Introduction

It is very interesting to study catalan number again. This time Julia likes to go over the wiki article and then try to get better understanding the algorithm.

Tonight she had mocking experience to learn an algorithm - find maximum number of path from bottom-left corner to top-right corner, and do not cross the diagonal line. In other words, always stay underneath the diagonal line. She learned that the algorithm is similar to Catalan number.

Catalan number 

Catalan number

January 21, 2018

Introduction

It was another 10:00 PM mock interview again. I had to write the algorithm called catalan number. After I finished coding, the peer asked me if I can make an array copy instead of writing a for loop. So I looked up Array.Copy and then used it first time in mock interview.

Code review

Here is the C# code.

Catalan number

January 27, 2018

Introduction

It is another mock interview and I had to work on the algorithm related to Catalan number. This time the peer dropped a hint, do not need to use previous row, only use current row and then save the space. I wrote the code based on his advice.

Algorithm 

Here is the code based on the advice from the peer.

Catalan number

August 30, 2017

Introduction

It is the classical algorithm and also I like to practice again and again. It is called Catalan number. When I am tired, my brain stops working partially but I do not know which part. Today, I had a mocking practice starting from 10:00 pm, and I was very tired after one day coding at work, and then I asked the peer which one is row and which is column. I looked at the graph and I did not know where the row is. The peer told me that row should be horizontal. You see, when I am tired, I still can tell quickly the horizontal and vertical, but I could not tell which is row and column. I have to ask the peer and get some assumption based on the common sense.

I practiced the algorithm before more than once, one time I was the interviewer and one time I was the interviewee.

Algorithm

Here is C# practice. I wrote the code to pass all test cases in my first writing.

Actionable Items

Try to figure out the tough situation, when I am tired and physical sleepy, after one day work, 10:00 pm, what is my best strategy to work with peers to solve data structure and algorithm problems.

Yesterday I booked 10:00 pm mocking, but at 9:30 pm, I laid on bed to read wechat and fell asleep, when I woke up, it was 10:10 pm, I missed the mocking practice.

Never lay down and I should sit up and keep myself wake until 10:00 pm.

Catalan number

January 17, 2018

Introduction

It is the algorithm peer gave it to me for a test since he had the algorithm the day before. I had to work on the algorithm called Catalan number on January 15, 2018, 10:00 mock interview. I explained the algorithm to the peer, and also showed last 3 practices.

Will write down the discussion of the algorithm here later.

Catalan number

Nov. 28, 2017

Introduction

It only takes 20 minutes to work on Catalan number algorithm. And then surprisingly, the peer asked me to reduce the space from O(n²) to O(n). The peer said that since you finished early, still 10 minutes left.

Code study 

C# code in practice is here.

Catalan number (II)

Sept. 12, 2017

Introduction

It is the classical algorithm to calculate the catalan number. My last practice is documented here. It is very challenge to work with the peer and I ran into the index out of range error in my first writing, and then I modified the code, and argued that first row and first column should exclude from the double for loop, and discuss first row and first column separately.

I need to work on the algorithm problem solving, need to look into the feedback.

Algorithm practice 

C# practice code is here which passes all test cases. 

From the above feedback, I did not communicate very well this time. Need to figure out how to clarify of my answers and line of reasoning. 

Follow up 

January 17, 2018

It is the first time I know how to review my own past practice. Missing the analysis of the algorithm writing is a big issue for me now, production ready code should be written with some analysis and time complexity and space complexity. I have to write down the algorithm, and constraints, and the requirement, what problem to solve. And also my analysis of the problem, solve it on a simple example, go over the example to explain to the peer first. And make sure that the peer understands the problem.

From the transcript of the practice, I did not write any analysis of the algorithm. That is not good practice at all.

The peer did complain and I should have let peer know the algorithm and how to solve it first using a simple example. 

Catalan number

Feb. 18, 2018

Introduction

It is my favorite quote saying that practice until you cannot get it wrong. On Feb. 17, 2018 I practiced the algorithm Catalan number but I got it wrong.

I had some issue with understanding n-grid.

Code review

I will look into the issue later. Here is the C# code.

Algorithms | system design | a list created by anonymous | Leetcode, Facebook offer

April 8, 2021

FB | London | Offer

Here is the link. 

 

Data Structure - LLDs - ( 1 Week )

List of data structures

• Lists

• Design Linked List

• Design Skiplist

• Stacks

• Implement Stack using Queues

• Design a Stack With Increment Operation

• LRU Cache

• Min Stack

• Max Stack

• Dinner Plate Stacks

• Implement Queue using Stacks

• Queue

• Design Circular Queue

• Hashtable

• Design HashMap

• Design HashSet

• BST 

• Binary Search Tree Iterator

• Serialize and Deserialize BST

• Red Black Tree

• Find Median from Data Stream

• Count of Range Sum

• Heaps 

• Design Twitter

• Kth Largest Element in a Stream

• Fibonacci Heaps

• Fibonacci Heaps

• Disjoint Sets

• Review of two popular approaches, Disjoint Sets and DFS

• Tries (PrefixTree, suffixTree)

• Implement Trie (Prefix Tree)

• Add and Search Word - Data structure design

• Interval Trees/Segment Tree

• Lazy Dynamic Segment Tree - A general template

• A Recursive approach to Segment Trees, Range Sum Queries & Lazy Propagation

• Other Tree Data Structures(Graphs)

• Serialize and Deserialize N-ary Tree

• Encode N-ary Tree to Binary Tree

Algorithms - Analysis Time and Space - ( 3 Weeks )

• Sorting  - 2 Days

• Selection Sort - Merge Sorted Array

• Bubble Sort - Sort Colors

• Insertion Sort - Insertion Sort List

• Merge Sort - Sort an Array

• Quick Sort 

• Kth Largest Element in an Array

• K Closest Points to Origin

• Counting Sort - Relative Sort Array

• Tree sort - Convert Sorted List to Binary Search Tree

• Bucket Sort - Top K Frequent Elements

• Radix Sort - Maximum Gap

• Topological sort - Covered in Graphs

• Divide-and-Conquer - 2 Days

• The maximum-subarray problem - Maximum Subarray

• Strassen’s algorithm for matrix multiplication - Divide and Conquer | Set 5 (Strassen's Matrix Multiplication)

• The substitution method for solving recurrences

• The recursion-tree method for solving recurrences

• The master method for solving recurrences

• Dynamic Programming - 2 Days

• Rod cutting - Integer Break

• Dynamic Programming for the confused : Rod cutting problem

• Matrix-chain multiplication - Burst Balloons

• Elements of dynamic programming

• Longest common subsequence - Longest Common Subsequence

• Optimal binary search trees

• Unique Binary Search Trees

• Unique Binary Search Trees II

• Greedy Algorithms - 2 Days

• An activity-selection problem - Minimum Number of Arrows to Burst Balloons

• Elements of the greedy strategy

• Huffman codes - Construct Huffman Tree, Google | Onsite | Software Engineer | Huffman Coding Algorithm, Minimum Cost Tree From Leaf Values

• Matroids and greedy methods - Matroid intersection in simple words

• A task-scheduling problem as a matroid - Task Scheduler

• Graph Algorithms - 6 Days

Leetcode Pattern 1 | DFS + BFS == 25% of the problems

• N-ary Tree Preorder Traversal

• N-ary Tree Postorder Traversal  

• N-ary Tree Level Order Traversal

• BFS

• Binary Tree Level Order Traversal

• Binary Tree Level Order Traversal II

• Web Crawler Multithreaded

• Web Crawler

• Cut Off Trees for Golf Event

• Course Schedule

• DFS

• Binary Tree Postorder Traversal

• Binary Tree Preorder Traversal

• Binary Tree Inorder Traversal

• Is Graph Bipartite?

• Remove Invalid Parentheses

• Construct Binary Tree from Preorder and Inorder Traversal

• Topological Sort - Topological Sort

• Strongly Connected Components - SCC - Course Schedule, Facebook | Minimum number of people to spread a message, Airbnb | Cover all vertices with the least number of vertices, Critical Connections in a Network

• Minimum spanning Tree - Prim's Algorithm

• Cheapest Flights Within K Stops

• Minimum Height Trees

• Number of Operations to Make Network Connected

• Connecting Cities With Minimum Cost

• Shortest Path Algos - 

• Bellman-Ford - Network Delay Time, https://leetcode.com/problems/get-watched-videos-by-your-friends/

• Dijkstra’s algorithm

• Reachable Nodes In Subdivided Graph

• Shortest Path Visiting All Nodes

• Floyd-Warshall

• Find the City With the Smallest Number of Neighbors at a Threshold Distance

• Evaluate Division

• Johnson’s algorithm

• All-pairs shortest paths - Johnson's algorithm for sparse graphs - GeeksforGeeks

• Johnson's algorithm

• The Ford-Fulkerson method

• Google | Onsite | Network flow for the matrix with given row and column sums

• Ford-Fulkerson Algorithm for Maximum Flow Problem

• Number-Theoretic Algorithms - 2 Days

• The Chinese remainder theorem - Check If It Is a Good Array

• Greatest common divisor

• Greatest Common Divisor of Strings

• X of a Kind in a Deck of Cards

• Google | OA Summer Intern 2020 | Greatest Common Divisor

• Powers of an element

• Pow(x, n)

• Sort Integers by The Power Value

• The RSA public-key cryptosystem

• Keys and Rooms

• Shortest Path to Get All Keys

• Integer factorization

• Largest Component Size by Common Factor

• Minimum Factorization

• 2 Keys Keyboard

• Bulb Switcher

• String Matching - 2 Day

• The Rabin-Karp algorithm

• Implement strStr()

• Binary String With Substrings Representing 1 To N

• Shortest Palindrome

• Find All Anagrams in a String

• String matching with finite automata

• The Knuth-Morris-Pratt algorithm

• Shortest Palindrome

• Rotate String

• KMP Algorithm for Pattern Searching

• Approximation Algorithms - 3 Days

• The vertex-cover problem

• Binary Tree Cameras

• Vertex Cover Problem-2

• Vertex Cover Problem

• The traveling-salesman problem Find the Shortest Superstring

• The set-covering problem

• Video Stitching

• Set Intersection Size At Least Two

• Non-overlapping Intervals

• Randomization and linear programming

• The subset-sum problem

• Partition Equal Subset Sum

• Partition to K Equal Sum Subsets

• Randomized Algorithms - 1 Day

• Quick Sort

• Min Cut Palindrome Partitioning II

Concepts Problems and Maths - ( 1 Week )

• Matrix Operations

• Linear Programming

• Polynomials - DFT, FFT

• Computational Geometry

• Line-segment properties

• Determining whether any pair of segments intersects

• Finding the convex hull - Erect the Fence, The Skyline Problem

• Finding the closest pair of points - K Closest Points to Origin

• GCD and LCM

• X of a Kind in a Deck of Cards

• Greatest Common Divisor of Strings

• Nth Magical Number

• Ugly Number III

• Prime Factorization and Divisors

• Largest Component Size by Common Factor

• 2 Keys Keyboard

• Fibonacci Numbers

• Length of Longest Fibonacci Subsequence

• Split Array into Fibonacci Sequence

• Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

• Catalan Numbers - Unique Binary Search Trees

• Modular Arithmetic

• Euler Totient Function

• nCr Computations

• Set Theory

• Factorial

• Last Substring in Lexicographical Order

• Snakes and Ladders

• Factor Combinations

• Path With Maximum Minimum Value

• Number of Closed Islands

• Prime numbers and Primality Tests

• Prime Arrangements

• K-th Smallest Prime Fraction

• Sieve Algorithms

• Count Primes

• Divisibility and Large Numbers

• Series

• Number Digit

• Triangles

• Triangle

• Valid Triangle Number

Networks - ( 1 Week )

Leetcode

• Network Topology, OSI Architecture

• TCP/IP models

• TCP and UDP

• Firewall, DNS, Domains, workgroups

• Protocols i.e ICMP

OS - ( 1 week )

Operating System Tutorial
Shared Memory Systems

• Cache

• Multithreading

• Producers-consumers problem

• Dining philosophers problem

• Cigarette smokers problem

• Readers–writers problem

• Web Crawler Multithreaded

• Scheduling algorithms

• Deadlock

• Virtual Memory

• Mutex and semaphore

• Kernels

• Paging

Software Design Principles - ( 2 weeks )

System Design Primer

Start learning about Theory of Distributed Systems?

Challenges with distributed systems

Microservices Design Guide 👨‍🏫 - Platform Engineer

Cloud design patterns - Azure Architecture Center

Design patterns for microservices | Azure Blog and Updates

TO READ:

Domain Driven Design (DDD) | Bounded Context (BC) | Polyglot Persistence (PP)| Command and Query Responsibility Segregation (CQRS) | Command Query Separation (CQS) | Event-Sourcing (ES) | CAP Theorem | Eventual Consistency | Twelve-Factor App | SOLID Principles |

Just some things to focus on.

• Load balancer

• API gateway

• Microservices - Scale Cube Concept, MVC - READ

• Database Sharding

• SQL vs NoSQL - Cassandra, Postgres, Hadoop, Data lake, other algorithms related to data lake, CAP Theorem

Leadership Principles - LPs - ( 1 Week )

TO BE UPDATED

Resume and Miscellaneous

#ADD WHATEVER YOU HAVE PUT IN RESUME

• Algos you have mentioned

• Project work and related references to read

• Achievements and information about it

REFERENCES

Introduction to Algorithms - Cormen

Leetcode

---