NOTES

STRINGS

• Continuous string combinations formula n*(n+1)/2.
• strtok() can be used to get delimiter seperated strings.

DYNAMIC PROGRAMMING

• Use static allocation for dp grid. eg static int dp[5001][5001];
• General formula for n-steps problem dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + ...... + dp[i-n];.
• The important point is that top-down = recursive and bottom-up = iterative.

BINARYSEARCH

• Effective way to search in a sorted array. O(log n) time.
• Steps to solve Binary Search Problem.
• Find if the problem shows a monotonic nature.
• MONOTONIC FUNCTIONS := Functions that are either non-increasing or non-decreasing.
• Find a Search Space. Mostly in problems the search space is not easly observable.
• SEARCH SPACE := space of values where the function can be optimized.
• search space should be monotonic to solve a problem using Binary Search.
• EX := Finding the root of the number, aggressive cow etc.

LINKEDLIST

TREES

GREEDY

STACKS

HASHMAP

DICTIONARIES

GRAPHS

QUEUES

BACKTRACKING

RECURSION

SORTING

SEARCH

MISCELLANEOUS