Recently, I have been attempting to complete various computer programming examples I see online to test my ability to complete future coding interviews. I never had an actual coding interview before, so I thought it would be an excellent time to start practicing for the real deal.
I came across this one question where I was given a "tree" that represented an array. Negative numbers are non-existent nodes. My task was to create a function that determined whether the left or the right branch of the tree was larger. If they were equal (or if there are no nodes), the function would return an empty string.
The example array provided gave the following diagram as a visual representation:
Input: [3, 4, 5, -6, 7, 8]
Output: "Right"
My first mistake when tackling this question was focusing too much on the example and the visuals because my main concern for this question was just to determine "which branch had the greater total sum". I went for a method of completing the task that prioritized obtaining the result rather than understanding the problem. I saw that the "branch" on the left had a total value of 14 (3 + 4 + 7) and the "branch" on the right had a total value of 16 (3 + 5 + 8). In other words, it was correct for the right "branch" was "larger" and the appropriate output would be shown.
Based on what I saw, the first number of the array was considered the "root". After that, the numbers would be allotted, one-by-one, to the left and the right branches. However, I saw that the (-6) in the sample array was skipped and replaced by the number 7. I thought that this was referring to the question where negative numbers were non-existent nodes. As such, I took note of that rule.
With the basic understanding of what I needed to consider to get the answer, I began coding.
using System;
using System.Collections.Generic;
public class Program
{
public static int[] removeNegatives(int[] o)
{
//instantiating a temporary list
var temp = new List<int>();
//only positive numbers in the array ...
//will be added to a temporary array
for (int i = 0; i < o.Length; i++)
{
//only add the number to the new list if it's positive
if (o[i] > 0)
{
temp.Add(o[i]);
}
}
//converting list back to array
int[] newNumbers = temp.ToArray();
//returning the new numbers - no negatives
return newNumbers;
}
public static String getLargeBranch(int[] n)
{
//call the removeNegatives method to remove negatives
int[] nums = (removeNegatives(n));
//if array is empty, return empty string
if (nums.Length == 0)
{
return "";
}
//declare variables
int sumLeft = nums[0];
int sumRight = nums[0];
string output = "";
//"creating the tree branches"
//since the "root" is the first number for both branches ...
//we will start adding to the branches starting with ...
//the second number ([1])
for (int i = 1; i < nums.Length; i++)
{
//adding alternating numbers to left and right branches
if (i % 2 == 1)
{
sumLeft = sumLeft + nums[i];
}
else
{
sumRight = sumRight + nums[i];
}
}
//output which branch is larger
if (sumLeft > sumRight)
{
output = "Left";
}
else if (sumLeft < sumRight)
{
output = "Right";
}
else if (sumLeft == sumRight)
{
output = "";
}
return output;
}
public static void Main()
{
int[] numbers = {3, 4, 5, -6, 7, 8};
Console.WriteLine(getLargeBranch(numbers));
}
}
Output
Since negative numbers in the array get replaced by the next valid number rather than skipping the branch, I just removed the negative numbers in a given array with a method I create: removeNegatives(). Since you cannot properly remove elements in an array by their specific index, I opted for using a temporary list that is only populated by positive numbers in an array. From there, I would only have the 5 elements I needed (rather than the original 6) and then I could convert that temporary list into an array again and return that.
After that, it became a simple matter of "adding numbers" to the branches. How did I proceed with that? I used a for loop to distribute the numbers to their appropriate branch totals using mod to check for odd and even positions in the array. Since [0] is the first number (the so-called "root"), it was already added to each branch in the beginning so [1] would be added to the left, [2] would be added to the right, [3] would be added to the left and so on. This would repeat until all the numbers have been added.
Running this code, I got the output I expected and I tested it out by outputting the actual sums of the branches.
//test
Console.WriteLine("Left: " + sumLeft.ToString());
Console.WriteLine("Right: " + sumRight.ToString());
Output
Now, to test with no branches. With an array containing a single element (the root), there should be no branches.
public static void Main()
{
int[] numbers = {3, 4, 5, -6, 7, 8};
Console.WriteLine(getLargeBranch(numbers));
//test
int[] noBranches = {0};
Console.WriteLine(getLargeBranch(noBranches));
Console.WriteLine("It works!");
}
Output
The blank line in between there means that an empty string was returned.
Conclusion
Does my solution give me the right answers? Yes.
Does that mean it is correct? No.
It just so happens that I could solve this problem with this method. What would happen if the tree for a problem looked like this?
Apparently, I can create an actual BinaryTree and create nodes like so:
Node root;
BinaryTree(int key)
{
root = new Node(key);
}
BinaryTree()
{
root = null;
}
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
Even though the solution I developed for this problem would pass the test cases, the overall understanding of the problem just flew over my head which makes my solution fundamentally wrong.
I do not remember studying this back then, but if I want to be able to ace these problems if they come up in interviews I have to do more studying on binary tree data structures!