This algorithm calculates the length of the longest increasing subsequence (LIS) within a given array of integers. It employs dynamic programming, where `dp[i]` represents the length of the LIS ending at index `i`. The a...

The `length_of_lis` function uses dynamic programming with a time complexity of O(N^2), where N is the number of elements in the input array. This is due to the nested loops iterating through all pairs of elements. The space complexity is O(N) for storing the `dp` array. The base cases for empty or single-element arrays are handled correctly. The core logic relies on the invariant that `dp[i]` stores the maximum length of an increasing subsequence ending at index `i`. For each `i`, it checks all `j < i`; if `nums[i] > nums[j]`, it means `nums[i]` can extend the LIS ending at `j`, so we update `dp[i]` to be the maximum of its current value and `dp[j] + 1`. The final answer is the maximum value found in the `dp` array, representing the overall longest increasing subsequence.

FUNCTION length_of_lis(array nums): IF nums is empty THEN RETURN 0 END IF IF nums has 1 element THEN RETURN 1 END IF CREATE an array dp of same size as nums, initialized with 1s FOR i from 1 to length(nums) - 1: FOR j fr...

This algorithm finds the first character in a given string that does not repeat. It iterates through the string twice: first to count the frequency of each character using a hash map, and second to find the first charact...

The `first_non_repeating_char` function uses a hash map to efficiently count character frequencies. The time complexity is O(N) because we iterate through the string twice, where N is the length of the string. The space complexity is O(K), where K is the number of unique characters in the string, for storing the hash map. The algorithm handles the edge case of an empty string by returning nil. It also correctly identifies cases where all characters repeat or no characters repeat. The correctness relies on the fact that the first pass accurately counts all occurrences, and the second pass, by iterating in the original string order, guarantees that the first character found with a count of 1 is indeed the first non-repeating one.

FUNCTION first_non_repeating_char(string s): IF s is empty THEN RETURN null END IF CREATE a hash map called char_counts FOR EACH character c in s: INCREMENT count for c in char_counts (initialize to 0 if not present) END...

This Crystal code demonstrates ORM query tuning techniques, focusing on efficient data retrieval. It includes methods for fetching records by IDs, applying conditions, selecting specific fields, and ordering results. A k...

The `ORM::Model` class provides static methods for database interaction, simulating ORM functionality. `find_by_ids` and `find_with_conditions` construct SQL queries dynamically, allowing selection of specific fields and applying filters. The `get_posts_for_users` method exemplifies eager loading by fetching all relevant posts for a given set of user IDs in one query, then restructuring the results. This avoids the N+1 problem where individual queries would be made for each user's posts. Time complexity for query generation is proportional to the number of fields and conditions. The actual database query execution time depends on the database and data size. Space complexity is O(R) where R is the number of records returned.

Module ORM: Class Model: Class Methods: Initialize table_name, columns Find_by_ids(ids, select_fields): If ids is empty, return empty array Determine fields to select (default to all columns) Construct SQL: SELECT fields...

This Crystal code implements a `BackgroundScheduler` that executes tasks at specified intervals. It maintains a list of `ScheduledTask` objects, each with a name, interval, and a `Proc` to execute. The scheduler loop con...

The `BackgroundScheduler` uses a main loop that runs in a separate fiber. In each iteration, it identifies tasks due for execution, spawns new fibers to run them concurrently, and updates their `next_run_time`. The loop then calculates the minimum time until the next task is due and sleeps for that duration, minimizing CPU usage. Error handling within individual tasks is done via `begin...rescue` in `ScheduledTask#run`, preventing a single task failure from crashing the scheduler. Time complexity of the scheduler loop is O(T) where T is the number of tasks, as it iterates through all tasks. Sleep duration calculation is O(T). Space complexity is O(T) to store the tasks.

Class ScheduledTask: Initialize(name, interval_seconds, task): Set name, interval_seconds, task Set next_run_time = current_time + interval_seconds Run(): Try: Execute task Print success message Catch any exception: Prin...

