Algorithms & Data Structures

Anagram check in a JavaScript interview?

I was recently at a job interview for a position related to Angular and C# development. After a few questions about design patterns and CSS I was finally asked to code something. I was never one to dislike technical interviews, even the whiteboard ones. Because I know that interviewers value the thought process more than the actual result. I know. I’ve been there.

But what surprised me was that the task at hand had nothing to do with Angular or C#. Instead it was a traditional interview question regarding anagrams.

So the interviewer asked me to code a function that would check if two strings are anagrams of each other.

The strategy when faced with a task like that is to first ask your interviewer some questions that you may have regarding the problem. If you don’t have any questions it’s always nice to repeat the problem back to your interviewer. Remember, they’re not just after your impressive coding skills, they want to see you’re equally able to communicate, an area in which quite a lot of developers are inferior.

After showing that you can communicate effectively, it’s time to analyze the problem. Again it’s imperative that you think out loud. If you sit silent staring at the keyboard, or the white board depending on your situation, two things will happen. First, you may be synthesizing the most architecturally and algorithmically perfect solution based on your impeccable skills and incomparable experience, but the interviewer might as well think that you’ve frozen. So, again, communicate. The second thing that’s gonna happen is that if you haven’t figured out the solution, anxiety will eventually cripple you. By talking you get your brain to start thinking. You can’t go from “completely frozen” to “devising the perfect algorithm” just like you can’t get your car from stationery to running at 200km/h in a second’s time.

Don’t attempt to arrive to the optimal solution on first try. Start by finding something that works. In the case of the anagram problem, the first possible solution that I mentioned was to create a “dictionary” for storing each letter in each word along with the number of times that the letter appears within the word. So of we have the strings “baba” and “abba” the we would have two equivalent objects like this:

Literally five seconds after recommending that solution to the interviewer, an actual better solution came to my mind. I would sort the two strings and then compare them. If they’re equal then we have an anagram.

The final touch that I added was an initial check of the strings’ lengths. If the strings don’t have equal lengths then we can immediately return false because we can be absolutely certain that the strings are not anagrams of each other.

The final algorithm after optimizations looks like this:

A fairly simplistic approach with chained calls to split, sort and join to enhance readability.

That’s it for today. I hope you found this answer to a common interview question helpful. See you next time.

dimlucas Leave a comment

Level-order traversal of a Binary Tree

Level order traversal is different from other more common types of tree traversal algorithms such as in-order, pre-order or post-order. Level order traversal visits the nodes level by level. Once it’s done with the root (level 0) it moves to level 1, then to level 2, e.t.c. Perhaps the two most major differences between level-order traversal and the other 3 algorithms are that:

  1. It is an iterative algorithm
  2. It makes use of an extra data structure, a FIFO queue.

The reason why we need to use a queue is because we have no easy way of travelling backwards in a tree.

For example, in the following tree, if we are at the node with value 2, it may be easy to go to node number 5, but what about node 8?

binarytree
(Node-2 and Node-8 belong to different subtrees, accessing one from the other requires going backwards)

The only node that connects these two nodes (formally called the Lowest Common Ancestor) is node number 6, the root of the tree. Now imagine a very deep tree with countless of leaves and the problem gets downright impossible.

That’s where the queue comes into play. The algorithm is pretty simple.

  1. Push the root into the queue
  2. While the queue is not empty
    1. Pop a node from the queue (Remember a queue works in a First-In First-Out way)
    2. Do something with its data
    3. Push its children into the queue
  4. By the time the queue is empty, the algorithm will have visited all nodes

Let’s apply level-order traversal to the above tree to visit and print all of its nodes. We start with a queue that only contains the root of the tree.

Queue: node-6
Output:

First loop (Level 0)

We begin by taking the first element out of the queue, which of course is the root of the tree. We print its value to the output and push its children into the queue

Queue: node-6, ode-4
Output: 6

Second loop (Level 1)

We take node-9 out of the queue, print its value and push its two children into the queue

Queue: node-4, node-2, node-5
Output: 6, 9

Third loop (Level 1)

We take node-4 out of the queue, print its value and push its right child into the queue

Queue: node-2, node-5, node-8
Output: 6, 9, 4

Fourth loop (Level 2)

We take node-2 out of the queue. Node-2 does not have any children so nothing gets pushed to the queue. We just print “2”.

