I will dedicate this post to two functions in particular: upper_bound and lower_bound. They make the impossible become possible. Basic facts about them:

  1. they act on sorted data structures (sorted vector, set, map, etc);
  2. they perform binary search in O(log(n)) time;
  3. they return iterators so you can move forward and backward.

I will then go over 2 problems to demonstrate the power of these functions.

Let’s say you have 5 integers in a data structure, {1, 3, 5, 7, 9}, either in a vector or a set. Say you would like to find the smallest number that is larger than k, then you simply do:

vector<int> v{1, 3, 5, 7, 9};
set<int> s(v.begin(), v.end());
int k = 6;
// Binary search in a vector
auto it = upper_bound(v.begin(), v.end(), k);
if (it != v.end())
    cout << *it << endl;
// Binary search in a set
it = s.upper_bound(k);
if (it != s.end())
    cout << *it << endl;

Lower bound is not the opposite of upper bound, surprisingly. It finds the smallest number that is larger than or equal to k, allowing the equal case (which is excluded in upper_bound).


The functions are simple, but let’s dive into practice. There are quite a few problems on Leetcode for which I used upper_bound, but many are quite hard (see this one: Perfect Rectangle). This series is supposed to be easy and about syntax rather than algorithm, so I decided to make up one problem.

Problem statement:

Given a vector of integers v and an integer k, find the smallest sum from all pairs of elements that is larger than k. For example for v = {6, 0, 5, 1, 9} and k = 12, possible sums would be {1, 5, 6, 7, 9, 10, 11, 14, 15}, and the smallest that is larger than 12 would be 14.

One way to do it is to sort it and use 2 pointers, which is O(nlog(n)). I will talk about that approach in a later post. Here, a way is to use set. The algorithm essentially picks an element x, then looks at all the numbers in front of it, and pick the smallest one y that is larger than k-x, since then we know x+y > k.

