Given an analog clock, return the angle that the hands make

Source
My team-lead asked me this one as interview prep

Language
C#

Question
Given an hour and a minute value, determine the angle that the hands would make on an analog clock. For example. given the time 3:05 (hour = 3, minute = 0), the angle would be 90º. 2:30 (hour = 2, minute = 30) would return 120º.

Process
At first I had absolutely no idea how I would go about solving this. I literally drew out a clock and drew a chart of some inputs and outputs.

From there, I figured out that my first step was to convert the input numbers into angle values (as in, 3 = 90º, 7 = 210º, etc). Figuring this out now seems really simple, but I could not figure this out in front of my team lead. I don’t know why, but not only could I not figure out that I need to divide 360 by 12… I also couldn’t figure out what that was. Now it seems obvious… you divide the clock (360º circle) by the amount of numbers on the clock (12), meaning 30º per clock number for the hours.

For the minutes, it was a little easier. Jut multiple the answer by 6. I think I struggled with this in the room as well… and even now I’m not immediately sure why 6 is the right answer…. but at least I can do the math now! After figuring out that the answer was to multiple by 6, I figured out that 60 (minutes) goes into 360 (degrees in a circle) 6 times.

After converting the incoming hours and minute to degrees, I just had to subtract them, and then take the absolute value! The code itself is very simple… I just got really caught up on the math of it all.

public static int GetAngleFromTime(int hour, int minute)
{
  int minDegrees = minute * 6;
  int hourDegrees;
  if (hour == 12)
  {
    hourDegrees = 0;
  }
  else
  {
    hourDegrees = hour * 30;
  }
  return Math.Abs(hourDegrees - minDegrees);
}

What I Learned
My biggest struggle with this was the math. It seems so simple , but I just could not figure it out in the room. I don’t know what the solution for this is… I think just breath, take a step back, and try to think in terms of mathematical operators. I want to find some interview problems that are similar to this one and see how I do solving them by myself.

What does this method do? A Bitwise Operator Question

Source
My team-lead asked me this one as interview prep

Language
C#

Question
What does this method do?

public int WhatDoIDo(int value)
{
  int a = 0;
  while (value > 0){
    a += value & 1;
    value >>= 1;
  }
  return a;
}

Process
As you might be able to tell by my recent post on binary, I was given a heads up that my team-lead would be asking me a question about bitwise operators. All I was was told was to study bitwise operators, specifically shift. Considering that I had never been able to really understand this topic in the past, I was pretty nervous and spent a lot of time studying. Thanks to that time, I was able to solve this one pretty easily! I started by walking through the method with a real value. I put in 7 and got out 3. I didn’t immediately see a pattern, so I walked through it again with input 4, output 1.

I wrote out a chart of the input/output that looked like the following, but still wasn’t able to see the pattern:

Input Output
0111 0011
0010 0001

My team-lead encouraged me to rewrite the able with the input as binary and the output as decimal:

Input Output
0111 3
0010 1

That’s when I saw it! The method returns the amount of bits that are turned “on” in the input (0111 has 3 signaled bits; 0010 has 1 signaled bit). Problem solved!

What I Learned

I was really proud of myself for this one. I went from feeling very uncomfortable with binary to being able to walk through this question very quickly. While I didn’t see the pattern immediately, I vocalized what I was seeing, and my team-lead was able to coach me towards the right answer.

Buying and Selling Stocks

Source
Interview Cake: Apple Stocks

Language
C#

Question
Suppose we could access yesterday’s stock prices as a list, where:

  • The indices are the time in minutes past trade opening time, which was 9:30am local time.
  • The values are the price in dollars of Apple stock at that time.

So if the stock cost $500 at 10:30am, stock_prices_yesterday[60] = 500.

Write an efficient function that takes stock_prices_yesterday and returns the best profit I could have made from 1 purchase and 1 sale of 1 Apple stock yesterday.

Process
My first idea was just to just brut force my way through it. I figured this wouldn’t be very efficient, but it would get the juices flowing:

public static int GetBestOutcomeGivenPrices(int[] prices)
{
  // establish starting variables
  int greatestIncome = prices[1] - prices[0];

  // get the largest difference in numbers (smallest must have lower index than highest)
  for (int start = 0; start < prices.Length - 1; start++) // for each starting time
  {
    for (int stop = start + 1; stop < prices.Length; stop++)
    {
      if (prices[stop] - prices[start] > greatestIncome)
      {
        greatestIncome = prices[stop] - prices[start];
      }
    }
  }

  // return answer
 return greatestIncome;
}

From there, I started trying to figure out a more efficient solution. I figured out a solution that only used 1 loop; I also added in some error checking in case my incoming prices list was shorter than expected.

