# 🐍 🐍 🐍 & C++

## python thingz
cos python is special

### Arithmetic operation on strings
`'a' * 5 -> 'aaaaa'`

### Copying list

a = [1,2,3]
b = a[:] or [x for x in a]

### Sorting
sort() -> mutate original list

a = [(4,a), (1,b), (3,z)]
a.sort(key=lambda x:x[1], reverse=True) # sort by descending alphabet

sorted() -> does not mutate original list, returns a sorted list

b = sorted(a, key=lambda x:x[0], reverse=True) # sort by descending number

### Advance List/Array

A = [1,2,3]
B = [4,5,6]
C = [7,8]
A += B       # A = [1,2,3,4,5,6] concatenation can use +=
A.extend(C)  # mutates A to become [1,2,3,4,5,6,7,8]

Good practice when looping tuples with irrelevant data

A = [(1,a,b), (5,c,d), (10,e,f)]

for x,_,_ in A:     # only the number is relevant for this algo
    ...

Enumerate pls, it makes looping cleaner when you need both the index and the value of an element in a list

Without enumerate:

def lcs(a, b):
    lengths = [[0 for j in range(len(b) + 1)]
                for i in range(len(a) + 1)]

    for i in range(len(a)):
        for j in range(len(b)):
            if a[i] == b[j]:
                lengths[i + 1][j + 1] = lengths[i][j] + 1
            ...

With enumerate:

def lcs(a, b):
    lengths = [[0 for j in range(len(b) + 1)]
                for i in range(len(a) + 1)]

    for i, x in enumerate(a):
        for j, y in enumerate(b):
            if x == y:
                lengths[i + 1][j + 1] = lengths[i][j] + 1
            ...

Matrix creation

dp = [[0 for j in range(10)] for i in range(20)]   # 20x10 matrix

### Generator and Yield
https://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do

### char-int conversion

ord('A') -> 65
chr(90) -> 'Z'

### base-x int conversion

int('1111', 2) # 15

### Smart debugging

var1 = 100
var2 = [1,2,3]
print(f"{var1=} {var2=}") #outputs var1=100 var2=[1,2,3]

### Useful libraries
Good stuff! makes your life and interviewer's life easier

#### collections
- Counter
- defaultdict (very useful for graph problem)

#### queue
- heapq
- PriorityQueue

#### dateutil.parser
- parse -> returns datetime object (can do datetime arithmetically)

#### concurrent
- ThreadPool

#### time
- sleep

#### others
- threading

x = threading.Thread(target=fn, args=(a,))

args param must contain a tuple, to create a single-element tuple is exactly like (elem,)

#### functools
- lru_cache

#### itertools
- permutation
- combination

#### math
- factorial
- pow

### OOP
#### `@classmethod` vs `@staticmethod`
- `classmethod`: the class of the object is implicitly passed as the first argument instead of `self`. When we define something to be classmethod, it is probably because we want to call the method from the class.
- `staticmethod`: neither `self` (object instance) nor `cls` (class) is implictly passed as the first argument. They behave like plain functions except that you can call them from an instance or the class.

class A: 
    _counter = 0
    
    @classmethod
    def class_foo(cls, x): 
        print(f'Executing class_foo({cls}, {x}')
    
    
    @staticmethod
    def static_foo(x): 
        print(f'Executing class_foo({x}')

a = A()

# classmethod 
a.class_foo(1) # executing class_foo(<class '__main__.A'>, 1)
A.class_foo(1) # executing class_foo(<class '__main__.A'>, 1)

# staticmethod
a.static_foo(1) # executing static_foo(1)
A.static_foo('hi') # executing static_foo(hi)

#### `@staticmethod` vs plain outside-of-class function
- Static method is an organization/stylistic feature. Sometimes a module have many classes, and some helper functions are logically tied to a given class and not to the others, so it makes sense not to pollute the module with many free functions. It is better to use a static method than relying on the ppor style of mixing classes and function defs together in code just to show they are related.

Reference on static and class method: https://stackoverflow.com/q/136097

### Python OOP (compared to Java)

#### creating class instance

Java needs to declare the class variables outside of the constructor method

Python don't need

