Question 1

Write a function that takes in an array of integers, which can be both positive and negative, along with a target integer. The function should return all unique pairs of integers from the array that sum up to the target integer.
```python
def find_pairs_with_sum(arr: List[int], target: int) -> List[Tuple[int, int]]:
    pass
```
Inputs
The inputs are defined as follows:
- arr: A list of integers containing both positive and negative numbers. The array may have duplicate values.
- target: An integer that we are interested in finding pairs for.
Output
Return a list of tuples, where each tuple contains a pair of integers that sum up to the target integer.
Example Tests
- find_pairs_with_sum([3, 4, 2, 5], 7) should return [(3, 4), (2, 5)]
- find_pairs_with_sum([2, 4, 1, 5], 9) should return [(4, 5)]
- find_pairs_with_sum([7, 1, 2, 3, 4, -2], 5) should return [(1, 4), (2, 3), (7, -2)]

Accepted Answer

Question 2

Write a function to filter out words from a given list that contain all the vowels ('a', 'e', 'i', 'o', 'u'). The function should be case insensitive.
```python
def words_with_all_vowels(list_of_words: List[str]) -> List[str]:
    pass
```
Input
The input `list_of_words` is defined as a list of strings, each string representing a word.
Output
Return a list of strings containing only the words that have all the vowels.
Example Tests
words_with_all_vowels(['car', 'multidirectional', 'hello', 'overqualified', 'university']) should return ['multidirectional', 'overqualified'].

Accepted Answer

Question 3

You are given an array A of N integers and an integer S. Your task is to compute how many ways one can choose a contiguous fragment of A that has an arithmetic mean equal to S. The arithmetic mean (average) of a fragment is the sum of the elements of the fragment divided by its length. For example, the arithmetic mean of [1, 3, 3, 5] = 12/4 = 3.
Write a function which returns the number of contiguous fragments of A whose arithmetic means are equal to S. Examples:
- Given A = [3, 2, 4] and S = 3, your function should return 3, since the arithmetic means of fragments [3], [2, 4], [3, 2, 4] are equal to 3.
- Given A = [-1, 3, 2, -2] and S = 1, your function should return 2, since fragments [-1, 3] and [3, 2, -2] have an arithmetic mean of 1.
- Given A = [2, 3, 6] and S = 5, your function should return 0, since there exist no contiguous fragments whose arithmetic mean is equal to 5.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1, ..., 100,000]
- S is an integer within the range [-100,000,000,000, 100,000,000,000]
- Each element of array A is an integer within the range [-100,000,000,000, 100,000,000,000]

Accepted Answer

Question 4

You're tasked with implementing various operations on a binary search tree (BST). The BST will store integers, and you need to implement methods for insertion, deletion, and finding the minimum and maximum values. Check out the Hint button if you need more information about the BST.
class
BinarySearchTree
:
```python
def __init__(self):
    pass
def insert(self, value: int):
    pass
def delete(self, value: int):
    pass
def find_min(self) -> int:
    pass
def find_max(self) -> int:
    pass
```
Methods
- insert(value: int): Inserts a new node with the given integer value into the BST.
- delete(value: int): Deletes a node with the given integer value from the BST. If the value doesn't exist, do nothing.
- find_min() -> int: Returns the minimum integer value stored in the BST.
- find_max() -> int: Returns the maximum integer value stored in the BST.
Note
- Implement the BST from scratch; do not use built-in data structures that behave like a BST.
- All integers in the BST need to be unique.
Example
example_bst
=
BinarySearchTree
(
)
# Insert elements to build the tree
values_to_insert
=
[
8
,
3
,
10
,
1
,
6
,
14
,
4
,
7
,
13
]
for `value` in
values_to_insert
:
example_bst
.
insert
(
value
)
print
(
example_bst
.
find_min
(
)
)
# Should return 1
print
(
example_bst
.
find_max
(
)
)
# Should return 14
example_bst
.
delete
(
1
)
print
(
example_bst
.
find_min
(
)
)
# Should return 3

Accepted Answer

