GPG Cheatsheet

GnuPG (GNU Privacy Guard) is a tool for encrypting and signing data. It is a completely free implementation of the OpenPGP standard (defined by RFC4880), which is also known as GPG. I myself prefer the command line over any GUI for GnuPG, because it is typically faster to execute stuff without having to move the mouse. This post contains a brief overview of the most important commands you probably have to use when working with GnuPG.

Generating GPG Keys

$ gpg --gen-key

You will be asked what kind of key you want, simply proceed with the instructions that are given to you.

Listing GPG Keys

Listing public keys:

$ gpg --list-keys

Listing private keys:

$ gpg --list-secret-keys

Exporting GPG Keys

To export a public key into a file called public.asc:

$ gpg --export -a "User Name" > public.asc

To export a private key into a file called private.asc:

$ gpg --export-secret-key -a "User Name" > private.asc

Back ’em up!

Importing GPG Keys

To import a public key from a file called public.asc:

$ gpg --import public.asc

To import a private key from a file called private.asc:

$ gpg --allow-secret-key-import --import private.asc

Trusting GPG Keys

Once you have imported the person’s public key, you must now set the trust level of the key. This also prevents GPG from warning you every time you encrypt something with the recently imported public key.

Respectively specify the other person’s name or email in the command and proceed with the instructions that are given to you:

$ gpg --edit-key joe

Deleting GPG Keys

To delete a public key:

$ gpg --delete-key "Real Name"

To delete private key:

$ gpg --delete-secret-key "Real Name"

Generating Fingerprint

$ gpg --fingerprint

Encrypting Data

To encrypt a file named file.txt for a single individual, specify that individual as a recipient.

$ gpg --encrypt --recipient joe file.txt

The encrypted file is going to have the .gpg extension. In this case file.txt.gpg will be created after executing the command, which you can send to the receiver.

To encrypt a file so that only you yourself can decrypt it, then specify yourself as the recipient.

$ gpg --encrypt --recipient 'My Name' file.txt

To encrypt a file so that both you and the other person can decrypt the file, specify both you and the other person as recipients.

$ gpg --encrypt --recipient joe --recipient 'My Name' file.txt

To encrypt a file for a group of individuals, define the group in your GPG configuration file (see below), and then specify the group as a recipient.

$ gpg --encrypt --recipient journalists filename.txt

There’s a shorter version to accomplish the things we have done above:

$ gpg -e -r journalists file.txt

Decrypting Data

$ gpg --decrypt file.txt.gpg

A new decrypted file without the .gpg extension will be created, in this case file.txt. Additionally omit --decrypt if you are working with a binary.

Groups for GPG

You can summarize individuals to single groups by editing your GPG configuration (e.g. in ~/.gnupg/gpg.conf). To get back to the example above, we create a group called journalists containing several individuals:

group journalists = joe tom donald

Add this line to your GPG configuration file.

yrCommerce – Revamped

As the year 2016 is coming to an end, I’ve recently introduced the fresh update to Twitch Copypasta DB. Today, I’m introducing the new update, namely v.8.0, to the E-Commerce software yrCommerce.

Backend Changes

Major backend changes have been done to help reduce server load by a large margin.

Frontend Changes

I’ve also reduced the JavaScript code as much as possible and revamped the whole mobile interface to match all existing desktop features. Additionally, pages have also been changed to make them a bit more SEO-friendlier.

Admin Panel

Subcategory-Types

Subcategory-types can now be explicitly created under a new tab below the subcategory management by specifying name and order. This also implies that you can now easily select types from drop-down menus within the subcategory manager.

Product Wishes

Products can now optionally have individual notes when adding to the cart.

PayPal PLUS Integration

PayPal PLUS has been added to the ever growing amount of payment options.

Bug Fixes

Fixed user resetting not working sometimes.

Twitch Copypasta DB – Revamped

Now that it is almost 2017, it’s a good time to reflect on where Twitch Copypasta DB is going. Since it was running on an old framework, I’ve decided to update and revamp most of the code. The most significant changes, some of which are not live yet, are listed below.

Sorting and Searching

Sorting and searching experience has been radically improved. Paginating through search results will now (finally) yield correct results.

Emoticons

The latest change adds another page listing global emoticons. Custom emoticons of streams are listed on their respective profile.

Mobile Improvements

Even more mobile-friendly than before!

Look & Feel

Good stuff (see attached image).

Using Git for Managing a Live Site

Uploading files to production level after every change in code can be quite a hassle. Most people would use an automated deployment system instead of doing it manually. We can create an automated deployment system ourself by just using a version control like Git, which would also only take a few seconds to set up.

This post outlines the exact steps on how to do that. You should be able to understand basic terminology like pushing or pulling.

Install Prerequisites

Install Git on the server- and client-side.

$ yum install git-core

Head to this page if you still don’t know how to install it.

Server Setup

You’ll want to start by creating a bare repository on your server. A folder without its actual source files. The repository should be set up somewhere outside of your web root. We are going to instruct Git where to put the actual files later. Once you decide on a location for your repository, go ahead and create the bare repository:

mkdir mysite.git
cd mysite.git
git init --bare

Now we need to instruct Git where to put the files after every commit. This can be done via hooks, basically actions defined by triggers.

Head to this page to read more about hooks.

Create a file named post-receive in the .git/hooks directory of your bare repository with the following content (replace the destination path as you see fit):

#!/bin/sh
GIT_WORK_TREE=/var/www/mysite git checkout -f

Once this is done, mark it as executable:

$ chmod +x post-receive

Git is going to put the files after every push directly to the destination folder (e.g. /var/www/mysite).

Now setup Apache Webserver, Nginx or whatever you use to serve your site from the destination folder.

Client Setup

Proceed to create the local repository and make the first commit and push by adding the remote repository we created:

$ git init
$ git add .
$ git commit -m "First commit"
$ git remote add live ssh:[email protected]:port/path/to/mysite.git
$ git push live master

Now every commit and push, as in every change you make on your local repository, will immediately affect the live environment. Not even a manual pull has to be executed!

Postfix and SMTP Relaying on CentOS 7

One way to transmit mail within a local server is by sending them directly through third party mail servers on the Internet using the SMTP protocol.

Postfix is a free and open-source mail transfer agent (MTA) and available in most Linux distributions (including CentOS 7!).

This guide will outline the basic steps on how to setup Postfix to use your mail-service-provider’s SMTP server for outgoing mail. Once configured, all mails from your server will be sent through it.

