## Leetcode 1768 – Merge Strings Alternatively

You are given two strings `word1` and `word2`. Merge the strings by adding letters in alternating order, starting with `word1`. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

Example 1:

```Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1:  a   b   c
word2:    p   q   r
merged: a p b q c r
```

Example 2:

```Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1:  a   b
word2:    p   q   r   s
merged: a p b q   r   s
```

Example 3:

```Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: Notice that as word1 is longer, "cd" is appended to the end.
word1:  a   b   c   d
word2:    p   q
merged: a p b q c   d
```

Constraints:

• `1 <= word1.length, word2.length <= 100`
• `word1` and `word2` consist of lowercase English letters.

This was my solution:

``````class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
letters = []
for index, letter in enumerate(word1):
letters.append(letter)
try:
letters.append(word2[index])
except IndexError:
pass

word1_size = len(word1)
if len(word2) > word1_size:
l = list(word2[word1_size:])
letters.extend(l)

return ''.join(letters)``````

## Leetcode 79 – Boggle Game / Word Search

The link above is to the leetcode question. This problem set can be solved using backtracking and depth first search.

The first thing to do when trying to understand these leetcode problems is to actually understand the problem and understand what it is asking you to do. So in this question, you are being asked to find out if a word is found on the game board. However, there are some restrictions.

1. The word must be constructed with sequentially adjacent cells
3. You cannot use the same letter cell twice

So when we first think about this, we can think about the rule set. The third rule is a pretty big giveaway that we want to use a set. The set data structure allows you to only hold unique items.

The first and second rule first makes me think that we are going to be using back tracking. Why? Because it is a situation where we can think of the solution as using a state space tree. We can also apply a bounding function which would restrict the certain “nodes” that we can search for. this would be the adjacent cells. Some pseudo code could look like this:

``````x + 1, y
x - 1, y
x, y + 1
x, y - y``````

These would be our four conditions for the different directions. We would also need to check and ensure that we are not going out of bounds of the game board.

``````def word_found_in_board(board: list[list[str]], word: str) -> bool:
rows = len(board)
columns = len(board[0])
path = set()

def dfs(row: str, column: str, index: int):
if index == len(word):
return True
if row < 0 or column < 0 or row >= rows or column >= columns or word[index] != board[row][column] or (row, column) in path:
return False

result = dfs(row + 1, column, index + 1) or dfs(row - 1, column, index + 1) or dfs(row, column + 1, index + 1) or dfs(row, column - 1, index + 1)
path.remove((row, column))
return result
for row in range(rows):
for column in range(columns):
if dfs(row, column, 0):
return True
return False
``````

We get the length and width of the game board and call them “rows” and “columns”. Then we create a set called “path” which stores tuples. Each tuple is a row and column which meets the rules and requirements as stated above. Anything that meets the rules will be added to the “path” variable and then we recursively check each of the four adjacent positions.

Over the last few weeks I found out that the company I work for is going to be sold over to Microsoft in a very large transaction. https://www.nytimes.com/2022/01/18/business/microsoft-activision-blizzard.html

I realized that if I’m going to become a Microsoft Engineer, I might as well start learning more about the windows ecosystem. So I picked up a copy of

As well as Programming Windows

Someone on stack overflow who is a principle engineer at Microsoft recommended these books to me. The programming windows book seems a bit boring for me, as it’s mostly about creating GUI applications. The Advanced Windows book is far more interesting as it goes over what Kernel Objects are and how windows creates different things like Threads, Files, etc. I highly recommend reading both of these if you want to get into windows programming. They seem to be the most comprehensive books I’ve found online.

## Perforce for Git Users

This is a quick cheat sheet guide for git users trying to migrate over to perforce. It does not include an exhaustive list of commands, this is just a simple cheat sheet to get people started.

## Leetcode 733 – FloodFill

``````class Solution:

def fill(self, image: List[List[int]], sr: int, sc: int, starting_color: int, newColor: int) -> List[List[int]]:
if sr < 0 or sc < 0 or sr >= len(image) or sc >= len(image[0]) or image[sr][sc] != starting_color:
return
image[sr][sc] = newColor
self.fill(image, sr + 1, sc, starting_color, newColor)
self.fill(image, sr - 1, sc, starting_color, newColor)
self.fill(image, sr, sc + 1, starting_color, newColor)
self.fill(image, sr, sc - 1, starting_color, newColor)

def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
if image[sr][sc] == newColor:
return image
self.fill(image, sr, sc, image[sr][sc], newColor)
return image
``````

This is my solution for the flood fill problem in python.

## Perforce Commit Master Bash Script

So I was recently commissioned to do some work on writing up a perforce installation script and also a script to create backups to install from s3 tarballs. This is the end result of the bash script I created. There are some issues with regards to chmod permissions on the system. However, the script is fully functional.

