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(): result.append(kheap.get()) return result arr =…

# Tag: data structure

## 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 represents consecutive operations: > -…

## Codeforces Problem: Azamon Web Services: Solution in Python

Problem Given two string, find if using max one swap of characters, the first string is lexicographically smaller than the other string. Solution The logic is as follows: Create an index map of each character in the string A. Compare String A & String B, character-by-character. If characters are the same, move to the next character. If char ‘c’ in…

## 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 it = hash_table.find(key); if (it…

## C++: Find Duplicates in a Positive Integers Range 1 to N

Given an array of integers where each value 1 <= x <= len(array), write a function that finds all the duplicates in the array. C++ Solution $ g++ -std=c++11 ./FindDuplicates.cc $ ./a.out 1 2 Reference https://www.byte-by-byte.com/findduplicates/

## How to Select a Random Key from a Hash Map in Constant Time?

Premise A hashmap has a time complexity of O(1) for all operations. Problem You have to find a constant time method to uniformly random selection of a key in a Hash map. Assumptions The map can grow to memory size. You can use any readymade hash map. Solution I’m discussing the pseudo code for a Python solution. All operations work…

## 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 c. A Euler walk of…

## 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 ugly to me and so…