The following configuration will use 1und1’s mail server as an example.

Install Prerequisites

Install the required packages:

$ yum install postfix cyrus-sasl cyrus-sasl-plain

Configuration

This configuration uses a made-up mail account, and, as already stated above, uses the 1und1 SMTP server to relay outgoing mail.

First and foremost, a password file needs to be created so that Postfix can authenticate to the SMTP server. This is done by creating a file named sasl_passwd in /etc/postfix. Replace smtp_user and smtp_passwd with their respective values for your account:

$ echo "smtp.1und1.de smtp_user:smtp_passwd" > /etc/postfix/sasl_passwd

The username in this case would be something like [email protected].

Now we must convert /etc/postfix/sasl_passwd into a format that Postfix can read:

$ postmap hash:/etc/postfix/sasl_passwd

The above command will create a file named sasl_passwd.db in the /etc/postfix/ directory.

And for additional security purposes, only root should have access to the password files:

$ chmod 600 /etc/postfix/sasl_passwd /etc/postfix/sasl_passwd.db
$ chown root:root /etc/postfix/sasl_passwd /etc/postfix/sasl_passwd.db

After all of those steps are completed, we now configure the main configuration file located under /etc/postfix/main.cf.

Search for relayhost and set it to the SMTP server address.

relayhost = smtp.1und1.de:587

Finally add the following lines to the configuration file:

smtp_sasl_auth_enable = yes
smtp_sasl_password_maps = hash:/etc/postfix/sasl_passwd
smtp_sasl_security_options = noanonymous
smtp_use_tls = yes

Keep in mind, that some mail providers force you to use certain security options.

Start or restart Postfix:

$ systemctl start postfix

Draft! This guide is work in progress.

SSH and Port Knocking

It turns out that SSH brute-force attacks, dictionary attacks or combinations of those are daily routines nowadays. Server logs are quickly filled with login attempts, in the hopes that one of them is right. The best prevention against these kind of attacks is to have a good password, or even better to force key-based authentication.

However, this won’t stop automated attacks from trying out usernames and passwords anyway, which is generally annoying. Thus, the approach to hide the SSH port, which by default is 22. One solution some people do is moving SSH to a non-standard port. Basically, some random number that won’t conflict with anything else.

Another interesting trick is to not immediately expose the SSH port, but only when a client is saying “Open Sesame”. Jokes aside, that’s roughly what port knocking allows us to do. There are many variants on port knocking and many programs that implement it. The following tutorial will use knockd as port-knocking server.

Install Prerequisites

Download and install the knock-server rpm package:

$ wget http://li.nux.ro/download/nux/misc/el6/i386/knock-server-0.5-7.el6.nux.i686.rpm
$ rpm -ivh knock-server-0.5-7.el6.nux.i686.rpm

Configuration

The configuration file can be found under /etc/knockd.conf.

[options]
        logfile = /var/log/knockd.log

[openSSH]
        sequence    = 6000,7000,8000
        seq_timeout = 15
        command     = /sbin/iptables -I INPUT -s %IP% -p tcp --dport 22 -j ACCEPT
        tcpflags    = syn

[closeSSH]
        sequence    = 8000,7000,6000
        seq_timeout = 15
        command     = /sbin/iptables -D INPUT -s %IP% -p tcp --dport 22 -j ACCEPT
        tcpflags    = syn

In the above configuration, we’ve stated that any host that sends a TCP SYN message to port 6000, then 7000 and finally to 8000, within 15 seconds, will cause the iptables command to be run. As you can see, the use of iptables is not hard-coded to knockd at all, meaning that any command can be run when the port sequence is triggered, allowing us to do all sorts of fancy stuff. To close it up, we do the same sequence in reverse order (that’s because we have configured it to do so).

Final Steps and Usage

Once everything is installed and configured, start it up and begin testing. Leave a separate SSH connection open to the server while you are testing!

$ systemctl enable knockd
$ systemctl start knockd

On the client, try out knocking with telnet:

$ telnet example.com 6000
$ telnet example.com 7000
$ telnet example.com 8000

The knockd log file, located under /var/log/knockd.log, should print out something like this:

[2016-11-12 16:11] <CLIENT_IP>: openSSH: Stage 1
[2016-11-12 16:12] <CLIENT_IP>: openSSH: Stage 2
[2016-11-12 16:12] <CLIENT_IP>: openSSH: Stage 3
[2016-11-12 16:12] <CLIENT_IP>: openSSH: OPEN SESAME
[2016-11-12 16:12] openSSH: running command: /sbin/iptables -I INPUT -s <CLIENT_IP> -p tcp --dport 22 -j ACCEPT

Your iptables configuration should now contain a new line, which accepts the client’s IP on port 22. Closing the connection can also be done as seen above, of course with the respective sequence of ports (8000, 7000, 6000 in this case).

The next step is to lock everyone else out from the SSH port. Add a new rule to the firewall, but make sure it goes to the bottom:

$ iptables -A INPUT -p tcp --dport ssh -j DROP

Finally restart iptables (ATTENTION: this will drop your current SSH connection, make sure that everything above is working!):

$ systemctl restart iptables

Conclusion

It certainly doesn’t prevent a targeted attack, but it might prevent most automated attacks. You are also not bound to the iptables command, meaning that you can do all sorts of fancy stuff with port knocking.

Shannon-Fano Coding

Shannon-Fano coding is another compression technique used to reduce the number of bits needed to store a message, however unlike Huffman coding, it does not use a bottom-up approach and neither does it generate minimal codes.

The following section summarizes the simple encoding process.

Example sentence: This_is_an_example

Step 1: Preparing

Count the frequencies of existing letters

A E H I L M N P S T X _
2 2 1 2 1 1 1 1 2 1 1 3

Sort symbols based on their frequencies

H L M N P T X A E I S _
1 1 1 1 1 1 1 2 2 2 2 3

Step 2: Combining (Top-Down)

Recursively divide the set of symbols into two parts, each with approximately same number of frequencies. The process of splitting two symbols has been omitted in the following section.

Step 2.1

Total AEISHLMNPTX: 18 => ~9 each.

     AEISHLMNPTX_
    /            \
AEISH            LMNPTX_

Step 2.2

Total AEISH: 9 => ~4.5 each.
Total LMNPTX_: 9 => ~4.5 each.

      AEISHLMNPTX_
     /             \
  AEISH            LMNPTX_
 /     \          /      \
AE      ISH      LMNP     TX_

Step 2.3