Immediately use self.x to create object attribute x

#### class level attributes

Java uses keyword static

Python is like this

class Car:
  wheels = 5
  def __init__(self):
    self.wheels = wheels
  
car = Car()
car.Car.wheels = 3 #mutate the class-level wheels
car.wheels = 5 #mutate the object's wheels

#### public vs private

All attributes in python are public

Make use of `_` and`__` to conceal attributes

`_attribute` technically still accessible - e.g, `object._attribute`, but VSCode with PEP8 plugin would throw warning

`__attribute` would not be accessible through `object.__attribute`. The `__` prefix would rename the attribute and technically could stil be accessed by determined developer - `object._Object__attribute`

setters and getters is the convention for Java, but not for python, everything is public yo

#### Methods & Functions
Python has functions, Java don't. That's it.

Every functions in Java have to be contained in a class. But, it can be static so that it can be called without instance.

#### Inheritance
Java single inheritance, Python multiple inheritance

class Device
class Vehicle

class Car(Device, Vehicle):
  def __init__(sef):
    # init the subclasses first
    Device.__init__() 
    Vehicle.__ini__()
    
    # only then create Car specific attributes
    self.year = ...

`Car` would have all the attributes and methods from `Device` and `Vehicle`

#### Types and Polymorphism

Java strict typing gives rise to inheritance to accomodate polymorphism

Python has duck typing. If it walk like duck, quacks like a duck, it's a duck. https://realpython.com/python-type-checking/

Java static typing, Python dynamic typing (it checks as the code execute)

#### Default Methods

All classes in Java inherit the methods from `Object`

In Python, each class also has default methods - `dunder` (double underscore) methods

.hashCode() -> __repr__()
.toString() -> __str__()
.equal() -> __eq__()

print(repr(my_car)) -> hashcode
print(str(my_car)) -> "Honda 2000"
...

Java needs `@Override`, python does not.

Additional `dunder` methods

def __eq__(self, other)
def __lt__(self, other)
def __add__(self, other):
  return Car(self.price + other.price)

### Pytest
Allows use of idiomatic python constructs without biolerplate code.

## C++ Data Structures & Algorithms
- `stack<T>`
- `queue<T>`
- `priority_queue<T>` -- there is also another signature that you can define your own order
- `deque<T>`
- `vector<T>`
- `pair<T, R>`
- `tuple<T, R, ...>`
- `map<T, R>` -- RB-Tree, O(log n) access, able to access the (key, value) pair in sorted order (sorted by key)
- `unordered_map<T, R>` -- Hashing, access & insert average O(1), worst O(n), unable to access in sorted order
- `set<T>` -- RB-Tree, O(log n) insert & access
- `unordered_set<T>` -- Hashing (not sure), access & insert average O(1), worst O(n).
- `multiset<T>` -- Able to store multiple elements
- `sort(start, end, [cmp])`
- `unique(start, end)` -- Reorder the elements inside an array / vector such that repeating elements are put at the back. Returns the pointer of first element that is repeated
- `reverse(start, end)`
- `erase(start, end)`

Note: always best to consult with the C++ reference. The list is not exhaustive, so it is also best to be complemented with googling some tips and tricks.

// Example:
stack<int> st;
st.push(1); st.push(2);
printf("%d\n", st.top()) // returns 2
st.pop();
printf("%d\n", st.top()) // returns 1



// Here, v = {3, 3, 5, 7, 10}
// `auto` will automatically infer the type of variable `k`.
// Also possible to use `int` instead of `auto`.
for (auto &k : v) {
    printf("%d\n", k); // Will output the whole element of vector v.
}

// unique(v.begin(), v.end()) will change the content of v
// into {3, 5, 7, 10, 3}
//                    ^ pointer returned by unique

// This basically means to take all unique elements inside
// vector `v`.
v.erase(unique(v.begin(), v.end()), v.end());

// v = {3, 5, 7, 10}

multiset<int> ms;
ms.insert(1);
ms.insert(1);
ms.insert(-1);

printf("%d\n", (int) ms.count(1)); // Outputs 2

// Erase **ALL** occurences of `1`
ms.erase(1);

printf("%d\n", (int) ms.count(1)); // Outputs 0

