Author: robert

Posted on by

1678. Goal Parser Interpretation

You own a Goal Parser that can interpret a string command. The command consists of an alphabet of "G", "()" and/or "(al)" in some order. The Goal Parser will interpret "G" as the string "G", "()" as the string "o", and "(al)" as the string "al". The interpreted strings are then concatenated in the original order.

Given the string command, return the Goal Parser‘s interpretation of command.

Example 1:

Input: command = "G()(al)"
Output: "Goal"
Explanation: The Goal Parser interprets the command as follows:
G -> G
() -> o
(al) -> al
The final concatenated result is "Goal".

Example 2:

Input: command = "G()()()()(al)"
Output: "Gooooal"

Example 3:

Input: command = "(al)G(al)()()G"
Output: "alGalooG"
class Solution {
public:
    string interpret(string command) {
        string result = "";
        for(int i=0; i<command.size(); i++){
            if(command[i] == 'G') result += "G";
            else if(command[i] == '(' && command[i+1] == ')') {
                result += "o";
                i++;
            }
            else if(command[i] == '(' && command.substr(i,4) == "(al)"){
                result += "al";
                i += 3;
            }
        }
        return result;
    }
};

Posted on by

2559. Count Vowel Strings in Ranges

You are given a 0-indexed array of strings words and a 2D array of integers queries.

Each query queries[i] = [l<sub>i</sub>, r<sub>i</sub>] asks us to find the number of strings present in the range l<sub>i</sub> to r<sub>i</sub> (both inclusive) of words that start and end with a vowel.

Return an array ans of size queries.length, where ans[i] is the answer to the ith query.

Note that the vowel letters are 'a', 'e', 'i', 'o', and 'u'.

Example 1:

Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
Output: [2,3,0]
Explanation: The strings starting and ending with a vowel are "aba", "ece", "aa" and "e".
The answer to the query [0,2] is 2 (strings "aba" and "ece").
to query [1,4] is 3 (strings "ece", "aa", "e").
to query [1,1] is 0.
We return [2,3,0].

Example 2:

Input: words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
Output: [3,2,1]
Explanation: Every string satisfies the conditions, so we return [3,2,1].
class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        vector<int> prefixSum(words.size()+1,0);
        vector<int> result;

        function<bool(char)> isVowel = [](char ch)->bool{
            if( ch == 'a' || ch == 'e' || ch =='i' || ch == 'o' || ch=='u'){
                return true;
            }

            return false;
        };

        int index = 1;
        for( string str:words){
            if( isVowel(str.front()) && isVowel(str.back()) ){
                prefixSum[index] = prefixSum[index-1]+1;
            } else
                prefixSum[index] = prefixSum[index-1];

            index++;
        }
 

        for( auto q: queries ){
          result.push_back( prefixSum[q[1]+1] - prefixSum[q[0]] );
        }

        return result;
    }
};
Posted on by

1030. Matrix Cells in Distance Order

You are given four integers row, cols, rCenter, and cCenter. There is a rows x cols matrix and you are on the cell with the coordinates (rCenter, cCenter).

Return the coordinates of all cells in the matrix, sorted by their distance from (rCenter, cCenter) from the smallest distance to the largest distance. You may return the answer in any order that satisfies this condition.

The distance between two cells (r<sub>1</sub>, c<sub>1</sub>) and (r<sub>2</sub>, c<sub>2</sub>) is |r<sub>1</sub> - r<sub>2</sub>| + |c<sub>1</sub> - c<sub>2</sub>|.

Example 1:
Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]
Explanation: The distances from (0, 0) to other cells are: [0,1]

Example 2:
Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Explanation: The distances from (0, 1) to other cells are: [0,1,1,2]
The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.

Example 3:
Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Explanation: The distances from (1, 2) to other cells are: [0,1,1,2,2,3]
There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].


class Solution {
public:

    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {

        queue<pair<int,int>> q;        
        vector<vector<int>> result;

        vector<vector<bool>> visited( rows , vector<bool>(cols, false));        
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        q.push({rCenter, cCenter});
        visited[rCenter][cCenter] = true;

        while( !q.empty() ){
            int size = q.size();
            while(size > 0){
                auto [currentRow, currentCol] = q.front();              
                result.push_back({currentRow, currentCol});

                q.pop();
                for (auto [dr, dc] : directions) {
                    int newRow = currentRow + dr;
                    int newCol = currentCol + dc;


                    if( newRow >= 0 && newRow < rows && newCol >=0 && newCol < cols 
                        && !visited[newRow][newCol]){                        
                        q.push({newRow,newCol});
                        visited[newRow][newCol] = true;
                    }
                }
                size--;
            }

        }
        return result;
        
    }
};
Posted on by

Maximum Score After Splitting a String

C++ Solution

