Editorials for Algorithmic problems explaining different approaches to a problem along with their complexities
Paradigm | Concept | Examples |
---|---|---|
two pointer approach | Use two pointers for the array and move the pointers based on some decission | --- |
sliding window | Similar to two pointer approach but usually the window (distace between two pointers) is fixed and the window is moved in a direction based on some decission | par |
use array as position array | use index of the array to flag the value of index | used in finding duplicates in array etc |
Computing left/right result arrays | Compute left result or right result arrays | |
Divide and conquer | Divide the given problem into sub problems and solve the subproblems recursively | |
Greedy | Choose the solution based on the first best way possible | https://www.geeksforgeeks.org/greedy-algorithms/ |
Dyanamic programming | Identify subproblems and try to solve the given problem with the help of the subproblems in a top down approach | https://www.geeksforgeeks.org/dynamic-programming/ |
- Typically used for arrays
- Usually used in the following ways.
- Two pointers start from either end of an array and move according to a condition
- one is slow pointer and another is fast pointer.
Further read: interviewbit-two-pointer leetcode-two pointer
Generally speaking a sliding window is a sub-list that runs over an underlying collection. I.e., if you have an array like
[a b c d e f g h]
a sliding window of size 3 would run over it like
[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]
This is useful if you for instance want to compute a running average, or if you want to create a set of all adjacent pairs etc. (Source: Stackoverflow)
More Information : https://www.geeksforgeeks.org/window-sliding-technique/
[To Do]
- Handle null object
- Look for "index out of bounds" exception
- Take care of -ve numbers
- Handle zero length string/array
- Handle empty string
- Handle string with length 1 (particularly important in two pointer approach)
- Ask for expected time complexity
- Ask for expected space complexity
- If it is number - number +ve/-ve/integer/float?
- Are you testing the script for multiple inputs or single input? (Intention is: sometimes you can use hashmap for storing the result and use it as a look up in case multiple inputs are being given)
- Characters only a-z ?
- Are there any duplicates present?
- All the numbers positive/negative?
- All the numbers integers or float?
- Ask if array is sorted