Question 5

Implement a circular queue using a fixed-size array. A circular queue is a data structure that uses a single array and two pointers to indicate the start and end positions. It appears as though the array is connected end-to-end. Click on the Hint button if you need more information about Circular Queues and find out why it's relevant in the trading industry.
class
CircularQueue
:
```python
def __init__(self, size: int):
    pass
def enqueue(self, item: Any) -> bool:
    pass
def dequeue(self) -> Optional[Any]:
    pass
def peek(self) -> Optional[Any]:
    pass
def is_empty(self) -> bool:
    pass
def is_full(self) -> bool:
    pass
```
Methods
- enqueue(item: Any) -> bool: Adds an item to the rear of the queue.
- dequeue() -> Optional[Any]: Removes and returns an item from the front of the queue.
- peek() -> Optional[Any]: Returns the item at the front of the queue without removing it.
- is_empty() -> bool: Checks if the queue is empty.
- is_full() -> bool: Checks if the queue is full.
Inputs and Outputs
- enqueue(item): Takes any type as input and returns a boolean. Returns True if the item was successfully added to the queue, and False otherwise.
- dequeue(): Returns the dequeued item if successful and None if the queue is empty.
- peek(): Returns the item at the front of the queue without removing it. Returns None if the queue is empty.
- is_empty(): Returns True if the queue is empty and False otherwise.
- is_full(): Returns True if the queue is full and False otherwise.
Example
cq
=
CircularQueue
(
3
)
print
(
cq
.
enqueue
(
1
)
)
# Should return True
print
(
cq
.
enqueue
(
2
)
)
# Should return True
print
(
cq
.
enqueue
(
3
)
)
# Should return True
print
(
cq
.
enqueue
(
4
)
)
# Should return False (Queue is full)
print
(
cq
.
dequeue
(
)
)
# Should return 1
print
(
cq
.
dequeue
(
)
)
# Should return 2
print
(
cq
.
dequeue
(
)
)
# Should return 3
print
(
cq
.
dequeue
(
)
)
# Should return None (Queue is empty)
print
(
cq
.
is_empty
(
)
)
# Should return True
print
(
cq
.
is_full
(
)
)
# Should return False
cq
.
enqueue
(
5
)
print
(
cq
.
peek
(
)
)
# Should return 5
print
(
cq
.
is_empty
(
)
)
# Should return False

Accepted Answer

Question 6

Write a function to find the longest common prefix among a list of strings.
```python
def longest_common_prefix(words_list: List[str]) -> str:
    pass
```
Input
The input word_list is a list of strings.
Output
Return a string representing the longest common prefix among all the strings in the list.
Example Tests
- longest_common_prefix(['applejuice', 'applebandit', 'apples']) should return 'apple'.
- longest_common_prefix(['helloyou', 'helloworld', 'hellohello']) should return 'hello'.
- longest_common_prefix(['tracing', 'tracker', 'traceability']) should return 'trac'.

Accepted Answer

Question 7

Write a function that takes a list of words and returns a list containing only those words that have three consecutive letters of the alphabet.
```python
def words_with_consecutive_letters(words_list: List[str]) -> List[str]:
    pass
```
Input
The input `word_list` is a list of strings, each representing a word.
Output
Return a list of strings containing only the words that have three consecutive letters of the alphabet.
Example Tests
- words_with_consecutive_letters(['definitive', 'random', 'example']) should return ['definitive'].
- words_with_consecutive_letters(['laughing', 'hello', 'world']) should return ['laughing'].
- words_with_consecutive_letters(['abcdef', 'ghijkl', 'mnopqr']) should return ['abcdef', 'ghijkl', 'mnopqr'].

Accepted Answer

