I like hackerrank because I can see other people's solution which is exactly same problem.

I've just solved 'Attribute Parser' problem on hackerrank. After I solved this problem and I had a look at the discussion to see other people's solution. I can see many good implementation!! I should learn from them. :) I think comparing other people's source code is really good way to think differently. My implementation is down below.


--------
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <map>
#include <cstring>

using namespace std;

/*struct NameEquals
{
    bool operator() (const Tag& rhs) const
    {
        return name == rhs.tagName;
    }
    NameEquals(const string str) : name(str) {}
private:
    const string name;
};*/

class Tag
{
public:
    Tag(int _level, string data)
        : level(_level)
    {
        int index = data.find(' ');

        if (index != string::npos)
        {
            // get the tag's name not attribute name.           
            tagName = data.substr(1, index - 1);
            indexAftertagName = index;
            //cout << tagName << endl;
        }
        else
        {
            noattribute = true;
            tagName = data.substr(1, data.size() - 2);
        }
    }

    void readAttributes(string data)
    {
        // attributeName1 = "blabla" attributeName2 = "blablabla" ... >

        if (noattribute) return;

        int i = indexAftertagName + 1;
        const char* p = data.c_str() + i;

        while (true)
        {
            char ch = *p;
            if (isalpha(ch)) // attributeName
            {
                const char* attrP = p;
                while (*p != ' ') p++; // find out the empty
                const int len = p - attrP;               
                string attributeName = std::string(attrP, len);

                while (*p != '"') p++;

                const char* value = ++p;

                while (*p != '"') p++;

                const int valueLen = p - value;
                string attributeValue = std::string(value, valueLen);

                attributes.insert(make_pair(attributeName, attributeValue));
            }
            else
            {
                p++;
                if (*p == 0) break;
            }
        }
    }

    void addChildTag(Tag* newTag)
    {
        childTags.push_back(newTag);
    }

    void command(char ch, const char* data)
    {
        if (ch == '.')
        {
            // find child tag
            const char* childName = data + 1;
            const char* p = childName;
            while (*p != '.' && *p != '~') p++;
            string childTagName = std::string(childName, p - childName);
           
            bool foundTag = false;
            for (auto element : childTags)
            {
                if (element->tagName == childTagName)
                {
                    foundTag = true;
                    element->command(*p, p);
                    break;
                }
            }                     

            if ( !foundTag )
            {
                cout << "Not Found!" << endl;               
            }
        }
        else if (ch == '~')
        {           
            // find an attribute
            const char* pAttributeName = data + 1;
            const char* p = pAttributeName;
            while (*p) p++;
            string attributeName = std::string(pAttributeName, p - pAttributeName);
           
            auto elementIter = attributes.find(attributeName);

            if (elementIter != attributes.end())
            {
                cout << elementIter->second << endl;
            }
            else
            {
                cout << "Not Found!" << endl;
            }
        }
    }
   
    int level;
    int indexAftertagName;
    bool noattribute;
    string tagName;
    map<string, string> attributes;
    vector<Tag*> childTags;
};



/*
<tag1 value = "HelloWorld">
<tag2 name = "Name1">
</tag2>
</tag1>
*/

int main() {
    int n; // count of tags
    int q; // query
    cin >> n >> q;

    // skip escape char
    char c;
    c = cin.get();

    int level = 0;

    vector<Tag*> tags;
    stack<Tag*> stackTags;

    for (int i = 0; i < n; ++i)
    {
        string data;
        std::getline(cin, data);

        //cout << "read : " << data << endl;

        // checks whether it start with </ or <%alphabet
        if (data.at(0) == '<' && data.at(1) == '/')
        {
            // end of tag
            level--;
            stackTags.pop();
        }
        else
        {
            Tag* newTag = new Tag(level, data);

            newTag->readAttributes(data);
         
            if (stackTags.size() == 0)
            {
                tags.push_back(newTag);
                stackTags.push(newTag);
            }
            else
            {
                // add this tag as a child
                stackTags.top()->addChildTag(newTag);
                stackTags.push(newTag);
            }


            level++;
        }
    }

    for (int i = 0; i < q; ++i)
    {
        string data;
        std::getline(cin, data);
       
        const char* p = data.c_str();
        const char* tagNameP = data.c_str();;
        while (*p != '.' && *p != '~') p++;

        const string tagName = std::string(tagNameP, p - tagNameP);

        //auto iter = std::find_if(tags.begin(), tags.end(), NameEquals(tagName));
        bool tagFound = false;
        for (auto element : tags)
        {
            if (element->tagName == tagName)
            {
                tagFound = true;
                element->command(*p, p);
                break;
            }
        }

        if ( !tagFound)
        {
            cout << "Not Found!" << endl;           
        }
    }


   
    return 0;
}

Dynamic Programming...

Well... be honest I never use DP in my whole career. I know benefit of using Dynamic Programming(DP) to solve specific problems but I had no chance to use it in my career. Maybe it's is because I wasn't familiar with or had no opportunity. Recently I'm reading some books which talks about DP. Probably I'll talk about DP soon. :)

about pointer assignment operation.

I never thought about it because I just knew how it works. Today I'll show you why pointer assignment statement in function is not working as intended.

Just assume there is a simple Node class like below.

class Node

{

public:

int data;

};

this Node class will contain integer data variable as a member and has nothing more. Normally Node class has prev, next pointer member but I'll ignore those in this article.

OK, let's create an head and give it a value 10.

Node* head = new Node();

head->data = 10;

now head pointer will point to some address which is sizeof(Node)