/*
 * If you only want to delete only an element, you can
 * play around with pointers.
 *
 * Example: ms.erase(ms.find(1));
 * 
 * That will only remove the element pointed out by the
 * pointer returned by `ms.find(1)`.
 */

### C++ thingz

#### Dijkstra

// Getting the matrix size
int m = M.size(), n = m ? board[0].size() : 0;

// Defining the 4 directions
static constexpr int DIRS[][2] {{0,1},{1,0},{0,-1},{-1,0}};
for(const auto& d : DIRS) {}

// PriorityQueue parts
priority_queue<tuple<int,int,int>> pq;
pq.emplace(A[0][0], 0, 0);
pq.top()
pq.pop()
pq.empty()

// Lazy to think of the type
auto [a,b,c] = pq.top()
auto i = 0

// Queue
queue<pair<int, int>> q;
q.push({ 0, 0 });
auto c = q.front();
q.pop();

### GCD, MIN, MAX

int min = *min_element(begin(nums), end(nums));
int max = *max_element(begin(nums), end(nums));

// begin() function is used to return an iterator pointing to the first element of the vector container
// end() function is used to return an iterator pointing to next to last element of the vector container

__gcd(a,b) // built-in C++ GCD method

### Binary/string/int conversion

// binary to int
stoi(bin_string, 0, 2) // base 2, default is 10

// int to binary
bitset<n>(num) 
// limitations: n is a constant, will be checked during compile time
// it will return binary representation of length n
// alternatively, do manually using mod + bitshift + reverse

// int to string
string x = to_string(num);
int x = stoi(string)

### Strings & char

combining string

string base = "";
for (string word: words) {
     base += word
}

single quote -> `char`
double quote -> `string`

Iterating string

for (char c: s){}
// creates copy of s and store it in c, modifying c won't modify s

for (char& c : s) {}
// directly references and stores it in c as an alias. Modifying c does modify s

for (const char& c: s) {}
// if you don't want to accidentally modify s, use const

front and back

string a = "abc";
cout << a.back();     // "c"
cout << a.front();    // "a"

char & int, typecast is unnecessary for declaration. But if you want to do arithmetic operation, it has to be typecasted into the same type.

char a = 97;      // 'a'
int b = 'a';      // 97

well, sadly there is no `s.split(" ")` or `" ".join(words)` like in python
below is the pre-made split and join, just copy paste it to the coding assessment

vector<string> split(string s, char delimiter) {
    vector<string> strings;
    string soFar;
    for (char& c : s) {
        if (c == delimiter) {
            strings.push_back(soFar);
            soFar = "";
        } else {
            soFar += c;
        }
    }
    strings.push_back(soFar);
    return strings;
}

string join(vector<string> strings, char delimiter) {
    string res = "";
    for (int i = 0; i < strings.size()-1; i++) {
        res += strings[i];
        res += delimiter;
    }
    res += strings.back();
    return res;
}

here's a very clean example of problem that involves a lot of string manipulation

useful:
`word.substr()`
`stringstream`
`joining strings routine`

string sortSentence(string s) 
{
    stringstream words(s); 
    string word;
    pair<int, string> m;
    vector<pair<int, string> > sent;

    //SECTION 1
    while(words>>word)
    {
        int len = word.size();
        int i = int(word[len-1]) - 48;
        sent.push_back(make_pair(i, word.substr(0, len-1)));
    }

    //SECTION 2
    sort(sent.begin(), sent.end());

    //SECTION 3
    string ans = "";
    int len = sent.size();
    for(int i=0; i<len; i++)
    {
        ans += sent[i].second;
        if(i!= len-1)
            ans += " ";
    }

    return ans;
}

### Trie
https://github.com/stevenhalim/cpbook-code/blob/master/ch6/Trie.cpp

### DP

For fixed matrix sizes, better use fixed array instead of Vector

int dp[71][70 * 70 + 1] = {[0 ... 70][0 ... 70 * 70] = INT_MAX};
// ... for range initializer to certain value (inclusive range)
// dp[71][70 * 70 + 1] is the array size

So what if we do not know the size of the array?

