development

K-Messed Array Sort: Python Solution

K-Messed Array Sort Given an array of integers arr where each element is at most k places away from its sorted position Solution from Queue import PriorityQueue def sort_k_messed_array(arr, k): kheap = PriorityQueue() result = [] for num in arr: kheap.put(num, ‘num’) if kheap.qsize() == (k + 1): item = kheap.get() result.append(item) while not kheap.empty(): […]

Read more
development

Codility: Maxed Counters Problem

Problem You are given N counters, initially set to 0, and you have two possible operations on them: > – _increase(X)_ − counter X is increased by 1, > – _max counter_ − all counters are set to the maximum value of any counter. A non-empty array A of M integers is given. This array […]

Read more
development

SIngle Thread LRUCache in C++

#include <iostream> #include <list> #include <unordered_map> using namespace std; size_t capacity; class LRUCache { public: bool Lookup(int key, int *price) { auto it = hash_table.find(key); if (it == hash_table.end()) { return false; } *price = it->second.second; // update the key in the queue MoveToFront(key, it); return true; } void Insert(int key, int price) { auto […]

Read more
data structure, development

Euler Traversal & LCA in a Tree

Euler Traversal Start as ROOT –> Subtree-1 –> ROOT –> Subtree-2 –> ROOT –> Subtree-3 –> ROOT Recurse at each subtree as above All nodes of a subtree appear together, contiguously in the traversal. Why Euler Traversal Gets LCA? Assume we want LCA of a node u in subtree a and node v in subtree […]

Read more
development

Headless link list implementation in C

Singly link list A link list is a non-linear data structure with a head pointer. The rest of the nodes in the list could be accessed by using “next” of head. The code to create a list of N node involves creating head separately. Rest of the nodes are appended to the head. That looked […]

Read more