class Solution {
public:
    int maxScore(string s) {
        int ones = count(s.begin(), s.end(), '1'); // Total 1's in the string
        int zeros = 0, result = 0; // Initialize count of zeros and result

        for (int i = 0; i < s.size() - 1; i++) { // Iterate but exclude the last split point
            if (s[i] == '1') 
                ones--; // Move '1' from right to left
            else 
                zeros++; // Increment count of '0's in the left part

            result = max(result, zeros + ones); // Update the maximum score
        }

        return result; // Return the best score
    }
};

Posted on by

90% of CS graduates can’t figure this out

Someone important on X posted:

https://x.com/vikhyatk/status/1873033432705712304

i have a very simple question i ask during phone screens: print each level of a tree on a separate line. 90% of CS grad candidates just can’t do it. someone needs to investigate these universities.

half the replies are saying i’m trolling because no one asks questions this simple. the other half are saying it’s a retarded leetcode question, they never have to use trees irl, why is it even relevant because ChatGPT can do it etc.

Solution with Boost Library

#include <boost/property_tree/ptree.hpp>
#include <iostream>
#include <string>
#include <queue>
using namespace std;

void levelOrder(const boost::property_tree::ptree& tree) {
    std::queue<boost::property_tree::ptree> q;
    q.push(tree);

    while (!q.empty()) {
        int levelSize = q.size();
        while (levelSize > 0) {
            boost::property_tree::ptree current = q.front();
            q.pop();

            // Print the value at the current level
            auto val = current.get_value<std::string>("");
            if (val != "")
                std::cout << current.get_value<std::string>("")<<" ";

            // Add children nodes to the queue
            for (const auto& node : current) {
                q.push(node.second);
            }
            --levelSize;
        }
        std::cout << std::endl;  // Newline after printing one level
    }
}

int main() {
    // Create a Boost property tree
    boost::property_tree::ptree tree;

    // Insert elements to mimic a binary tree
    tree.put("root.value", "10");

    // Left child
    tree.put("root.left.value", "5");
    tree.put("root.left.left.value", "3");
    tree.put("root.left.right.value", "7");

    // Right child
    tree.put("root.right.value", "15");
    tree.put("root.right.right.value", "20");

    levelOrder(tree);

    return 0;
}

So I wanted to try out using Boost with CLion. What a nightmare. First the issue of using a flatpak install ruins everything when it comes to integrating with the system.

Second using a property tree was a bad idea. I should have went with a graph. Since the original post on X was talking about to solution with a graphic of a binary tree, I tried the property_tree in boost and I didn’t like the output of the tree still, nor the key value pair structure of it.

I will follow up later with a Breath First Search on a Undirected Graph from Boost library next time.

Posted on by

Count Ways To Build Good Strings

Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:

  • Append the character '0' zero times.
  • Append the character '1' one times.

This can be performed any number of times.

A good string is a string constructed by the above process having a length between low and high (inclusive).

Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 10<sup>9</sup> + 7.

Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation: 
One possible valid good string is "011". 
It can be constructed as follows: "" -> "0" -> "01" -> "011". 
All binary strings from "000" to "111" are good strings in this example.

Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: The good strings are "00", "11", "000", "110", and "011".

Solution: fastest one is using tabulation dynamic programming technique.

    int countGoodStrings(int low, int high, int zero, int one) {
        int sum[100001];
        sum[0] = 1;
        for (int i = 1; i <= high; i++)
        {
            long long sumCur = 0;
            if (i >= zero)
                sumCur += sum[i-zero];
            if (i >= one)
                sumCur += sum[i-one];
            if (sumCur > 0x3000000000000000ll)
                sumCur %= 1000000007;
            sum[i] = sumCur % 1000000007;
        }

        long long sumTotal = 0;
        for (int i = low; i <= high; i++)
            sumTotal += sum[i];
        return sumTotal % 1000000007;
    }

Way slower approach is to use a map in your code for memoization, and a recursive DFS method.

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        map<int, int> dp;
        long mod = pow(10,9) +7;    
        function<int(int)> dfs = [&](int length) -> int{
            
            if( length > high ) return 0;

            if(dp.find(length) != dp.end() )
                return dp[length];

            int count = ( length >= low) ? 1 : 0;
            count = (count + dfs(length + zero)) % mod;
            count = (count + dfs(length + one)) % mod;
            
            return dp[length] = count;
        };

        return dfs(0);    
    }
};

Posted on by

Custom Dockerfile for PHP 5.6 / Apache / WPCLI

I wanted to get my old wordpress 3.4 websites running again, so I had to build a couple docker images, and a docker compose file. This starts with Ubuntu 16, as I thought I would be able to get PHP5 on there. But in reality this container comes with PHP7 hooked up in the apt sources. So I ended up compiling PHP 5.6.40 in the container.

Base Image