Queue: node-5, node-8
Output: 6, 9, 4, 2

Fifth loop (Level 2)

We take node-5 out of the queue. Node-5 has no children nodes so we just print its value and move on

Queue: node-8
Output: 6, 9, 4, 2, 5

Sixth loop (Level 2)

We take node-8 out of the queue. Node-8 has no children nodes, so we print “8” and then notice that the queue is empty. So the sixth loop is the final one and we’ve managed to print all elements of the tree in a level-order from left to right.

Queue:
Output: 6, 9, 4, 2, 5, 8

Now to the C++ implementation of the algorithm:

Each node is described by the following struct:

And here’s the levelOrderTraversal function

The C++ Standard Library provides a FIFO queue out of the box accessible to you by including the header. However you can still use a custom implementation of it if you like .

dimlucas Leave a comment

Post-order Traversal of a Binary Tree in C++

If you know about pre-order traversal you know that it visits the root first and the subtrees later. If you know about in-order traversal you know that it visits the nodes in-order (duh), first the left subtree , then the root and finally the right subtree. The remaining combination is to operate on the root when you’re done with the subtrees. That’s what post-order traversal does.

Let’s see an example of printing all the nodes of a tree using post-order traversal:

binarytree

Starting from the root the post-order traversal algorithm will visit the left subtree, the right subtree and then return to the root node when it’s done.

Output so far:

We visit the left subtree on node-9 and move on its own subtrees until we find the tree’s leaves.

Output so far:

When we reach node-2 there are no left and right subtrees so we print it

Output so far: 2

Same way with node-5

Output so far: 2, 5

We return to node-9 and since we’re done with its subtrees we print the value 9

Output so far: 2, 5, 9

Back to node-6. We haven’t yet visited its right subtree so on we go

Output so far: 2, 5, 9

Node-4 has no left subtree, so we visit its right-hand one.

Output so far: 2, 5, 9

We visit node-8’s left and right subtrees which are empty and then return to node-8 and print its value

Output so far: 2, 5, 9, 8

Now that we’re done with node-4’s subtrees we print its value

Output so far: 2, 5, 9, 8, 4

We’re done with both subtrees of our tree’s root, node-6. It’s time to print its value too.

Output so far: 2, 5, 9, 8, 4, 6

And that’s it. We’ve traversed the tree In a post-order fashion and have printed its nodes.

The algorithm that achieves that in C++ is the following:

dimlucas Leave a comment

In-order Traversal of a Binary Tree in C++

In-order traversal is probably the most widely used type of tree traversal algorithm mainly because when applied to Binary Search Trees it can operate on the nodes in order (duh!). The in-order traversal algorithm first operates on the left subtree, returns on the root operates on it and then traverses the right subtree.

To demonstrate the algorithm we’re going to print the integer values of a binary tree whose nodes are described by the following struct:

An unconventional and not very scientific way to think about the algorithm is that it visits nodes in this order:

  1. Left
  2. Middle
  3. Right

It helps if you’re trying to visualize it. Speaking of visualization let’s see an example of the algorithm in action. We have the following binary tree:

binarytree

Starting from root-node 6, the algorithm will check if the node is NULL and since it is not, it will visit its left subtree first, then it will return print 6 and visit the right subtree.

Output so far:

We are at node 9, the start of node-6 left subtree. The node is not NULL so the algorithm goes deeper to the next left subtree

Output so far:

Node 2, also not null. The algorithm goes to the left again

Output so far:

We’ve bumped into NULL, the function returns control to the caller. So we’re back at node 2. We print it

Output so far: 2

Now it’s time for the right subtree. We visit it, find out it’s NULL and then return to node-2. Node-2 is done so back to node-9

Output so far: 2

We’re done with node-9’s left sub tree so we print 9 and head over to its right subtree

Output so far: 2, 9

We’re at node-5, it’s not NULL so we go to its left subtree which is NULL so we return to node-5, print 5 and move to the right subtree which is also non-existent so we go back to node-9

Output so far: 2, 9, 5

We’ve printed node-9’s left subtree, its own value and its right subtree so we’re done and return to node-6. We print 6 and move to the right subtree

Output so far: 2, 9, 5, 6

We are at node-4 which is not NULL so we visit its left sub-tree

Output so far: 2, 9, 5, 6