int* dp = new int[n];
delete[] dp;
dp = NULL // prevent dangling pointer

What about dynamic multidimensional array of size mxn?

int** dp = new int*[m];
for (int i = 0; i < m; i++)
    dp[i] = new int[n];
    
// cleanup
for (int i = 0; i < m; i++)
    delete[] dp[i];
delete[] dp;
dp = NULL // prevent dangling pointer

infinite values

float('inf') -> INT_MAX

### Smart Pointers

Why? Because it deallocates itself

#include <memory>

unique_ptr<int> unPtr = make_unique<int>(25);
unique_ptr<int> unPtr2 = move(unPtr); // unPtr = NULL;
shared_ptr<int> shPtr = make_shared<int>(25);
shared_ptr<int> shPtr2 = shPtr; // shPtr.use_count() = 2 
weak_ptr<int> wePtr;

### Function Pointers
Why? So that we can pass functions as arguments to other functions e.g., custom comparator

bool compare(int a, int b) return a < b;
bool(*fnPtr)(int, int) = compare; 
fnPtr(5, 7) // invoke normally

### Set

// Initializing from a vector
vector<vector<int>> mat;
vector<set<int>> m;
for (auto &row : mat) {
    m.push_back(set<int>(begin(row), end(row)));
}

### Iterator

vector<int> m;
for (auto it = begin(m); it != end(m); it++) {
    cout << *it // dereference, iterator is a pointer
}

Iterating through vector vs array

for(const string &text : texts) // vector & array
for(int i = 0; i < n; i++) // vector & array if you know n

for(unsigned int a = 0; a < sizeof(texts)/sizeof(texts[0]); a = a + 1 ) // array
for(unsigned int i = 0; i < texts.size(); i++) // vector

### Lambda

[](){}

// [] -> allows access to variables outside the lambda body
// () -> parameters
// {} -> function body

auto comparator = [](const auto& node1, const auto& node2) {
    return node1.val < node2.val;
}

### R-Value vs L-Value

int pow2(int&& x) {
    ...
}

// && is only used for function parameters
// it means the function can only take r-value

int x = 2           // x is l-value
int z = x + 2       // x + 2 is r-value
pow2(z)             // error
pow2(z+2)           // valid

so the question is, when to use && in a function? when is it useful?

### PriorityQueue
It's max-heap by default, min-heap needs extra parameter

priority_queue<int> p1; // max-heap
priority_queue <int, vector<int>, greater<int> > p1; // min-heap

To make a custom element & comparator

priority_queue<tuple<int,int,int>> pq; // max-heap
priority_queue<tuple<int,int>, vector<tuple<int,int>>, greater<tuple<int,int>>> pq; // min-heap

pq.emplace(1,2,3);
auto [a,b,c] = pq.top();

PriorityQueue can contain any elemnt type, just need to create the custom comparator

priority_queue<ListNode*, vector<ListNode*>, compare> minheap;

struct compare {
    bool operator()(const ListNode* a, const ListNode* b) {
        return a->val < b->val;
    }
};

Tuple is like an unnamed struct, can also be used for typedef

typedef tuple<int, int, int> Triplet;
priority_queue<Triplet> pq;
priority_queue<Triplet, vector<Triplet>, greater<Triplet>> pq;

### map, unordered_map, set, unordered_set

map<string, int> mp;

mp["qwerty"] = 10;
mp["ponder"] = 11;

for (auto &k : mp) {
    // k = pair(key, value);
    cout << k.first << " " << k.second << "\n";
    
    // will be output in sorted order of key
}

// initializing multiple things at once
unordered_map<char, int> T = { { 'I' , 1 },
                               { 'V' , 5 },
                               { 'X' , 10 },
                               { 'L' , 50 },
                               { 'C' , 100 },
                               { 'D' , 500 },
                               { 'M' , 1000 } };

set<int> s;
s.insert(1);
s.insert(1);
s.insert(-1);

printf("%d\n", (int) s.count(1)); // Outputs 1

for (auto &k : s) {
    printf("%d\n", k); // Will output all elements in the set in order
}

s.erase(1); // Erases 1

### Stack

this is work of art lol. Stack in c++ is strictly a stack and doesn't work like a vector, it doesn't have random access using index, only the top element is available.