Question 8

Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo
$10^9 + 7$
.
- A string is homogenous if all the characters of the string are the same.
- A substring is a contiguous sequence of characters within a string.
Example 1
Input: s = "abbcccaa"
Output: 13
Explanation: The homogenous substrings are listed as below:
- "a" appears 3 times.
- "aa" appears 1 time.
- "b" appears 2 times.
- "bb" appears 1 time.
- "c" appears 3 times.
- "cc" appears 2 times.
- "ccc" appears 1 time.
- 3 + 1 + 2 + 1 + 3 + 2 + 1 = 13.
Example 2
Input: s = "ab"
Output: 2
Explanation: The homogenous substrings are "a" and "b".
Example 3
Input: s = "aaaaa"
Output: 15
Constraints
- 1 <= s.length <= $10^5$
- s consists of lowercase letters.

Accepted Answer

Question 9

Dijkstra's algorithm is used for finding the shortest path in a weighted graph from a source node to all other nodes. It works by iteratively selecting the vertex `u` that has the smallest distance, relaxing all edges that go from `u` to its neighbors, and updating the distances to these neighbors if smaller distances are found.
Objective
You're given a weighted graph, represented as an adjacency list. Your task is to find the shortest path between two specified nodes using Dijkstra's algorithm.
```python
def dijkstra_shortest_path(graph: dict, start: str, end: str) -> list:
    pass
```
Inputs
- graph: A dictionary where the keys are node names (as strings), and the values are dictionaries containing adjacent nodes and the weights of the edges to those nodes.
- start: A string representing the starting node.
- end: A string representing the ending node.
Output
Return a list of nodes that form the shortest path from start to end. If there's no path, return 'None'.
Example
For the graph defined as:
graph
=
{
'A'
:
{
'B'
:
1
,
'C'
:
4
}
,
'B'
:
{
'A'
:
1
,
'C'
:
2
,
'D'
:
5
}
,
'C'
:
{
'A'
:
4
,
'B'
:
2
,
'D'
:
1
}
,
'D'
:
{
'B'
:
5
,
'C'
:
1
}
}
The function call dijkstra_shortest_path(graph, 'A', 'D') should return ['A', 'B', 'C', 'D'] as this is the shortest path from 'A' to 'D'.
- The distance from 'A' to 'B' is 1
- The distance from 'B' to 'C' is 2
- The distance from 'C' to 'D' is 1
If you add these up, the total distance from 'A' to 'D' through this path is 1 + 2 + 1 = 4. No other path from 'A' to 'D' gives a shorter distance, so Dijkstra's algorithm identifies this as the shortest path.
For more information, take a look at
this video
.
Notes
Write an efficient algorithm. A graph can have over 1000 nodes and the edge weights are positive integers.

Accepted Answer

Question 10

This is another assignment about Dijkstra's algorithm, just like
Dijkstra's algorithm #1
. The main difference between this assignment and the previous one involving Dijkstra's algorithm is the nature of the graph and how it's represented. In the previous assignment, we used a dictionary to represent the graph and focused on finding the shortest path length between two nodes. In this new assignment, the graph is represented as a list of tuples, each containing a source node, destination node, and the weight of the edge between them. The objective here is to find the shortest path length and also the actual nodes that form the shortest path from `start` to
end
.
Objective
Implement a function that finds the shortest path between two nodes in a weighted graph using Dijkstra's algorithm.
from `typing` import
List
,
Tuple
```python
def dijkstra_shortest_path(graph: List[Tuple[int, int, int]], start: int, end: int) -> List[int]:
    pass
```
Input and Output
dijkstra_shortest_path(graph, start, end)
takes a list of tuples representing the graph, where each tuple contains the source node, destination node, and the weight of the edge between them. The function returns a list of integers representing the nodes in the shortest path from start to end.
Example Test Cases
graph
=
[
(
0
,
1
,
4
)
,
(
0
,
2
,
1
)
,
(
1
,
3
,
1
)
,
(
2
,
1
,
2
)
,
(
2
,
3
,
5
)
,
(
3
,
4
,
3
)
]
print
(
dijkstra_shortest_path
(
graph
,
0
,
4
)
)
# Should return [0, 2, 1, 3, 4]
graph
=
[
(
0
,
1
,
2
)
,
(
1
,
2
,
2
)
,
(
1
,
3
,
2
)
,
(
2
,
3
,
2
)
,
(
2
,
4
,
2
)
]
print
(
dijkstra_shortest_path
(
graph
,
0
,
4
)
)
# Should return [0, 1, 2, 4]
graph
=
[
(
0
,
1
,
1
)
,
(
0
,
3
,
3
)
,
(
1
,
3
,
3
)
,
(
1
,
2
,
1
)
,
(
2
,
3
,
1
)
,
(
3
,
4
,
1
)
]
print
(
dijkstra_shortest_path
(
graph
,
0
,
4
)
)
# Should return [0, 1, 2, 3, 4]
For clarification: a tuple as (x, y, z) means (start node, end node, distance).