Here is a list of commands:

./p4d_install.sh -c 1 – Uninstalls everything that the script had installed previously

./p4d_install.sh -r -b s3://bucket-url -p superuserpassword – Installs perforce from an s3 bucket tarball, it will grab the latest tarball and use this for installation.

./p4d_install.sh -p superuserpassword – will install perforce without a backup, clean installation

``````#!/bin/bash
: ' @Author Daniel Gleason
@Email [email protected]
@Script_Name p4d_install.sh
@Date 12/11/2021

-- Developer Notes --
Most if not all of the permissions of the perforce files are owned by the perforce user
Use sudo -u perforce CMD_LINE for most commands
p4dctl commands:
sudo -u perforce p4dctl stop master
sudo -u perforce p4dctl start master
sudo -u perforce p4dctl status master
'
set -e

# Prints error to stderr in red
function print_error {
local RED='\033[0;31m'
local NC='\033[0m'
printf "\${RED}\$1\${NC}\n" 1>&2;
}

# Prints out the usage of the script
function usage() {
local usage="Usage: \$0 [-r <1|0> restore_from_s3 number] [-k aws_access_key str] [-s aws_secret_key str] [-d aws_region str] [-b s3_bucket_path str] [-p perforce_password str] [-c <1|0> clean_install]";
print_error \$usage
exit 1;
}

# Removes any potential installation residue from previous runs of the script
function clean() {
sudo slay perforce 2> /dev/null
sudo rm -rf /perforce
sudo apt-get --purge remove helix-p4d -y
sudo apt-get remove awscli -y
sudo apt-get autoremove -y
sudo rm /etc/perforce/p4dctl.conf.d/master.conf 2> /dev/null
sudo userdel perforce -f 2> /dev/null
sudo delgroup perforce 2> /dev/null
}

# Get inputs
while getopts "r:k:s:d:b:p:c:" flag; do
case "\${flag}" in
r)
export restore=\${OPTARG}
;;
k)
export AWS_ACCESS_KEY_ID=\${OPTARG}
;;
s)
export AWS_SECRET_ACCESS_KEY=\${OPTARG}
;;
d)
export AWS_DEFAULT_REGION=\${OPTARG}
;;
b)
export S3_BUCKET_PATH=\${OPTARG}
;;
p)
;;
c)
export CLEAN=1
clean
;;
*)
usage
;;
esac
done

function install_p4d() {
local ubuntu_distro=`lsb_release --codename --short` # focal, xenial, etc
wget -qO - https://package.perforce.com/perforce.pubkey | sudo apt-key add -
sudo rm /etc/apt/sources.list.d/perforce.list 2> /dev/null # Delete perforce apt file if it already eixsts, ignore the error output.
echo "deb http://package.perforce.com/apt/ubuntu \$ubuntu_distro release" | sudo tee -a /etc/apt/sources.list.d/perforce.list
sudo apt-get update
sudo apt-get install helix-p4d -y
}

function configure_p4d() {
sudo mkdir /perforce 2> /dev/null
sudo /opt/perforce/sbin/configure-helix-p4d.sh -n master -p ssl:1666 -r /perforce -u perforce -P \$PERFORCE_PASSWORD
sudo chown -R perforce.perforce /perforce
sudo usermod -aG perforce ubuntu # Add ubuntu user to perforce group
sudo -u perforce mkdir /perforce/depots
# All depot data will be located in /perforce/depots
p4 configure set master#server.depot.root=/perforce/depots
sudo chmod -R 777 /perforce/
sudo chmod -R 770 /perforce/depots
}

# Just some sueful tools I like to use
function install_prerequisites() {
sudo apt-get install awscli -y
sudo apt-get install slay -y
sudo apt-get install mlocate -y
}

# Produces credentials file in ~/.aws/credentials and config file in ~/.aws/config used by aws cli
function setup_aws_cli() {
aws configure set aws_access_key_id \$AWS_ACCESS_KEY_ID
aws configure set aws_secret_access_key \$AWS_SECRET_ACCESS_KEY
aws configure set default.region \$AWS_DEFAULT_REGION
}