This Crystal code simulates an actor system using fibers and channels. A central `Actor` class manages a mailbox (channel) and an `ActorState` object. Actors process messages asynchronously, updating their state and pote...

Each `Actor` runs in its own fiber, processing messages from its `mailbox` channel. The `ActorState` object encapsulates the actor's data and logic for handling different message types. Messages are passed as JSON-encoded Hashes, which are then parsed into specific message structs (`IncrementMessage`, `GetValueMessage`). The `GetValueMessage` demonstrates request-reply pattern by including a reply channel. Actors communicate asynchronously, and state is managed internally, avoiding shared mutable state issues. Time complexity for processing a message is O(M) where M is the complexity of message processing (parsing and state update). Space complexity is O(C) where C is the channel capacity and O(S) for actor state.

Struct IncrementMessage: amount Struct GetValueMessage: reply_to (channel) Class ActorState: Initialize(value = 0) Process_message(message): Parse message to determine type If type is "Increment": Deserialize into Increm...

This Crystal code defines a concurrent web request pipeline with integrated rate limiting. It uses channels to pass requests between a producer and worker fibers, and a `RateLimiter` struct to control the request frequen...

The `WebPipeline` utilizes channels for asynchronous communication between request producers and worker fibers. The `RateLimiter` employs a token bucket-like approach, refilling tokens based on elapsed time and the defined rate. Workers `acquire_token` before making an HTTP request. If a token is unavailable, the worker waits. This ensures that the rate limit is not exceeded. The `select` statement in the worker allows it to simultaneously listen for new requests and a stop signal. Time complexity for processing a request is dominated by the network I/O and rate limiting, which can be O(1) amortized for token acquisition but O(N) in worst-case scenarios for waiting. Space complexity is O(W + R), where W is the number of worker channels and R is the capacity of the request/response channels.

Class RateLimiter: Initialize(rate_limit, time_window_seconds): Set tokens = rate_limit Set last_refill_time = current_time Initialize mutex Acquire_token(): Acquire mutex Refill tokens based on elapsed time While tokens...

This code implements a Fiber pool manager in Crystal to control the maximum number of concurrently executing fibers. It uses a mutex and a condition variable to ensure thread-safe access to the active fiber count and to...

The FiberPool class manages a fixed number of concurrent fibers. The `schedule` method ensures that no more than `max_concurrency` fibers run simultaneously. If the limit is reached, new fiber requests `wait` on a condition variable until a fiber completes. When a fiber finishes, it signals the condition variable, allowing a waiting fiber to proceed. The `wait_for_completion` method blocks until all scheduled fibers have finished. This pattern ensures bounded concurrency, preventing resource exhaustion. Time complexity for scheduling a task is O(1) on average, but can be O(N) in the worst case if all fibers are waiting. Space complexity is O(1) for the pool itself, plus O(N) for the tasks being executed.

Class FiberPool: Initialize(max_concurrency): Set active_fibers = 0 Initialize mutex and condition variable Schedule(task): Acquire mutex While active_fibers >= max_concurrency: Wait on condition variable Increment activ...

This Crystal code provides a `ConfigLoader` class for parsing nested configuration data from a YAML file. It supports retrieving values of various types (string, integer, float, boolean, array) using dot-notation for nes...

The `ConfigLoader` reads a YAML file, parses it into a nested hash structure, and provides methods to access configuration values by a dot-separated key path. The `get_value` method recursively traverses the nested hashes. Specific `get_type` methods (e.g., `get_string`, `get_int`) handle type conversions and validation, returning a default value or `nil` on failure. Error handling is implemented using `begin...rescue` blocks for file operations, YAML parsing, and type assertions. Time complexity for loading is O(N) where N is the number of nodes in the YAML file. Accessing a value is O(D) where D is the depth of the key path. Space complexity is O(N) to store the configuration data.

Class ConfigLoader: Initialize(file_path): Set config_data = empty hash Load_config(): Try: Read file content Parse content as YAML If root is not a hash, raise error Store parsed data in config_data Return true Catch IO...