1. Binary Tree Search
In a binary search tree, each node holds a value and a reference to as many as 2 child nodes, or children. The root node has no ancestors. The children are called left and right, and subtrees rooted at left and right are the left and right subtrees. If each node is considered the root of a subtree, each node value in its left subtree must be less than its own value. Likewise, each node in its right subtree must have a greater or equal value to the root. This allows for efficient searching.
For each value in a list of integers, determine if it is present in a tree. If it is, return the integer 1, otherwise, return 0.
Function Description
Complete the function isPresent in the editor below.
isPresent has the following parameters:
- BSTreeNode root: a reference to the root node of a tree of integers
- int val[q]: an array of integer items to search for
- Returns:
- int[q]: an integer array where each value at index i denotes whether val[i] is found in the BST or not
Constraints
- 1 ≤ n, q ≤ 10⁵
- 1 ≤ val[i] ≤ 10⁴
Input Format for Custom Testing
Input from stdin will be processed as follows and passed to the function:
- The first line contains an integer, n, the number of elements in the tree.
- Each of the next n lines contains an integer, the value of node[i] where 0 ≤ i ≤ n, and node[0] is the root.
- The next line contains an integer, q, the number of queries.
- Each of the next q lines contains an integer, int to search in the tree.
Sample Case 0
Sample Input
tree size n = 11
node values = [20, 10, 30, 8, 12, 25, 40, 6, 11, 13, 23]
q = 4
val = [30, 12, 45, 6]
Sample Output
1
1
0
1
2. Planning Production
Acme Corp has a number of products that need to be manufactured. However, careful planning must take place before production begins. For each product, there is a worst-case cost and an expected cost. Before starting a project, Acme must have at least enough cash on hand to pay the worst-case cost for each product. If every product is produced at expected cost, determine the minimum beginning cash requirement to get all products produced. Products can be produced in any order.
Example
Suppose that for three products these are the worst-case and expected costs:
| Product | worstCase | expected |
|---|---|---|
| 0 | 6 | 4 |
| 1 | 5 | 2 |
| 2 | 7 | 2 |
worstCase = [6, 5, 7], expected = [4, 2, 2]
For this case, the optimal order of production is product 2, 1, and 0.
- Starting with 9 units of cash on hand, they can begin production of product 2 because cash on hand (9 units) ≥ worstCase(2) = 7 units.
- After finishing product 2, they will have 9 - 2 = 7 units of cash on hand. They can then move to product 1 as cash on hand (7 units) ≥ worstCase(1) = 5 units.
- When product 1 is complete, they will have 7 - 2 = 5 units of cash on hand, which is enough to start product 0 as cash on hand (5 units) ≥ worstCase(0) = 6 units.
Function Description
Complete the function planProduction in the editor below. The function must return an integer.
planProduction has the following parameters:
- worstCase[0..n-1]: an array of n integers representing the minimum cash-on-hand to produce the ith product.
- expected[0..n-1]: an array of n integers, representing the expected cost to produce the ith product.
Constraints
- 1 ≤ n ≤ 10⁵
- 1 ≤ worstCase[i] ≤ 10⁹
- 1 ≤ expected[i] ≤ 10⁹
- It is guaranteed that expected[i] ≤ worstCase[i] for every 0 ≤ i < n.
Input Format for Custom Testing
Sample Case 0
Sample Input
3
6 5 7
4 2 2
Sample Output
9
3. K-Means Clustering
In a k-means clustering problem, a dataset contains n data points, where the ith data point is represented by the feature vector location[i]. The goal is to create k clusters, where the cluster centers or the cluster centroids can be placed at any point in the feature space. The overall quality of the clustering is measured by the maximum distance between any data point and its nearest cluster center.
The best possible quality is achieved by optimally placing the cluster centers to minimize this maximum distance. Determine this maximum distance between any data point and its nearest cluster center.
Note: The distance between two feature points x and y is defined as |x - y|, where |x| denotes the absolute value of x.
Example
n = 5
location = [4, 1, 6, 7, 2]
k = 2
Let the cluster centers be placed at points 3 and 7.
| Current Location | Closest Cluster Center | Distance |
|---|---|---|
| 1 | 1 - 3 | |
| 2 | 2 - 3 | |
| 4 | 4 - 3 | |
| 6 | 6 - 7 | |
| 7 | 7 - 7 |
Hence, the maximum of all distances is 2.
Function Description
Complete the function getMaximumDistance in the editor below.
getMaximumDistance takes the following parameters:
- int location[n]: the feature locations of all the data points
- int k: the number of clusters
Returns:
- int: the maximum distance between any data point and its nearest cluster center by optimally placing the k clusters
Constraints
- 1 ≤ n ≤ 10⁵
- 1 ≤ k ≤ n
- 1 ≤ location[i] ≤ 10⁹
Input Format for Custom Testing
Sample Case 0
Sample Input
5 2
4 1 6 7 2
Sample Output
2
我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。
We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.