Accepted Answer

Question 11

You have 13 red cards and 13 blue cards, labeled from 1 to 13. You remove 7 blue cards at random.
What is the probability that the card drawn is blue given that the number on the card is 3? Please write a simulation that has the probability as an output.

Accepted Answer

Question 12

Write a function to calculate the expected number of empty boxes when you have 100 balls and 50 boxes, with each ball being placed into a random box independently.
```python
def expected_empty_boxes(balls: int, boxes: int) -> float:
    pass
```
Inputs
The inputs are defined as follows:
- balls: The number of balls to be distributed. Default should be 100.
- boxes: The number of boxes to distribute the balls into. Default should be 50.
Output
Return a float representing the expected number of empty boxes.

Accepted Answer

Question 13

Your task is to write a function that takes a directed graph, a start node, and an end node, and returns all unique paths from the start node to the end node.
```python
def find_all_paths(graph: Dict[str, List[str]], start: str, end: str) -> List[List[str]]:
    pass
```
Input
- graph: A dictionary where the keys are node names (strings) and the values are lists of neighbor nodes (also strings).
- start: The name of the start node (a string).
- end: The name of the end node (a string).
Output
A list of lists, where each inner list represents a unique path from start to end. Each path is represented as a list of node names.
Examples
graph
=
{
'A'
:
[
'B'
,
'C'
]
,
'B'
:
[
'D'
]
,
'C'
:
[
'D'
,
'E'
]
,
'D'
:
[
'F'
]
,
'E'
:
[
'F'
]
,
'F'
:
[
]
}
print
(
find_all_paths
(
graph
,
'A'
,
'F'
)
)
# Should return [['A', 'B', 'D', 'F'], ['A', 'C', 'D', 'F'], ['A', 'C', 'E', 'F']]
Notes
- You can assume that the graph does not contain cycles.
- If there are no paths from start to end, the function should return an empty list.
- Nodes are represented as single uppercase letters.

Accepted Answer

Question 14

Create a function to find the single missing number in a given array that is supposed to contain integers from 0 to
n
.
```python
def find_missing_number(arr: List[int]) -> int:
    pass
```
Input
The input `arr` is a list of integers ranging from 0 to
n
, with one number missing.
Output
Return an integer representing the missing number in the array.
Bonus
Try to solve this problem without using loops.
Example Tests
- find_missing_number([1, 2, 4, 5, 6]) should return 3.
- find_missing_number([1, 2, 3, 5, 6]) should return 4.
- find_missing_number([1, 2, 3, 4, 6]) should return 5.

Accepted Answer

Question 15

Write a function to construct the largest possible number by rearranging the integers in a given list.
```python
def create_largest_number(list_of_numbers: List[int]) -> int:
    pass
```
Input
The input `list_of_integers` is a list of integers (round numbers).
Output
Return an integer representing the largest possible number that can be formed.
Example Tests
- create_largest_number([4, 56, 6, 3]) should return 65643.
- create_largest_number([6, 3, 59]) should return 6593.
- create_largest_number([91, 62, 7, 12, 3999, 913]) should return 91913762399912.

Accepted Answer

Question 16

You're given a list of words. Write a function that groups these words into sets of anagrams. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.
```python
def group_anagrams(word_list: list) -> list:
    pass
```
Input
The input `word_list` is defined as a list containing words as strings.
Output
Return a list of lists, where each inner list contains all words from the `word_list` that are anagrams of each other.
Constraints
Assume that all words are in lowercase and words can contain any ASCII characters.

