Let’s take an array for example: int arr[] = {1,2,3,4,5,6}; The above array is sorted in increasing and non-decreasing order. Now, let’s add a few duplicates. int arr[] = {1,1,2,2,3,4,4}; The above array is not in an increasing order. But it is in non-decreasing order.
Tag: C++
Quicksort in C++
// cat quicksort.cc #include <bits/stdc++.h> #include <algorithm> // std::swap using namespace std; int partition(int arr[], int low, int high); void qsort(int arr[], int start, int end) { int p; if (start < end) { p = partition(arr, start, end); qsort(arr, start, p – 1); qsort(arr, p + 1, end); } } int partition(int arr[], int…
Basic HashMap in C++
Useful Points I use chaining for key collisions. The key is also stored with the payload. A GET operation searches the key in bucket’s linked-list and returns the value. #include<bits/stdc++.h> using namespace std; class HashNode { private: string key; string value; HashNode *next; public: HashNode(string key, string value) { this->key = key; this->value = value;…
Palindrome LinkedList Recursive
Details Send the pointer to head(phead) and head itself. Recurse till next of head is not NULL. Start popping the frames. If *phead == *head, good to move to next frame-up. Before moving up, move phead to next // Recursive function to check if linked list is palindrome or not int checkPalindrome(struct Node** left, struct…
Notes on Memory Mapped Files using mmap
Introduction mmap maps a file to a process virtual address space. The file blocks are loaded as needed, in units of the system page size. Each I/O must align with the page size. A block load is handled as a page fault. mmap() can provide a private or shared mapping of a region. mmap() to…
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…
One Way Communication with Pipe in Linux
Pipe uses kernel buffer to store data. It is a unidirectional read/write buffer and connects two processes. Each end (read or write) Pipe mimics a file operation. A process can choose to read or write (but not both). The processes have to use at least two pipes for two-way communication. Example Communication Parent process can…
How a Regex Engine Work?
A regular expression defines a set of string. A regex engine matches a pattern against input and returns true/false for the condition that pattern exists in the input. I have got a C++ implementation of a regex engine which uses simple constructs of matching the following: A single character An equal length pattern and input…
C++: Max Product in a Matrix witout Backtrack
Problem Given a matrix, find the path from top left to bottom right with the greatest product by moving only down and right. The code is in C++. The only moves allowed are down and right. The solution works for positive numbers. Reference https://www.byte-by-byte.com/matrixproduct/?utm_source=optin_carrot&utm_medium=pdf&utm_campaign=50questions Written with StackEdit.
C++: Find Longest Sequence of Numbers in An Unsorted Array
Given an unsorted array, find the length of the longest sequence of consecutive numbers in the array. $ g++ -std=c++11 ./FindLongestSequence.cc $ ./a.out 4 Reference https://www.byte-by-byte.com/consecutivearray Written with StackEdit.