Node-4’s left subtree does not exist so we return to node-4 and print its value

Output so far: 2, 9, 5, 6, 4

Next, we visit node-4’s right subtree at node-8

Output so far: 2, 9, 5, 6, 4

Node-8 is not NULL so we visit its left subtree. Node-8’s left subtree is NULL so we return to node-8 print its value and visit its right subtree

Output so far: 2, 9, 5, 6, 4, 8

Nothing here so back to node-8. But we’re done with node-8 so back to node-4. Node-4 is also finished, so back to the root. The root is also finished so we’re done.

Final Output: 2, 9, 5, 6, 4, 8

Here’s the code of in-order traversal in C++ :

dimlucas Leave a comment

Pre-order Traversal of a binary-tree in C++

The pre-order traversal algorithm is a traversal algorithm that visits the root node of the tree first, and then recursively visits the left and right subtrees for binary trees, or every other subtree for non-binary ones. In this blog post we’re going to see how the recursive pre-order traversal works. An iterative method is also possible with the use of a stack but I find the recursive method more intuitive, plus if you’re not yet familiar with recursive functions, then recursive tree traversal algorithms is a very nice place to start. To demonstrate the algorithm we are going to print the values of a tree in a pre-order fashion.

Every node in our Binary Tree representation is described by the following struct:

We will be using integers for this example but of course a binary tree may contain whatever data type is needed. You can replace int data with char data or double data, or, even better, use Abstract Data Types and C++ templates. The left and right pointers point to the left and right subtree respectively.

The first thing the algorithm does is to check if the node passed to it is actually a valid node. If it isn’t, the algorithm stops and does nothing more. I know this may sound obvious but it’s vital to understanding the algorithm as you’ll see later in this post.
If the node is an existent one (not NULL) the value of the node gets printed and then the algorithm visits the left subtree followed by the right subtree. Notice that I’m not saying left node but left subtree, so after the root node gets printed the algorithm will visit the left subtree recursively and only after the left subtree has been dealt with, will the algorithm move on to the right subtree. And this is applied recursively to the subtrees of the subtrees and so on.

Ok, enough with theory. Recursive algorithms and especially tree traversal ones are best explained with the use of an example.
Let’s say we want to traverse the following tree:

binarytree

 

Starting at the node we print the value 6 and then do a pre-order traversal of the left subtree. Only after we’re done with the left subtree will we move to traverse the right one.

Output up until now: 6

The algorithm visits the node with value 9, it’s not null so it prints the value to the output and then traverses the left subtree (the one starting with the value 2)

Output up until now: 6, 9

We’ve reached the node with value 2, the node is not a NULL one so we print the value and move to traverse the left subtree

Output up until now: 6, 9, 2

The left subtree of node 2 is non-existent!. We’ve passed NULL to our algorithm so it will stop. There is nothing more in the left subtree so the algorithm will now visit the right subtree. What subtree? The one on the right of node 2. But that’s non-existent too. So the algorithm is done with the subtree starting at node 2 so it goes back to node 9. The traversal of this node’s left subtree is over so the algorithm will visit its right subtree, namely node 5

Output up until now: 6, 9, 2, 5

Node 5 does not have any child nodes so we’re back at node 6, the root of the tree. Now it’s time to explore the right subtree. The algorithm goes to node 4, prints it and moves to its left subtree

Output up until now: 6, 9, 2, 5, 4

Node 5 does not have a left sub tree, nothing to do here, back to 4. Time to search the right subtree. The root of the right subtree is 8, the algorithm prints it

Output up until now: 6, 9, 2, 5, 4, 8

No left, or right subtree for node 8, back to node 4. We’ve visited both subtrees of node 4, so back to node 6. Same thing here, so we’re done. We’ve traversed the whole tree.

Now let’s see how this translates into code:

As we’ve seen earlier in this post, the algorithm stops if the given root is NULL. If the node is not NULL the algorithm immediately prints the data and then moves on to do the same for the left and right subtree. That’s it! It’s actually simple.

A variation of the algorithm that actually results into a smaller call stack size, checks the left and right subtrees before traversing:

The check for NULL takes place in both algorithms so the second one is a very minor optimization because of the fewer function calls. However the first algorithm seems cleaner and easier for beginners to grasp.

dimlucas Leave a comment