to see the address of head. we can do this.

cout << head << endl;   <--- 1

cout << &head << endl; <--- 2

line 1 will print the address of sizeof(Node) which contains Node's value(integer 10)

If you are using Visual Studio then you can use memory viewer and see the content of the memory like below.

As you can see 0x00526ED0 has integer value of 10. Second address which is address of head pointer. 0x002CF718.

Just think about what is there.

D06E5200 is an reverse order of address 0x00526ED0. This is because intel CPU uses little endian.

Anyway 0x002CF718 which is &head, contains the address of sizeof(Node) (actual value)

now if we pass head pointer to other function and assign new Node. see what happen.

void foo(Node* p)

{

cout << p << endl;

cout << &p << endl;

Node* item = new Node();

item->data = 1024;

p = item;

}

As you can see third address is same as sizeof(Node)'s address. but forth address is different. that's address of p pointer!

when we call foo function and pass head pointer as a param like below.

foo(head);

p is a copy of head pointer which is different variable. their target address which is 0x00526ED0 are same but address of itself are different. so somebody wants to change head's target address like this.

p = item;

it is not working properly. if you see memory window then you will see what's changed.

after p = item statement is executed then address will be changed.

ok p's target address is changed but the problem is that address of p and address of head are different! so basically head's target address is not changed.

if we exit foo function then effect(changing address) will be gone. because p = item is actually changed value of p pointer's address.

This is really trivial thing for C/C++ programmer but cumbersome.

if we want to change head pointer's target address then we should pass pointer of pointer of head variable which is Node**

void foo(Node** p)

{

Node* item = new Node();

item->data = 1024;

*p = item;

}

and use it like this.

foo(&head);

or there are different way to change address of head which is returning Node* in the function foo.

Node* foo(Node* p)

{

Node* item = new Node();

item->data = 1024;

return item;

}

head = foo(head);

Simple LRUCache class implementation.

This is not the best way to implement LRU Cache class. I just implement it for hackerrank problem. Concept of LRU Cache is not difficult but implement doubly linked list was a little bit hard without compiler :^O

------
// inheritance from the Cache class
class LRUCache : public Cache
{
public:
    LRUCache(int _capacity)
        : capacity(_capacity)
        , count(0)
    {
        head = nullptr;
        tail = nullptr;
    }

    void set(int key, int value) override
    {
        auto iter = mp.find(key);
        bool keyExist = false;
        if (iter != mp.end())
        {
            keyExist = true;
        }

        // if key is exist then update LRU
        if (keyExist)
        {
            // for instance there are 3 2 1 5 6
            // and then found 1
            // data will be 1 3 2 5 6
            // doesn't change any data size, just update head, tail pointer and map.

            if (head == iter->second)
            {
                // update value.
                iter->second->value = value;
            }
            else if (tail == iter->second)
            {
                Node* beforeTail = tail->prev;
                Node* afterHead = head->next;

                Node* backupHead = head;
                head = tail;
                tail = backupHead;

                beforeTail->next = tail;
                tail->prev = beforeTail;
                tail->next = nullptr;

                afterHead->prev = head;
                head->next = afterHead;
                head->prev = nullptr;

                // update map pointer and value.
                iter->second = head;
                iter->second->value = value;
            }
            else
            {
                // value is in between head and tail.
                Node* backupPrev = iter->second->prev;
                Node* backupNext = iter->second->next;
               
                backupPrev->next = backupNext;
                backupNext->prev = backupPrev;

                head->prev = iter->second;
                iter->second->next = head;

                head = iter->second;
                               
                iter->second = head;
                iter->second->value = value;
            }
        }
        else
        {
            // if key is not in the map then insert it and based on the capacity
            // remove oldest one.
            if (count >= capacity)
            {
                // insert new one into head
                Node* node = new Node(key, value);
                node->next = head;
                head->prev = node;

                head = node;
                mp.insert(make_pair(key, head));

                // remove old one
                // first remove old one in the map and then update tail pointer.           
                Node* tailPrev = tail->prev;
                tail->prev->next = nullptr;               
                mp.erase(tail->key);       
                delete tail;
                tail = tailPrev;
            }
            else
            {
                // add new one and update count
                if (head == nullptr)
                {
                    head = new Node(key, value);
                    tail = head;
                    mp.insert(make_pair(key, head));
                }
                else
                {
                    // update head
                    Node* node = new Node(key, value);
                    node->next = head;
                    head->prev = node;
                    head = node;

                    mp.insert(make_pair(key, head));
                }
                count++;
            }
        }
    }

    int get(int key) override
    {
        // if the key is in the cache then print the value
        // otherwise print -1 (if the key is not in the cache)
        auto iter = mp.find(key);
        if (iter != mp.end())
        {
            return iter->second->value;
        }
        return -1;
    }
       
private:
    int capacity;
    int count;
};

Keep author or translator is really hard.

I like share things what I've figured out to other programmers. I wrote many programming books, translated game programming books in South Korea. but well... be honest I got few things and lost many things. I started to write/translate books because it helps me develop myself and wanted to be helped to korean gaming industry. But recently I realized that I should change a method.

It took 20 years! I'll show you what is a new method later :)

Long time ago, I had a portfolio website

Long time ago, I had a portfolio website but since I worked on gaming industry professionally I stopped because I had no time to maintain it. It's been 20 years... and I suddenly feels lost everything. I'm not sure how long Blogger.com service is maintained but I decided to use it more frequently from now on and will share more things that I've figured out.

Fair enough...

I'll use English from now on. Because I need to improve myself!!