Computer MAD SCIENCE. A queue?! With two stacks?!!

You're receiving this issue as a Coding for Interviews newsletter member or a new visitor from the Coding for Interviews course. Welcome new members, glad to have you on board!

Quote of the week

"What is a group of software developers called? A merge conflict."

Links of the week


Topic of the Week: Breadth-first Search

Breadth-first search is a tree traversal algorithm that visits the nodes of a tree level by level, increasing the depth after each row's traversal.

What is BFS used for?

You'll come across BFS in a few common situations—

  1. finding the shortest path between two nodes in a graph—like LinkedIn finding the friends-of-friends.
  2. filesystem traversal—while UNIX find is a pre-order depth-first search, some prefer breadth-first for faster searches in certain situations (like this Emacs-er from 1999)
  3. generally printing hierarchies in rank-order... e.g., if you wanted to print a tree of military officers by their level in the rank hierarchy

What does it look like?

Pop quiz, hot-shot! You have a tree. And your task is to verbally breadth-first traverse it. What do you do?

Well, a breadth-first printing of the tree would be 1 2 3 4 5. Each row, you visit the nodes from left to right.

How do you perform a BFS?

When you’re performing a breadth-first traversal, you need some sort of way to keep track of where you’ve been (otherwise, looking at a given node, you wouldn’t know which node to visit next).

One way is to use a queue to maintain a list of nodes to visit next, remove the nodes and their add children to the end of the queue as you visit them.

The general steps:

  1. Add the root node to the queue
  2. While there are still any nodes in the queue:
    • Remove and visit the front node in the queue
    • Add each of the current node's children to the queue

Here's an animated version (from Wikipedia on BFS)—gray nodes are the ones remaining in the queue. Black nodes are the ones which have been visited.

BFS -> DFS with just one swap

If you swap out the queue in that algorithm for a stack, you'd get a depth-first search. Can you wrap your head around why that is?

In graphs to avoid cycles

Unlike trees, graphs can have cycles—paths from a given node around to itself. When you're performing a breadth-first search of a graph, you will want to avoid getting caught up in these cycles, as they can cause the algorithm to never terminate (though, unlike depth-first searches, it will continue to traverse the entire graph).

To counter this, a common approach is to mark visited graph nodes as you go along and ignore them when encountered later. This marking can be done either as an attribute on the node or by maintaining a set of visited nodes.

This week's challenge: The Staqueue

This week's challenge—not directly related to BFS—is to implement a queue using two stacks.

Queues are a first-in-first-out data structure that we just saw used as a "next to visit" data store in breadth-first search.

Stacks are a last-in-first-out data structure used in depth-first search, and can often be used to implement recursive algorithms iteratively (because the call stack is, itself, a stack).

For this problem, you are to create a queue using two stacks. So your Queue will support the operations:

  • enqueue(item), which inserts an item into the queue
  • dequeue(), which removes and returns the oldest item in the queue

Your two Stacks (which your programming language may have available already, otherwise you can create your own pretty easily) have the following operations:

  • push(item), which inserts an item at the top of the stack
  • pop(), which removes and returns the top item of the stack

Let's say we just tried using one stack as a queue, pushing instead of enqueueing:

Not so easy! (BTW—we'll see the wonderful source of these animations with next week's solutions).

Can you figure out a way to make a queue using two stacks? Give it a shot, if you get stuck, try drawing some pictures or working through sample inputs with your work-in-progress. Good luck!

Time complexity: what is the time complexity of your solution? An O(m) solution is possible, where m is the number of enqueue and dequeue operations performed. Can you figure one out? Hint—does it matter if an operation is expensive the first time you do it, and then really cheap afterwards?

Bonus points for solutions with visualizations!

Extra bonus followup: Use your fancy new Queue to hold integers, but now add an O(1) time getMinimum operation, which returns the smallest integer in the queue. What are the extra space requirements for this operation?

Thanks to group members Asim Ihsan, Andrew Yates and Greg Jordan for their feedback on this issue!

Submitting your answer

Reply directly to me with your solutions (photos of paper or whiteboards uploaded to imgur get bonus points) and you may be featured in next week's email. If you typed your solution out, you can post your code as a gist and reply with the link.

Last week's challenge: The Big 3 Language Questions

Last week's challenge was to research programming language paradigms (from the course / free cheat sheet) and think up answers to the following classic interview questions:

  1. What do you like about your most often used programming language?
  2. What don't you like about it, and why?
  3. What paradigms does your language support?

Responses from group members:

Two wonderful responses from last issue!

How CFI ruined Michael's relationship with Python (jk)

Excerpt from Michael's solution writeup, in which there are many things he likes about Python, too.

Until recently, I didn't really have much to say about why I don't like Python.

But then, I saw "Python vs. Ruby: a Battle to the Death". One of the great points made in the video is:

Python is relatively syntactically inflexible.

In plain English, this means that you can't extend the Python language itself by adding things like new control statements. This is possible in some other languages, like Ruby. Syntactic flexibility enables more expressive code like RSpec and makes mundane testing code read more like plain English. To summarize, the above video offers the opinion:

Ruby is ugly; Python is beautiful Nose is ugly; RSpec is beautiful

After playing around with Ruby for a short while, I'm starting to agree.

Got the job?!

While my mailing list fees are fueled by course purchases and writing web scrapers, I am fueled by your encouraging stories.

Even if you can't get the always-expanding Udemy course, it's great to hear when people are enjoying the week's issue—reply to me and let me know how your interview preparation is going!

Leave your friends speechless

I end up putting some significant time into preparing our topic overviews and collecting submissions—but the upshot of it is something that's roughly the same amount of work no matter how many of our friends receive this weekly prep. It's like O(log (us and our friends)).

Makes sense to give your friends and colleagues a link to join us: http://codingforinterviews.com/ so you can practice with them!

Follow the group at: https://twitter.com/interviewcoding

Code every day. Continue improving,

Brian (@bcjordan)

PS. As always, if you order the course and would like the full CFI issue archive, email me with the full name you registered with on Udemy and I'll send you the back issues.