# Use an Ubuntu base image
FROM ubuntu:16.04

# Set environment variables
ENV DEBIAN_FRONTEND=noninteractive
ENV PHP_VERSION=5.6.40

# Install dependencies
RUN apt-get update && apt-get install -y --no-install-recommends \
    build-essential \
    apache2 \
    apache2-dev \
    libxml2-dev \
    libcurl4-openssl-dev \
    libssl-dev \
    libmysqlclient-dev \
    libreadline-dev \
    libzip-dev \
    libbz2-dev \
    libjpeg-dev \
    libpng-dev \
    libxpm-dev \
    libfreetype6-dev \
    libmcrypt-dev \
    libicu-dev \
    zlib1g-dev \
    libxslt-dev \
    libsodium-dev \
    libmagickwand-dev \
    libpcre3-dev \
    curl \
    wget \
    re2c \
    bison \
    && apt-get clean \
    && rm -rf /var/lib/apt/lists/*

# Download and extract PHP source
RUN wget --no-check-certificate https://www.php.net/distributions/php-${PHP_VERSION}.tar.gz && \
    tar -xvf php-${PHP_VERSION}.tar.gz && \
    rm php-${PHP_VERSION}.tar.gz

# Change directory to PHP source
WORKDIR php-${PHP_VERSION}

# Install MySQL development libraries for the mysql extension
RUN apt-get update && apt-get install -y --no-install-recommends libmysqlclient-dev && \
    apt-get clean && rm -rf /var/lib/apt/lists/*

# Reconfigure and build PHP to include the MySQL extension
RUN ./configure \
    --prefix=/usr/local/php5.6 \
    --with-apxs2=/usr/bin/apxs \
    --enable-maintainer-zts \
    --with-mysql \
    --with-mysqli \
    --with-pdo-mysql \
    --enable-mbstring \
    --enable-calendar \
    --enable-ctype \
    --with-curl \
    --enable-exif \
    --enable-ffi \
    --enable-fileinfo \
    --enable-filter \
    --enable-ftp \
    --with-gd \
    --with-gettext \
    --with-iconv \
    --with-imagick \
    --with-libdir=/usr/lib/x86_64-linux-gnu \
    --enable-json \
    --with-libxml-dir=/usr \
    --enable-mbstring \
    --with-mysqli=mysqlnd \
    --with-openssl \
    --enable-pcntl \
    --with-pcre-dir=/usr \
    --enable-pdo \
    --enable-phar \
    --enable-posix \
    --with-readline \
    --enable-session \
    --enable-shmop \
    --enable-simplexml \
    --enable-sockets \
    --with-sodium \
    --enable-sysvmsg \
    --enable-sysvsem \
    --enable-sysvshm \
    --enable-tokenizer \
    --enable-xml \
    --enable-xmlreader \
    --enable-xmlwriter \
    --with-xsl \
    --enable-opcache \
    --enable-zip \
    --with-zlib && \
    make -j$(nproc) && \
    make install

# Create a symlink for PHP to /bin
RUN ln -s /usr/local/php5.6/bin/php /bin/php

# Enable mod_rewrite module and configure Apache to allow .htaccess files
RUN a2enmod rewrite

# Configure Apache for PHP
RUN echo "LoadModule php5_module /usr/local/php5.6/lib/php/extensions/no-debug-non-zts-20131226/libphp5.so" >> /etc/apache2/apache2.conf && \
    echo "AddType application/x-httpd-php .php" >> /etc/apache2/apache2.conf && \
    echo "DirectoryIndex index.php" >> /etc/apache2/apache2.conf

# Allow overrides for .htaccess files in the Apache configuration
RUN echo "<Directory /var/www/html>" >> /etc/apache2/apache2.conf && \
    echo "    AllowOverride All" >> /etc/apache2/apache2.conf && \
    echo "</Directory>" >> /etc/apache2/apache2.conf

# Switch Apache to prefork MPM if needed (threaded MPM requires threadsafe PHP)
RUN a2dismod mpm_event mpm_worker && a2enmod mpm_prefork

# Copy test PHP file
RUN echo "<?php phpinfo(); ?>" > /var/www/html/phpinfo.php

# Expose HTTP port
EXPOSE 80

# Start Apache
CMD ["apachectl", "-D", "FOREGROUND"]

The next step was adding WPCLI

# Use your custom PHP image as the base
FROM php56:latest


# Install dependencies for WP-CLI
RUN apt-get update && apt-get install -y \
    curl \
    ca-certificates \
    && rm -rf /var/lib/apt/lists/*

# Ensure PHP is linked to /usr/local/bin/php (change path based on where PHP was compiled)
ENV PATH="/usr/local/bin:/usr/local/php5.6/bin:$PATH"
RUN ln -s /usr/local/php-5.6.40/bin/php /usr/local/bin/php

# Install WP-CLI
RUN curl -O https://raw.githubusercontent.com/wp-cli/builds/gh-pages/phar/wp-cli.phar && \
    php wp-cli.phar --info && \
    chmod +x wp-cli.phar && \
    mv wp-cli.phar /usr/local/bin/wp

# Verify WP-CLI installation
RUN wp --info

# Expose port 80 (optional)
EXPOSE 80

# Start Apache (or your desired service)
CMD ["apache2ctl", "-D", "FOREGROUND"]

And then using docker compose to bring up Apache / PHP / MYSQL services online:

version: '3.7'
services:
  mysql:
    image: mysql/mysql-server:5.7.37
    environment:
     MYSQL_DATABASE: webdesign
     MYSQL_USER: ROOT
     MYSQL_PASSWORD: PASSWORD
    restart: always
    volumes:
     - ./init.sql:/docker-entrypoint-initdb.d/init.sql
    ports:
     - "3307:3306"
  legacy-php:
    depends_on:
     - mysql
    image: php5.6-apache-wpcli
    volumes:
     - .:/var/www/html
    ports:
     - "80:80"

Over writing the WordPress 3.4 files with 3.7 allowed me to export an XML.

Posted on by

Set Matrix Zeros

class Solution {
  public:
    void setMatrixZeroes(vector<vector<int>> &mat) {
        int n = mat.size();
        int m = mat[0].size();
    
        bool firstRowHasZero = false;
        bool firstColHasZero = false;
    
        // Check if the first row has any zero
        for (int j = 0; j < m; j++) {
            if (mat[0][j] == 0) {
                firstRowHasZero = true;
                break;
            }
        }
    
        // Check if the first column has any zero
        for (int i = 0; i < n; i++) {
            if (mat[i][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }
    
        // Use the first row and column to mark zeros
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (mat[i][j] == 0) {
                    mat[i][0] = 0;
                    mat[0][j] = 0;
                }
            }
        }
    
        // Update the matrix based on the markers
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (mat[i][0] == 0 || mat[0][j] == 0) {
                    mat[i][j] = 0;
                }
            }
        }
    
        // Update the first row if needed
        if (firstRowHasZero) {
            for (int j = 0; j < m; j++) {
                mat[0][j] = 0;
            }
        }
    
        // Update the first column if needed
        if (firstColHasZero) {
            for (int i = 0; i < n; i++) {
                mat[i][0] = 0;
            }
        }
        
    }
};

The idea here is using the first row and column as a Dynamic Programming table to mark which rows and columns need to be zeroed out.
That being done, then first column and row itself is updated at the end.

Posted on by

Zigzag string conversion solution in C++

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this

Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"
P   A   H   N
A P L S I I G
Y   I   R

Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI"
P     I    N
A   L S  I G
Y A   H R
P     I

Solution

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.size();
        if (n == 1 || numRows < 2 || n <= numRows) return s;
        
        string ans;
        
        for (int i = 0; i < numRows; i++) {
            int j = i;
            ans.push_back(s[i]); // First character of the row
            int down = 2 * (numRows - 1 - i); // Downward step size
            int up = 2 * i; // Upward step size
            
            if (up == 0 && down == 0) return s; // If no movement, just return the string
            
            while (j < n) {
                j += down;
                if (j < n && down > 0) ans.push_back(s[j]);
                
                j += up;
                if (j < n && up > 0) ans.push_back(s[j]);
            }
        }
        
        return ans;
    }
};

int main() {
    Solution solution;
    string s = "PAYPALISHIRING"; // Example input
    int numRows = 3; // Example row count
    
    string result = solution.convert(s, numRows);
    cout << "Zigzag Conversion: " << result << endl; // Output the result
    return 0;
}
Posted on by

Search Sorted Matrix Solution in C++

The idea here is to implement binary search after discovering the correct row.


#include <bits/stdc++.h>
using namespace std;



class Solution {
  public:
  
  
    // Function to search a given number in row-column sorted matrix.
    bool searchMatrix(vector<vector<int>> &mat, int x) {
        // code here
        vector<int>*row = nullptr;
        int rows = mat.size();
        int cols = mat[0].size();
        
        for( int i = 0; i < rows; i++ ){
            if( mat[i][0] <= x && mat[i][cols-1] >= x ){
                row = &(mat[i]);
                break;
            }
        }
        
        if( row == nullptr ) return false;
        
        auto binarySearch = [row, x]( int low, int high ) -> bool{
            
            while( low <= high ){
                int mid = low + (high-low)/2;
            
                if( (*row)[mid] == x ){
                    return true;
                }else if((*row)[mid] < x ){
                    low =  mid + 1;
                } else {
                    high = mid - 1;
                }
                
            }
            
            return false;
            
        };   
        
        return binarySearch(0, cols -1 );
    }
};