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).

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.