[Google Singapore OA Questions] GCD and Trapped Rain Water in C++ and Python

Google Singapore OA Question (Summer 2020 Internship)

Code : LeetCode

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <limits>

// compute the GCD(Greatest Common Divisor)
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int n; //represents the depth of the binary tree
    std::cin >> n;

    // tree is empty
    if (n == -1) {
        std::cout << -1 << std::endl;
        return 0;
    }

    // The tree is represented as a vector of vectors
    std::vector<std::vector<int>> tree(n + 1);

    for (int i = 0; i <= n; ++i) {
        std::string line;
        std::getline(std::cin >> std::ws, line); // remove ws(WhiteSpace) and read
        std::istringstream iss(line);
        int value;
        // The extraction operator (>>) reads the next integer from the stream
        while (iss >> value) {
            tree[i].push_back(value);
        }
    }
    // Result:
    // tree[0] = {3},
    // tree[1] = {6,9},
    // etc...s

    // print tree levels (for check)
    for (int i = 0; i <= n; ++i) {
        std::cout << "Level " << i << ": ";
        for (int value : tree[i]) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }

    int max_gcd = std::numeric_limits<int>::min(); //max_gcd = -2147483648
    int min_gcd = std::numeric_limits<int>::max(); //min_gcd = 2147483647
    bool has_siblings = false;

    // Calculating GCD for Sibling Pairs
    for (const auto& level : tree) {
        for (size_t i = 0; i + 1 < level.size(); i += 2) {

            // updates max and min values until 'has_siblings' is false
            if (level[i] != -1 && level[i + 1] != -1) {
                int current_gcd = gcd(level[i], level[i + 1]);
                max_gcd = std::max(max_gcd, current_gcd);
                min_gcd = std::min(min_gcd, current_gcd);
                has_siblings = true;
            }
        }
    }

    // Output
    if (!has_siblings) {
        std::cout << 0 << std::endl;
    } else {
        std::cout << (max_gcd - min_gcd) << std::endl;
    }
    return 0;
}

Reviews

1. Both methods serve the same purpose of adding an elements

• C++ push_back() : Used in the std::vector classs
• Python append() : Used in lists to add an elements

2. In C++, size_t

• Unsigned integer type : Ensure non-negative values

3. Int is generally a 32-bit integer, and this value is usually 2,147,483,647

4. Buffer Flush

• Buffer flushing ensures that all data stored in the output buffer is immediately sent to the output device(screen)

• In C++, buffer flushing can be done automatically (using std::endl) or manually (using std::flush)

    #include <iostream>
    #include <chrono>
    #include <thread>
  
    int main() {
        // Immediately output the data stored in the buffer
        std::cout << "Hello, World!" << std::endl;  // std::endl prints '\n' and flushes the buffer.
  
        // Print a newline but do not flush the buffer
        std::cout << "Hello, again!\n";  // '\n' alone does not flush the buffer.
  
        // Manually flush the buffer
        std::cout << std::flush;  // Manually flush the buffer.
  
        // Add a short delay
        std::this_thread::sleep_for(std::chrono::seconds(2));
  
        // Check if there is any output left in the buffer
        std::cout << "Buffer flush test\n";
  
        // Forcefully flush the buffer with std::flush
        std::cout << std::flush;
  
        return 0;
    }    
  

• Frequent flushing can degrade performance due to the overhead of multiple I/O operations

5. Batch Processing

• A computer technique in which a group of tasks or jobs is executed sequentially without manual intervention

  Useful for automating repetitive tasks, processing large amount of data.

• In this code, Output is collected and processed in batches, flushing the buffer frequently is unnecessary

    std::ostringstream oss;
    for (int i = 0; i < 1000; ++i) {
        oss << i << ' ';
    }
    std::cout << oss.str() << std::endl;  // Flushes once at the end
  

Calculating GCD in Python

1. Code

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def main():
    import sys
    input = sys.stdin.read
    data = input().splitlines() # data is stored as a list of strings at each newline(\n)
    # Result:
    # data = [
    # "2",
    # "3 4",
    # "3 5 6 8"
    # ]

    # convert chart to integer
    n = int(data[0])
    if n == -1:
        print(-1)
        return

    tree = []
    for i in range(1, n + 2):
        level = list(map(int, data[i].split()))
        tree.append(level)

    # Result
    for i in range(n + 1):
        print(f"Level {i}: {' '.join(map(str, tree[i]))}")

    # ensure that the first comparison will always correctly update these values
    max_gcd = float('-inf')
    min_gcd = float('inf')
    has_siblings = False

    # Calculate the GCD by examining silbling node pairs at each level
    for level in tree:
        for i in range(0, len(level) - 1, 2):
            if level[i] != -1 and level[i + 1] != -1:
                current_gcd = gcd(level[i], level[i + 1])
                max_gcd = max(max_gcd, current_gcd)
                min_gcd = min(min_gcd, current_gcd)
                has_siblings = True

    if not has_siblings:
        print(0)
    else:
        print(max_gcd - min_gcd)

if __name__ == "__main__":
    main()

Review

1. map(function, iterable)

• Example

    numbers = [1, 2, 3, 4, 5]
    squares = map(lambda x: x**2, numbers)
  
    print(list(squares))  # Output: [1, 4, 9, 16, 25]
  

• Concise way to apply a function to all items in an iterable

42.Trapped Rain Water

1. Code

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) return 0;

        int left = 0, right = height.size() -1;
        int left_max = 0, right_max = 0;
        int water = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    water += left_max - height[left];
                }
                ++left;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    water += right_max - height[right];
                }
                --right;
            }
        }
        return water;
    }
};

Review

1. Place two pointers, left and right, at the ends of the array. (Two-Pointer Technique)

• Initialize left_max, right_max, and water to 0

2. Repeat while the condition left < right is satisfied:

• A. When height[left] <= height[right]:

  • Update left_max by comparing it with height[left]

    If height[left] is less than left_max, add left_max - height[left] to the water.

  • Move left to the right.

• B. When height[left] > height[right]:
  

  • Update right_max by comparing it with height[right].

  • If height[right] is less than right_max, add right_max - height[right] to the water.

  • Move right to the left.

3. Repeat until the left and right pointers meet.

• Finally, return the total amount of water stored in water.

4. Greedy Algorithm

• The algorithm updates the left_max and right_max values
  to ensure the maximum height seen so far is tracked.