DS/Algo/OS



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

1) List

2) Arrays/Vectors



3) Tree


    
  
5) Stack
    Stack with STL     (Must Read *) 

2. 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




     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 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 tiny URL 
    

       2.3.5) Parentheses ()

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

2.4) Graph 

2.5) Dynamic Programming

2.6) Interval  (Greedy Algorithm)

2.7) Bitwise Operations

Packing & Unpacking the number 

Read the below for grokking:


All leetcode problems 

Array 

Strings




Linked List

21. Merge two sorted list (75 Blind Leetcode)
206. Reverse a linked list (75 Blind Leetcode)


Dynamic Programming


3. Operating System (OS)

Process & Process management

What is preprocessing?  (Must Read) *
Memory Layout of a Process
How malloc works? (Must Read) *
Concurrency in C++ (Must Read) *

Semaphore vs Mutex vs Spinlock

Semaphore/Mutex/Spinlock  (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

Comments