Accepted Answer

Question 17

Given a singly linked list, your task is to write a function that finds and returns the last node of the list. If the list is empty, your function should return null.

Accepted Answer

Question 18

You're given two sequences of integers. Your task is to write a function that finds the Longest Common Subsequence (LCS) of the two sequences.
```python
def find_lcs(seq1: list, seq2: list) -> list:
    pass
```
Inputs
- seq1: A list of integers representing the first sequence.
- seq2: A list of integers representing the second sequence.
Output
Return a list of integers representing the Longest Common Subsequence of seq1 and seq2.
Example
Given the sequences seq1 = [1, 2, 3, 4, 5] and seq2 = [6, 7, 1, 2, 8], your function should return [1, 2].

Accepted Answer

Question 19

The Minimum Spanning Tree (MST) of a graph is a subset of its edges that connects all vertices together, without forming any cycles, and with the minimum possible total edge weight. In other words, it's the cheapest possible way to connect all the nodes together without any loops.
To clarify with an example, consider a network of cities connected by roads with different distances. The MST would be the smallest set of roads that connect all cities together, while minimizing the total distance.
A graph can have multiple MSTs, but they will all have the same total weight. Algorithms like Kruskal's and Prim's are commonly used to find an MST of a given weighted, undirected graph.
In the context of the assignment, you would implement Kruskal's algorithm to find an MST of a given graph. The output would be a list of edges that form the MST, ideally with the smallest total edge weight.
Objective
You're given a weighted, undirected graph. Your task is to implement a function that finds the Minimum Spanning Tree (MST) of this graph using Kruskal's algorithm.
```python
def kruskal_mst(graph: dict) -> list:
    pass
```
Inputs `The` graph
is a dictionary representing the weighted, undirected graph. The keys are the node names (strings), and the values are dictionaries containing adjacent nodes and the weights of the edges to them.
Output
Return a list of tuples, each representing an edge in the MST. Each tuple should contain the source node, destination node, and the edge weight.
Example
Given the following graph:
graph
=
{
'NewYork'
:
{
'Chicago'
:
790
,
'LosAngeles'
:
2445
}
,
'Chicago'
:
{
'NewYork'
:
790
,
'LosAngeles'
:
1745
,
'SanFrancisco'
:
1850
}
,
'LosAngeles'
:
{
'NewYork'
:
2445
,
'Chicago'
:
1745
,
'SanFrancisco'
:
350
}
,
'SanFrancisco'
:
{
'Chicago'
:
1850
,
'LosAngeles'
:
350
}
}
The function call kruskal_mst(graph) should return:
[
(
'LosAngeles'
,
'SanFrancisco'
,
350
)
,
(
'NewYork'
,
'Chicago'
,
790
)
,
(
'Chicago'
,
'LosAngeles'
,
1745
)
]

Accepted Answer

Question 20

Imagine you are playing a card game. You start with a well-shuffled deck of 52 cards, containing 26 red cards and 26 black cards, stacked face down. You have a sequence of turns, 52 possible turns in total, each turn you either pull the top card and turn it over, or you quit. If you pull a red card you win €1, and if you pull a black card you lose €1. If you play all 52 turns without stopping, you are guaranteed to break even. What is the optimal stopping strategy?

Accepted Answer

Question 21