function restore_from_s3_backup() {
echo 'Restoring from s3 backup'
sudo mkdir /perforce/backups 2> /dev/null
sudo chown perforce.perforce /perforce/backups
sudo -u perforce p4dctl stop master

pushd /perforce/backups/
local most_recent_checkpoint_s3=\$(aws s3 ls \$S3_BUCKET_PATH | sort | tail -n 1 | awk '{print \$4}')
local backup_dir=`pwd`
sudo -u perforce aws s3 cp \$S3_BUCKET_PATH/\$most_recent_checkpoint_s3 .
sudo -u perforce tar -xf \$most_recent_checkpoint_s3
sudo -u perforce rsync -a perforce/depots/ /perforce/depots/ # Move the depot files over

# Get checkpoint file we just extracted from the tarball
pushd perforce/backups/
local most_recent_checkpoint_file=`ls -t master.ckp.*.gz | head -1`
popd

# Restore the checkpoint
pushd /perforce/root/
sudo rm -rf /perforce/root/db.*
sudo -u perforce p4d -r . -jr \$backup_dir/perforce/backups/\$most_recent_checkpoint_file
popd

# Remove extracted files to keep things clean
sudo rm -rf perforce/
popd

sudo sed -i '/P4SSLDIR\s.*=\s.*ssl/a \\tP4PORT=ssl:1666' /etc/perforce/p4dctl.conf.d/master.conf

# Change permissions of db files
sudo chmod -R 600 /perforce/root/db.*

# Generate new ssl certs
pushd /perforce/root/
sudo chmod -R 0700 ssl/
sudo rm ssl/privatekey.txt ssl/certificate.txt
P4SSLDIR=ssl sudo -Eu perforce p4d -Gc
popd

# Start p4d
sudo -u perforce p4dctl start master

# Run p4 trust on the new server setup.
p4 trust -f -y
}

function main() {

if [ ! \$CLEAN ]
then
install_prerequisites
fi

then
install_p4d
configure_p4d
fi

if [ \$AWS_ACCESS_KEY_ID ] && [ \$AWS_SECRET_ACCESS_KEY ] && [ \$AWS_DEFAULT_REGION ]
then
setup_aws_cli
fi

if [ \$restore ] && [ \$restore -eq 1 ]
then
if [ \$S3_BUCKET_PATH ]
then
echo Bucket Path: \$S3_BUCKET_PATH
restore_from_s3_backup
else
print_error "Error: restore flag must be 1 and s3_bucket_path must be set to restore from a backup."
usage
fi
fi
}

main``````

This next script is used in conjunction with the script above to create backups. You can run this script on a cron task and it will create a tarball and create a new perforce checkpoint and upload it to s3. It does not have functionality to setup an aws cli configuration. You will need to do that yourself, or give the aws instance the permissions it needs. I also hard coded the s3 backup location, you will need to change this to a variable and use getopts or just change the hard coded path for the bucket url.

``````#!/bin/bash
: ' @Author Daniel Gleason
@Email [email protected]
@Script_Name create_backup.sh
@Date 12/13/2021
'

function get_most_recent_checkpoint() {
pushd /perforce/backups/ > /dev/null
echo `ls -t master.ckp.*.gz | head -1`
popd > /dev/null
}

function make_backup() {
pushd /perforce > /dev/null
mkdir backups 2> /dev/null
sudo chown -R perforce.perforce backups/
pushd backups/
# Creates a checkpoint in /perforce/backups using the p4 database in /perforce/root and the journal in /perforce/root
sudo -u perforce p4d -r /perforce/root -J /perforce/root/journal -z -jc `pwd`/master

# Create tarball of depots and the checkpoint
local backup_name="\$(date +"%m.%d.%Y.%I.%M.%p")_backup.tar.gz"
local most_recent_checkpoint=\$(get_most_recent_checkpoint)
sudo -u perforce tar -Ppzcf \$backup_name /perforce/depots/ /perforce/backups/\$most_recent_checkpoint
aws s3 cp `pwd`/\$backup_name " S3_LOCATION "
popd > /dev/null
popd > /dev/null
}

make_backup
``````

## How to sort all elements in an array such that all negative numbers are first, and then positive numbers.

``````    int ar[] = {-2,3,4,-5,6,9,-1,-5};
int i = 0;
int j = sizeof(ar) / sizeof(ar[0]) - 1;
while(i <= j)
{
while(ar[i] < 0) { i++; }
while(ar[j] >= 0) { j--; }

if (i < j) {
std::swap(ar[i], ar[j]);
}
}``````

So this code is pretty simple. First we are creating an array of numbers, some negative, some positive, not in any order. Second we determine two index values, one at the beginning of the array and one at the end of the array. Then, as long as the starting index is less than or equal to the ending index, we loop.

After this we basically find the two indices to swap. We do two while loops. While the element in ar[i] is less than 0, which means it’s negative, increase i by 1. We stop once ar[i] is not negative. Then we do another loop where ar[j] is greater than or equal to zero, which means it is positive, and we keep doing this until a number that is not positive is found.

Finally, we just swap the values once we have found one that is positive and one that is negative. The final if statement if (i < j) is to make sure that we don’t swap it incorrectly after i is incremented by 1.

