Leetcoding in C++11: Vector Initialization

How to initialize an array[m][n] with all elements in -1

C++98:

vector<vector<int>> array(m, vector<int>(n, -1)); // vector (size_type n, const value_type& val)

C++11:

vector<vector<int>> array(m, vector<int>(n, -1)); // vector (size_type n, const value_type val)

How to initialize an array[m] with another array {0, 1, table[1], -1*5}

C++98

int il[5] = {0, 1, table[1], -1*5}
vector<int> array(il, il+4); // vector (InputIterator begin, InputIterator end)

C++11

vector<int> array{0, 1, table[1], -1*5}; // vector (initializer_list)

References:

vector

http://www.cplusplus.com/reference/vector/vector/vector/

Leetcoding in C++11: Min/Max

How to get the minimum value of a set of number?

C++98:

int nums[] = { 1, a, tabl[0], 0 };
cout << *max_element(num, sizeof(nums)/sizeof(int));

C++11:

//1.
int nums[] = { 1, a, table[0], 0 };
cout << *max_element(begin(nums), end(num)); // T* end(T (&a)[N])
//2.
cout << max({1, a, table[0], 0}); // T max(initlizer_list<T> il)

References:

std::begin/end

http://www.cplusplus.com/reference/iterator/end/?kw=end

std::max

http://www.cplusplus.com/reference/algorithm/max/?kw=max

Leetcoding in C++11, An Act of God

Remember the time I become obsessed in C++. It was 2007. I knew nothing and was hacking a OJ problem. I ended up writing probably 100 lines of C code. I felt painful and messy so I searched for better solutions. A snippet of C++ solution came out with no more than 10 lines of code including Main(). And I still remembered how shock it was when I saw “table[“abc”] = 1″, where an array taking a string as index. I was like what the heck!

Since then, I’ve started coding in C++ for everything. Taking full advantages of STL has become my hobbe. I got to know map, pair, lower_bound, swap and sort, all these good stuff. Back then, C was the main trend for hacking OJ and Java wasn’t even an option yet.

In 2013, GCC 4.8 has come out recently, as the first compiler that fully supports C++11. At the mean while, friends and I have started hacking OJ again. Nevertheless, LeetCode OJ enables C++11! I think this is an act of god so that I could continues my journay in C++11.

Chapter 1 – Arrays & Strings – Solution 1.3

Question:

1.3 Write a method to decide if two strings are permutation. i.e. “hello” is a permuataion of “oellh”.

If one string is a permutation of the other, they should has the same length and every character appear the same times in these two strings.

So the solution is to check the length and appear time of each character of these two strings.

We can use the same idea in question in 1.1 to solve this question. For example, use an array to store the appear time of all the characters in ASCII table.

Here is my solution, the time complexity was O(n) and space complexity is O(1).

bool
permutation(string a, string b)
{
  // if the length is different, can not be permutation
  if(a.size() != b.size()) return false;

  // use idea of Bucket-sort to count every ASCII character
  int bucket[256] = {};

  // count the apprear time of every character in a
  for(size_t i=0; i<a.size(); i++)
    bucket[a[i]]++;

  // the appear time of character in b shold be the same with a
  for(size_t i=0; i<b.size(); i++)
    if(bucket[b[i]]-- == 0) return false;

  return true;
}

Chapter 1 – Arrays & Strings – Solution 1.2

1.2 Write code to reverse a C-Style String (char* str). (C-String means that “abcd” is represented as five characters, including the null terminator.)

We can use two pointer, one is pointed to the first character, the other is pointed to the last character before the null pointer. Then we can swap the two character, and move the two pointer one step to each other and repeat.

Here is my solution, the time complexity  of this algorithm is O(n), and the space complexity is O(1).

void
reverse(char* str)
{
  size_t i = 0, j = 0;

  while(str[i]!=0) ++i; // go to the end of string "\0"
  --i; // move to the charcter before "\0"

  while(i>j) // swap the head and end characters one by one
  { // xor swap
    str[i] ^= str[j]; // a = a xor b
    str[j] ^= str[i]; // b = b xor (a xor b) = a
    str[i--] ^= str[j++]; // a = (a xor b) xor a = b
  }

  return;
}

Chapter 1 – Arrays & Strings – Solution 1.1

Cracking the code interviews – Solution

Chapter 1 Arrays & Strings

1.1 Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structure?

If the characters comes from the ASCII table, there can only be 256 types of them. We can use a boolean array of size 256 to mark each type of characters. This is the same idea of Bucket-sort algorithm.
About Bucket-Sort: http://en.wikipedia.org/wiki/Bucket_sort

