TikTok OA 真题 02/28/24

Tiktok近期更新了他们的OA题目，有一定难度，但依然全过，快来看看吧

Heap Operations Complexity

A heap is a special type of binary tree in which every parent node is less than or equal to its child node(s)(min-heap)or greater than or equal to its child node(s)(max-heap).This property must be recursively true for all sub-trees within that binary tree.
Given the following Heap class:

Class Heap {
array
// methods
insert(element)// inserts an element into the heap and maintains the heap property
removeTop()// removes and returns the top element of the heap, and restores the heap property
heapify()//transforms an arbitrary array into a heap
}

The task is to correctly implement the insert(element) and removeTop() methods, ensuring they run in O(log n) and O(log n) time complexities respectively.

• insert(element) method: Add a new element to the heap while maintaining the heap property, requiring the operation of “sift up,” where the added element is moved up the heap until the heap property is restored.
• removeTop() method: Remove the topmost element and restore the heap property using “sift down,” moving down the heap accordingly.

Which of the following code snippets achieves this?

Pick ONE OR MORE options

// Insert Element
Function insert(element){
Add element at the end of the array
Sift up the added element until the heap property is restored
}

//Remove Top Element
Function removeTop(){
     Swap the first and the last element in the array
     Remove the last element from the array
     Sift down the first element until the heap property is restored
}

//Insert Element
Function insert(element){
     Add element at the end of the array
     Sift Down the added element until the heap property is restored
 }

//Remove Top Element
Function removeTop(){
     Swap the first and the last element in the array
     Remove the last element from the array
     Sift up the last element until the heap property is restored
}

Maximum Subarray Sum

Which two pseudo-code snippets implement Kadane’s algorithm to find the maximum subarray sum?

Pick ONE OR MORE options

1.

int maxSubArraySum(int a[], int size) {
    int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;
    for(int i = 0; i < size; i++) {
        max_ending_here = max_ending_here + a[i];
        if(max_so_far < max_ending_here)
            max_so_far = max_ending_here;
        if(max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}

2.

int maxSubArraySum(int a[], int size) {
    int max_so_far = a[0];
    int curr_max = a[0];
    for(int i = 1; i < size; i++) {
        curr_max = Math.max(a[i], curr_max + a[i]);
        max_so_far = Math.max(max_so_far, curr_max);
    }
    return max_so_far;
}

3.

int maxSubArraySum(int a[], int size) {
    int max_so_far = 0;
    int max_ending_here = 0;
    for(int i = 0; i < size; i++) {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}

4.

int maxSubArraySum(int a[], int size) {
    int max_so_far = a[0];
    int curr_max = a[0];
    for(int i = 1; i < size; i++) {
        curr_max = Math.max(a[i], curr_max + a[i]);
        max_so_far = Math.max(max_so_far, curr_max);
    }
    return max_so_far;
}

Function Description:

Complete the function findMinimumSum in the editor below. findMinimumSum has the following parameters:

• int arr[]: the array to optimize

Returns:

• long:the minimum sum of products from the array

Constraints:

• 1 <= n <= 2 * 10^9
• 1 <= arr[i] <= 10^5

我们还提供OA与VO的咨询与支持服务，如果有需要，请联系我们：

chen@csoahelp.com

We also provide consultation and support services for OA and VO. If needed, please feel free to contact us：

chen@csoahelp.com