🐍 🐍 🐍 & 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)