This is just a simple leetcode style question I found the solution to so I wanted to share it. The time complexity should be O(N).

## What is C K&R Syntax?

Okay I just want to start out and say that this is outdated. The only reason why I am posting about this is because I find the history of technology very interesting and I want to share what I’ve read up on.

Alright so, if you’re a programmer you’re probably aware of multiple types of syntax. With Python we have:

``````def MyFunction:
print("Hello World")

MyFunction()``````

In Java we have:

``````public static void main(String[] args)
{
Chicken();
}

void Chicken()
{
System.out.println("Hello World");
}``````

In standard C/C++ we have:

``````int main(void)
{
printf("Hello World");
return 0;
}``````

But in the old days we had something called K & R syntax in C. It looked like this:

``````int Chicken(a, b, c)
int a;
float b;
char c;
{
return 0;
}``````

What’s interesting about this is that some modern compilers still support this syntax but will scream at you and tell you to not do it. However there’s some important things to note here. Look at the following code block.

``````int Chicken(a,b,c)
int a;
int b;
{

}``````

If you notice, I never declared the data type for c. By default, the compiler will use integer data types for anything that is undeclared. So the entire concept behind K & R syntax is that you define the function name, and it’s inputs. Then, you define the types of inputs afterwards. It’s very different from what I was taught in university. I just wanted to share this. Hopefully someone finds this interesting. 🙂

## isPalindrome(int n) – Leetcode question 9

https://leetcode.com/problems/palindrome-number/

So I was doing a few leetcode questions today. Honestly, I just found this one and it seemed interesting because it was easy, and it had multiple solutions to the problem. You could take multiple jabs at it from different angles. For example, you could simply do math operations on it and get the modulo of 10 of the number which would give you the last digit, or you could do string manipulation.

You could also create a stack and a queue of each value and do the modulo of 10 for each number and then compare the stack and queue values because of the FIFO/LIFO rules of these data structures. However, this is not only inefficient in time complexity, but also in space because we are creating two unnecessary data structures.

We could also just convert the number to a string and then compare each value from the ends, for example:

``````bool isPalindrome(int x) {
string s = to_string(x);

int len = s.size() - 1;
int n = 0;

while(n < len)
{
if (s[n] != s[len])
return false;

len--;
n++;
}

return true;
}``````

However, this solution is not very good either because we are converting the integer to a string, which I believe is an O(N) time complexity, because each character has to be individually converted to a number.

So I found another solution which basically takes advantage of how math works.

``````bool isPalindrome(int n)
{
int original = n;

int reversed = 0;

while(n > 0)
{
reversed = reversed * 10 + n % 10;
n /= 10;
}

if (original == reversed)
return true;
else
return false;
}``````

This may not even be the most efficient solution as I may be ignorant on other mathematical concepts and how they work. However, given this, the math is simple. We know that n % 10 will give us the last digit in the number. So for example: 123 % 10 would give us 3.

Because we know this, we can simply loop through n, and say, while n is not 0, the reversed version of the number will be itself times 10 + the remainder (n % 10).

So given reversed = 0 for the first iteration of our loop, the math would be:
0 = 0 * 10 + 3

Obviously, this is assuming that n is 123. So after the first iteration, reversed will equate to 3. On the second iteration, after we divide x by 10, it would be:

3 = 3 * 10 + 2, which is 32, so reversed is now 32, which is obviously the first two digits in reverse of 123, it’s 32. If we do it again we will get the one. Let’s do it.

If we do n % 10 again, we get a remainder of 1, or our last digit. So then we take 32 = 32 * 10 + 1 which is 321. And there we go, we have the numbers in reverse. The last thing to do is to essentially check if the original value of n, is equal to this newly reversed value of n.

Return true if they are equal, return false otherwise.

Anyways, hopefully this helps other people who are trying to practice algorithms!

## What is the build order of a C program? (Interview Questions)

Today I had an interview and I incorrectly answered a question. It was silly because I remember reading about this a long time ago honestly in a C++ book written by IBM from the 1990s. It’s one of the first books I read growing up when learning to code. My mother bought it for me from Salvation Army. It had a yellowish-orange and red cover. Anyways, just as a personal note and so that I don’t forget this again.

The order is as follows:

• Preprocessing – this is essentially the stage where the preprocessor parses the source files and looks for macros. This one is the one I’m most familiar with due to my heavy usage of Unreal Engine. Unreal Engine uses a lot of macros, and conditional compilation instructions.

Just as an example, in unreal engine there’s tons of conditional compilation instructions like this:

``````#if WITH_SERVER_CODE
#endif

#if WITH_EDITOR
#endif``````

``````#define paster( n ) printf_s( "token" #n " = %d", token##n )