public static int GetBestOutcomeGivenPrices2(int[] prices)
{
  if (prices.Length > 2)
  {
    // establish starting variables
    int lowestPrice = prices[0];
    int highestProfit = prices[1] - prices[0];

    // start with comparing index 1, as we've already set index 0 to the default above
    for (int i = 1; i < prices.Length; i++)
    {
      var price = prices[i];

      if (price < lowestPrice)
      {
        lowestPrice = price;
      }
      else if (price - lowestPrice > highestProfit)
      {
        highestProfit = price - lowestPrice;
      }
    }

    return highestProfit;
  }

  throw new ArgumentOutOfRangeException("The given price list must contain at least two values so that a comparison can be made");
}

Analysis

  • Solution 1: For every element, loops through every element with a higher index (nested for loops). O(n²)
  • Solution 2: For every element, do work. O(n).

Binary and Bitwise Operators

What is Binary

Like our decimal number system, binary is another way of representing numbers. Instead of counting in 10s (decimal), you count in 2s (binary). Each value in a binary number is either 0 or 1. You can add, subtract, multiply, and do other types of arithmetic on binary numbers, just like you can with decimal numbers.

  • In decimal: 45,939 = 40,000 + 5,000 + 900 + 30 + 9
    4 4 * 10 ^ 4 40,000
    5 5 * 10 ^ 3 5,000
    9 9 * 10 ^ 2 900
    3 3 * 10 ^ 1 30
    9 9 * 10 ^ 0 9
  • In binary: 101010 =32 + 0 + 8 + 0 + 2 + 0 = 42
    1 1 * 2 ^ 5 32
    0 0 * 2 ^ 4 0
    1 1 * 2 ^ 3 8
    0 0 * 2 ^ 2 0
    1 1 *  2 ^ 1 2
    0 0 * 2 ^ 0 0

So, what’s your point?

So, that’s great, we can now count in a different language… but why do we care? Well, when you’re coding, even when you type in regular decimal numbers, the compiler is converting them to binary before the computer has a chance to read them. That’s right… your computer reads binary!

Let’s say you want to store the number 27 (11011) as a variable for your program. Your compiler will tell you computer that it needs to reserve 1 byte of memory (or, 8 bits), and ask it to store the following binary number there: 0001 1011. Each digit takes up one bit of data. The extra zeros at the front don’t affect the value of the number; they just pad out the rest of the 8-bit sized byte. Each digit signals the computer off (0) or on (1). So, when you write 27, what you’re actually telling the computer is off-off-off-on-on-off-on-on, which the computer knows means 27.

So, to review:

  • Binary numbers are padded at the front so that they will take up memory in byte-sized chunks (11011 becomes 0001 1011)
  • These extra zeros don’t change the value, they just reserve the space in memory so the computer doesn’t mix up this value with another value

Bitwise Operations in C#

Now that we understand how binary numbers are stored in memory, let’s talk about C# bitwise operators. In our example from before, our variable that stores the number 27 is stored as 0001 1011 in memory. These individual bits make up 27, but the bits can also be acted on individually. That’s where bitwise operators come in. These are logical operator similar to && (logical and) and || (logical Or) that you’ve probably used in programming before. Here is how they work:

Logical And ( & )
Returns a value where there is a 1 if both original numbers had a 1 in that position. If not, there is a 0 in that position.
Example: 0110 1001 &  0000 1111 = 0000 1001

Logical Or ( | )
Returns a value where there is a 1 if at least one of the original numbers had a 1 in that position.If not, there is a 0 in that position.
Example: 0110 1001 &  0000 1111 = 0110 1111

Exclusive Or ( ^ )
Returns a value where there is a 1 if only one of the original numbers had a 1 in that position.If not, there is a 0 in that position.
Example: 0110 1001 &  0000 1111 = 01100110

Complement ( ~ )
Returns a value that is the exact opposite of the bit values of the given values; 1 becomes 0 and 0 becomes 1.
Example ~1100 1101 = 0011 0010

Shift Left ( << )
Takes in a value and a number that represents how many digits to shift. The result is a new binary number where the original number has been shifted x amount of positions to the left, and then padded out with zeros on the far right side.
Example: 0010 1001 << 2 = 1010 0100

Shift Right ( >> )
Takes in a value and a number that represents how many digits to shift. The result is a new binary number where the original number has been shifted x amount of positions to the right, and then padded out with zeros on the far left side.
Example: 0010 1001 >> 3 = 0000 0101

Negative Numbers

