Appearance
question:# Scenario: You are developing a data structure to manage a dynamic array of integers. This array is used frequently in a system that requires two main operations: updating the value of an element at a given index and querying the sum of a subarray. To handle both types of operations efficiently, you decide to use a **Segment Tree**. # Task: Implement a class to support the following operations: 1. **update_value(index: int, value: int)**: Update the integer at the specified index to the new value. 2. **sum_query(start_index: int, end_index: int)**: Compute and return the sum of the elements within the range [start_index, end_index). # Constraints: - `0 <= index < N`, where `N` is the size of the array. - `-10^9 <= value <= 10^9` - `0 <= start_index < end_index <= N` - You cannot use built-in library functions for querying ranges (like `sum`). # Function Signature: ```python class DynamicArray: def __init__(self, size: int) -> None: ... def update_value(self, index: int, value: int) -> None: ... def sum_query(self, start_index: int, end_index: int) -> int: ... # Example Usage: # arr = DynamicArray(6) # arr.update_value(2, 10) # arr.update_value(3, 5) # print(arr.sum_query(1, 4)) # Output: 15 (5 + 10) # arr.update_value(2, 7) # print(arr.sum_query(2, 6)) # Output: 12 (7 + 5) ``` # Notes: - Ensure that the solution efficiently supports both value updates and sum queries. - Handle edge cases where updates or queries might include boundary values. - Maintain the performance goals of Segment Trees to achieve optimal querying and updating time complexity. This new question aligns with the given guidelines by focusing on the creation and handling of a dynamic array structure, employing advanced data structures (like the Segment Tree) to manage efficient range queries and updates, complementing the existing question set's coverage of related concepts.
answer:class DynamicArray: def __init__(self, size: int) -> None: self.size = size self.arr = [0] * size self.seg_tree = [0] * (4 * size) self._build(0, 0, size - 1) def _build(self, node, start, end): if start == end: self.seg_tree[node] = self.arr[start] else: mid = (start + end) // 2 left_node = 2 * node + 1 right_node = 2 * node + 2 self._build(left_node, start, mid) self._build(right_node, mid + 1, end) self.seg_tree[node] = self.seg_tree[left_node] + self.seg_tree[right_node] def _update(self, node, start, end, idx, value): if start == end: self.arr[idx] = value self.seg_tree[node] = value else: mid = (start + end) // 2 left_node = 2 * node + 1 right_node = 2 * node + 2 if start <= idx <= mid: self._update(left_node, start, mid, idx, value) else: self._update(right_node, mid + 1, end, idx, value) self.seg_tree[node] = self.seg_tree[left_node] + self.seg_tree[right_node] def _sum_query(self, node, start, end, l, r): if r < start or l > end: return 0 if l <= start and end <= r: return self.seg_tree[node] mid = (start + end) // 2 left_node = 2 * node + 1 right_node = 2 * node + 2 sum_left = self._sum_query(left_node, start, mid, l, r) sum_right = self._sum_query(right_node, mid + 1, end, l, r) return sum_left + sum_right def update_value(self, index: int, value: int) -> None: self._update(0, 0, self.size - 1, index, value) def sum_query(self, start_index: int, end_index: int) -> int: return self._sum_query(0, 0, self.size - 1, start_index, end_index - 1)
question:# Coding Assessment Question Context You have been hired by a company to write software that processes textual data. One of the functionalities required is the ability to count the occurrences of each unique word within a given text string. Problem Description Write a function `word_count` that takes a single string `text` as an argument and returns a dictionary where the keys are unique words (case-insensitive), and the values are the counts of those words. The function should normalize the casing of words and remove punctuation to ensure accurate counts. Input and Output - **Input**: - `text` (str): A string of text from which to count word occurrences. - **Output**: - A dictionary where keys are words (str) and values are their respective counts (int). Constraints - You are only allowed to use standard Python libraries. - Words are separated by whitespace characters and punctuation marks should be ignored. - Treat uppercase and lowercase versions of a word as the same word. Examples ``` >>> word_count("Hello, world! Hello!") {'hello': 2, 'world': 1} >>> word_count("Python is great. Python is popular. Python!") {'python': 3, 'is': 2, 'great': 1, 'popular': 1} >>> word_count("Data, data everywhere... and not a byte to spare!") {'data': 2, 'everywhere': 1, 'and': 1, 'not': 1, 'a': 1, 'byte': 1, 'to': 1, 'spare': 1} ``` Performance Requirement Your solution should efficiently handle text strings of up to 10,000 characters. Hints - Consider using the `re` library for regular expressions to aid in removing punctuation. - Utilize the `str.lower()` method to normalize the case of words.
answer:import re from collections import defaultdict def word_count(text): Given a string `text`, returns a dictionary with the count of each unique word (case insensitive). Punctuation is ignored in the count. Args: text (str): input string containing the text. Returns: dict: dictionary where keys are unique lowercase words and values are their counts. # Normalize text to lowercase and remove punctuation text = re.sub(r'[^ws]', '', text).lower() words = text.split() # Count the occurrences of each word word_counts = defaultdict(int) for word in words: word_counts[word] += 1 return dict(word_counts)
question:# Financial Data Analysis using Python You are required to implement a Python function to parse and analyze stock trading data from a CSV file and then generate summary statistics. This task aims to assess your data manipulation, analysis capabilities, and proficiency with the Pandas library in Python. Context: You are given a CSV file containing historical stock prices and trading volumes for multiple companies over a period of time. The CSV file includes columns: 'Date', 'Company', 'Close_Price', 'Volume'. Your goal is to read this data, process it, and provide statistical summaries of closing prices and volumes for each company. Task: 1. Write a function `analyze_stock_data(filename: str) -> dict` that reads a CSV file, processes the data, and returns a dictionary with companies as keys and their summary statistics as values. 2. In the same function, compute the following statistics per company: - Average closing price. - Standard deviation of closing prices. - Total volume of stocks traded. Input: - `filename`: (str) The name of the CSV file containing the stock data. The CSV file is expected to have columns: 'Date' (string), 'Company' (string), 'Close_Price' (float), and 'Volume' (integer). Output: - A dictionary where each key is a company name (string) and the value is another dictionary with the keys 'Average_Price', 'Price_StdDev', and 'Total_Volume', containing the corresponding calculated values. Notes: - Assume all columns in the CSV file are correctly formatted and contain valid data. - Use the Pandas library for data loading and manipulation. - Ensure to handle large files efficiently. - Handle potential missing or NaN values appropriately by excluding them from calculations. - Code should be written in a modular and readable manner. Example: Here is an example of expected function usage: ```python filename = "stock_data.csv" summary_statistics = analyze_stock_data(filename) # Example of the returned dictionary: # { # "CompanyA": { # "Average_Price": 150.5, # "Price_StdDev": 12.34, # "Total_Volume": 1050000 # }, # "CompanyB": { # "Average_Price": 75.4, # "Price_StdDev": 8.24, # "Total_Volume": 850000 # } # } ``` # Sample CSV File (`stock_data.csv`): ``` Date,Company,Close_Price,Volume 2023-01-01,CompanyA,155.2,10000 2023-01-02,CompanyA,152.3,8500 2023-01-01,CompanyB,78.9,15000 2023-01-02,CompanyB,72.0,17000 ```
answer:import pandas as pd def analyze_stock_data(filename: str) -> dict: # Read the CSV file into a DataFrame df = pd.read_csv(filename) # Initialize result dictionary result = {} # Group the data by Company grouped = df.groupby('Company') # Iterate over each group to compute statistics for name, group in grouped: # Drop NaN values in Close_Price and Volume columns close_prices = group['Close_Price'].dropna() volumes = group['Volume'].dropna() # Compute statistics avg_price = close_prices.mean() stddev_price = close_prices.std() total_volume = volumes.sum() # Store results in the dictionary result[name] = { 'Average_Price': avg_price, 'Price_StdDev': stddev_price, 'Total_Volume': total_volume } return result
question:# Coding Assessment Question Context Sorting algorithms are fundamental in computer science, and understanding them is crucial for efficiency in data handling. We're going to explore one of the classic sorting algorithms, Merge Sort, and see how it performs on different data sets. The Task Using your knowledge of sorting algorithms, implement the **Merge Sort** algorithm to sort a list of integers and test its performance on varied input sizes and values. Input A list of integers `arr` (0 ≤ len(arr) ≤ 10^5) where each integer can range from -10^9 to 10^9. Output A new list with the elements from `arr` sorted in non-decreasing order. Performance Requirements - Your solution should be efficient: aim for O(n log n) time complexity and O(n) space complexity. # Implementation Guide 1. Implement the main function `merge_sort(arr: List[int]) -> List[int]` using the Merge Sort algorithm: * Handle edge cases where the list length is 0 or 1. * Use a divide-and-conquer approach to split the list into smaller sublists. * Merge the sorted sublists back together to form the sorted list. 2. Test your implementation with various inputs to ensure correctness. Include edge cases like empty lists, already sorted lists, and lists with all elements the same. # Example Usage ```python from typing import List def merge_sort(arr: List[int]) -> List[int]: # Your code here to implement merge sort # Example usage: print(merge_sort([])) # Output: [] print(merge_sort([5])) # Output: [5] print(merge_sort([3, 1, 2])) # Output: [1, 2, 3] print(merge_sort([10, -1, 100, 4])) # Output: [-1, 4, 10, 100] ```
answer:from typing import List def merge_sort(arr: List[int]) -> List[int]: if len(arr) <= 1: return arr # Splitting the array into two halves mid = len(arr) // 2 left_half = merge_sort(arr[:mid]) right_half = merge_sort(arr[mid:]) return merge(left_half, right_half) def merge(left: List[int], right: List[int]) -> List[int]: sorted_list = [] left_index = right_index = 0 # Merging the two halves until one is exhausted while left_index < len(left) and right_index < len(right): if left[left_index] < right[right_index]: sorted_list.append(left[left_index]) left_index += 1 else: sorted_list.append(right[right_index]) right_index += 1 # Append any remaining elements from left and right halves sorted_list.extend(left[left_index:]) sorted_list.extend(right[right_index:]) return sorted_list