Total ISH: 5 => 2.5 each.
Total LMNP: 4 => 2 each.
Total TX_: 5 => 2.5 each.

        AEISHLMNPTX_
       /             \
    AEISH            LMNPTX_
   /     \          /      \
  AE      ISH      LMNP     TX_
 /  \    /  \      /  \     /  \
A    E  I   SH    LM  NP   TX   _

Step 2.4

And we finally get the desired tree…

        AEISHLMNPTX_
       /             \
    AEISH            LMNPTX_
   /     \          /      \
  AE      ISH      LMNP     TX_
 /  \    /  \      /  \     /  \
A    E  I   SH    LM  NP   TX   _
            /\   /\   /\   /\
           S H  L M  N P  T X

Step 3: Assigning Codes

Now arbitrary declare that the left path of every parent node is indicating the number 0 and the right path respectivly 1.

Analysis

The above encoding process leads to the following result:

Symbol  Code  Frequency  Code     Total
                         Length   Length
-----------------------------------------
A       000     2         3        6
E       001     2         3        6
I       010     2         3        6
S       0110    2         4        8
H       0111    1         4        4
L       1000    1         4        4
M       1001    1         4        4
N       1010    1         4        4
P       1011    1         4        4
T       1100    1         4        4
X       1101    1         4        4
_       111     3         3        9

Total symbols: 18 (sum of frequencies)
Bits needed with Shannon-Fano coding: 63 Bit (sum of total length)
Bits needed without Shannon-Fano coding: 64 Bit (see below)

Calculating how many Bits we need when not using Shannon-Fano coding:

12 (2^4) unique symbols => 4 Bit/Symbol needed
Total Bits needed: 4 Bit * 18 = 64 Bit

Python Script as Systemd Service

Running a python script on a remote machine can be achieved by using a terminal multiplexer (see GNU screen). Another rather convenient alternative to that would be systemd.

Creating our Service

The following python script acts as a single-threaded server, which does not have much functionality besides receiving and sending back (the same) data.

#!/usr/bin/python3 -u
import socket

TCP_IP = '127.0.0.1'
TCP_PORT = 1337
BUFFER_SIZE = 1024

while True:
   s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
   s.bind((TCP_IP, TCP_PORT))
   s.listen(1)

   conn, addr = s.accept()
   print('Connection address:', addr)
   while True:
      data = conn.recv(BUFFER_SIZE)
      if not data: break
      print("Data received:", data)
      conn.send(data)
   conn.close()

We save the file under /etc/myserver/server.py and mark it as executable via chmod +x /etc/myserver/server.py.

Keep in mind that our server isn’t multi-threaded, meaning that only one connection can be processed at a given time.

Now we create a separate user, that runs the server script:

$ useradd -r -s /bin/false myserveruser
$ chown -R myserveruser:myserveruser /etc/myserver

We proceed to create a unit file for our service:

[Unit]
Description=My Server
After=syslog.target

[Service]
Type=simple
User=myserveruser
Group=myserveruser
WorkingDirectory=/etc/myserver
ExecStart=/etc/myserver/server.py
SyslogIdentifier=myserver
StandardOutput=syslog
StandardError=syslog
Restart=always
RestartSec=3

[Install]
WantedBy=multi-user.target

And save it under /etc/systemd/system/myserver.service. Note: to tell systemd that we have modified the configuration file(s), use systemctl daemon-reload.

Running via systemd

Now that we have created our custom systemd service, enable and start it:

$ systemctl enable myserver
$ systemctl start myserver

Other useful commands to know:

$ systemctl restart myserver
$ systemctl stop myserver

Logging

Logs can be fetched with journalctl:

$ journalctl -u myserver

Huffman Coding

Huffman coding is a compression technique used to reduce the number of bits needed to store a message. Codes are basically generated by building a tree from bottom up (as opposed to Shannon-Fano coding), using the occurrence amount of input entities (letters in the following example).
This leads to the codes being prefix-free, meaning that each input yields a unique sequence of bits.

The following section summarizes the simple encoding process.