There is switch case! switch case in c++ is fallthrough and requires a `break`.

bool isValid(string s) {
    stack<char> paren;
    for (char& c : s) {
        switch (c) {
            case '(': 
            case '{': 
            case '[': paren.push(c); break;
            case ')': if (paren.empty() || paren.top()!='(') return false; else paren.pop(); break;
            case '}': if (paren.empty() || paren.top()!='{') return false; else paren.pop(); break;
            case ']': if (paren.empty() || paren.top()!='[') return false; else paren.pop(); break;
            default: ; // pass
        }
    }
    return paren.empty() ;
}

### Iterator & Sorting

Iterator

vector<int> v = {3, 10, 5, 7, 3};
sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<int>()); // to sort descendingly
sort(next(v.begin(), 1), prev(v.end(), 1)) // sort subarray -> {3, 5, 7, 10, 3}

Sorting vector of vectors

// sort based on the third element in the vector
sort(logs.begin(), logs.end(), 
        [](const vector<int>& a, const vector<int>& b) {
            return a[2] < b[2];});
            
// without specification, it will sort the vector lexicographically

### LinkedList

for dummy nodes initialization, don't use pointer

ListNode dummy;
ListNode* node = &dummy;p
...
...
return dummy.next;

### Threading

void print(int n, string name) {cout << n << " " <<  name << "\n";}

int main() {
  vector<thread> threads;
  vector<string> names = {"a", "b", "c", "d"};

  for (int i = 0; i < names.size(); i++)
    threads.push_back(thread(print, i, names[i]));

  for (auto& t: threads)
    t.join();

### Sleep

#include <unistd.h>
usleep(n) // n here is in microseconds

### Regex

string str = "the ape was at the apex";
regex reg ("(ape[^ ]?)");
sregex_iterator currentMatch(str.begin(), str.end(), reg);
sregex_iterator lastMatch;
while (currentMatch != lastMatch) {
    smatch match = *currentMatch;
    cout << match.str() << "\n";
    currentMatch++;
}

### Unordered_map vs map
`unordered_map` uses hashmap
`map` uses self-balancing BST

which means, `unordered_map` cannot take a `pair<int, int>` as key, whereas map can, because `map` uses < comparison to build the data structure.

`pair<int, int>` does not have a default hash function, we need to define it and pass the function as third parameter

#include <boost/functional/hash.hpp>

struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        size_t seed = 0;
        boost::combine(seed, p.first);
        boost::combine(seed, p.second);
        return seed;
    }
}

but alternatively, you can just do away with nested `unordered_map<int, unordered_map<int, int>>`

### Long Long

typedef long long ll;

// working with accumulate need 3rd parameter 0ll
ll top = accumulate(begin(g[0]), end(g[0]), 0ll), bottom = 0;

// INT_MAX for long long
ll res = LLONG_MAX;

### Chrono - datetime util

### Random

int n = rand() % (hi - lo) + lo  // [lo, hi)

### Writing and Reading files

#include <fstream>
fstream myFile;
myFile.open("ted.txt", ios::out) // out -> write, app -> append, in -> read
myFile << "hello world";

// for reading
string line;
while (getline(myFile, line)) {}

myFile.close() // dont forget to close!

### abs vs labs vs llabs vs fabs
The difference is the input and output types

int abs(T x); // where T can be int, long long, etc
ll llabs(ll x); //where ll is long long
U fabs(U x); // where U is double / float

### Know your <algorithm> !!

// A is a vector, B is an array
all_of    	(A.begin(), A.end(), [](int i){return i%2 == 0;})
any_of    	(...)
find      	(A.begin(), A.end(), 5)
equal     	(A.begin(), A.end(), B)
search    	(A.begin(), A.end(), B, B+2)
count     	(A.begin(), A.end(), 5)
replace   	(A.begin(), A.end(), 20, 99) //replace 20 -> 99
shuffle   	(A.begin(), A.end(), default_random_engine(seed))
sort        (A.begin(), A.end(), Comp)
stable_sort (A.begin(), A.end(), Comp)
is_sorted   (A.begin(), A.end(), Comp)