DS/Algo/OS

When you don't have enough time for interview, read the posts which are tagged as 'Must Read'

1. Data Structure

What datastructure to choose?

1) List

   Singly Linked List 

   list.assign(), list.insert(), return list in C++

   Merge two sorted linked lists

2) Arrays/Vectors

3) Tree

   Binary Search Tree

   Count good nodes in Binary Tree 

4) Graph 

    

  

5) Stack

    Stack with STL     (Must Read *) 

    Stack.empty example

2. Algorithm

     Design and analysis of algorithm

Efficient Algorithm

2.1) Searching & Sorting

Graph Search 
Breadth First Search - Find the shortest path 
Binary Search  - Divide & Conquer Technique
Searching a BST 
Bruteforce Algorithm

Sorting 

Merge Sort
Sort the characters in the given string
Sort the vector of classes

2.2) Arrays/Vectors

Charcount Array

Maximum frequency of the characters in an array

Finding Middle element in the array

Accessing array with index as char array element 

Array hacks

Contains Duplicate (#217 Leetcode)

Find all Duplicates in an array (#442 Leetcode)

Spiral Matrix #54 Leetcode

Find minimum in Rotated Sorted Array (#53 Leetcode)

Best time to buy and sell stock (#121 leetcode)

Karatsuba's Algorithm

Product of array except self (#238 Leetcode)

     2.2.1) Subarray Problems 

         Subarray without range (Kadane's)

              Kadane's Algorithm - Video - Maximum SubArray Sum - O(n) (Must Read)*

               Subarrays with K different integers 

               Maximum Erasure value 

               Number of Equal count substrings

         Subarray with range  (Sliding Window Technique)

              Maximum Subarray sum in a specific range of elements (Must Read *)

               Longest Substring with Same Letters after Replacement 

               Longest Subarray with Ones after Replacement

     2.2.2) Suffix Array Problems :

              1) Pattern Searching 

              2) Finding the Longest Repeated Substring 

              3) Finding the Longest Common Substring 

              4) Finding the Longest Palindrome in a string

              5) Longest even length substring 

     2.2.3) Two Pointers

             1) Container with most water  - O(n) 

             2) Trapping Rain water  - O(n) (Must Read *)

            3) Number of Brush Strokes  - O(n)

2.3) String 

Frequency of the digits in the given string

        2.3.1) Substring problems

             Longest substring without repeating characters (#3 Leetcode) - O(n) (Must Read *)

             Longest substring with at most two distinct characters

             Longest substring with at most K distinct characters

             Longest repeating character replacement (#424 Leetcode) - O(n) (Must read *)

             Minimum Window Substring  (Must read *)

          

       2.3.2) Pattern Search

Input:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
Output: Pattern found at index 0
               Pattern found at index 9
               Pattern found at index 12

Rabin-Karp Algorithm - Video - Pattern Searching with hash method- O(n+m) Best case & O(nm) Worst Case

Boyer Moore Algorithm  - Pattern Searching with heuristic - O(n/m)

     2.3.3) Anagram Search

 Input:  txt[] = "BACDGABCDA"  pat[] = "ABCD"
   Output:   Found at Index 0
                    Found at Index 5
                    Found at Index 6

            Permutation vs Combinations

            Search for all permutations

           Valid Anagrams (#242 Leetcode)  (Must Read *)

           Group Anagrams (#49 Leetcode) (Must Read *)

      2.3.4) Palindrome

            Longest Palindromic Substring (#5 Leetcode)  (Must Read *)

            Valid Palindrome (#125 Leetcode)  (Must Read *)

            Palindromic Substrings

            Encode and Decode Strings (Leetcode Premium)

            Encode and Decode tiny URL 

    

       2.3.5) Parentheses ()

              Valid Parentheses (#22 Leetcode) (Must Read *)

              Generate parentheses (#22 Leetcode)

              Score of Parentheses (#856 Leetcode)

              Minimum add to make parentheses valid (#921 Leetcode)

        

2.4) Graph 

BFS vs DFS 

2.5) Dynamic Programming

2.6) Interval  (Greedy Algorithm)

  a) Non-overlapping Intervals

  b) Merge Intervals

2.7) Bitwise Operations

Packing & Unpacking the number 

32bit to 64bit masking

Set/Clear/Toggle/Swap bits  (Must Read *)

32 bit & 31 bit explanation

Endianness of the system (Must Read *)

Convert an integer into bits  (Must Read *) - Little different libraries

Read the below for grokking:

14 Patterns
Topic Wise LeetCode Problems
Click here and read here too 

All leetcode problems solved by me

20. Valid Parentheses (75 Blind Leetcode)

125. Valid Palindrome (75 Blind Leetcode)

856.Score of Parentheses

3. Operating System (OS)

Process & Process management

What is preprocessing?  (Must Read) *

Memory Layout of a Process

How malloc works? (Must Read) *

Interrupts & Interrupt Service Routine

Threads & Concurrency

Multithreading without pjoin()
Multithreading with pjoin()

Overview of Hang Process

Concurrency in C++ (Must Read) *

Semaphore vs Mutex vs Spinlock

Semaphore/Mutex/Spinlock  (Must Read) *

Preemptive and Non-preemptive

Race Condition

Mutex vs Semaphore
Mutex Program

Debugging a hang issue (Unable to unlock) (Must Read) *

Socket Programming

Socket Programming
Server & Multi-Client Socket
Inter-Process Communication
Message Queue
Shared Memory
File Systems

System Calls

fork() & wait()
Dead Lock  (Must Read) *
Common Bash Errors 
DRAM vs Flash  (Must Read) *


Reference : medium