Objective
In this programming assignment, you will create a Python script that checks whether a given word or phrase is a palindrome. A palindrome is a word, phrase, or sequence of characters that reads the same forwards and backwards (ignoring spaces, punctuation, and capitalization).
Instructions
1. Write a function called is_palindrome(input_string) that takes a single argument, input_string , which is a string containing a word or phrase.
2. The function should ignore spaces, punctuation, and capitalization when determining if the input string is a palindrome. For example, the function should return True for the input strings "A man, a plan, a canal, Panama!" and "amanaplanacanalpanama".
3. To accomplish this, you may use string manipulation techniques and/or Python's built-in string methods to filter out non-alphanumeric characters and convert the input string to lowercase.
4. Implement a palindrome-checking algorithm to determine whether the cleaned input string is a palindrome. You may use any approach you like (e.g., comparing characters, slicing, or reversing the string).
5. Write a test function called test_is_palindrome() that tests your is_palindrome() function using a few example input strings. Include test cases with palindromes, non-palindromes, and edge cases (e.g., empty strings or strings with only special characters).
Deliverables (in 30 minutes)
1. A Python script containing the is_palindrome(input_string) function and the test_is_palindrome() function.
2. A brief report (1-2 paragraphs) describing your approach and any challenges you encountered while completing the assignment.

Accepted Answer

Question 22

In this assignment, you will compare the accuracy of the Binomial Tree Model and the Black-Scholes Model. You can use the code snippets in the two lectures in this code for both models. Write code that returns the number of steps that the Binomial Tree Model should have such that the difference in price between the call (or put) option in the BT model and the BS model is less than 0.5%.

Accepted Answer

Question 23

Objective
In this programming assignment, you will create a Python script that generates a list of prime numbers within a specified range. A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers.
Instructions
1. Write a function called is_prime(number) that takes a single argument, number , which is a positive integer. The function should return True if the number is prime and False otherwise.
2. Implement a prime-checking algorithm in the is_prime() function. You may use any approach you like (e.g., trial division, checking for divisors up to the square root of the number, or using a Sieve of Eratosthenes-style algorithm).
3. Write another function called generate_primes(start, end) that takes two arguments, start and end , which are positive integers representing the range within which you want to generate prime numbers. The function should return a list of prime numbers within the specified range (inclusive of start and end ).
4. Utilize the is_prime() function within the generate_primes() function to check if a number is prime before adding it to the list of primes.
5. Write a test function called test_generate_primes() that tests your generate_primes(start, end) function using a few example ranges. Include test cases with various ranges and edge cases (e.g., a range with no prime numbers or a range containing only one number).
Deliverables (in 1 hour)
1. A Python script containing the is_prime(number) function, the generate_primes(start, end) function, and the test_generate_primes() function.
2. A brief report (1-2 paragraphs) describing your approach, the prime-checking algorithm used, and any challenges you encountered while completing the assignment.

Accepted Answer

Question 24

Your task is to implement a Priority Queue using a binary heap data structure. The Priority Queue should support insertion, deletion, and retrieval of the element with the highest priority. To read more about the Priority Queue, check out the Hint button.
class
PriorityQueue
:
```python
def __init__(self):
    pass
def insert(self, element: int) -> None:
    pass
def delete(self) -> int:
    pass
def peek(self) -> int:
    pass
def _heapify_up(self) -> None:
    pass
def _heapify_down(self) -> None:
    pass
```
Methods
- __init__(): Initializes the Priority Queue.
- insert(element: int): Inserts an element into the Priority Queue while maintaining the heap property.
- delete(): Removes and returns the element with the highest priority (maximum value for max-heap, minimum value for min-heap).
- peek() -> int: Returns the element with the highest priority without removing it from the Priority Queue.
- _heapify_up(): Called after an insert operation. If the max heap condition is violated due to the newly inserted element, this method adjusts the heap to restore the max heap property.
- _heapify_down(): Called after a delete operation. If the max heap condition is violated due to the swap and removal of the root, this method adjusts the heap to restore the max heap property.
Example
pq
=
PriorityQueue
(
)
pq
.
insert
(
3
)
pq
.
insert
(
1
)
pq
.
insert
(
4
)
print
(
pq
.
peek
(
)
)
# Should return 4 if max-heap, 1 if min-heap
pq
.
delete
(
)
print
(
pq
.
peek
(
)
)
# Should return 3 if max-heap, 1 if min-heap
Note
You can assume that the delete() and peek() methods will not be called on an empty Priority Queue.

Accepted Answer

Question 25

