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

There’s more information about the visual studio C++ preprocessor here: https://docs.microsoft.com/en-us/cpp/preprocessor/c-cpp-preprocessor-reference?view=msvc-160

The preprocessor is really amazing honestly. There’s some token-pasting operations using the ## tag in a macro. I found this example on here: https://docs.microsoft.com/en-us/cpp/preprocessor/token-pasting-operator-hash-hash?view=msvc-160

#define paster( n ) printf_s( "token" #n " = %d", token##n )
int token10 = 15;

So essentially, if we call paster(10). It will essentially put token10 as the last parameter and it will fill in 15 where #n is at. So this will cause the console to print out “token10 = 15” There are other examples of preprocessor usage but those can be looked at on the reference I linked above.

  • Compilation – This is basically where the compiler goes over the code again (after it has been filled in with proper pre-processor changes) and then it begins to generate assembly source code.
  • Assembly – Takes assembly source code and builds an object file.
  • Linking – Takes libraries and object files to create the executable file.

Implementing Binary Search in C++ Practice

So this is something we have all learned in a basic Computer Science course. However, I just wanted to write down a super simple implementation of Binary Search for people who are interested. As you should already know, Binary Search can only be done on a sorted array. This function will only give you the index of the target in the given array. When first calling it, pass 0 for left ptr and array.size() – 1 for the right ptr.

int binarySearch(vector<int>& array, int target, int leftPtr, int rightPtr)
{
   int middle_index = (leftPtr + rightPtr) / 2;
   int potentialMatch = array[middle_index];
   if (target == potentialMatch)
   {
      return middle_index;
   }
   else if (target > potentialMatch)
   {
      return binarySearch(array, target, middle_index + 1, rightPtr);
   }
   else
   {
      return binarySearch(array, target, leftPtr, middle_index - 1);
   }
}

Balanced Brackets (Interview Question) in C++

So the question essentially asks you to write a boolean function that returns true if the input string is “balanced.” Balancing simply means that each open bracket has a closed bracket. You’re given a string like this:

string inString = "{[()]}";

In this example, this is a “balanced” string, because each opening bracket must have a closed bracket.

string inString = "[(])";

Now this one is not balanced. Why? Because it has overlapping brackets. Think of it like a venn diagram

Venn Diagram Maker | Lucidchart

Nothing can be in the center. So the question is, how do we implement this algorithm? This is my solution:

using namespace std;
#include <stack>
#include <vector>
#include <map>

