Tutor profile: Santhosh K.

What is the difference between mutex and semaphores?

Mutex and Semaphores are both primitives that allow for synchronization. While there is some similarity between them, they are used for different purposes. Mutex (mutual exclusion object) is a locking mechanism for synchronizing access to shared a resource. At any given point in time, only one thread is allowed to acquire the lock, execute the critical section code, and release the lock. In particular, the thread that acquired the lock has to be the one to release it as well. Semaphores on the other hand are signalling mechanism. They offer wait and signal mechanisms that allow an internal counter to increase or decrease. Threads waiting on a semaphore are allowed to continue as and when the counter becomes positive (i.e, when other threads call the signal operation). Binary semaphores are a specific case where the counter can only be 0 or 1. However, unlike with mutex, semaphores don't require that the thread that calls the wait has to be the one to call the signal again.

Solve the following initial value problem $$\frac{dy}{dx} = y^2 + 1$$ $$y(1) = 0$$

$$\frac{dy}{dx} = y^2 + 1$$ $$\frac{dy}{y^2 + 1} = dx$$ integrating on both sides, $$tan^{-1}y = x + C$$ $$y = tan(x + C)$$ given $$y(1) = 0$$ $$\implies tan(1+C) = 0$$ $$\implies 1+C = k\pi,\;for\;k=\dots,-2,-1,0,1,2,\dots$$ $$\implies y = tan(x-1)$$

Design a data structure to store and retrieve counts of strings, with the ability to return the strings with minimum and maximum counts. All operations should have time complexity O(1) in number of strings.

// in order to support the increment and decrement operations in order O(1), we use a hash map (unordered_set) to store the strings as keys // in order to get the max and min frequency strings in order O(1) time, we maintain a sorted linked list of structure bucket, where each bucket corresponds to a frequency, and stores the strings with that frequency. // the values in the hash map for each string correspond to its iterator location in the list of buckets class Solution { private: struct Bucket { int value; unordered_set<string> keys; }; list<Bucket> buckets; unordered_map<string, list<Bucket>::iterator> bucketOfKey; public: void increment (const string &key) { // If the key doesn't exist, insert it with value 0 before incrementing it. if (bucketOfKey.count(key) == 0) bucketOfKey[key] = buckets.insert(buckets.begin(), {0, {key}}); // Insert the key in next bucket and update the lookup. auto bucket = bucketOfKey[key]; auto next = bucketOfKey[key]; next++; if (next == buckets.end() || next->value > bucket->value + 1) { // have to create new bucket next = buckets.insert(next, {bucket->value + 1, {}}); } next->keys.insert(key); bucketOfKey[key] = next; // Remove the key from its old bucket. bucket->keys.erase(key); if (bucket->keys.empty()) buckets.erase(bucket); } void dec(const string &key) { // If the key doesn't exist, just leave. if (!bucketOfKey.count(key)) return; // Maybe insert the key in previous bucket and update the lookup. auto bucket = bucketOfKey[key]; auto prev = bucketOfKey[key]; prev--; bucketOfKey.erase(key); if (bucket->value > 1) { if (bucket == buckets.begin() || prev->value < bucket->value - 1) prev = buckets.insert(bucket, {bucket->value - 1, {}}); prev->keys.insert(key); bucketOfKey[key] = prev; } // Remove the key from its old bucket. bucket->keys.erase(key); if (bucket->keys.empty()) buckets.erase(bucket); } string getMaxKey() { return buckets.empty() ? "" : *(buckets.rbegin()->keys.begin()); } string getMinKey() { return buckets.empty() ? "" : *(buckets.begin()->keys.begin()); } };