You start with a budget of 200 euros. You keep betting on black at the roulette table, with a probability of winning of 18/37. You start by betting 20 euros. Any time you win, you bet 20 euros again. Any time you lose, you double your previous bet. The game ends when you either run out of money or realise a profit of 40 euros.
Questions:
1. Compute the expected value of this game using Monte Carlo.
2. Compute the expected value of this game using an infinite budget.

Accepted Answer

Question 26

Create a function that takes a string S as input and returns the alphabetically smallest string that can be obtained by removing exactly one letter from S.
For example, given S = 'efg', removing one letter would result in either 'ef', 'eg' or 'fg'. Your function should return 'ef', since this is alphabetically smaller than 'eg' and 'fg'.
```python
def smallest_string_by_removing_one_letter(S: str) -> str:
    pass
```
Inputs
S: A string `S` containing alphabetic characters.
Output
Return a string representing the smallest string that can be formed by removing exactly one character from
S
.
Example Tests
- smallest_string_by_removing_one_letter('wedding') should return 'edding'.
- smallest_string_by_removing_one_letter('house') should return 'hose'.
- smallest_string_by_removing_one_letter('trading') should return 'rading'.

Accepted Answer

Question 27

Given two sorted lists, write a function to merge them into one sorted list. You can't use sort() or any other inbuilt sorting function. Please write the solution as efficiently as possible.
Bonus: What’s the time complexity?

Accepted Answer

Question 28

Develop a Python function named
$solution$
that takes an array
$A$
of
$N$
integers as input and returns the number of subarrays (or fragments) of
$A$
whose elements sum to zero. Specifically, you need to identify pairs
$(P, Q)$
where
$P \leq Q$
and the sum of the elements from index
$P$
to
$Q$
(inclusive) is zero. If the number of such subarrays exceeds
$1,000,000,000$
, the function should return
$-1$
.
Examples
For the array
$A = [2, -2, 3, 0, 4, -7]$
, the function should return
$4$
. The four subarrays that sum to zero are:
- $[2, -2]$
- $[3, 0, 4, -7]$
- $[0]$
- $[2, -2, 3, 0, 4, -7]$
Constraints:
- $N$ is an integer within the range $[1..100,000]$ .
- Each element of the array $A$ is an integer within the range $[-10,000..10,000]$ .
Write an efficient algorithm to solve this problem.

Accepted Answer

Question 29

Sudoku is a well-known puzzle. A solved Sudoku grid obeys the following rules:
- The grid has a valid structure: it has n rows and n columns (with n being an integer), divided sub blocks of sqrt(n) x sqrt(n)
- For every row, it should contain all the numbers from 1 up to and including n.
- For every column, it should contain all the numbers from 1 up to and including n.
- Every sub block should contain all the numbers from 1 up to and including n.
In this assignment, you will implement the function is_valid_sudoku that takes as input a 2-dimensional list sudoku of size n x n. This function should return True if the values in the grid obey all the Sudoku rules described above. Otherwise, it should return False.
This is an example of a Sudoku you can expect as input to the sudoku function:
[
[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 2, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 1],
[7, 1, 3, 9, 2, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4, 1, 9, 6, 3, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9]
]
We suggest you use a class / multiple functions instead of just one function, but it's up to you to come up with the most efficient and clean solution.

Accepted Answer

Question 30

Given two strings, num_str1 and num_str2, write a function to sum the two strings together without directly converting them to integers. You can convert a single characters to an integer. Write the function as efficiently as possible.
Note: Return the output in string format.

Accepted Answer

Question 31

Given two strings, num_str1 and num_str2, write a function to sum the two strings together without directly converting them to integers. You are not allowed to convert any characters to an integer. Write the function as efficiently as possible.
Note: Return the output in string format.

Accepted Answer

Question 32

Develop a simulation for the following problem. Emilie is driving in her bus. She is on a road trip and has downloaded the top 2000 songs. The songs are shuffled, so she hears a random song out of the 2000 songs whenever a song is finished. Emilie makes a bet with her travel mate that she can listen to 100 songs without repeating any song. Is this a safe bet? After how many songs do you expect that Emilie will hear a song for the second time?