bool IsOpenBracket(char InCharacter)
{
	vector<char> openCharacters = { '{', '(', '[' };
	if (count(openCharacters.begin(), openCharacters.end(), InCharacter))
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool IsClosedBracket(char InCharacter)
{
	vector<char> closedCharacters = {'}', ')', ']'};
	if (count(closedCharacters.begin(), closedCharacters.end(), InCharacter))
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool balancedBrackets(string str) {
    stack<char> s;
    map<char, char> matching_brackets =
		{
			{'}', '{'},
			{')', '('},
			{']', '['}
		};

    for (int i = 0; i < str.size(); i++)
    {
        char currentCharacter = str[i];
        if (IsOpenBracket(currentCharacter))
        {
            s.push(currentCharacter);
        }
        else if (IsClosedBracket(currentCharacter))
        {
            if (s.size() == 0)
            {
                return false;
            }
            
					  if(s.top() == matching_brackets[currentCharacter])
            {
                s.pop();
            }
            else
            {
                return false;
            }
        }
    }

    if (s.size() == 0)
    {
        return true;
    }
    
    return false;
}

In my code I essentially start out by making two boolean methods for readability. One is called “IsOpenBracket” and the other is called “IsClosedBracket” both of these functions take in a character and then return true or false if they are an open or closed bracket respectively.

After this is our “balancedBrackets” method which takes in a string. At the beginning of the method, I define a stack of characters called “s”

After this I define a map called matching_brackets which essentially is used later to give us the opposite bracket of what we turn in. So if you pass in ‘)’ it gives you ‘(‘

The next step is to essentially loop through each character in the string one by one and then I define a character called currentCharacter, which I set as a local temp variable for each loop iteration.

The first step now is to essentially check if this currentCharacter is an open bracket or a closed bracket. If it’s an open bracket, we just push it to the stack. Why? Because at the end of our function, we will check to see if there is anything in the stack. If the stack is empty, we return true, if it’s not empty, we return false. The whole premise of this method is that we push when it’s an open character, and pop when it’s a matching closing character.

Alright so, if it’s not an open bracket, we then check to see if the size of the stack is 0. We do this because if the stack is empty and we are inside of the “IsClosedBracket” part of the if statement, then we essentially are adding a closed bracket because we have an open bracket, which would be an immediate failure case.

After this we essentially check if the top of the stack is equal to the opposite of our current closing bracket. This is essentially the main trick. Remember the map that was made earlier? This is why it was made. So essentially, because a stack is last in, first out, the top of the stack is essentially the last open bracket we pushed, and we are checking if the top of that stack is equal to the opposite of our current closing bracket.

The last part is that we return false. Why do we return false here? This is because if we are on a closing bracket, and the current top is not equal to the opposite of our closing bracket, then we are overlapping. This would not follow the rules, so we would return false.

Lastly, we just check if the current size is 0, which means we popped off all of the opening brackets, meaning there is no open bracket without a matching closing bracket. If it’s not zero, we just return false as to say that the string is not balanced.

If you want to read the entire rules of this algorithm, you can read it here on hackerrank: https://www.hackerrank.com/challenges/balanced-brackets/editorial

Breadth First Search

This is similar to what I was doing when I was researching DFS (Depth First Search), which you can see below here I posted a link to my other posting.

Alright so hopefully the DFS algorithm makes sense. It’s very simple once you got it. Once you got it, you got it!

Breadth First Search is a little bit trickier, but don’t worry. It’s still easy to learn. For BFS, it might be implemented like this:

vector<string> breadthFirstSearch(vector<string> *array) {
    queue<Node*> q;
		array->push_back(name);
		q.push(this);
		
		while (!q.empty())
		{
			Node* n = q.front();
			q.pop();
			
			for (int i = 0; i < n->children.size(); i++)
			{
				if (count(array->begin(), array->end(), n->children[i]->name) == 0)
				{
					array->push_back(n->children[i]->name);
					q.push(n->children[i]);
				}
			}
		}
			
    return *array;
  }

In the above sample, this method will essentially print out all of the children of a graph in breadth first search. That is, level by level. However, in a real situation, you would simply return the node when you find what you are looking for.

Implementing DFS (Depth First Search) in C++

So I was trying to practice for some interviews with some gaming studios. I read on GlassDoor.com that one of the companies I had an interview for would ask about Tree Traversal methods. Upon doing some research I found multiple websites mentioning Depth First Search and Breadth first search.

I learned that there are essentially a few rules to DFS (Depth First Search).

  • Depth first search goes all the way down one side of the tree first, and then moves left to right.
  • For each node, we will add it to the array
  • For each child node, we will call the depth first search method to add the children to the array

For example, given the tree :

Image result for tree structure

The algorithm will first go down the left side, look at the root, it will start at letter A, and then move left to B, add A and B to the array of elements. After this, it will go down to D, and check all the nodes on D. The new array would look like: [A,B,D] and then it will look at it’s left and right child nodes, and add them. The new array would look like: [A,B,D,H,I] so essentially the rule is, add the elements and then check the children, and add the children, recursively.

So I came up with a super duper simple method of doing this:

void dfs(Node* node, vector<int>& levelOrder)
{
  if (node == nullptr)
    return;
  
  levelOrder.push_back(node->data);
  
  dfs(node->left, levelOrder);
  dfs(node->right, levelOrder);
}

Essentially, it’s using a recursive method to first check that the incoming node is not a nullptr. If it’s not a null pointer, we then add the node’s data element to the incoming vector, and then call the dfs method on both the left and right nodes.

I just wanted to mention that in a recursive function like this, you can have a stack overflow if the depth of the tree is too large. This is just something to be aware of.

BST Traversal

There’s actually there different methods of traversing a binary search tree. The first one that I posted above is essentially root, left, right. This is just a pre-order traversal.

There’s actually three in total, and they all are essentially just different places where we put the root node.

The three are called:

Preorder Traversal

Postorder Traversal

Inorder Traversal

This is very simple honestly. In order is literally “in order”, left, root, right.

It could be implemented like this:

void inOrderTraversal(BST* tree, vector<int> &array)
{
    if (tree)
    {
         inOrderTraversal(tree->left, array);
         array.push_back(tree->value);
         inOrderTraversal(tree->right, array);
    }
}

If you notice, it’s literally the same as the above pre-order traversal but we change the order of when we call the recursive methods. If you notice, first we call the method on the left of this tree, then we add “this” to the array, and finally we call it again on the right. So if you imagine it, it’s going to essentially add the inputted tree’s value to the array, after adding the left node, then it will add the root and finally the right node’s value. It’s a bit tricky but I hope that makes sense.

Pre Order is the version all the way at the top, so now, I’m going to go over postorder.

void postOrderTraversal(BST* tree, vector<int> &array)
{
    if (tree)
    {
         postOrderTraversal(tree->left, array);
         postOrderTraversal(tree->right, array);
         array.push_back(tree->value);

    }
}

If you notice, the only thing that changed is now we are basically going to add the left and right nodes first, and then finally the root node.

I think the best way to think about this is to take a large tree, and split it into it’s sub-trees and think of them separately and imagine how this method would work if called on a single 3 node tree with a root, left and right node.

I hope this helps other people who are studying.

FizzBuzz Solution

So I wrote up a solution for the FizzBuzz problem, here it is

#include <iostream>

using namespace std;

int main()
{
for (int i = 1; i <= 100; i++)
{
if (i % 3 == 0 && i % 5 == 0)
{
cout << "FizzBuzz" << endl;
continue;
}

if (i % 3 == 0)
{
cout << "Fizz" << endl;
continue;
}

if (i % 5 == 0)
{
cout << "Buzz" << endl;
continue;
}

cout << i << endl;

}

return 0;
}