File System 


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
#pragma once
#include<iostream>
#include<unordered_map>
#include<string>
#include<sstream>

using namespace std;

namespace airbnb
{
    struct TrieNode
    {
        TrieNode()
    {
        this->value = -1;
    }

    unordered_map<string, TrieNode*> children;
    int value;
    };

    class FileSystem
    {
    private:
        TrieNode *root;

        void deleteTrie(TrieNode *p) {
            for (auto& pchild : p->children) {
                deleteTrie(pchild.second);
            }
            delete p;
        }

    public:
        FileSystem()
        {
            root = new TrieNode();
        }

        ~FileSystem()
        {
            deleteTrie(root);
        }

        void Create(string path, int value)
        {
            TrieNode *p = root;

            string dir = "";
            string logStr = "";
            stringstream sspath(path);
            while (getline(sspath, dir, '/')) {
                if (dir == "") {
                    continue;
                }

                logStr.append("/" + dir);
                if (p->children.find(dir) == p->children.end()) {
                    break;
                }
                p = p->children[dir];
            }

            if (!sspath.eof()) {
                cout << "Create: Error because " << logStr << " does not exist" << endl;
                return;
            }

            p->children[dir] = new TrieNode();
            p->children[dir]->value = value;

            cout << "create path: " << logStr << " successfully" << endl;
        }

        int Get(string path)
        {
            TrieNode* p = root;

            stringstream sspath(path);
            string dir = "";
            while (getline(sspath, dir, '/')) {
                if (dir == "") {
                    continue;
                }

                if (p->children.find(dir) == p->children.end()) {
                    cout << "Get: Error. Path: " << path << " does not exist" << endl;
                    return - 1;
                }
                p = p->children[dir];
            }

            cout << "Get value: " << p->value << endl;
            return p->value;
        }

        void DoTest()
        {
            FileSystem fs;
            fs.Create("/a", 1);
            fs.Get("/a");
            fs.Create("/a/b", 2);
            fs.Create("/c/d", 1);
            fs.Get("/c");
        }
    };
}

Comments

Post a Comment

Popular posts from this blog

Unique Binary Search Trees

/*** Given  n , how many structurally unique  BST's  (binary search trees) that store values 1... n ? For example, Given  n  = 3, there are a total of 5 unique BST's.    1         3     3      2      1     \       /     /      / \      \      3     2     1      1   3      2     /     /       \                 \    2     1         2                 3  ***/ class Solution { public :        int getnumTrees( int st , int ed ) {               if ( st >= ed ) return 1;               int sum = 0;               for ( int i= st ; i<= ed ; i++) {                      sum += getnumTrees( st , i-1) * getnumTrees(i+1, ed );               }               return sum;        }        int numTrees( int n ) {               // Start typing your C/C++ solution below               // DO NOT write int main() function               return getnumTrees(1, n );        } };
Read more

Coin in Line

/*** There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Would you rather go first or second? Does it matter? Assume that you go first, describe an algorithm to compute the maximum amount of money you can win. eg. int a[] = { 3, 2, 2, 3, 1, 2 } Note: 1. array is unsorted 2. the guaranteed win strategy compute the sum of odd and the sum of even (the index of coin) if even > odd, every round, only picked the even coin otherwise, only picked the odd coin 3. the maximum amount of money you can win (different with 2.) Recursive, consider the way to compute subset sum http://leetcode.com/2011/02/coins-in-line.html ***/ #include <iostream> using namespace std; int maxWin( int * a , int index_x , int index_y , int sum ) {        //base case        if ( index_x == i
Read more