Posts
-
Binary Tree Traversals
For this post, we will take a slightly different approach. Instead of covering a single problem, we will cover a slew of related tree traversal problems. But before we start with the traversal algorithms, let’s talk about how we can create a Balanced Binary Search Tree from a sorted array. It’s an interesting problem because it combines tree creation with Binary Search.
-
Letter Combinations of a Phone Number
In the lowest common ancestor post, we briefly talked about backtracking. In this problem, we will dig a little deeper into that idea. Here the problem is figuring out for a given number sequence, all possible strings it could represent based on a mapping (think of your smartphone’s dialer app and how each number has a set of letters on it).
-
Lowest common ancestor of two nodes in a binary search tree
In this post, I’m going to go over the problem of finding the lowest common ancestor of two nodes in a binary search tree. There is a recursive way to solve this problem without using extra space. I want to solve it using some extra space to get a better handle on the problem. This implementation I believe is easy to understand and in fact was acceptable in one my interviews.
-
Random pick weight
In this post, I plan to tackle the problem of picking a number based on a given weight (probability). In Leetcode, this is called Random pick with weight problem. The main thing I want to highlight here is how we can use pure STL constructs to solve the entire problem in 5 lines. Of course, we’d want to know how binary search works. But it is also useful to know the STL libraries that implement binary search for you.
-
Add two numbers represented as linked lists
Today, I want to tackle a simpler problem of adding two numbers represented as linked lists. Each node contains a digit between 0 and 9. This problem will use some of the techniques we used in the merging of k sorted lists. Even though this problem is quite simple to solve, it helps build intuition on solving linked list problems.
-
Zigzag Level Order Traversal of Binary Tree
In this post, I’m going to tackle a medium difficulty problem called Binary Tree Zigzag Level Order Traversal. I believe this is an important technique to learn while doing a breadth first traversal of a tree. This approach is generic enough to be used with many other leetcode problems.
-
Merge k sorted linked lists
The next hard problem I want to tackle is merging of k sorted linked lists. An obvious way to solve this problem is by copying all the values from the k lists into a vector and sorting the vector. This is extremely inefficient both in terms in time and space complexity. If N1, N2, …, Nk are the sizes of each list, let’s call N = N1 + N2 + … + Nk. Then space complexity of such an approach would be O(N). Time complexity would be O(NlogN). Here’s this simple approach:
-
Vertical order traversal of a binary tree
I recently got back to Leetcode to keep myself sharp with interview style coding exercises. This time around, I am trying to solve problems that are medium or hard. One such problem is the vertical order traversal of a binary tree.
-
ARM NEON vector sum
Recently I was working on optimizing a piece of code for ARM architecture using NEON intrinsics. But, I found the documentation quite dense for beginners. This is an introduction post for those interested in optimizing their code for ARM processors. If you are not familiar with it, the usual way to optimize math operations for ARM processors is by using the NEON instruction set. Basic idea is to load several items into the registers and do operations in batches.
-
Nqueens using Webassembly
In the last post, we discussed the 8 queens problem and showed some C++ code. But, when we wanted to use it in Web (without any server side interaction), we had to give away our source code and also had to rewrite everything in Javascript. Is there a way to hide the code and also reuse the C++ code, you ask? Yes, there is. It is called Webassembly. I will show you how.
-
Nqueens
These days, I spend a lot of time doing cross-platform development. Meaning, I write a lot of native (C/C++) which then gets compiled for all sorts of platforms (Windows, Linux, Android, iOS with x86, x64, ARM, ARM64 architectures). There are so many little things I have learnt in the past two years at work. I want to document some of those things so it can help others.
-
Catch2 test framework
In one of our previous posts, we discussed the LRU cache algorithm. How do we go about writing tests for such an algorithm or in general any code we write? There are a multitude of test frameworks to choose from - Google Test, Boost Test, etc., But, I am going to cover the Catch2 framework here as it is very easy to get started with and works really well for most simple use cases. It is also a single header file so very simple to integrate.
-
LRU cache
Another interesting algorithm I ran into recently is for a Least Recently Used (LRU) cache. Imagine a caching system that stores key-value pairs. And you have room for only a limited number of key-value pairs. So, when the capacity is exceeded, we need to remove the least recently used (used means accessed) key-value pair. This can be simply implemented using a linked list to keep track of which key was accessed least recently. Whenever a key is read / written, we can just move the corresponding linked list node to the head of the list. And when the capacity is exceeded, simply delete the last key in the linked list and remove that key-value pair from the hash table. Hash table look up is O(1). So is removing a node and adding it to the head of the list. But, what about figuring out where the key is in the linked list itself so we can move it?
-
Word Break
I recently ran into this interesting problem called “Word Break” - quite a popular interview question. If you want to practice solving this problem, head over to leetcode. First variant of this problem is quite simple. Given a string, check if it can be split into words to form a full sentence. You are also given a dictionary to check if the word is valid or not. For example, given a string “thisisatest” and a dictionary (list of words) - “this”, “is”, “a”, “test”, your function should return true. For the same dictionary, “thisisnotatest” should return false.
-
Optimized Integer Programming
For one of my side projects, I had to solve an Integer Programming problem. I was initially contemplating on using some existing MATLAB/Octave package to the job. The first option that was available was the Genetic Algorithm module in MATLAB. It turned out to be too random and not methodical at all. This is not surprising as genetic algorithm is in essence a random algorithm and does not suit all kinds of problems. It could work for some problems. Next option was Simulated Annealing. Even for this, there was a package in MATLAB. It worked ok but the convergence was too slow for my needs. So, I ended up writing my own custom gradient descent algorithm to solve this problem using Python. In this article, I am going the detail the algorithm and the design choices.
-
Neural Network Implementation of an XOR gate
I have been meaning to refresh my memory about neural networks. As any beginner would do, I started with the XOR problem. In fact, this was the first neural network problem I solved when I was in grad school.
-
Binary Search
Binary Search is probably one of the first algorithms Computer Science students learn. It is quite simple to implement but you are likely to run into a couple of corner case scenarios. As codekata puts it, practicing it over and over helps. Not just praciticing writing the same code, but trying to achieve the same results through different implementations. A note on choice of language: I chose Python for its simplicity of accessing and slicing lists.
-
Logistic Regression Theory
Several years ago, I took multiple Machine Learning related courses on Coursera. And I did a quite a few projects on those courses. I don’t really have the results or the code documented anywhere. So, I am starting a small Machine Learning series to help me also recollect all those projects. One of the first projects we did on the Coursera ML course is Digit Recognition. There is a well known digit dataset called MNIST. For the course though, we used a small subset of the dataset. We have a set of scanned images which contain numbers and we have to design a model to correctly classify them. Before we look into the full classification, it makes sense to start with something simpler. How about just classifying the 0s and the 1s?
-
Setting up your own site with Flask
If you want to host your own blog with minimal setup time, you could use something like tumblr or wordpress. But, if you are like me, you would want to code everything up yourself. Flask is a very lightweight Python based framework which supports templating, database support etc., Flask provides some excellent documentation on how to set it up to write your own blog system. But, I ran into a few snags. So, I thought of sharing some of the gotchas.
-
Practical Queues
Queue is one of the simplest data structures around. Understanding queues is very simple if you just use a primitive data type like say integer. In fact, most tutorials leave you with just that implementation. Here, I am going to start with that implementation but will eventually expand it to work with any datatype you want.
-
Learn to love the heap
I have never used the heap datastructure in my life till recently. I didn’t think it was that useful. But, after using it to solve this order statistics problem, I am in total love with this datastructure. My first theoretical exposure to heap came when I took the Algorithms course by Robert Sedgewick. This is a great course. You can pretty much find all the videos for the course on Youtube.
-
Ecobee Experiments
I got a free ecobee thermostat from my utility company. It was a big step forward from my older analog Honeywell thermostat. For one I could use an iPhone app to control the thermostat. Their App is great and all. But, I need to click through 5 different buttons to turn off my thermostat. I got lazy and so I got inspired. I went and looked into their developer API which turned out to be a pretty good reference. Best place to start is their examples page.
-
Little Javascript tricks for your chrome extension
While developing my chrome plugin Shut up and cast, I learned a lot of tricks in Javascript. I shared one of them in them in the last post. In this post, I am planning to share a few small tricks.
-
The Old Switcheroo
I recently learned (the hard way, as usual) something about the Switch statement in C. I had a part of code which I want executed for all the cases in the switch statement. So I naively put that statement just above the first case statement inside the switch structure.
-
Sending data to your site from your Chrome Extension
How to open a new tab with a specific address from your Chrome extension is well documented in Google’s help articles. For completeness sake, let us start with discussing this. Before we create a new tab, we should add permissions for accessing “chrome.tabs” in your
manifest.json. -
Design of Antenna Arrays using Windows
When I was in grad school, I wrote a paper on how to design Antenna Arrays using Window functions. I uploaded it to Academia.edu and forgot all about it. Once in a while I get an email from Academia.edu that someone searched for me. I got intrigued today and did a google search for “Antenna Arrays Windows” and was surprised to note that my paper is the second best match
. Here is my shameless
blog article to get that traffic to come to my site instead. If you prefer a PDF version
of the paper, you can find it here. -
Announcing shut up and cast
Thanks for the 4000 odd users of my previous chrome plugin Stream to XBMC, I have decided to extend the plugin’s capability to be used with the most popular casting device and the one which started it all, Chromecast. If you have a Chromecast and want to watch videos from sites for which there is no Chromecast app, you have come to the right place.
-
How scripting languages spoil you
I love Python. But, I have to admit that it spoils you. I just spent 20 minutes trying to code up a simple program to do linear regression. This problem looks deceptively simple. In fact, it is deceptively simple, on paper.
-
HOWTO: Using Openssl C library
For one of the Matasano crypto challenges, I had to decrypt the text which was encrypted using AES in ECB mode. Everything about AES is actually documented by the National Institute of Standards and Technology. You can get all the algorithms behind AES encryption. It is probably not a good idea to implement it from scratch. Openssl has a well tested and widely used library which works.
-
Hex to base64 conversion
I came across another set of online coding challenges called The Matasano Crypto Challenges. From a quick google search, it seems like lots of people have tried and recommended it. I got intrigued and started coding right away. To keep the blog rolling, I will share my experience with these coding challenges.
-
Sudokids
Sudokids as the name so obviously states is Sudoku for kids. Motivation behind Sudokids is to teach kids set theory with the help of Sudoku.
-
Stream to XBMC FAQ
As a follow up to my previous post about my plugin Stream to XBMC, here are some frequently asked questions about how to setup the plugin. Just two for now, more to follow.
-
Stream to XBMC
This is a chrome-plugin to push videos to an XBMC setup. It can be used it with Raspberry Pi or any other XBMC setup to watch videos from CBS, Youtube and so many other sites on your TV. Big bang theory anyone?
-
Upstream linux kernel on a Raspberry Pi
Recently, I signed up for the Eudyptula Challenge. If you have not heard of it, it is a series of programming exercises designed to train you with Linux Kernel Development process. One of the tasks is to install the latest linux kernel on your machine. You have an option of doing it in a Virtual box setting. Hey, but where is the fun in doing that? I had a Raspberry Pi handy and found a couple of good Wiki pages on how to compile your own kernel for Raspberry Pi (here and here). These two pages have the all the info needed but it is kind of scattered. Fastest way to compile the kernel is to do in in Ubuntu (You could technically do it on a MAC, but it is slightly more involved). I tried on my MAC first but ended up installing Ubuntu through Virtualbox to do the compilation. Here are the steps:
-
Welcome to my blog!
As part of my learn something new everyday, I am migrating all my ramblings to a Jekyll-based blog. It is simple, easy to maintain and super customizable. With this change, I am hoping to write more often.
subscribe via RSS