Accepted Answer

Question 33

Objective
In this programming assignment, you will create a Python script that retrieves weather data from the OpenWeatherMap API and analyzes it. Your script should be able to fetch weather data for a given location, process the data, and output basic statistics about the temperature, humidity, and pressure for a specified period.
Instructions
1. Visit the OpenWeatherMap API documentation ( https://openweathermap.org/api ) to learn how to access historical weather data. Sign up for a free API key if required.
2. Write a function called fetch_weather_data(location, start_date, end_date, api_key) that takes four arguments: location (a string representing the location for which you want to fetch weather data), start_date and end_date (strings representing the date range for the data in the format 'YYYY-MM-DD'), and api_key (a string representing your API key). The function should fetch weather data for the specified location and date range and return the data as a list of dictionaries or a similar data structure.
3. Write another function called calculate_statistics(weather_data) that takes a single argument, weather_data , which is a list of dictionaries containing the weather data to be processed. The function should return a dictionary containing the average temperature, humidity, and pressure for the specified period. For example, the output could look like: {"avg_temperature": 20.5, "avg_humidity": 60.0, "avg_pressure": 1010.0} .
4. To accomplish this, you may use loops or list comprehensions to iterate through the weather data and calculate the averages. Ensure that your function can handle data with missing or non-numerical values by skipping them during the calculation.
5. Write a function called print_statistics(statistics) that takes a single argument, statistics , which is a dictionary containing the calculated statistics. The function should print the statistics in a user-friendly format, displaying the average temperature, humidity, and pressure for the specified period.
Deliverables
1. A Python script containing the fetch_weather_data(location, start_date, end_date, api_key) , calculate_statistics(weather_data) , and print_statistics(statistics) functions.
2. A brief report (1-2 paragraphs) describing your approach, the OpenWeatherMap API, any challenges you encountered, and possible improvements or alternative methods for retrieving and analyzing weather data.

Accepted Answer

Question 34

Objective
In this programming assignment, you will create a Python script that counts the frequency of words in a given text file. Your script should be able to read a text file, process its content, and output the word frequencies in descending order.
Instructions
1. Write a function called read_file(file_path) that takes a single argument, file_path , which is a string representing the path to the text file. The function should read the contents of the file and return a string containing the entire text.
2. Write another function called word_frequency(text) that takes a single argument, text , which is a string containing the text to be processed. The function should return a dictionary containing the frequency of each word in the text. For example, the output could look like: {"the": 10, "cat": 3, "sat": 2} .
3. To accomplish this, you may use string manipulation techniques and/or Python's built-in string methods to split the input text into words. Ensure that your function ignores punctuation, capitalization, and common stopwords (e.g., "a", "an", "the", "and", "in").
4. Write a function called sort_by_frequency(word_freq) that takes a single argument, word_freq , which is a dictionary containing word frequencies. The function should return a list of tuples containing the words and their frequencies, sorted in descending order by frequency. For example, the output could look like: [("the", 10), ("cat", 3), ("sat", 2)] .
5. Write a test function called test_word_frequency() that tests your word_frequency(text) and sort_by_frequency(word_freq) functions using a sample text or a small text file. Include test cases with different types of text, as well as edge cases (e.g., empty text, text containing only special characters, or text with only stopwords).
Deliverables
1. A Python script containing the read_file(file_path) , word_frequency(text) , sort_by_frequency(word_freq) , and test_word_frequency() functions.
2. A brief report (1-2 paragraphs) describing your approach, any challenges you encountered, and possible improvements or alternative methods for word frequency counting.

Accepted Answer

Question 35

You're given a list and a string. The list contains different words. Create a function, given the list and the string, that returns a list with booleans whether the words occur in the string or not. For example, the inputs (['trading', 'interview'], 'ncdtradingpmwinterkow') should return [True, False]. Try to write this function as short and efficient as possible.

Accepted Answer

Quantitative Finance

Quantitative Finance

Quantitative Finance

Quantitative Finance