TIW: STL #1

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.

 

Vector

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;
    stack.pop_back();
}
// 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.

 

Set

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:

s.insert(k);

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:

s.erase(k);
s.erase(s.begin());
s.erase(*s.begin());

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.

 

Map

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;

m[0]++;

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:

m.at(0)++;

 

Pair

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++) {
        f[s[i]-'a']++;
        f[t[i]-'a']--;
    }
    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++) {
        m[s[i]]++;
        m[t[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

 

Gameplay

First you register a name and put in a password, but make sure you have at least one number and one uppercase letter (don’t ask me why).

Then you either create a room or join a room. So yeah those who don’t have any friend can go home now.

Each person picks a color,

Basically you control a tank and shoot other guys, and they respawn after a while. Pretty typical stuff, but there are two different features:

  1. Bullets rebounce: bullets don’t die until the third time they bump into something;
  2. Tanks can move in all directions, instead of just wasd.

These features make the game quite different.

 

Development

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.