igvedmak
BAN USER#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
std::vector<int> getRandomSublist(const std::vector<int>& L, int N) {
std::vector<int> sublist;
int remainingElements = N;
int availableChoices = L.size();
for (size_t i = 0; i < L.size() && remainingElements > 0; ++i) {
int randChoice = rand() % availableChoices;
if (randChoice < remainingElements) {
sublist.push_back(L[i]);
--remainingElements;
}
--availableChoices;
}
return sublist;
}
int main() {
srand(time(0)); // Seed for random number generation
std::vector<int> L = {1, 2, 3, 4, 5};
int N = 3;
auto sublist = getRandomSublist(L, N);
std::cout << "Random sublist of size " << N << ": [";
for (size_t i = 0; i < sublist.size(); ++i) {
std::cout << sublist[i];
if (i < sublist.size() - 1) std::cout << ", ";
}
std::cout << "]" << std::endl;
return 0;
}
#include <iostream>
#include <vector>
int countSubarraysLessThanK(const std::vector<int>& nums, int K) {
int count = 0, start = 0;
for (size_t end = 0; end < nums.size(); ++end) {
// If the current element is valid, extend the window to the right.
if (nums[end] < K) {
// The number of subarrays ending with nums[end] is (end - start + 1)
count += end - start + 1;
} else {
// If the current element is not valid, move start to end + 1
start = end + 1;
}
}
return count;
}
int main() {
std::vector<int> nums = {1, 11, 2, 3, 15};
int K = 10;
std::cout << "Number of subarrays where all elements are less than " << K << ": "
<< countSubarraysLessThanK(nums, K) << std::endl;
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
std::pair<int, int> findMaxConsecutiveOnes(const std::vector<int>& nums, int k) {
int start = 0, end = 0, zeroCount = 0, maxLen = 0, flipIndex = 0;
int leftIndexForMaxLen = 0; // To remember where the maxLen sequence starts.
for (; end < (int)nums.size(); ++end) {
if (nums[end] == 0) {
++zeroCount;
}
// If we have more than k zeros in the window, shrink it from the left
while (zeroCount > k) {
if (nums[start] == 0) {
--zeroCount;
}
++start;
}
// Update maxLen and the starting index of maxLen
if (end - start + 1 > maxLen) {
maxLen = end - start + 1;
leftIndexForMaxLen = start;
}
}
// Find the index to flip. It's the leftmost 0 in the max sequence.
for (int i = leftIndexForMaxLen; i < leftIndexForMaxLen + maxLen; ++i) {
if (nums[i] == 0) {
flipIndex = i;
break; // We just need the first one to maximize the sequence.
}
}
return {flipIndex, maxLen};
}
int main() {
std::vector<int> nums = {1, 1, 1, 0, 1, 0, 0, 1};
int k = 2;
auto result = findMaxConsecutiveOnes(nums, k);
std::cout << "Flip index for maximizing consecutive 1s: " << result.first
<< "\nAfter flipping, maximum consecutive 1s: " << result.second << std::endl;
return 0;
}
#include <iostream>
#include <string>
std::string formatNumberWithCommas(const std::string& number) {
std::string formattedNumber{};
int count = 0;
const int Len = number.length();
// Iterate from the end of the string
for (int i = Len - 1; i >= 0; --i) {
formattedNumber = number[i] + formattedNumber;
++count;
// Insert a comma every three digits, except at the beginning
if (count % 3 == 0 && i != 0) {
formattedNumber = "," + formattedNumber;
}
}
return formattedNumber;
}
int main() {
std::string number = "1010503";
std::cout << formatNumberWithCommas(number) << std::endl; // Output: 1,010,503
return 0;
}
#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#include <algorithm>
class SqrtDecomposition {
public:
SqrtDecomposition(const std::vector<int>& array) {
n = array.size();
blockSize = std::sqrt(n);
blocks = std::vector<int>((n + blockSize - 1) / blockSize, std::numeric_limits<int>::min());
for (int i = 0; i < n; ++i) {
blocks[i / blockSize] = std::max(blocks[i / blockSize], array[i]);
}
this->array = array;
}
int query(int L, int R) {
int maxVal = std::numeric_limits<int>::min();
while (L % blockSize != 0 && L <= R) {
maxVal = std::max(maxVal, array[L++]);
}
while (L + blockSize <= R) {
maxVal = std::max(maxVal, blocks[L / blockSize]);
L += blockSize;
}
while (L <= R) {
maxVal = std::max(maxVal, array[L++]);
}
return maxVal;
}
private:
std::vector<int> blocks;
std::vector<int> array;
int n;
int blockSize;
};
int main() {
std::vector<int> nums = {1, 5, 4, 3, 6, 7, 2};
SqrtDecomposition sd(nums);
// Example queries
std::cout << "Max between [1, 3]: " << sd.query(1, 3) << std::endl;
std::cout << "Max between [0, 6]: " << sd.query(0, 6) << std::endl;
std::cout << "Max between [4, 5]: " << sd.query(4, 5) << std::endl;
return 0;
}
#include <iostream>
#include <vector>
#include <stack>
#include <utility>
// Utility function to find the next greater element positions for each element
void findNextGreaterElements(const std::vector<int>& nums, std::vector<int>& left, std::vector<int>& right) {
int n = nums.size();
std::stack<int> s; // Stack to store indices
// Find next greater element positions on the right
for (int i = 0; i < n; ++i) {
while (!s.empty() && nums[s.top()] < nums[i]) {
right[s.top()] = i;
s.pop();
}
s.push(i);
}
// Clear the stack to reuse it
while (!s.empty()) s.pop();
// Find next greater element positions on the left
for (int i = n - 1; i >= 0; --i) {
while (!s.empty() && nums[s.top()] < nums[i]) {
left[s.top()] = i;
s.pop();
}
s.push(i);
}
}
// Function to find and print ranges where each element is the maximum
void printMaxElementRanges(const std::vector<int>& nums) {
int n = nums.size();
std::vector<int> left(n, -1); // Position of next greater element on the left
std::vector<int> right(n, n); // Position of next greater element on the right
findNextGreaterElements(nums, left, right);
for (int i = 0; i < n; ++i) {
// Adjust the range according to the problem statement
std::cout << nums[i] << " [" << (left[i] + 2) << ", " << (right[i]) << "]" << std::endl;
}
}
int main() {
std::vector<int> nums = {1, 5, 4, 3, 6};
printMaxElementRanges(nums);
return 0;
}
#include <iostream>
#include <vector>
#include <limits>
int findPartitionIndex(const std::vector<int>& nums) {
const int n = nums.size();
std::vector<int> minFromRight(n, std::numeric_limits<int>::max());
// Initialize the last element of minFromRight with the last element of nums
minFromRight[n - 1] = nums[n - 1];
// Populate minFromRight by tracking the minimum from right to left
for (int i = n - 2; i >= 0; --i) {
minFromRight[i] = std::min(minFromRight[i + 1], nums[i]);
}
int maxFromLeft = std::numeric_limits<int>::min();
for (int i = 0; i < n - 1; ++i) {
maxFromLeft = std::max(maxFromLeft, nums[i]);
if (maxFromLeft < minFromRight[i + 1]) {
// Found the partition index
return i + 1;
}
}
// If no partition is found that satisfies the condition, return -1 to indicate no valid partition exists.
return -1;
}
int main() {
std::vector<int> nums = {5, -1, 3, 8, 6};
int partitionIndex = findPartitionIndex(nums);
std::cout << "Partition Index: " << partitionIndex << std::endl;
return 0;
}
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
// Define the structure to hold hotel information
struct Hotel {
int hotelId;
int parentHotelId;
int score;
};
// Function to find the root parent of a hotel
int findRootParent(int hotelId, unordered_map<int, int>& parentMap) {
while (parentMap[hotelId] != hotelId) {
hotelId = parentMap[hotelId];
}
return hotelId;
}
// Function to solve the problem
vector<vector<int>> findTopKRootParents(vector<Hotel>& hotels, int K) {
// Maps to store parent relationships and scores
unordered_map<int, int> parentMap, scoreMap;
// Initialize the maps
for (const auto& hotel : hotels) {
parentMap[hotel.hotelId] = hotel.parentHotelId;
if (parentMap.find(hotel.parentHotelId) == parentMap.end()) {
parentMap[hotel.parentHotelId] = hotel.parentHotelId;
}
}
// Aggregate scores under root parents
for (const auto& hotel : hotels) {
int rootParent = findRootParent(hotel.hotelId, parentMap);
scoreMap[rootParent] += hotel.score;
}
// Move the map to a vector to sort
vector<pair<int, int>> scoreVec(scoreMap.begin(), scoreMap.end());
// Sort by score in descending order
sort(scoreVec.begin(), scoreVec.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
});
// Select top K root parents
vector<vector<int>> result;
for (int i = 0; i < min(K, (int)scoreVec.size()); ++i) {
result.push_back({scoreVec[i].first, scoreVec[i].second});
}
return result;
}
int main() {
// Example input
vector<Hotel> hotels = {{0, 1, 10}, {1, 2, 20}, {3, 4, 10}, {7, 8, 5}};
int K = 2;
// Solve
vector<vector<int>> topK = findTopKRootParents(hotels, K);
// Output the result
for (const auto& pair : topK) {
cout << "[" << pair[0] << ", " << pair[1] << "]" << endl;
}
return 0;
}
#include <iostream>
#include <unordered_set>
#include <vector>
class StreamChecker {
public:
StreamChecker() { }
bool hasSeen(int number) {
// Check if the number is in the set of seen numbers
if (seen.find(number) != seen.end()) {
return true; // Number has already been seen
} else {
seen.insert(number); // Add the number to the set of seen numbers
return false; // This is the first time seeing the number
}
}
private:
std::unordered_set<int> seen; // Set to store seen numbers
};
int main() {
StreamChecker checker;
std::vector<int> stream = {1, 2, 3, 5, 6, 11, 7, 3, 4, 1, 2, 5, 9, 22, 12};
for (int num : stream) {
if (checker.hasSeen(num)) {
std::cout << num << " has been seen before." << std::endl;
} else {
std::cout << num << " is seen for the first time." << std::endl;
}
}
return 0;
}
#include <iostream>
template <typename T>
class Node {
public:
T data;
Node* prev;
Node* next;
Node(T val) : data(val), prev(nullptr), next(nullptr) {}
};
template <typename T>
class DoublyLinkedList {
private:
Node<T>* head;
Node<T>* tail;
int size;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
~DoublyLinkedList() {
while (head != nullptr) {
Node<T>* temp = head;
head = head->next;
delete temp;
}
}
void insertFront(T val) {
Node<T>* newNode = new Node<T>(val);
if (head == nullptr) {
head = tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
++size;
}
void insertBack(T val) {
Node<T>* newNode = new Node<T>(val);
if (tail == nullptr) {
head = tail = newNode;
} else {
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
++size;
}
void removeFront() {
if (head == nullptr) {
std::cout << "List is empty. Cannot remove from an empty list.\n";
return;
}
Node<T>* temp = head;
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
} else {
tail = nullptr; // If head is null, the list is empty, so set tail to null as well.
}
delete temp;
size--;
}
void removeBack() {
if (tail == nullptr) {
std::cout << "List is empty. Cannot remove from an empty list.\n";
return;
}
Node<T>* temp = tail;
tail = tail->prev;
if (tail != nullptr) {
tail->next = nullptr;
} else {
head = nullptr; // If tail is null, the list is empty, so set head to null as well.
}
delete temp;
--size;
}
void display() {
Node<T>* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
int getSize() const {
return size;
}
};
int main() {
DoublyLinkedList<int> dll;
dll.insertFront(1);
dll.insertFront(2);
dll.insertBack(3);
dll.insertBack(4);
std::cout << "Doubly Linked List: ";
dll.display(); // Output: 2 1 3 4
dll.removeFront();
dll.removeBack();
std::cout << "Doubly Linked List after removal: ";
dll.display(); // Output: 1 3
std::cout << "Size of Doubly Linked List: " << dll.getSize() << std::endl; // Output: 2
return 0;
}
Doubly Linked List: 2 1 3 4
Doubly Linked List after removal: 1 3
Size of Doubly Linked List: 2
Output:
#include <chrono>
#include <condition_variable>
#include <iostream>
#include <mutex>
#include <queue>
#include <stdexcept>
#include <thread>
template<typename T>
class BoundedQueue {
private:
std::mutex readMutex, writeMutex;
std::condition_variable readCond, writeCond;
std::queue<T> queue;
size_t capacity;
public:
BoundedQueue(size_t capacity) : capacity(capacity) {}
// Attempt to read an element with a timeout
bool Read(T& value, std::chrono::milliseconds timeout) {
std::unique_lock<std::mutex> readLock(readMutex);
if (!readCond.wait_for(readLock, timeout, [this]{ return !queue.empty(); })) {
return false; // Timeout or condition not met
}
{
std::lock_guard<std::mutex> writeLock(writeMutex); // Ensure not to block writers
value = queue.front();
queue.pop();
}
writeCond.notify_one(); // Notify one waiting writer, if any
return true;
}
// Attempt to write an element with a timeout
bool Write(const T& value, std::chrono::milliseconds timeout) {
std::unique_lock<std::mutex> writeLock(writeMutex);
if (!writeCond.wait_for(writeLock, timeout, [this]{ return queue.size() < capacity; })) {
return false; // Timeout or condition not met
}
{
std::lock_guard<std::mutex> readLock(readMutex); // Ensure not to block readers
queue.push(value);
}
readCond.notify_one(); // Notify one waiting reader, if any
return true;
}
};
int main() {
BoundedQueue<int> queue(5); // Example with an int queue and capacity of 5
// Example usage
std::thread writer([&queue] {
for (int i = 0; i < 10; ++i) {
if (queue.Write(i, std::chrono::seconds(1))) {
std::cout << "Wrote: " << i << std::endl;
} else {
std::cout << "Write timed out for: " << i << std::endl;
}
std::this_thread::sleep_for(std::chrono::milliseconds(100));
}
});
std::thread reader([&queue] {
int value;
while (queue.Read(value, std::chrono::seconds(2))) {
std::cout << "Read: " << value << std::endl;
}
std::cout << "Read timed out or queue closed." << std::endl;
});
writer.join();
reader.join();
return 0;
}
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
std::mutex mtx;
std::condition_variable cv_even, cv_odd;
int current = 1; // Shared variable to determine the next number to print
const int MAX = 10; // Set the maximum value to be printed
void printEven() {
while (current <= MAX) {
std::unique_lock<std::mutex> lk(mtx);
cv_even.wait(lk, [] { return current % 2 == 0; });
if (current > MAX) break;
std::cout << "Even Thread: " << current << std::endl;
current++;
cv_odd.notify_one(); // Notify odd thread to print next
}
}
void printOdd() {
while (current <= MAX) {
std::unique_lock<std::mutex> lk(mtx);
cv_odd.wait(lk, [] { return current % 2 != 0; });
if (current > MAX) break;
std::cout << "Odd Thread: " << current << std::endl;
current++;
cv_even.notify_one(); // Notify even thread to print next
}
}
int main() {
std::thread evenThread(printEven);
std::thread oddThread(printOdd);
evenThread.join();
oddThread.join();
return 0;
}
#include <chrono>
#include <mutex>
#include <thread>
#include <condition_variable>
#include <iostream>
class ThreadSafeTimer {
private:
std::mutex mtx;
std::chrono::steady_clock::time_point start_time;
std::chrono::duration<double> elapsed{0};
bool running = false;
public:
void Start() {
std::lock_guard<std::mutex> lock(mtx);
if (!running) {
start_time = std::chrono::steady_clock::now();
running = true;
}
}
void Stop() {
std::lock_guard<std::mutex> lock(mtx);
if (running) {
auto end_time = std::chrono::steady_clock::now();
elapsed += end_time - start_time;
running = false;
}
}
void Reset() {
std::lock_guard<std::mutex> lock(mtx);
running = false;
elapsed = std::chrono::duration<double>::zero();
}
double Elapsed() {
std::lock_guard<std::mutex> lock(mtx);
if (running) {
auto current_time = std::chrono::steady_clock::now();
return std::chrono::duration_cast<std::chrono::duration<double>>(elapsed + (current_time - start_time)).count();
}
return elapsed.count();
}
};
int main() {
ThreadSafeTimer timer;
timer.Start();
std::this_thread::sleep_for(std::chrono::seconds(1));
timer.Stop();
std::cout << "Elapsed time: " << timer.Elapsed() << " seconds" << std::endl;
timer.Reset();
timer.Start();
std::this_thread::sleep_for(std::chrono::seconds(2));
std::cout << "Elapsed time after reset and 2 seconds: " << timer.Elapsed() << " seconds" << std::endl;
return 0;
}
Output:
Elapsed time: 1.00007 seconds
Elapsed time after reset and 2 seconds: 2.00007 seconds
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
std::mutex mtx;
std::condition_variable cv;
int current = 0; // Shared variable to determine the next number to print
const int MAX = 6; // Set the maximum value to be printed
void printZero() {
while (true) {
std::unique_lockstd::mutex lk(mtx);
cv.wait(lk, [] { return current % 2 == 0 || current > MAX; });
if (current > MAX) break;
std::cout << "0";
current++;
lk.unlock();
cv.notify_all();
}
}
void printEven() {
for (int i = 2; i <= MAX; i += 2) {
std::unique_lockstd::mutex lk(mtx);
cv.wait(lk, [i] { return current == i || current > MAX; });
if (current > MAX) break;
std::cout << i;
current++;
lk.unlock();
cv.notify_all();
}
}
void printOdd() {
for (int i = 1; i <= MAX; i += 2) {
std::unique_lockstd::mutex lk(mtx);
cv.wait(lk, [i] { return current == i || current > MAX; });
if (current > MAX) break;
std::cout << i;
current++;
lk.unlock();
cv.notify_all();
}
}
int main() {
std::thread threads[3];
threads[0] = std::thread(printZero);
threads[1] = std::thread(printEven);
threads[2] = std::thread(printOdd);
// Join threads with the main thread
for (auto& t : threads) {
t.join();
}
std::cout << std::endl;
return 0;
}
- igvedmak April 06, 2024