Up until now, we’ve only worked with positive numbers in binary, but there are actually a couple of different ways to express negative numbers in binary. The most common way is via Two’s Complement. Here are the rules:

  • When working with two’s compliment binary numbers, we must predetermine what size number we’re working with (4-bite, 8-bite, 16-bite, etc), and then pad out with zeros as needed.
  • The left most bit, known as the Most Significant Bit, in addition to representing a number, now also represents whether the entire number is positive or negative.
  • Numbers that use Two’s Complement are known as ‘signed,’ whereas the numbers we’ve been working with up until this point are known as ‘unsigned.’
  • To get the Two’s Complement version of an unsigned binary number, you simply invert it (reverse the 1s and 0s), and then add 1 to the final result.
    -13 Start with a negative number
    13 Take the absolute value
    1101 Convert the positive number to binary
    0000 1101 Pad out the number with extra 0s to be the amount of bits as established (8 bit in this case)
    1111 0010 Invert the number
    1111 0011 Add 1 to the final result
    -13 Convert back to decimal (-128 + 64 + 32 + 16 + 2 + 1 = -13)

Real World Application

Using bitwise operators to determine if an item exists within a collection of items. This first example makes it pretty simple to understand because of the enum. However, enum also has a build in method (Enum.HasFlag(Enum flag)) that does the same thing. Still a good example!

public class Program
{
  // Each item in the enum aligns with a base 2 number
  public enum Animals {Cat=1, Dog=2, Elephant=4, Hippo=8, Rhino=16, Giraffe=32};
 
  public static void Main(string[] args)
  {
    // Use bitwise OR operator to get binary value 0011 1100
    Animals myFavAnimals = Animals.Elephant | Animals.Hippo | Animals.Rhino | Animals.Giraffe;

    // Do an AND compare between our collection (0011 1100) and the item we're checking for (0000 0001).
    // In this case, & will return 0000 0000, so the check will be false
    if ((myFavAnimals & Animals.Cat) == Animals.Cat){
      Console.WriteLine("Cats are one of my favorite animals");
    } else {
      Console.WriteLine("Cats are NOT one of my favorite animals");
    }
 
    // ((0011 1100) & (0000 0100) = 00000100 == 0000 0100) evaluates to true
    if ((myFavAnimals & Animals.Elephant) == Animals.Elephant){
      Console.WriteLine("Elephants are one of my favorite animals");
    } else {
      Console.WriteLine("Elephants are NOT one of my favorite animals");
    } 
  }
 }

Another example uses binary operators to help solve a Sudoku. This method takes in a collection of Sudoku values (a row, a column, or the values in a square) and then validates if there are any repeats

private bool ValidateValues(int[] values)
{
  int flag = 0;
  foreach (int value in values)
  {
    if (value != 0)
    {
      // get the bit that will represent n, where the flagged value (the 1) is in the value-th position in the binary number
        int thisBit = 1 << value;
        if ((thisBit & flag) != 0)
        {
          // there is a duplicate, because n lined up with a bit that has already been accounted for in values
          return false;
        }
        // No duplicate. Glad this value in the overall flag for next time
        flag |= thisBit;
    }
  }
 return true;
}

Resources

This topic is especially difficult to grasp at first. When I first learned this stuff, my exact thought was “Why do I care?” It seemed irrelevant and way too difficult to make it worth it. Coming back to it a few months later, it’s so much easier to understand, and I was able to get the real-world application. Here are a few of the links that I found the most helpful:

Breadth-First Traversal of a Binary Tree

Source
My team-lead asked me this one as interview prep

Language
C#

Question
Here’s how you traverse a binary tree depth-first:

class Node<T>
{
  public T Value;
  public Node<T> Left;
  public Node<T> Right;

  public static void PrintTreeDepthFirst(Node<T> node)
  {
    if (node != null)
    {
      Console.Write(node.Value);
      PrintTreeDepthFirst(node.Left);
      PrintTreeDepthFirst(node.Right);
    }
  }
}

How would you traverse a tree breadth-first?

Process
My team-lead had to coach me through this, but once again, it’s easy once you know the trick!

public static void PrintTreeBreadthFirst(Node<T> node)
{
  Queue<Node<T>> q = new Queue<Node<T>>();
  q.Enqueue(node);
  Node<T> current;
  while (q.Peek() != null)
  {
    current = q.Dequeue();
    Console.Write(current.Value);
    q.Enqueue(current.Left);
    q.Enqueue(current.Right);
  }
}

What I Learned
Once again, I had never worked with a binary tree in practice, only theory. It’s a more complex data structure, but is so practical for so many business purposes!

Implement a Queue using Stacks

Source
My team lead asked me this one as interview prep

Language
C#

Question
Implement a functioning queue with Enqueue, Dequeue, and Peek methods, using only stacks as the data type.

Process
My team lead had to coach me through this on the white board, but I went back to my desk and replicated it pretty quickly. It’s pretty simple once you know how it works!

public class Queue<T>
{
  Stack<T> backOfLine;
  Stack<T> frontOfLine;

  public Queue()
  {
    backOfLine = new Stack<T>();
    frontOfLine = new Stack<T>();
  }

