Interview Algorithms: Difference between revisions

Created page with "Insights from Leetcode problems. ====Finding a cycle in a linked-list==== Use two runners. <math>O(n)</math><br> Runner 1 goes two steps per iteration.<br> Runner 2 goes one..."
 
No edit summary
 
(29 intermediate revisions by the same user not shown)
Line 1: Line 1:
Insights from Leetcode problems.
Insights from Leetcode problems.


==Two Pointers Algorithms==
Having two pointers can make your algorithm run in linear time.


====Finding a cycle in a linked-list====
====Finding a cycle in a linked-list====
Line 7: Line 9:
Runner 2 goes one step per iteration.<br>
Runner 2 goes one step per iteration.<br>
If there is a cycle, runner 2 will lap runner 1 within 2 cycles.
If there is a cycle, runner 2 will lap runner 1 within 2 cycles.
==Sliding Window==
If you need to find a '''contiguous subarray''' or '''contiguous substring''', chances are it's a sliding window problem.
Usually the structure will be something like:
<syntaxhighlight lang=cpp>
int best_case = WORST_POSSIBLE_VALUE;
int left = 0;
for (int right = 0; right < arr.size(); right++) {
  // Add right to your subarray
  int subarray_length = right + 1 - left;
  // Do some checks to see if the subarray is valid
  // Do left++ while keeping the subarray valid
  // Update best_case
}
return best_case;
</syntaxhighlight>
Example problems: https://leetcode.com/discuss/study-guide/3630462/Top-20-Sliding-Window-Problems-for-beginners
==Backtracking==
====Permutations====
Print all permutations of an array.<br>
The idea here is that you need a for-loop nested for each element of an array.<br>
So n elements means n nested for-loops. You use recursion to nest the loops.<br>
You can also think of this as a graph problem when you need to find every possible path with DFS.<br>
* [https://leetcode.com/problems/permutations/ Permutations]
* [https://leetcode.com/problems/permutations-ii/ Permutations-ii]
{{ hidden | Permute Brute-force solution |
A more advanced solution would use backtracking, however it is time-consuming to implement for an interview.<br>
Here is a quick brute-force solution.
* Enumerate all possible n^n numbers from 000 to 999 and then filter out number with duplicate digits
<syntaxhighlight lang="cpp">
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> indices(nums.size());
        permuteHelper(nums, indices, 0, ans);
        return ans;
    }
   
    bool isValid(vector<int>& indices) {
        vector<char> check(indices.size(), false);
        for (int i = 0; i < indices.size(); i++) {
            if (check[indices[i]]) {
                return false;
            }
            check[indices[i]] = true;
        }
        return true;
    }
   
    void permuteHelper(vector<int>& nums, vector<int>& indices,
                      int col, vector<vector<int>>& ans) {
        if (col == nums.size()) {
            if (isValid(indices))
                print(nums, indices, ans);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            indices[col] = i;
            permuteHelper(nums, indices, col+1, ans);
        }
    }
   
    void print(vector<int>& nums, vector<int>& indices, vector<vector<int>>& ans) {
        vector<int> new_nums(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            new_nums[i] = nums[indices[i]];
        }
        ans.push_back(new_nums);
    }
};
</syntaxhighlight>
}}
==Data Structures==
===Hashmap===
Also known as a dictionary or associative array. These are used everywhere.<br>
If you know your inputs are bounded non-negative values, then you can use an array like <code>std::vector</code>.<br>
Otherwise, just use a hashmap to build a lookup table.
===Segment Trees===
See [https://cp-algorithms.com/data_structures/segment_tree.html CP Algorithms segment tree]
===Union Find===
In Union Find, you build a tree where each tree represents a set.<br>
Your given a pair of relations where (a, b) indices a and b are in the same set.<br>
The ''Union'' operation places a and b in the same set by attaching the root of b to the root of a.
The ''Find'' operation recursively looks up the parent of a to find the root of the tree of a.
<syntaxhighlight lang="python">
parents = {}
def find(a):
  while parents[a] != a:
    a = parents[a]
  return a
for (a, b) in relations:
  if a not in parents:
    parent[a] = a
  a_root = find(a)
  if b not in parents:
    parent[b] = b
  b_root = find(b)
  parents[b_root] = a_root  # Attach b_root to a_root
</syntaxhighlight>
==Dynamic Programming==
DP is mostly used for Google interviews. Meta for example will not ask DP problems. You should study DP after everything else or if you've secured a Google interview.
If you're given an arbitrary function with <code>n*m</code> possible inputs, you should aim to find an O(n*m) solution.
==Prefix Sum==
If you need to do a reduce operation on a continuous subarray, chances are you can turn that O(n) into O(1) by building a prefix sum. Similarly for 2D with axis-aligned regions.
==Tricks==
===Bit tricks===
See https://www.geeksforgeeks.org/bit-tricks-competitive-programming/
It's rare that you will need bit tricks for an interview. However some leetcode questions may require them to get decent performance.
The most useful one is
<pre>
n & n-1
</pre>
which zeros the least significant set bit.
E.g. this can be used to count the number of set bits.
===Bitmask===
===Counting===
Counting as in tabulate not as in combinatorial counting.
====Finding duplicates in an array====
If you have an array of ints where each number appears <math>n</math> times and one number appears <math>m>n</math> times where <math>gcd(n,m)==1</math>,
then you count the number of times each bit appears and take it mod <math>n</math>.<br>
The remaining bits will remain <math>m \mod n</math> times.<br>
* [https://leetcode.com/problems/single-number/ single-number]
* [https://leetcode.com/problems/single-number-ii/ single-number-ii]
* [https://leetcode.com/problems/single-number-iii/ single-number-iii]