DEV Community: Yash

Skip Lists - Advanced DSA

Yash — Fri, 16 Aug 2024 21:21:04 +0000

Redis which is a popular fast in-memory database uses many optimization techniques to speed up the retrievals, one of them is the concept of using skip lists, in simple terms skip lists are augmented linked lists for faster search, as you can skip through portions of the list which don't contain the data you're looking for.

The data is stored in the form of linked lists with an additional information pertaining to an abstract concept of lanes, each node contains 3 data members: value, next and down and the data has a layer of abstraction called lanes, there are 2 types of lanes: normal lane, which is the original linked list and express lanes which are the abstractions, here is a representation:

// Image courtesy: https://www.geeksforgeeks.org/skip-list/

The code for searching in a linked list is really neat:

SkipNode* search(int key) {
    curr = head;
    while(curr != nullptr) {
        while(curr -> right != nullptr && curr -> right -> value <= key) {
            curr = curr -> right;
        }
        if(curr -> val == key) break;
        curr = curr -> down;
    }
}

Python notes/tricks/lessons/nuances

Yash — Fri, 16 Aug 2024 21:14:01 +0000

I made a C++ tricks post and I wanted to write about a lot more of tricks that I know, since most of them are in Python and JS even though I have coded in C++ a lot more but anyways here they are, I'll start with trivial things about basic Python syntax but there are some things that are not known to beginners, which I've marked with a star ⭐️:

1. Lists

An ordered collection of items data structure
Can have multiple types
aa = ["apple", 'd', 3, 9.3]

Initialization:

a = [1, 2]
a = list()
a = list([2, 3])
[0]*5
concat_list = list1 + list2

Accessing elements ⭐️

0 ... n-1 and -n ... -1

Functions

len(list1)
a.append(value)
a.insert(index, value): inserts value at index and pushes everything to the right
a.pop(): returns the end value and removes it
a.remove(value): if the value is not present you will get a ValueError
a.clear()
a.reverse(): reverses in place
a.sort(): modifies orginal
b = sorted(a): doesn't modify original

Slicing ⭐️

An easy way to access subarrays of a list

slicedList = a[1:5]: start at index 1 and stop at index 5, index 5 is excluded
slicedList = a[:3]: from 0 ... 2
slicedList = a[1:3]: from 1 to 2
slicedList = a[:]: duplicate the entire list
slicedList = myList[::2]: step index, every second item, start with first, basically i=0;i<n;i+=2
slicedList = myList[::-1]: nice way to reverse a list

Copying a list

1. Shallow copy

a = [1, 2, 3]
b = a

Modifying one also modifies the other since both are same memory allocations

2. Deep Copy ⭐️

3 ways:

b = a.copy()
b = list(a)
b = a[:]

List Comprehension

I will start off with some basic list comprehensions, but they'll quickly get less trivial.

values = [x+1 for x in range(10)] -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

- `values = [x for x in range(51) if x % 2 == 0]`

values = [word for word in values if len(word) > 1 and word[0] == 'a' and word[-1] == 'y']
# OR, a nicer way is ⭐️
values = [
    string
    for string in values
    if len(string) > 1
    if string[0] == 'a'
    if string[-1] == 'y'
]

Nested List Comprehension ⭐️

Flattening a list of lists, or a 2D matrix
Nested list comprehension: Flattening a matrix (a list of lists) ⭐️

Example: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

values = [
    number for row in matrix for number in row
]
# first for loop then the next for loop is inside the first and so on

Other list comprehensions:

values = [
    "Even" if x % 2 == 0 
    else "Odd" 
    for x in range(10)
]

This syntax ->
"Even" if x % 2 == 0 else "Odd" is valid in a lot of places in python, you can also put it in variables, this is basically a ternary operator but more verbose
⭐️ For understanding any list comprehension always look on the left and the right side of the expression, any nested loops go from left to right, when the if else is on the left of the for loop we check what value do we wanna insert depending on the if else condition, whereas when the for loop is on the right we are trying to filter from the list
For example to create a 5x5x5 list: ⭐️

values = [[[num+1 for num in range(5)] for _ in range(5)] for _ in range(5)]