  public void Enqueue(T value)
  {
    backOfLine.Push(value);
  }

  public T Dequeue()
  {
    if (!frontOfLine.Any())
    {
      EmptyBackStackToFrontStack();
    }
    return frontOfLine.Pop();
  }

  public T Peek()
  {
    if (!frontOfLine.Any())
    {
      EmptyBackStackToFrontStack();
    }
    return frontOfLine.Peek();
  }

  private void EmptyBackStackToFrontStack()
  {
    while (backOfLine.Any())
    {
      frontOfLine.Push(backOfLine.Pop());
    }
  }
 }

What I Learned
I had only learned about queues and stacks in theory before working through this problem. I feel at lot more confident with both of these data types, and want make an effort to find opportunities to use them where they make sense.

Arrays and Strings: Is Unique

Source
CtCI, Chapter 1, Question 1.1

Topic
Arrays and Strings

Language
C#

Question
Is Unique: Implement an algorithm to determine if an array has all unique strings. What if you cannot use additional data structures?

Process
My first though was to iterate through the array, adding each item to a new array, which I would search through each time I added an element.

//Solution 1
public bool IsUnique(string[] arr){
  string[] newArray = new string[arr.Length];
  for (int i = 0; i < arr.Length; i++){
    if (newArray.Contains(arr[i])){
      return false;
    }
    newArray[i] = arr[i];
  }
  return true;
}

Then I tried to solve the problem without using the additional “newArray”. My first though was if there was some LINQ tool that could solve this for me. I didn’t know off the top of my head, so I looked it up. While there is a .Distinct within LINQ, it does not return a boolean; it returns a new list of distinct items from the original collection. I could use that and compare the counts, but I would technically have created an additional data structure, so this does not solve the problem. It did seem better than my original solution though, so wrote it out:

//Solution 2
public bool IsUnique(string[] arr){
  string[] newArray = arr.Distinct().ToArray();
  if (newArray.Length < arr.Length){
    return false;
  }
  return true;
}

My next idea was to compare each item in the array to each other item by iterating through the array twice. This would solve the problem, but I wasn’t sure if it was possible. Turns out that is was pretty simple (though I accidentally the for to set j=i+1 at first, which meant that the function always returned false. But, it did solve the entire problem!

//Solution 3
public bool IsUnique(string[] arr){
  for (int i = 0; i < arr.Length; i++){
    for (int j = i+1; j< arr.Length; j++){
      if (arr[i] == arr[j]) {
        return false;
      }
    }
  }
  return true;
}

After finding my own solution, I checked out the hints in Cracking the Coding Interview. The first one was: Try a Hash Table. A solution wasn’t immediately clear to me, but I figured that if I assigned each word in the array to a key in the hash table, a duplicate key exception would lead to a false return. However, I didn’t want to use the exception as part of my logic flow, so I thought I would try using the word as the key and then incrementing the count as the value. While writing this code, I realized that I could simply check if the hashtable contains the key, and if it does, I could return false; I wouldn’t have to increment the value. The value wouldn’t really actually matter. That said, this is pretty much identical to my first solution, just using a hashtable instead of an array.

//Solution 4
public bool IsUnique(string[] arr){
  Hashtable ht = new Hashtable();
  foreach (string s in arr){
    if (ht.ContainsKey(s)){
      return false;
    }
    ht[s] = 0;
  }
  return true;
}

After reviewing the book’s solution, I realized that my last solution efficiency could be improved by using an if statement, and testing if the value was not null. This would prevent me from having to loop (via Hashtable.ContainsKey).

//Solution 5
public bool IsUnique(string[] arr){
  Hashtable ht = new Hashtable();
  foreach (string s in arr){
    if (ht[s] != null){
      return false;
    }
    ht[s] = true;
  }
  return true;
}

Analysis

  • Solution 1: Loops through each element once, and then loops through the entire array (Array.Contains) for each iteration of the first loop. O(n²)
  • Solution 2: Loops through the array once when it queries it for distinct values. O(n)
  • Solution 3: Loops through the array once, and then loops through each remaining element for each element. O(n²)
  • Solution 4: Loops through each element, and then loops through each key in the hashtable for each element (Hashtable.ContainsKey). O(n²)
  • Solution 5: Loops through the array until it “fails”. O(n)

Notes

  • I wrote all of my Array.Length with the wrong case originally; I wrote Array.length. Writing C# outside of Visual Studio is new to me, and this is an example of the kind of thing that I’m going to need to memorize for when I can’t rely on IntelliSense. That said, this one should be pretty easy to remember. Array.Length is a public getter, and is therefore capitalized.
  • This was the first time using a HashTable (I had only used Dictionaries). I’ll want to study up on the available helper function for this data structure.
  • I did not think of using the hashtable until the prompted by the book. I’ll try to keep this method in mind for other problems.