Example sentence: “`This_is_an_example“

Step 1: Preparing

Count the frequencies of existing letters

A E H I L M N P S T X _
2 2 1 2 1 1 1 1 2 1 1 3

Step 2: Combining (Bottom-Up)

Recursively combine the lowest two frequencies.

Step 2.1

In this example multiple letters with the same (and lowest) frequency (namely H, L, M, N, P, T and X) exist, therefore arbitrary combine those. The parent node displays the sum of frequencies.

   2         2          2          3
 /   \     /   \      /   \      /   \
H     L   M     N    P     T    X     A

X has been combined with A, as there is no letter with frequency 1 left.

The new frequency table:

HL MN PT XA E I S _
2  2  2  3  2 2 2 3

Step 2.2

We repeat the step on the above table and combine the letters with frequency 2…

HLE MNI PTS XA _
4   4   4   3  3 

     4          4           4
    / \        / \         / \
   2   E      2   I       2   S   
 /   \      /   \       /   \  
H     L    M     N     P     T

Step 2.3

And again for the above table (letters with frequency 3)…

HLE MNI PTS XA_
4   4   4   6

     4          4           4          6
    / \        / \         / \        / \
   2   E      2   I       2   S      3   _
 /   \      /   \       /   \      /   \
H     L    M     N     P     T    X     A

Step 2.4

And again (letters with frequency 4)…

HLMNPTE ISXA
8       10

       ___8___                ___10____  
      /       \              /         \
     4          4           4           6
    / \        / \         / \         / \
   2   E      2   I       2   S       3   _
 /   \      /   \       /   \       /   \
H     L    M     N     P     T     X     A

Step 2.5

To round it up…

HLMNPTEISXA
18 (root)

            _________18_________
           /                    \
       ___8___                ___10____  
      /       \              /         \
     4          4           4           6
    / \        / \         / \         / \
   2   E      2   I       2   S       3   _
 /   \      /   \       /   \       /   \
H     L    M     N     P     T     X     A

Step 3: Assigning Codes

Now arbitrary declare that the left path of every parent node is indicating the number 0 and the right path respectivly 1.

This leads to the following (prefix-free) codes:

H: 0000
L: 0001
M: 0100
N: 0101
P: 1000
T: 1001
X: 1100
A: 1101
E: 001
I: 011
S: 101
_: 111

Analysis

Symbol  Code  Frequency  Code     Total
                         Length   Length
-----------------------------------------
H       0000  1          4        4
L       0001  1          4        4
M       0100  1          4        4          
N       0101  1          4        4
P       1000  1          4        4
T       1001  1          4        4
X       1100  1          4        4
A       1101  2          4        8
E       001   2          3        6
I       011   2          3        6
S       101   2          3        6
_       111   3          3        9

Black Desert Knowledge Guide

This guide will lead you through every knowledge from some categories that are quite hard to obtain for the first time. There are two ways of actually getting all the knowledge. The first way is to buy the knowledge from Clara Siciliano, the Bookseller in Calpheon. The second way is by interacting with different NPCs and spending energy or doing a quest chain. The latter option is probably the easier one to do, as you don’t have to spend any silver or much amity.

Theology I

1. Road of Penitence

In order to obtain this knowledge you will need to be above level 39 and have to visit Calpheon and take the quest A Sinner from the Villager at the square next to Lavientia Batian’s house. Another way for players under level 39: finish the chain quest A Talk with Elion from Annolisa Rosie, make sure to follow previous steps as well. To start the chain quests, talk to Elina Leight in Calpheon.

2. Bell Ringing from the City

Look for the Adventurer in Calpheon outside the inn next to Fredelles Herba. You will get the knowledge from this NPC after finishing quest The Calpheon Bell. In order to do this quest you must be above level 35 and you must have the Apprentice Manager Certificate quest completed beforehand.

3. Tower of Will

The knowledge can be acquired from the Mysterious Man in Heidel city. Meet him inside the old building near eastern gates, he is wearing dark clothes, kneels down while surrounded by candles. The cost to obtain the knowledge is 5 energy, you also have to be above level 29.

4. Will of Elion

To receive the knowledge talk to Ottavio Ferre, a Elionian Priest inside Velia’s Chapel.

5. Evil Gods in Darkness

In the South of Glish meet Annalynn, the node manager of the Bloody Monastery. She will share her knowledge for 35 energy.

6. After Death

Search for the villager on the left side of Velia’s chapel. You will need 3 energy to obtain his knowledge. If the villager is not there, try it in the morning.

7. Birth of Faith

Visit Glish town and find a priest Lionel Riche inside the chapel. Once you reach 50 amity with him, the quest Elionian Doctrines will be available. Meet the villager sitting on the well to receive the knowledge for 3 energy (she’ll be there during the daytime).

8. Elion Definition of Heresy

Look for Lionel Richi, the priest in the chapel of Glish, he will share his knowledge for 3 energy.

9. Dragon Watcher

Examine the lion statue on top of the Holy Altar near the Northern Plain of Serendia node. You need 10 energy to obtain the knowledge.

Introduction to C

C Preprocessor

C preprocessor code will be executed before compiling the actual c code.
Preprocessor lines start with # and do not end with a semicolon (in contrast to usual code instructions).

#define MAX_SIZE = 1
#undef MAX_SIZE

The first instruction replaces instances of MAX_SIZE with 1. The second instruction undefines the previous made call.

#include <stdio.h>
#include "myheader.h"

Tells the cpp to include stdio.h from the system libraries, where else the next line includes the header file myheader.h from the local directory.

#ifndef MAX_SIZE 
    ...
#endif

#ifdef DEBUG
    ...
#endif

Pointers

A pointer points to a variable address/stores a variable address.

char val = 'c';
char val2;
char *pointer = &val;
val2 = *pointer;

& is used to get the address of a variable, * to an already declared pointer gives us the actual value again.
We initialize the pointer in line 3 and set val2 to the actual value of the pointer (c in this case).

Strings

A string is basically an array of characters, which by default also ends with a null character (\0) indicating the end of the string. If a pointer points to the string, then it will hold the starting address of the string (the first character).

char *pointer = "Some string";
printf("%c, %s", *pointer, pointer);

Above code outputs S, Some string. We get the value of the first character followed by the full string, as the format specifier %s lets us print out all characters of the array until it reaches a null character.

Pointers and Structs

struct student {
    int a;
    int b;
} obj;

...
struct *s = &obj;
s->a = 5;
s->b = 1;
...

Accessing pointer objects is done with -> instead of ..

Data Structures

struct

Grouping of a list of variables.

struct student {
    int student_id;
    float balance; 
};

struct student s1;
s1.student_id = 1;

Alternative:

struct student {
    int student_id;
    float balance;
} s1, s2;

typedef

Gives a type a new name.

typedef unsigned long long ull;
ull a, b;

Also useful in regard to structs:

typedef struct student {
    int student_id;
    float balance;
} Student;

Student s1;
s1.student_id = 1;

Error Handling

Taken from the errno(3) linux man page:

The <errno.h> header file defines the integer variable errno, which
is set by system calls and some library functions in the event of an
error to indicate what went wrong.

The function void perror(const char *str) lets you pass a custom C string, which will be displayed before the actual error message.

...
fp = fopen("file.txt", "r");
if (fp == NULL) {
    perror("file.txt: ");
    return(-1);
}
...

The above code could output something like this: file.txt: No such file or directory.

Another useful function would be char *strerror(int errnum), which acts similar to perror, except it returns a pointer to the error message string. Following code should print out the same as the above one.

...
fp = fopen("file.txt", "r");
if (fp == NULL) {
    printf("file.txt: %s", strerror(errno));
    return(-1); 
}
...

Program Structure

Top-Down/Procedural programming

Mix everything in one pot and hope that your pot is still edible after mixing it for years. Therefore, it would be more clever to split your growing pot into so called modules: split code into several c files, combine declarations into header files.

Object Oriented Programming

The new deal within the programming industry.

Visibility of Variables/Functions

Folder with examples to this sub section can be found here.

  1. global visibility (over modules and functions)
  2. global visibility in a module (over functions within the module)
  3. local visibility within a function
  4. local visibility within a block

Overriding happens as we go from bottom to top.

To use variables, which are already defined in another source file: extern int x;.
Limiting the visiblity to a module happens with the keyword static.

Lifespan of Variables

Space of global variables are reserved during the total runtime of our program.

  1. static variables (static)
    • space reserved as in the default behaviour for global variables
    • static variables have the value 0 when not initialized
  2. dynamic variables (auto)
    • local variables
    • auto variables have undefined values when not initialized
    • space reserved during runtime of a block, freed when leaving the block

Rechenbeispiele zu Caching und Paging

Cache

Beispiel direkt-abbildender Cache

Hauptspeichergröße: 4MiB
Einträge des Caches: 4096
Blockgröße: 16 Byte

Cachezeilen/Einträge des Caches = Cachegröße / Blockgröße

Cacheadresse = Gültigkeitsbit + Tag + Index + Byteblock
Wie viel Bit benötigt man um den kompletten Hauptspeicher anzusprechen?
4 MiB = 4 * 2^20 = 2^22 => 22 Bit

Wie viel Bit besitzt der Block-Offset Bereich?
16 Byte = 2^4 Byte => 4 Bit

Wie viel Bit besitzt der Index Bereich?
4096 = 4 * 2^10 = 2^12 => 12 Bit

Wie viel Bit besitzt der Tag Bereich?
Aus den vorherigen Ergebnissen: 22-4-12 = 6 Bit

Wie viel Bit lang wird die Cacheadresse mit zusätzlichem Validbit?
Zur Adressierungslänge (s. oben) 1 Bit hinzufügen => 22 + 1 = 23 Bit

Paging

Virtuelle Seitennummer | Seiten-Offset
    |
    | (Abbildung/Übersetzung)
    v
Physikalische Seitennummer | Seiten-Offset
Virtuelle Adresslänge: 32 Bit
Physikalische Adresslänge: 30 Bit
Seitengröße: 4K (2^12)

Wie viele Einträge in der Seiten Tabelle?
Größe Virtueller Speicher / Seitengröße
zB. 2^32 / 2^12 = 2^20

Wie viele Seitenrahmen?
Größe Physikalischer Speicher / Seitengröße
zB. 2^30 / 2^12 = 2^18

Wie viel Bit pro Seiteneintrag?
1 Valid Bit + 18 Bit = 19 Bit

Maximale Größe der Seitentabelle?
2^20 * 19 Bit = 19 MBit

1 Dimensionales Paging

Größe virtueller Adressraum: 2^32 Bytes
Größe virtuelle Seite: 2^12 Bytes

=> 2^32/2^12 = 2^20 Einträge die in die physikalische Seite Verweisen

2^20 Einträge à 32 Bit (4 Byte) => 4 MiB für Seitentabelle

Verwaltung + Nutzdaten:
4 MiB (Seitentabelle) + 4 KiB (physikalische Seite) = ~4,008 MiB

2 Dimensionales Paging

Größe Seitenverzeichnis: 2^10 Bytes
Größe Seitentabelle: 2^10 Bytes

=> 2^10 Einträge à 32 Bit => 4 KiB für Seitenverzeichnis
=> 2^10 Einträge à 32 Bit => 4 KiB für eine Seitentabelle

Verwaltung + Nutzdaten:
4 KiB (Seitenverzeichnis) + 4 KiB (Seitentabelle) + 4 KiB (phys. Seite) = ~16 KiB

Introduction to SQL

SQL (Structured Query Language) is used for retrieving and managing data in relational databases. This page will give you an overview of the general syntax.

Some useful data types are:

INT[EGER], SHORTINT, FLOAT [REAL], DECIMAL(a, b), VARCHAR(n), CHAR(n), BIT(n), BOOLEAN, NULL, DATE, TIME, TIMESTAMP

which should be self-explanatory.

Basic SQL Query

SELECT <Attribute(s)> -- What?
FROM <Relation(s)> -- Where from?
WHERE <Condition(s)> -- With what condition?

Equivalent meaning in relational algebra:

  • Projection: SELECT
  • Restriction/Selection: WHERE

If no projection is intended, use the asterisk operator: SELECT * FROM somewhere;

Projections as defined above can result duplicate attributes. This means that the regular outcome of a SELECT statement can be mathematically generalized as a multiset (or bag). Nevertheless, we also have the ability to generate tuples with set-property (collection without duplicates) by simply using the DISTINCT keyword.

SELECT DISTINCT name FROM Employee;

Types of SQL Statements

Data Definition Language (DDL)

Statements used to define the database structure/schema.
These include: CREATE, ALTER, DROP, TRUNCATE, COMMENT, RENAME.

Data Manipulation Language (DML)

Statements used for managing data within tables.
These include: SELECT, INSERT, UPDATE, DELETE

Data Control Language (DCL)

GRANT and REVOKE user’s access privileges.

Order Of Operations

1. FROM
2. WHERE
3. GROUP BY
4. HAVING
5. SELECT
6. ORDER BY

This is important in regards to determining on how results turn out to be!

Creating Tables

The general syntax looks like this:

CREATE TABLE table_name (
    columnName1 <type> <constraint>
    columnName2 <type> <constraint>
    columnName3 <type> <constraint>
);

The following table lists available constraint keywords.

Syntax Meaning
NOT NULL Must not store NULL value
UNIQUE Unique value for each row
PRIMARY KEY Combination of NOT NULL and UNIQUE
FOREIGN KEY Reference to data in another table (see referential integrity)
CHECK Value has to meet specific requirement
DEFAULT Specifies default value

Examples (excerpts):

columnName INTEGER NOT NULL
columnName INTEGER UNIQUE NOT NULL
columnName INTEGER UNIQUE
columnName INTEGER PRIMARY KEY
columnName INTEGER DEFAULT 5
columnName INTEGER CHECK(columnName < 10)

Constraints can be applied to multiple columns (also works for just one) through the following syntax:

CONSTRAINT constraint_name <constraint> (column1, column2...)

To sum it up, a short example showcasing most things from above:

CREATE TABLE Employee (
    FirstName VARCHAR(255),
    LastName VARCHAR(255),
    SupID INT NOT NULL,
    City VARCHAR(255),
    Smile INT,

    CONSTRAINT pk_employee PRIMARY KEY(FirstName, LastName),
    CONSTRAINT fk_boss FOREIGN KEY SupID REFERENCES Superiors(BossID),
    CONSTRAINT chk_good CHECK (City = 'GoodCity' AND Smile > 10)
);

Set Comparison

An example with constants:

SELECT * FROM somewhere
WHERE id IN (1, 2, 3);

Nested query as comparison:

SELECT attribute FROM somewhere
WHERE id IN (SELECT id
             FROM somewhereElse
             WHERE otherAttribute = 'example');

Exists

Select all departments associated with at least one employee.

SELECT * FROM Department 
WHERE EXISTS (SELECT * FROM Employees WHERE depId = id);

Quantors

These should be self-explanatory (ANY and SOME are synonyms).

SELECT * FROM Department
WHERE place = ANY(SELECT name FROM Places);

SELECT * FROM Department 
WHERE place = SOME(SELECT name FROM Places);

SELECT * FROM Employees
WHERE salary >= ALL(SELECT salary FROM Employees);

Set Operations

Note that both tables have to have the same amount of columns, which furthermore have similar domains to each other.
Results contain distinct attribute columns.

UNION [ALL]

SELECT * FROM LeftTable UNION (SELECT * FROM RightTable);
SELECT * FROM LeftTable UNION ALL SELECT * FROM RightTable;

The union operator removes duplicate rows by default.

INTERSECT [ALL]

The intersect operator removes duplicate rows by default.

EXCEPT [ALL]

The except operator removes duplicate rows by default.

Joins

Syntax Explanation
INNER JOIN or JOIN Result set matching both tables
LEFT OUTER JOIN or LEFT JOIN Returns all rows from the left table, unmatched attributes from the right table are respectively filled with NULL
RIGHT OUTER JOIN or RIGHT JOIN Returns all rows from the left table, unmatched attributes from the right table are respectively filled with NULL
FULL OUTER JOIN or FULL JOIN Returns matching rows from the left and right table, an unmatched row gets respectively filled with NULL values
CROSS JOIN Returns the cartesian product of both tables
NATURAL JOIN Join via columns with equal names (result consists of distinct attribute columns)

Note to cross join: *each row in the first table gets concatenated with every row in the second table (new size: size of first table multiplied with the size of our second table)*

We are also able to join a table with itself (Self Join), by defining aliases:

SELECT p1.firstname AS "Employee", p2.firstname AS "Superior"
FROM Person AS p1, Person AS p2
WHERE p1.superior = p2.id;

Equi-join via using() (distinct attribute columns as in natural-join):

SELECT * FROM Person JOIN Department USING(firstname, surname);

Aggregation Functions

Built-in functions, which are applicable on single columns.

Syntax Meaning
MIN(<attribute>) Minimum attribute value
MAX(<attribute>) Maximum attribute value
COUNT(<attribute>) Amount of rows (for which its attribute value is not null)
COUNT(*) Amount of rows
COUNT(DISTINCT <attribute>) Amount of different attribute values
AVG(<attribute>) Average of numbers
SUM(<attribute>) Sum of numbers
SUM(DISTINCT <attribute>) SUM(DISTINCT <attribute>) No duplicates (see above)

Examples:

SELECT AVG(salary) FROM Employees WHERE depId = 5; -- Returns average salary
SELECT COUNT(DISTINCT lastname) FROM Employees; -- Returns amount of different lastnames (no duplicates)
SELECT COUNT(*) AS Amount
FROM Employees e, Employees b
WHERE e.bossId = b.id AND e.salary > b.salary; -- Returns amount of employees, who earn more than their defined superior

Having

  1. Restriction before grouping: WHERE
  2. Restriction after grouping: HAVING

Sorting

Task: Give me all employees sorted by their underlying surnames, which have salary greater than 2000.

SELECT firstname, surname
FROM Employee
WHERE Salary > 2000
ORDER BY surname;

The above query sorts our desired records in ascending order, considering we did not specify the optional keyword DESC to ORDER BY. Therefore it isn’t necessary to use the ASC keyword, as sorting defaults to that.

ORDER BY surname DESC -- Descending order
ORDER BY surname ASC -- Ascending order (default)

It is also possible to sort multiple columns, one after another.

ORDER BY surname DESC, firstname ASC 

This would sort surnames in a descending order first, and then firstnames by ascending (optional) order.

Grant/Revoke Privilege

General syntax:

GRANT <Privileges> ON <TableName> TO <UserName>;
GRANT SELECT, INSERT ON Employee TO SubAdmin 

Available privileges:

Privilege Description
SELECT Ability to perform SELECT statement
INSERT Ability to perform INSERT statement
UPDATE Ability to perform UPDATE statement
DELETE Ability to perform DELETE statement
REFERENCES Ability to create a reference constraint
ALTER Ability to change the table definition
ALL Grants SELECT, INSERT, UPDATE; DELETE and REFERENCES

Views

General syntax:

CREATE VIEW ViewName AS
<statement>;

An example:

CREATE VIEW GetTopEmployees AS
SELECT firstname, surname, salary
FROM Employee
WHERE rank <= 50
ORDER BY rank, salary ASC;

Trigger

General syntax:

CREATE TRIGGER TriggerName
{BEFORE | AFTER | INSTEAD OF}
{INSERT | UPDATE | DELETE} [OF <column(s)>] ON TableName
REFERENCING NEW ROW AS newrow
FOR EACH ROW WHEN (<condition>)
<statement>;

Assertions

CREATE ASSERTION allows us to specify specific constraint rules (same as the previous CHECK usage in our table creation).

CREATE ASSERTION AssertionName
CHECK (
NOT EXISTS (SELECT * FROM Employees WHERE salary < 1000)
);

Make sure that there is no employee with a salary less than 1000.

Number Conversion Tricks

Curious about how to convert numbers from hexadecimal to binary as quick as possible? I’ve got good news for you, the following post contains methods to help you accomplish exactly that!

1.0 Conversion of Akin Bases

Assume we have to convert from one base to another (a \rightarrow b).

1.1 Higher Base to Lower Base

If we have to convert two bases in the form of a = b^n, then simply convert each digit from base a to base b. Add leading zeroes to each converted digit until the length of n has been reached. The last step is to combine them.

Example:
6421_8 \rightarrow 110|100|010|001_2 \rightarrow 110100010001_2

Each digit gets converted to binary and the last two resulting binary numbers also get leading zeroes (as 8 = 2^n \rightarrow n = 3).

1.2 Higher Base to Lower Base

Furthermore, if we have to convert two bases in the form of a^n = b, then simply split the number in base a in intervals of n digits. Proceed to convert the resulting numbers from base a to base b.

Example:
231211_4 \rightarrow 23|12|11_4 \rightarrow B65_{16}

The former number gets split in two-digit intervals (as 4^n = 16 \rightarrow n = 2). The resulting numbers finally get converted from base a to base b.

2.0 Conversion of Different Bases

If both bases do not have any correlation as seen above, proceed to use the following algorithm:

  1. Divide the given number with the target base b. The division is done within base a.
  2. Remember the remainder
  3. Repeat step 1 with the result of the previous division (not the remainder!) until it becomes 0

Combine the remainders from bottom to top to get the desired result.

Introduction to XML

A XML (short for Extensible Markup Language) document consists of:

  1. the prolog (optional)
  2. the document type definition (DTD, optional)
  3. the root element (which furthermore consists of more elements, tree structure)

Comments and processing instructions can be defined outside of tags.

Prolog

The basic prolog looks like this: <?xml version="1.0" ?>
An extended version: <?xml version="1.0" encoding="ISO-8859-1" standalone="yes" ?>

Attributes explained:

  • version: XML version
  • encoding: Character set, defaults to UTF-8
  • standalone: define if extern entities or DTDs are being referenced in this document

Document Type Definition

The DTD defines structure validation rules for our documents. We fundamentally construct elements with their respective type (analogous to the database schema).

Reasons to use DTD:

  • validation purposes
  • gathering information about the document
  • force same structure for multiple documents
  • comparability of documents
  • automated processing of specific document types

The DTD construct looks like this:

<!DOCTYPE root-element [
    ...
]>

The above DTD can be directly placed in the respective XML document. To reference an external DTD file:

<!DOCTYPE root-element SYSTEM "path-to-dtd.dtd">

An example for the external DTD file (note that it does not require the doctype declaration):

<!ELEMENT root-element (test-element*)>
<!ELEMENT test-element (#PCDATA)>
<!ATTLIST test-element id ID #REQUIRED>

Elements

The general syntax for element declarations: <!ELEMENT name category> or <!ELEMENT name (content)>. A quick overview of some category keywords:

Syntax Meaning
`` An empty element
`` Element with arbitrary content

Content is furthermore specified through these keywords:

Syntax Meaning
<!ELEMENT name (#PCDATA)> Element with parsed character data
<!ELEMENT name (#CDATA)> Element with (non parsed) character data
<!ELEMENT name (child1, child2)> Element surrounding a child1 followed by child2 element (strict order!)
<!ELEMENT name (child1 | child2)> Element surrounding either a child1 or child2 element

Occurrences of these children can also be specified:

Syntax Meaning
<!ELEMENT name (child)> Exact one children
<!ELEMENT name (child?)> 0..1 children
<!ELEMENT name (child*)> 0..N children
<!ELEMENT name (child+)> 1..N children

Attributes

An ATTLIST can declare 0..N attributes to an element, which is equal to having multiple ATTLISTs pointing to the same element.

<!ATTLIST element-name attribute-name attribute-type attribute-value>

<!ATTLIST human 
            id ID #REQUIRED
            salary Currency(Dollar, Euro) "Dollar">

As you already noticed, we are able to specify an explicit value range aside a type. The following table lists some of the attribute-types:

Syntax Meaning
CDATA Character data
(val1, val2...) Explicit value range
ID A unique ID
IDREF Reference to another ID
IDREFS Set of IDREFS
NMTOKEN Valid XML name
NMTOKENS Set of NMTOKENS
ENTITY An entity
ENTITIES Set of entities

Note: Set values are separated with whitespaces

Now a list of valid attribute-values:

Syntax Meaning
"value" Explicit value
#REQUIRED Attribute is required
#IMPLIED Attribute is optional
#FIXED "value" Explicit fixed value

XML Schema

An alternative to DTDs are XML schemas, which actually use XML syntax, support more data types and offer better referencing (in contrast to the IDREF mechanism).

Note: XML schemas extensively use the namespace mechanism (see bottom section).

XML Schema Structure

The schema element is the root element of every XML Schema:

<?xml version="1.0" ?>
<xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema">
    ...
</xsd:schema>

Simple Element

<xsd:element name="test-element" type="xsd:string" default="Default Value">
<xsd:element name="test-element2" type="xsd:string" default="Fixed Value">

The equivalent to above using DTD:

<!ELEMENT test-element "Default Value">
<!ELEMENT test-element2 #FIXED "Fixed Value">

Types: xsd:string, xsd:decimal, xsd:integer, xsd:boolean, xsd:date, xsd:time.

Note: simple elements cannot contain attributes.

Complex Element

<xs:element name="employee" type="person-info"/> <!-- Reference to a complex type (similar to nesting in DTD) -->

<xs:complexType name="person-info">
    <xs:sequence><!-- Firstname, then lastname (similar to DTD: comma separation) -->
        <xs:element name="firstname" type="xs:string"/>
        <xs:element name="lastname" type="xs:string"/>
    </xs:sequence>
</xs:complexType>

Referencing to XML Schema

And finally a reference to an XML schema:

<?xml version="1.0" ?>
<root-element xmlns:xsi="https://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="namespace_path_for_schema schema.xsd">
</root-element>

<?xml version="1.0" ?>
<root-element xmlns:xsi="https://www.w3.org/2001/XMLSchema-instance" xsi:noNamespaceSchemaLocation="schema.xsd">
</root-element>

Entities

An entity is a separate data unit within a XML document. Entities are also resolved before a validation is taking place.

<!ENTITY entityname "value">

We categorize entities into two sections:

Parsed entity (XML-fragment):
– Internal: defined within a DTD
– External: defined in another document

Unparsed entity (miscellaneous data):
– Value of an attribute with type ENTITY or ENTITIES
– Reference to an external file

Predefined Entities

Syntax Parsed
&lt; <
&gt; >
&amp; &
&apos;
&quot;

Using an already defined entity: &entityname;

References In XML

References to entities (as we already know): entityname;.
References to elements: an element with an ID attribute can be references through IDREF(S).

Note: references via IDREF(S) only work within a document

Namespace

Motivation: Mixing different XML documents will result in a conflict, when they contain elements with the same names.
General syntax: xmlns:PREFIX="URI".

<store xmlns:s="http://gimu.org/s">
    <s:title>Something</s:title>
    <s:example s:id="1">Example</s:example>
</store>

Note: an attribute does not inherit the namespace of its parent element (also applies for the default namespace)

Default Namespace

A namespace which applies to all child elements without a prefix.

<html xmlns="http://www.w3.org/1999/xhtml">
    <head>
        <title>All unprefixed elements belong to the xhtml namespace</title>
    </head>
    ...
</html>

XPath

XML documents are treated as trees. There are several distinguishable node types:

  • root node
  • element nodes
  • attribute nodes
  • text nodes
  • instructional processing nodes
  • comment nodes
  • namespace nodes

Explicit Path

The XPath query /PersonalFile/Particulars/Firstname would result in

Result
<Firstname>Foo</Firstname>
<Firstname>Foo2</Firstname>

as defined in the previous section.

Predicates

<AAA>
    <BBB/>
    <BBB/>
    <CCC/>
    <BBB/>
</AAA>
Query Result
/AAA/BBB/ <BBB/>, <BBB/>, <CCC/>, <BBB/>
/AAA/BBB[1]/ <BBB/> (first one)
/AA/BBB[last()] <BBB/> (last one)
/AAA/* <BBB/>, <BBB/>, <CCC/>, <BBB/> (any child of AAA)
//BBB <BBB/>, <BBB/>, <BBB/> (hierarchical independent node localization)

Processing Instructions

To influence XML processing, you can use processing instructions: <?name data>

Character Data

Arbitrary character sets can be included in XML (e.g. HTML documents).
This is done by enclosing the data with <![CDATA[...]]>

<xml>
    <![CDATA[
        <html>
            <b>Bold text</b><br/>
        </html>
    ]]>
</xml>

MathJax Cheatsheet

Table of Contents

  1. The Basics
    1. Displaying Formulas
    2. Greek Letters
    3. Super- and Subscripts
  2. Logic
    1. Basic Symbols
    2. Quantifier Symbols
  3. Set Theory
    1. Empty Sets and Number Sets
    2. Set Operations
  4. Order Theory
    1. Order Operations
  5. Matrices
    1. Augmented Matrices

The Basics

The following chapter will introduce you to the most basic commands used in MathJax and probably LaTeX.

Displaying Formulas

Formulas can be arranged in one line by enclosing them in $...$, whereas fully displayed formulas are wrapped in $$...$$. This serves as a basis for all of the upcoming MathJax examples underneath.

Greek Letters

Greek alphabet is conventionally used in mathematics and similar fields.
The following table contains the whole Greek alphabet along with the commands.

Codes Lowercase Uppercase
\alpha A \alpha A
\beta B \beta B
\gamma \Gamma \gamma \Gamma
\delta \Delta \delta \Delta
\epsilon E \epsilon E
\zeta Z \zeta Z
\eta E \eta E
\theta \Theta \theta \Theta
\iota I \iota I
\kappa K \kappa K
\lambda \Lambda \lambda \Lambda
\mu M \mu M
\nu N \nu N
o O o O
\pi \PI \pi \Pi
\rho R \rho R
\sigma \Sigma \sigma \Sigma
\tau T \tau T
\upsilon \Upsilon \upsilon \Upsilon
\phi \Phi \phi \Phi
\chi X \chi X
\psi \Psi \psi \Psi
\omega \Omega \omega \Omega

Super- and Subscripts

Superscripts are preceded by ^, subscripts respectively by _.
An example: x_i^2 represents x_i^2.
The order is exchangeable: x^2_i also displays x^2_i.

Logic

Basic Symbols

Some symbols are basically identical, the other ones are just different notations (or differ in size).

Code Symbols Meaning
\lnot and \neg \lnot and \neg negation
\land and \wedge \land and \wedge conjunction
\lor and \vee \lor and \vee inclusive disjunction
\equiv or \Leftrightarrow \equiv or \Leftrightarrow if and only if
\implies and \Longrightarrow or \Rightarrow \implies and \Longrightarrow or \Rightarrow if a then b
\Longleftarrow or \Leftarrow$ \Longleftarrow or \Leftarrow if a then b (reversed)

Quantifier Symbols

Code Symbol Meaning
\forall \forall for all
\exists \exists there exists
\exists! \exists! there exists exactly one
\nexists \nexists there does not exist

Set Theory

Empty Sets and Number Sets

Blackboard bold is a popular typeface style used to indicate basic number sets.
You can either use \mathbb{TEXT} or \Bbb{TEXT} to write in blackboard bold style.

Code Symbol Meaning
\emptyset and \varnothing \emptyset and \varnothing empty set
\Bbb N \Bbb N set of natural numbers
\Bbb Z \Bbb Z set of integers
\Bbb Q \Bbb Q set of rational numbers
\Bbb R \Bbb R set of real numbers
\Bbb C \Bbb C set of complex numbers

Set Operations

Code Symbol Meaning
\in \in is member
\notin \notin is not member
\subset \subset is subset
\subseteq \subseteq is subset or equal
\cap \cap set intersection
\cup \cup set union
\setminus \setminus set difference

Order Theory

Relation Operators

Code Symbol Meaning
\nless \nless not less than
\ngtr \ngtr not greater than
\leq \leq less than or equal to
\geq \geq greather than or equal to
\nleq \nleq neither less than nor equal to
\ngeq \ngeq neither greater than nor equal to
\nleqslant \nleqslant neither less than nor equal to
\ngeqslant \ngeqslant neither greater than nor equal to

Matrices

Elements are placed between \begin{KEYWORD}...\end{KEYWORD} and rows are separated with \\.

Keyword Brackets
matrix No Brackets
pmatrix (\:)
bmatrix [\:]
Bmatrix \{\}
vmatrix \lvert \rvert
Vmatrix \Vert\:\Vert

The above table covers the most important keywords.

Augmented Matrices

\left(
    \begin{array}{cccc|c}
      1 & -5 & 2i & 2i & 4i \\
      4 & 5 & 6 & 3i & 0
    \end{array}
\right)

It is also possible to draw matrices by enclosing a formatted table with parantheses or brackets.

\left(      \begin{array}{cccc|c}        1 & -5 & 2i & 2i & 4i \\        4 & 5 & 6 & 3i & 0      \end{array}  \right)

Binary Tree Path Sum

Problem

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exists a root-to-leaf path (5->4->11->2) with a sum of 22.

The binary tree:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL)}
};

Solution

A depth-first search is being used.

class Solution {
public:
    bool deepFirstSearch(TreeNode *node, int sum, int curSum)
    {
        if (node == NULL) return false;

        if (node->left == NULL && node->right == NULL) {
            return curSum + node->val == sum;
        }

        return deepFirstSearch(node->left, sum, curSum + node->val) || deepFirstSearch(node->right, sum, curSum + node->val);
    }

    bool hasPathSum(TreeNode *root, int sum) {
        return deepFirstSearch(root, sum, 0);
    }
};

Native Libraries and Steam

To force Steam to use system libraries instead of the provided ones: 

export STEAM_RUNTIME=0

Listing missing system libraries:

cd ~/.local/share/Steam/ubuntu12_32
file * | grep ELF | cut -d: -f1 | LD_LIBRARY_PATH=. xargs ldd | grep 'Not found!' | sort | uniq

Inverting a Binary Tree

Input tree

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Result tree

     4
   /   \
  7     2
 / \   / \
9   6 3   1

The binary tree:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

Solution

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        TreeNode* temp;
        temp = invertTree(root->left);
        root->left = invertTree(root->right);
        root->right = temp;
        return root;
    }
};