When a new character is already marked as true (already appeared), then we will know that this string contains duplicate characters. The time complexity of isUnique() is O(n) and space complexity is O(1).

Here is my solution in c++:

bool
isUnique(string str)
{
  // if length bigger than 256, it must have duplicate character
  if(str.size() >= 256) return false;

  // use idea of Bucket-sort to find the duplicate character
  bool bucket[256] = {}; // remember every ASCII character

  for(size_t i=0; i<str.size(); ++i)
  {
    // mark the appeared character to true
    // if already set true, report the duplicated character
    if(bucket[str[i]])
      return false;

    bucket[str[i]] = true;
  }

  return true;
}

Another solution is to use a 256-bit-map to mark the characters in ASCII table.
The time / space complexity of isUniqueV2() is also O(n) / O(1).

bool
isUniqueV2(string str)
{
  // if length bigger than 256, it must have duplicate character
  if(str.size() >= 256) return false;

  // use idea of Bucket-sort to find the duplicate character
  uint64_t bucket[4] = {};

  for(size_t i=0; i<str.size(); ++i)
  {
    int index = str[i] / 64; // which bucket should be check
    int bit = str[i] % 64; // which bit in the bucket should be check

    // mark the appeared character to true
    // if already set true, report the duplicated character
    if( (bucket[index] & (1 << bit)) != 0)
      return false;

    bucket[index] |= (1 << bit);
  }

  return true;
}

NS-3 (Network Simulator): Some Compile or Syntax Errors

I will post some of the errors I meet in developing NS-3 programs. Some of them are C++ compiler errors, some are not.

Just for records so that I can quickly check for the similar issues.

 

 

1. If you use any static function in NS-3, i.e. static int val = func(xxx); or include some c codes link md5, you may meet this error on a 64-bit system:

/usr/bin/ld: /tmp/ccQ1dkqh.o: relocation R_X86_64_32 against `a local symbol' can not be used when making a shared object; recompile with -fPIC

Solution: build code with –enable-static option:

./waf -d optimized configure --enable-static --enable-examples --enable-tests; ./waf build

NS-3 (Network Simulator): How to find a specific header in packet in NS-3

We can remove the header from a packet in NS-3 and get it out as following:

// To get a header from Ptr<Packet> p
// first, copy the packet
Ptr<Packet> q = p->Copy();

// use indicator to search the packet
PacketMetadata::ItemIterator metadataIterator = copy->BeginItem();
PacketMetadata::Item item;
while (metadataIterator.HasNext())
{
    item = metadataIterator.Next();
    NS_LOG_FUNCTION("item name: " << item.tid.GetName());

    // for example, if we want to have an ip header
    if(item.tid.GetName() == "ns3::Ipv4Header")
    {
        Callback constructor = item.tid.GetConstructor();
        NS_ASSERT(!constructor.IsNull());

        // Ptr<> and DynamicCast<> won't work here as all headers are from ObjectBase, not Object
        ObjectBase *instance = constructor();
        NS_ASSERT(instance != 0);

        Ipv4Header *ipv4Header = dynamic_cast (instance);
        NS_ASSERT(ipv4Header != 0);

        ipv4Header->Deserialize(item.current);
        // you can use the ip header then ...

        // finished, clear the ip header
        delete ipv4Header;
    }
}

Codes are origined from here:

http://matinrad.com/index.php/2010/08/how-to-find-a-packet-header-in-ns-3/

http://adrian.idv.hk/doku.php/research/ns3/headerinmiddle

C++: Observer pattern in C++

Goals:

1. no inheritance needed for observers and subjects.
2. provide a uniform interface with sufficient flexibility on parameter types.
3. no RTTI needed for casting parameters.

repository: https://github.com/toliuweijing/ObserverPatternInCPP

#include
#include "wl/Subject.hpp"
using namespace wl;
using namespace std;

struct FireEvent {
    string location;
    int level;
};

class FireDepartment {
public:
    void response(FireEvent fire_event) {
        cout << "A level " << fire_event.level <<
            " fire at " << fire_event.location << endl;
        cout << "On my way" << endl;
    }
};

class SecuritySystem {
public:
    Subject fire_alarm;
};

int main(int argc, const char *argv[]) {
    SecuritySystem sys;
    FireDepartment dep;

    sys.fire_alarm += wl::bind(&dep, &FireDepartment::response);
    sys.fire_alarm(FireEvent{"NYC", 100000});
    return 0;
}