int closestTwoSum(vector<int>& v, int k) {
    set<int> s;
    int ans = INT_MAX;
    for (auto x : v) {
        auto y = s.upper_bound(k-x);
        if (y != s.end())
            ans = min(ans, x+*y);
    return ans;

To get the largest sum that is smaller than k, there are two things you can do: negate all numbers and apply the same code (essentially reversing order of integers), or move the iterator given by upper_bound. Just to demonstrate, the second approach looks like this:

int closestTwoSum(vector<int> v, int k) {
    set<int> s;
    int ans = INT_MIN;
    for (auto x : v) {
        auto y = s.lower_bound(k-x); // *y larger than or equal to k-x
        if (y != s.begin()) { // if *y is not the smallest number we have
            y--;  // go back to the smaller one
            ans = max(ans, x+*y);
    return ans;

That’s a teaser problem. Now let’s get to the real business, longest increasing subsequence. The problem statement is:

Given an array of integers, find the longest increasing subsequence and return its length. For example in {1, 4, 5, 7, 2, 9, 3}, the longest increasing subsequence is {1, 4, 5, 7, 9}, so we return 5.

It’s also on Leetcode: Longest Increasing Subsequence

This is a well known dynamic programming problem, depending on how you design your dp algorithm, you can get either O(n^2) or O(nlog(n)) solutions. The O(nlog(n)) algorithm is well known, so I will just briefly describe it.

Our basic idea is to keep appending elements to increasing subsequences. Key observation: if using the first x numbers, you can create two increasing subsequences of length 5: one ending with number 7 and another ending with number 9, then we can discard the latter. This is because if we could append a later element k to 9, we can definitely append k to 5 to make a sequence of length 6. Therefore in our dp array, for each dp[i], we store the smallest element that an increasing subsequence of length i can end with. With a new element k, we search for the largest dp[i] that is smaller than k, then assign k to dp[i+1] in case k is smaller than dp[i+1]. Then the length of the longest increasing subsequence would be the largest i such that dp[i] exists.

Since this post is not meant to teach you introductions to algorithms, you should google it if you don’t understand. I’m just trying to how to implement it without making a mess. In the algorithm, there’s a part of binary search, so that could be replaced by a vector upper_bound. It turns out that instead of appending to the subsequences, it’s easier to work in reverse and prepend to them. If we are searching for a larger element, that means we are finding an increasing subsequence that starts with a number larger than the current one, and we are trying to prepend to it. Let’s look at the code and analyze it:

int lengthOfLIS(vector<int>& nums) {
    vector<int> s;
    for (int i = nums.size()-1; i >= 0; i--) {
        auto it = upper_bound(s.rbegin(), s.rend(), nums[i]);
        if (it == s.rbegin())
        else if (*(--it) < nums[i])
            *it = nums[i];
    return s.size();

Here, s[i] denotes the largest number that a subsequence with length i can start with. As the length increases, intuitively the starting number has to be smaller, so this vector is strictly decreasing. To use upper_bound to binary search for the slightly larger element to update, we need to pass in the reverse iterators rbegin() and rend(). If the returned iterator is the last element in the vector, that means we have found a new longest increasing subsequence. Otherwise, it means we have found a better increasing subsequence of the same length with a larger (better) starting value.

Final remark on longest increasing subsequence: to get the longest nondecreasing subsequence, we can preprocess the array to use almost the exact same code above. Here’s how:

int lengthOfLNDS(vector<int> nums) {
    vector<pair<int, int> > v;
    for (int i = 0; i < nums.size(); i++)
        v.push_back(make_pair(nums[i], i));
    vector<pair<int, int> > s;
    for (int i = v.size()-1; i >= 0; i--) {
        auto it = upper_bound(s.rbegin(), s.rend(), v[i]);
        if (it == s.rbegin())
        else if (*(--it) < v[i])
            *it = v[i];
    return s.size();

Pretty simple, I just used a pair<int, int> to replace int. The first item is the original data, the second item is the array index, used to tie break equal values.


This should be a relatively easy post. Things covered: auto, iterator, sort, next permutation, reverse and swap. If you know all of these you can skip.



Auto is a keyword that saves you some thinking time. It is nothing but a lazy way to write code, no concept or algorithm whatsoever. Like how Python induces the data type, you can use auto to force your compiler to do your job.

auto x = 5;
auto p = make_pair(2, 4);
auto s = vector<int>(4);

When would you ever want to be lazy, as a hardworking programmer, you ask? Well it helps shorten the code sometimes, especially in the case of iterators.



Since implementation is hidden in a black box for STL data structures, we have less control over how to mess with the data directly. That’s why we have iterators to let us peep into the black box. Iterators for each data structure are different from others, but they mostly do one thing: iterating through data points you put in the data structure. You always initialize an iterator from an instance of a data structure, for example the begin() function of sets and maps, which we have seen in the previous post.

Iterators act as pointers to elements, so you need to dereference to get the value. For sets and maps, they could be quite useful:

vector<int> v{1, 5, 8, 2, 9};
set<int> s;
map<int, int> m;
for (int i = 0; i < v.size(); i++) {
    m[v[i]] = i;
for (auto it = s.begin(); it != s.end(); it++)
    cout << *s << endl;
for (auto it = m.begin(); it != m.end(); it++)
    cout << it->first << " " << it->second << endl;

Had I not used auto, I would have written set<int>::iterator and map<int, int>::iterator. Then your code will look uglier, but that’s a personal preference.

To explain a little bit, .begin() gives an iterator to the first item in the data structure. In the case of set and map, begin() points to the smallest element.

Then, .end() returns a special iterator marking the end of the data structure. It is not the last element; it is the iterator after the last element. Trying to dereference it will crash your program.

To print things in reverse order, just use rbegin() and rend() in place of begin() and end(), no pain at all. The ++ operator gives you the next iterator, and — gives you the previous one. We will see subtleties later on with these two operators.

Another shorthand for the loop in order above:

for (auto it : m)
    cout << it.first << " " << it.second << endl;

note that the “it” here is not actually the iterator, but a dereferenced key-value pair. Like literally a pair<int, int>.



To sort a vector, just pass in the begin() and end() iterators. Obviously it modifies the vector you pass into it.

vector<int> v{1, 4, 5, 2, 6, 3}
sort(v.begin(), v.end()); // {1, 2, 3, 4, 5, 6}
sort(v.rbegin(), v.rend()); // {6, 5, 4, 3, 2, 1}

If you are a hardcore c fan, you can even pass in c array pointers, since iterators are like pointers anyways:

int v[] = {1, 4, 5, 2, 6, 3};
sort(v, v+6);

Strings are like vector<char>, so you can sort a string too. For example, for the anagram problem last time, a really short piece of code could be:

sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;

This is going to be O(nlog(n)), n being the sum of length of the two strings. So strictly speaking this is not the best solution ever, but hey it’s only three lines.


Next permutation

This is a really handy way to enumerate all n! ways to permute a vector of size n. Let’s say for some reason you need to generate all 720 permutations of {1, 2, 3, 4, 5}, this is all you need to do:

vector<int> v{1, 2, 3, 4 ,5};
do {
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    cout << endl;
} while (next_permutation(v.begin(), v.end()));

It is good to know the algorithm behind this function, basically you just go from the back to the front, until the next number is smaller, then you swap that next number with a slightly larger number from this number to the back, and keep everything in ascending order after this slightly larger guy.

One cool aspect about this function is that you can hack it so it gives you combinations instead of permutations. Let’s say you have 5 guys, and you want to choose 2 of them. Then you just feed the function with a special vector:

vector<int> v{0, 0, 0, 1, 1};
do {
    for (int i = 0; i < v.size(); i++)
        if (v[i] == 1)
            cout << i << " is chosen" << endl;
    cout << endl;
} while (next_permutation(v.begin(), v.end()));

This function is useful in interviews, but rarely applicable in real life. But when you actually need to enumerate, things will be so much easier with a bug-free built-in function.



To reverse a vector, there’s a function aptly called reverse. Like sort, that will modify the original vector. If you don’t want to modify it, you can make a new vector via a special constructor.

vector<int> v{1, 2, 3, 4 ,5};
string s = "abcde";
reverse(v.begin(), v.end()); // {5, 4, 3, 2, 1}
reverse(s.begin(), s.end()); // "edcba"
vector<int> u(v.rbegin(), v.rend()); // {1, 2, 3, 4, 5}
string t(s.rbegin(), s.rend()); // "abcde"

Please don’t write a for loop to do what you can do with built-in functions. You will be surprised how many fewer bugs you need to clean with shorter code and fewer loops.

Another trick that is occasionally useful: let’s say you want to reverse the 3rd to 6th character (start counting from 0th) of string s. Then you can:

string s = "12345678";
reverse(s.begin()+3, s.begin()+7);
cout << s << endl; // 12376548

Note that the second parameter is always one after the last element you want to swap.



There are two swap functions. The first is swap(x, y) which swaps two variables of the same type, the other is a way to rename your black boxes.

To swap two variables:

int x = 3, y = 6;
swap(x, y);
string s = "12345";
swap(s[2], s[4]);

Another is to swap the content of STL data structures.


But you can just write swap(s0, s1) instead, because since C++11 there is no performance difference between the two.



Sometimes if you want to deal with an object, there are some unnecessary deep copies that make your code less efficient. For example in the following code, if we ignore the function move(), there will be two copies of “test”, one stored in s and one stored in the vector. The point is, we don’t care what s becomes afterwards, so we can destroy it after pushing it to the vector. Move does exactly this: destroy the original, so we only have 1 instance of the object, and we can eliminate the time complexity due to deep copy.

// Destroying a string after pushing to the vector
vector<string> v;
string s = "test";
// Setting v1 to v2 in O(1) time
v1 = move(v2);


Ok, that should be enough for us to grab a problem. Here’s a medium level one:

Binary Tree Right Side View

TLDR: given a binary tree, output the rightmost element in each layer in a vector. The algorithm is to traverse the tree layer by layer, each time pushing in the value of the right most node:

vector<int> rightSideView(TreeNode* root) {
    vector<int> ans;
    if (!root)
        return ans;
    vector<TreeNode*> layer{root};
    while (!layer.empty()) {
        vector<TreeNode*> next;
        for (auto it : layer)
            for (TreeNode* c : {it->left, it->right})
                if (c)
        layer = move(next);
    return ans;

Notice the use of for (auto x : y) in this context: x would be the actual element, so I did not dereference it before I used it as a TreeNode*. Also note the move at the end of the loop.

Last small remark: in C++, NULL is the only pointer value that means false, and 0 is the only integer value that means false. So you can write if (ptr) or if (!ptr) to test for null, and if (num) or if (!num) to test for 0 value.

Next, we’ll talk about upper_bound and lower_bound.


This post in a nutshell:

vector<vector<pair<int, map<int, set<int> > > > >
    nutshell(n, vector<pair<int, map<int, set<int> > > >(m));

If you know what that means (not that it MEANS anything), then you can skip this post.

STL is the most basic and useful topic. With good practices, they can make your code much more concise and easier to debug.



Basic facts:

  1. push_back() is O(1), pop_back() is O(1);
  2. you can make 2D arrays with different lengths for each row;
  3. initialize a multi-dimensional array in 1 line;
  4. let vector take care of all the dynamic allocation and deallocation of memory you ever need;
  5. avoid stack overflow at times.

Some initialization methods:

// Initialization of 1D vector with no elements:
vector<int> x;

// Initialization of 1D vector with 10 elements, default value 0:
vector<int> x(10);

// Initialization of 1D vector with 10 elements, default value -1:
vector<int> x(10, -1);

// Initialization of 2D vector of 10 rows x 20 columns, default value 0:
vector<vector<int> > x(10, vector<int>(20));

// Initialization of 2D vector of 10 rows x 20 columns, default value -1:
vector<vector<int> > x(10, vector<int>(20, -1));

// Initialization of a 1D vector of user defined values:
vector<int> x{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

Vectors can be used as stacks, with push_back(), back(), and pop_back().

vector<int> stack{1, 2, 3, 4, 5};
while (!stack.empty()) {
    cout << stack.back() << endl;
// output: 5 4 3 2 1

I will cover more usages of vectors, for example for BFS and DFS, when I get through more problems.



Sets are very useful and powerful. Basic facts:

  1. elements are unique;
  2. insert, take smallest, take largest, find, erase any element are O(log(n)), so you can use it as a heap/priority queue;
  3. elements are in sorted order;
  4. binary search is built-in, which I will go through in a coming post;
  5. inside the black box, sets are balanced binary search trees.

Making a set:

// Initializing an empty set
set<int> s;

// Initializing a set with elements from a vector
set<int> s(v.begin(), v.end());

Finding if an element is in a set:

if (s.find(k) == s.end()) { // alternatively, if (s.count(k) == 0) {
    cout << "not in the set" << endl;
} else {
    cout << "found in the set" << endl;

Inserting to a set:


Finding the smallest and largest in a set:

if (!s.empty()) {

    cout << "smallest element: " << *s.begin() << endl;

    cout << "largest element: " << *s.rbegin() << endl;


Erasing an element in the set:


Notice that there are two ways to erase an element: you can either pass in the iterator of the element, or pass in the actual element value. I will probably leave iterators to another post so this one is not super long.

When you do not need the elements sorted, you might want to consider using std::unordered_set instead of set, which is basically a hash table version of set. Insert, find, erase will become O(1), but space required is larger, time constant is larger which means it might hurt performance for small set sizes, and you will not be able to get the smallest element in O(log(n)).

Sometimes you do not want the elements to be unique, say you want to keep the height of each student in a class in a set. Then you would want std::multiset, which is basically set without the unique element requirement.



Maps are like dictionaries, it maps one simple thing (a word) to another thing (its definition). Basic facts:

  1. keys are unique;
  2. insert, take smallest, take largest, find, erase any key are O(log(n));
  3. keys are in sorted order;
  4. binary search is built-in;
  5. inside the black box, maps are balanced binary search trees, each node containing a second data (the value) that is not used for comparison.

Make a map:

map<int, int> m;

Put something in the map:

m[42] = 3;

Tip: you can access a non-existent key-value pair this way:

map<int, int> m;


This way of access to a non-existent key-value pair will throw an exception, sometimes good for debugging, and otherwise equivalent to the above:




I think pair is the most underrated STL data structure ever. It is not taught in classes usually (not in mine anyways) because it does not contain any special algorithm, but it is a great shorthand for simple data structures. Basic facts:

  1. a pair sticks 2 things together;
  2. it has a default comparator which compares the first guy, and if they tie, compares the second guy.

To make a pair:

pair<int, int> p0;
pair<int, int> p1 = make_pair(1, 2);
if (p0 < p1)
    cout << "0 < 1 confirmed" << endl;


Now that we have all the pieces, we can start sticking things one inside another. Let’s grab a Leetcode problem:

Valid Anagram
TLDR: given two strings with lowercase letters, determine if they are anagrams of each other.

Here’s one way to do it using vector, with f[i] counting the frequency of the (i+1)th alphabet:

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;
    vector<int> f(26);
    for (int i = 0; i < s.length(); i++) {
    for (int i = 0; i < 26; i++)
        if (f[i] != 0) return false;
    return true;

Here’s another way to do it using map, same idea:

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;
    unordered_map<char, int> m;
    for (int i = 0; i < s.length(); i++) {
    for (unordered_map<char, int>::iterator i = m.begin(); i != m.end(); i++)
        if (i->second != 0) return false;
    return true;

Yeah… That’s quite trivial. But we’ll get to the fun stuff after we have all the basics.

One final remark for STL data structures: put them in the scope where they belong. For example, if you need to create a vector 10 times, don’t make one vector as a global variable but rather create the vector within the for loop, so you won’t accidentally use garbage values left from the last iteration.

Index: Tech Interview Walkthrough

In order to prove the worth of this site, I am planning to write a series of posts about writing clean code in CS tech interviews. The entire series will focus on only the basics. Although these topics are supposedly basic stuff, there’s a lot that I didn’t know a year ago, before I got into semi-serious programming training. I will pick interesting problems from Leetcode, group them by similarity, and discuss the tricks to make debugging less painful.


Target audience:

  • If you are looking for a job in CS;
  • and you are not extremely good at it;
  • and you often write long and clumsy code very slowly during interviews;
  • and you plan on using C++, then my posts might be useful.

If you compete a lot in programming contests, then you probably have seen most of what I will talk about.


What this series is NOT:

  • Introduction to algorithms: there are many algorithms that I will not cover, simply because there is not a single way to write elegant code for that particular algorithm (for example greedy), or will not be useful in interviews (say, max flow).
  • How to get a job offer in a month: after learning the tricks, it takes a lot of practice to know how to apply them.
  • Professional C++: you might learn a bit about the language, but I’m not an expert in C++, so you won’t become one by reading my posts.
  • ACM programming contests guide: I am simply unqualified to be your coach.


Things to know:

  • my code runs on C++11, if you don’t know how to compile, Google it;
  • I ignore all the includes, using namespace std and stuff, fix it yourself.


List of topics:

1. STL

2. Things about arrays

3. Edgy things

4. Linked lists

5. Special topics

Happy coding!

CS201 Project: Tank War

Last semester for CS201 at USC, my group wrote up a game project for class. Not exactly the most innovative or beautifully designed game ever, but the gameplay is pretty fun when it doesn’t lag.

Here’s a link to the executable JAR file: Download

Note that this only runs on Java 8. They took out some libraries in later versions of Java that broke the client-server communication.


First you register a name and put in a password, but make sure you have at least one number and one uppercase letter. Only players with accounts can create rooms.

Then you either create a room or join a room. Each player picks a color, checks the ready button, and the room creator starts the game.

Basically you control a tank (arrow keys) and shoot other guys (space). Pretty typical stuff, but bullets bounce off surfaces for a few times, which makes the game much more chaotic.


My team has five people, including the following:

Yifan Meng

Anne Yu

Erdong Hu

Hexi Xiao

…and Me

We spent at least 2 weeks on this project, with at least one all-nighter. Ended up with a monster with like 6k lines of Java code.

The game server runs on the EC2 machine that powers this website, and is the lowest tier so please tolerate the lag. I’ll probably keep the server running until my credit card runs out of money.