⭐️ Look for the exterior most for loop, whatever is to its left will get added to the values[] array, and the meaning of this syntax: for _ in range(5) is that I want to do whatever is on the left of this for loop 5 times (because I don't care about the value of the iterator variable at each iteration)

Funtions in comprehensions:\ values = [x**2 for x in values if valid(x)]

Dictionary comprehension

If we have pairs = [("a", 1), ("b", 2)]: a list of pairs or tuples

-> my_dict = {k:v for k, v in pairs}: value unpacking, for this to work, each "pair" in pairs must have exactly 2 entities

Set comprehension

Let nums = [1, 2, 3, 1, 3, 2, 4, 2, 1, 3]

unique_nums = {x for x in nums}: python will know that this should be a set because you don't have any keys

I will write this once I get some time, but you can still check them out here: AdvancedPythonConcepts this is my git repo where I documented python concepts when I first learnt them. I will write this post based off of this repo once I get the time...

C++ nuances/tricks

Yash — Fri, 16 Aug 2024 20:31:22 +0000

This is a post I will regularly update with the nuances and tricks that I discover while solving complex DSA questions in C++.

Sets in C++:

You can refer to this code if you want to experiment with the functions listed below: code
Let's say you have a set<int> nums;, then:

1. To get the edge elements you can do:

int first = *nums.begin();
int last = *(--(nums.end()));
// OR    
first = *(--(nums.rend()));
last = *nums.rbegin();

⭐️ so basically try to not use end() and rend() as they are a bit tricky and there are simpler alternatives:

❗️ Note that rbegin() and rend() are reverse iterators so to get the second last element using rbegin() what do you think we will do?

-> The answer is: int secondLast = *(++(nums.rbegin()));

❗️ Also remember that rend() and end() don't give iterators pointing to elements, rather they return the pointer of one past the first or the last, i.e, nums.end() will give iterator pointing to the address after the last element which is not dereference-able similarly nums.rend() will give the iterator of the location one before the first element so be careful of how you use them otherwise it will result in memory segmentation errors.

Also one final note about edge operators:
You can also use constant operators if your functionality requires, to write more predictable and debuggable code:

auto FIRST_ITR = nums.cbegin();
auto LAST_ITR = nums.cend();
auto FIRST_REV_ITR = nums.crbegin();
auto LAST_REV_ITR = nums.crend();

2. Different ways to erase elements:

There are 3 methods:

nums.erase(iterator)

⭐️ If you want to remove the 4th element in the set you cannot do:
nums.erase(((nums.begin())+4));
because while sets are ordered containers they don't allow random access like vectors so you must iterate with the iterator one at a time like so:

auto it = nums.begin();
int x = 4;
while(x--) it++;
nums.erase(it);

nums.erase(value) - straightforward, just removes the value from the set if present.
nums.erase(iterator1, iterator2) - useful, removes elements in the range [iterator1, iterator2) ❗️ note the closed-open interval

3. Trivial but useful functions:

find()
lower_bound(x) - Returns an iterator pointing to the first element not less than the given value.
upper_bound(x) - Returns an iterator pointing to the first element greater than the given value.
equal_range(x) - Basically returns a pair of iterators equivalent to make_pair(nums.lower_bound(x), nums.upper_bound(x))
empty()
size()

4. Hidden but awesome functions:

emplace(): an interesting function to say the least:
- consider this code:

set<pair<int, int>>s;
s.insert({1, 2});
// or
s.insert(make_pair(1, 2));
// but with emplace you can do:
s.emplace(1, 2);  // because emplace creates the object in the set directly so it will just pass 1, 2 to the container's element's constructor which is pair<int, int> here.
// or
s.emplace(make_pair(1, 2));
// but not using list initializer like s.emplace({1, 2)) ❌ because emplace() doesn't automatically deduce that {1, 2} should be converted to a pair<int, int>, so instead you'll have to do:
s.emplace(pair<int, int>{1, 2});
// anyways its better to just stick to make_pair() or direct args passing in .emplace() rather than relying on implicit template deduction

benefit of using .emplace() over .insert() as they both provide the same utility is the performance difference of the two methods, insert(x) will create x then transfer it to the set in memory, emplace(x) will directly create x in the set's internal memory saving transfer/copy cost. this is a negligible advantage for simple objects but for more complicated objects it can be a key optimization.
- swap() - Exchanges the contents of two sets. This is a fast operation because it swaps pointers and size metadata rather than copying the elements.
- merge(anotherSet) - Transfers all elements from anotherSet into the set which are not present in destination set, removing duplicates.

    std::set<int> set1 = {1, 3, 5, 7, 9};
    std::set<int> set2 = {2, 4, 6, 8, 10, 5};

    // Merge set2 into set1
    set1.merge(set2);

    // Now set2 has one element 5 and set1 contains the union of both.

comparison operators - surprisingly you can compare sets in C++ accordign to their lexicographical order, for example:

    set<int> set1 = {1, 3, 5};
    set<int> set2 = {1, 3, 5};
    set<int> set3 = {1, 2, 6};
    set<int> set4 = {1, 3, 4, 7};

    // Compare set1 and set2
    if (set1 == set2) {
        cout << "set1 is equal to set2" << endl;
    }

    // Compare set1 and set3
    if (set1 < set3) {
        cout << "set1 is less than set3" << endl;
    }

    // Compare set1 and set4
    if (set1 < set4) {
        cout << "set1 is less than set4" << endl;
    }

    // output: set1 is equal to set2

Custom set - When constructing a set, you can provide a custom comparator to change the default ordering of the elements.

struct ReverseComparator {
    bool operator()(const int& lhs, const int& rhs) const {
        return lhs > rhs; // Reverse order
    }
};

std::set<int, ReverseComparator> mySet;

Sneaky optimization while iterating through containers

Let's say you have a map<string, set<int>> mapper structure, there are two optimizations you should know if you want iterate over them in the most efficient way possible:

for(auto &z : mapper) {             // use &z instead of z
    set<int> &values = z.second;    // same here, reference the value instead of copying it anew
}

This might seem trivial but many people make this mistake and get TLE as I have seen in many editorials, so I thought should address it.

Object Destructuring in pair

Similar to Python and JS object and array destructuring you can do the following in c++:

    queue<pair<int, vector<int>>> q;
    q.push({INT_MAX, {1, 2}});

    auto [x, y] = q.front();        // works
//  auto [x, &y] = q.front();       // doesn't work

    auto &v = q.front().second;     // do this instead for initialization via reference

Because, when you use structured bindings like auto [x, y], you are effectively unpacking the members of a tuple-like object (like std::pair, std::tuple, etc.) into separate variables. This syntax is intended for value bindings, meaning it creates new variables (x and y) that are copies of the values from the tuple (or pair) being unpacked. So it works well with primitive types but when copying entire objects it could be the cause of TLE.

String caution

In c++, you should avoid adding characters to string literals directly as it leads to pointer arithmetic instead of string concatenation. For example:

    string str = "";
    str += "abc" + 'd';    // Runtime Error
    cout << str << '\n';

because, when you do "abc" + 'd', the expression "abc" is treated as a pointer, and 'd' (which is an integer in this context, representing the ASCII value of 'd') is added to the pointer. This results in pointer arithmetic, not string concatenation, which throws an out of bounds exception.

Observe the below example:

    string str = "";
    str += "abcdefg" + 2;
    cout << str << '\n';
    // Output: cdefg

Lambda functions

If you are familiar with Lambda functions in Python (or JS) you know how awesome they can be, I use them excessively in Python, so I thought I should explore them in C++, so here goes:
Basic syntax is:
[capture list](parameters) -> return type { body }

// This is not complete yet, I will write once I find the time...

Design a stack that supports getMin() in O(1) time and O(1) extra space

Yash — Fri, 16 Aug 2024 15:28:47 +0000

I came across this interview question the other day, and when I saw the solution, I learned something new. I decided to share it for anyone interested. The task is to design a variation of the stack data structure but with the additional functionality of fetching the current minimum element in the stack without using more than constant extra space. Try to work it out on your own; I will lay out one of the solutions that I found. If your solution is something else, I would love to know it. Anyway, here it is:

The Idea

Whenever there is a new minimum pushed to the stack, use the old minimum in a way to relate to the new minimum while simultaneously being able to regenerate the old minimum. Here is a clearer representation:

Maintain one extra variable associated with the stack, let it be minEle.

Push(int x):

Case 1: If the stack is empty, insert x and set minEle = x.
Case 2: If x >= minEle, simply push x.
Case 3: If x < minEle (when x is the new minimum), push 2*x - minEle. This is because 2*x - previous_minEle < x is always true. Then, set minEle = x.

Pop():

Case 1: If stk.top() >= minEle, just pop the topmost element.
Case 2: If stk.top() < minEle, then we know that this is actually 2*minEle - previous_minEle. Since we know minEle, we can find the previous minEle, update minEle, and then pop the top element.

I have written an implementation in C++ using an object-oriented approach here: MinStack.cpp.

Here is a sample test run: