In the last week I wasted a lost of time for not turly understand others’ codes. And I wanna make a self-criticism.

At the beginning of the tasks OpFromGraph.c_code(), Fred pointed to me a few commits which he thought might be and majorly implemented make_thunk() method. “This is wired, why he provided codes of other method?”, I thought. With only a glance of the codes and some confusions, I turned to CLinker and gof.Op.

I thought this might be a simple mission, which wasn’t. The biggest problem was my misunderstand of CLinker – I thought it is something like PerformLinker and VM_Likner, called by orig_func() and linking the whole graph. But the truth is CLinker did not serve the fgraph, but the node. In gof.Op.make_thunk(), if op_use_c_code is true, it will call make_c_thunk() and use CLinker to generate a C code and link the storage. And then return a ret(what’s a ret?)

So there’s two equivalence ways to impelemnt c_code(), to make an Op faster. One is the way I took – implementing serious of C code method of Op, so that Op can return C code accords to fgraph. In this way I need to generate C code fitst. And then I need to break apart those code while ensuring they can be compiled after being resembled by CLinker. This require a thorough understand of CLinker. Yes I can only get the basic idea. Therefore I stucked.

The other way is override the make_thunk()(or make_c_thunk)method, which is Fred’s way. This is much easier. Because we do not need to seperate the codes, it is generated in a whole and independently. We don’t link the cthunk with storage until it’s generated(really?), which save a lot of problem and make full use of CLinker’s ability.

Fred already gave me a workable code. I only need to improve it a bit. But my ignorant lead me into another way.Therefoer I decide to post this blog to remind me that everytime before I take a step, I need to full understand what I’m going to do and how I’m going to accomlish it, as well as suggestion from others. Otherwise, the more effort I make, I more resoureces I waste. Also, ask question when confused.

Shame on me this time.

In this two weeks connection_pattern and infer_shape were merged. I was supposted to implemented the GPU optimization feature. As I don’t have a machine with Nvidia GPU, I truned to the c_code method after several days.

Reusing the code of CLinker would be our original idea. But thing wuold not be that simple. CLinker generate code at a function scale which mean it treat node OpFromGraph as a function. Yet we want to generate code at a OP scale. Therefore we need to remove some code in a larger scale to make OpFromGraph.c_code() return a ‘node like’ c_code.

There’re to solution. One is to add a new feature to CLinker so that it can detect OpFromGraph node and do some special behavior. The other one is to avoid high level method like code_gen() in CLinker – only use auxilary method to assemble a ‘node like’ c_code. The later solution seems easier and I am working on it. CLinker is a very complicated class, I try to understand it and work out a workable code in the next two weeks.

Wish myself good luck~~!

This two week, I start working on OpFromGraph. Which is the second part of the proposal.

Currently, if a FunctionGraph have repeated subgraph, theano will optimize these sub-graphs individually, which is not only a waste of computational resources but a waste of time. If we can extract a common structure in FunctionGraph and make it a Op, we can only optimize the sub-graph of this Op once and reuse it every where. This will speed up the optimization process. And OpFromGraph provides such feature.

To make OpFromGraph works well, it should support GPU and can be optimized. Following feature are expected:

• __eq__() and __hash__()
• connection_pattern() and “infer__shape()“`
• Support GPU
• c_code()

I implement two feature in last two week: connection_pattern and infer_shape. I hope I can make OpFromGraph a useful feature at the end of this GSoC :).

Evaluation passed and the next step: OpFromGraph

The PR of function.copy() is ready to merged, only need fred to fix a small bug. And in this Friday I passed the mid-term evaluation. So it’s time to take the next step.

In the original proposal ,the next step is to swap output and updates. After a discussion with Fred, we thought this feature is useless so we skip this and head to the next feature directly – OpFromGraph.

Goal:

make class OpFromGraph work.

Big How?

OpFromGraph should init a gof.op that has no difference with other Ops and can be optimized. Otherwise it has no sense.

For this, we need to make it work on GPU, make sure it works with C code and document it. Make sure infer_shape(), grad() work with it. Ideally, make R_op() work too.

Detailed how.

• Implement __hash__() and __eq__() method so it is a basic
• Implement infer_shape() method so that it’s optimizable
• test if it work with shared variable as input and if not make it work. Add test for that.
• Move it correctly to the GPU. We can do it quickly for the old back-end, move all float32 inputs to the GPU. Otherwise, we need to compile the inner function, see which inputs get moved to the GPU, then create a new OpFromGraph with the corresponding input to the GPU. #2982
• Makergrad() work. This should remove the grad_depth parameter

First Step: infer_shape:

The main idea is to calculatet the shapes of outputs from given input shapes. This is a process similar to executing a function – we cannot know the shape of a variable before knowing the shape of the variables it depends on. So, we can mimic the make_thunk() method to calculate the shape from output to input. I come out with a draft now, and need some help with test case.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

order = self.fn.maker.fgraph.toposort()

# A dict that map variable to its shape(list)
shape_map = {}

# set the input shape of the fgraph
for in_var, shape in izip(in_vars, shapes);
    shape_map.set_default(in_var, shape)

# calculate the output shape from input shape
for node in order:
    assert all([var in shape_map.keys() for var in node.inputs])

    # calculate output shape
    in_shapes = [ shape_map[var] for var in node.inputs]
    out_shapes = node.op.infer_shape(node, in_shapes)

    # store the shape of that variable
    for out_var, shape in izip(node.outputs, out_shapes):
        shape_map.set_default(out_var, list(shape))

# extract output shape
return [ tuple(shape_map[var]) for var in fgraph.outputs]

Almost forget to update a post.

In this two week, I finished the first feature “Allow user to regenerate a function from compiled one”, and this feature “can be merged. But there’s another PR need to rebase.” So, it’s done.

Also, I get a draft of the code that allow user to swap SharedVariable. When I said ‘draft’, I mean that I’ve finish the code as well as the testcase and they work. I’ll make a PR for review at the beginning of next week. Also I have some new idea need to discuss with Fred.

I hope I can finish all 3 feature in the first 6-week: copy, swap_sharedvariable and delete_update. So that I can focus on OpFromGraph in the next half. It seems that someone has started working on it now. I hope he did not ‘rob’ my job. :)

The first feature was done and is being reviewed! This post is my reading notes of theano core this week and how I implements the share_memory feature.

Data sturctures

Function

Function is a callable object whose core is a function ```fn``` generate by linker. Every time a function is call, it will first examinate input data and then evaluate the ```fn``` to get output value.

PARAMETERS:

• input/output_storages: two list of Container instance.
• maker: the maker of this function
• finder/inv_finder: provide mapping between Container and In( seems useless )
• fn: Core, what the real ‘function’ is, a python function that evaluate graph.
• default and indices: List of tuples, partially useful. default[i][2] is input_storage[i] ; indices[i][0] is inputs[i] in FunctionMaker.

METHODS:

• __init__(): Initialize input containers value and set up “[]” operator of container and self
• __call__(): verify input data types and then execute the self.fn. Pickup value in some of the the output storages and set up corresponding input_storage in there’s updates.

FunctionMaker

FunctionMaker is a Factory that create function. However, it's not like a factory very much cause every maker only corrsponds to one function. In FunctionMaker some important info of a theano.function are stored, such as Inputs/Outputs(represented by SymbolicKit), FunctionGraph.

PARAMS:

• indices: ( almost deprecated, ignore )
• inputs: List of In() instances. In()
• output: List of Out() instances
• expanded_inputs: equals to inputs plus sharedvariables
• fgraph: FunctionGraph that represents the function it creates.
• Linker: Linker that link storage and apply method to create a fn. By default, FAST_RUN mode use VM_Linker , FAST_COMPILE uses PerformLinker.
• Optimizer, mode, profile …: some configuration that has less to do with my job

METHOD:

• create(input_storages): Given input_storages(by default, list of In.value), start the linker and link the function using Linker.make_thunk() return a theano.function.

Linker/VM

Linker is a class that allocate storage for allpy_nodes and link them together. Understanding Linker and FunctionGraph definitely helps understands how theano works. The core method of Linker is make_thunk(). 

PARAMS:

• fgraph: FunctionGraph accpeted by Linker.accept().
• allow_gc,recycle…: some configuration bools

METHODS:

• make_thunk/all… : make_thunk() is defined in class Linker. It calls method make_all(). Every subclass of linker will have slightly different implementation of make_all(). Bascially, at first, make_all() will toposort a fgraph, to acquire the order that apply_nodes should be executed. Next, it will call Op.make_thunk(), whick return a function. This function take input_storage of node, apply computation on them, and put result on output storage. Meanwhile, make_all() will allocate storage for all variables . Same variables in different node will have same storages. This is done by a dict sotarge_map that map variable to storage. At last, Linker return a function that executes list of thunks in certain order to acquire function outputs data.

Storage

Storage is quite a tricky thing in theano. Theano use a list with one element to be a storage. The element is true data. But all object only refer to the list. 
The list works like a pointer. When some objects refer to a storage, they refers to the list, not the true data. Therefore, modifying the data of storage will not change this reference. By doing this, theano can access and modify storage data from several places without change the reference relationship.

FunctionGraph

A representation of the computational graph of a function. It stores given the input and output variables of one function, by calling node.input and variable.owner recursively we can get the whole graph 

PARAMS:

• features: Still Don’t understand now, ignore it.
• input/output: List of input/output variabls.
• variables: Set of variables( all variables in the subgraph)
• apply_nodes: Set of apply_nodes in the subgraph defined by inputs and outputs

METHODS

• __import_r__ and __import__(): import variable and apply_node to this fgraph.
• clone_get_equiv : Clone fgraph. Return new fgraph and a dict that map old variables to new variables.
• replace() : Replace all certain variables in fgraph by given new variables.

How theano work?( Simplified version )

Without update:

1.Input Variables will be wraped and become In()s. Each In() contains variable, it’s value( defaults is none ) as well as some other configuration. 2.Generate fgraph by input and output variables, and then optimize it. 3.Linker toposorts fgraph to get an order of apply_nodes.Next, Linker allocates storages and links function based on this order. 4.Done

With update:

Update is given by a dict { ori_var:update_var ... }. Ori_var is limited to be an SharedVariable therefore it will transfer into In() and become the input of this function. update_var will be add into the output of fgraph. Everytime a function called, the function extract the storage of update_var and use it to set the value of corresponding input.

How to implement the share_memory feature?

This is simple after understand how theano works. I implements it following sevaral steps: 1. Copy In() and Out() instances in Maker 2. Copy fgraph and get the dict equiv that map old variables to new variables 3. Copy old storage_map in Function.fn.storage_map 4. Modify copied storage_map accord to equiv, so that in the copied storage_map, new variables are mapped to old storage if memory need to be shared. 5. Reinitialize the maker, linke the function using the copied storage_map 6. Done

Ok, basically this is the report of this week’s work. Now I need to figure out how to implement the following features.

Several days a ago, I reveived a Fedex package. When I opened it … Bomb!

Payoneer pre-paid MasterCard with Google icon on it!

Good looking card. I guass someone will regret for using existing bank account. Also this is my first own credit card. Finally I can make payment without a phone from my dad :)

Google is ready to pay me now. “Are you OK?”( Leijun’s ‘Chinglish’ )

Kinda occupied in the last week. Luckily, I finished those buinesses. And now I am back again. The first feature I will add to theano is a function that allow user to make a copy of function and allow functions run multi-theadedly. There exist two similar features: pickle() and copy() of a function. To figure how I need to work. I need to take 3 steps as preparation:

• Look into the code and see how function is generated Done
• Look into the code and understand Function, FunctionMaker, Linker and FunctionGraph. next
• Have a look at pickle and copy(), use them, figure out how them work and the differneces. Then think about my own idea.

Ok, now I need to go and take the step two now.

It’s been a week and a half since google-melange anounced the accepted student for google summer of code. I was luckcy enough to be accepted by Theano – sub-foundation of Python organization, to help them add new features: Allow user to modify compiled function. As scheduled, from 27th April to 23rd May is the community bounding period. During these days I ought to get familiar with Theano core code and Theano dev community.

Before the application started, I’ve dived into Theano cored and got the basic idea of what I’am going to do. However, to make the idea more clear and to fit the requirement that student should post every week about their progress. I decide to write two post about Theano core – about how theano work. This is the first post. This post will talk about what is a function? And how a function is generate.

How a function is generated?

Just recall how we compiled a function func = theano.function( [ inputs ], output ), we can know that we should start out journey from method function(), which locates in theano/compile/founction.py.
In method function(), after some data verification, it will call orig_func() or pfunc() which return a function that user will get. Since pfunc() will also call orig_func(), we are going to look into pfunc() first.

pfunc.py

pfunc() have two major tasks:

• Transfer input_variable into In() instances. So does shared_variable. ( In function graph, SharedVariabls are treated as input, updates are treated as output ).
• Rebuild computational graph using updates and inputs, transform output into Out instances.

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

def pfunc( ... some arguments ... ):

    # Clones the replacements named in the givens argument, and points each Var1 to
    # the clone of Var2.
    # Transform params into theano.compile.In objects.
    inputs = [_pfunc_param_to_in(p, allow_downcast=allow_input_downcast)
                for p in params]

    #  clones the outputs and the update expressions.  This rebuilds a computation graph
    # from the inputs and the givens. ( Irrelative to me. Pass )

    output_vars = rebuild_collect_shared(outputs,
                                             in_variables,
                                             replace=givens,
                                             updates=updates,
                                             rebuild_strict=rebuild_strict,
                                             copy_inputs_over=True,
                                             no_default_updates=no_default_updates)
    # extracting the arguments
    input_variables, cloned_outputs, other_stuff = output_vars
    clone_d, update_d, update_expr, shared_inputs = other_stuff

    for i, iv in zip(inputs, input_variables):
        i.variable = iv

    for sv in shared_inputs:
        # pass value of None here
        # value will be stored in the resulting functions' defaults list
        # but since the value of shared variables never needs to be refed, it is not needed
        if sv in update_d:
            si = In(variable=sv, value=sv.container, mutable=True,
                    borrow=True, update=update_d[sv], shared=True)
        else:
            si = In(variable=sv, value=sv.container,
                    mutable=False, borrow=True, shared=True)
        inputs.append(si)

    return orig_function(inputs, cloned_outputs, mode,
            accept_inplace=accept_inplace, name=name, profile=profile,
            on_unused_input=on_unused_input, output_keys=output_keys

orig_func():

Now it time for a look into orig_func(). orig_func() will again makes sure that inputs and outputs are transformed into In an Out. And then it will use create method in FunctionMaker to make a function, which will be return.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def orig_function(inputs, outputs, mode=None, accept_inplace=False,
                  name=None, profile=None, on_unused_input=None,
                  output_keys=None):

    # conver input variable into instances of In() instances
    inputs = map(convert_function_input, inputs)

    # so do outputs
    if outputs is not None:
        if isinstance(outputs, (list, tuple)):
            outputs = map(FunctionMaker.wrap_out, outputs)
        else:
            outputs = FunctionMaker.wrap_out(outputs)

    # In()s and Out()s will be passed into FunctionMaker and a function will be create from it by calling create() method.
    fn = Maker(inputs,
                   outputs,
                   mode,
                   accept_inplace=accept_inplace,
                   profile=profile,
                   on_unused_input=on_unused_input,
                   output_keys = output_keys).create(
                       defaults)         #     ^^^^ 

FunctionMaker:

FunctionMaker.__init()__ is where fgraph is extracted and optimized. FuncitonMaker.create() is where function will be compiled and linked. In fact, FunctionMaker.linker.make_thunk() is where function is linked.

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

class FunctionMaker:
    def __init__( ...args... ):
        # again, make sure that input/output are tranformed into In and Out
        inputs, outputs = map(self.wrap_in, inputs), map(self.wrap_out, outputs)

        # ???
        _inputs = gof.graph.inputs([o.variable for o in outputs] + [i.update for i in inputs if getattr(i, 'update', False)])

        # make indices ... which is useless
        indices = [[input] + self.expand_in(input, _inputs) for input in inputs]

        # get fgraph
        if fgraph is Node:
            fgraph, additional_outputs = std_fgraph(inputs, outputs, accept_inplace)
        else:
            _, additional_outputs = std_fgraph(inputs, outputs, accept_inplace)
        self.fgraph = fgraph

        # fetch optimizor and linker
        optimizer, linker = mode.optimizer, copy.copy(mode.linker)

        # optimize fgraph
        # if need_opt:
            # optimization code here

        # linker accept fgraph 
        if no_borrow:
            self.linker = linker.accept(fgraph, no_recycling=infer_reuse_pattern(fgraph, no_borrow))
        else:
            self.linker = linker.accept(fgraph)

        if hasattr(linker, 'accept_var_updates'):
            # hacky thing so VMLinker knows about updates
            self.linker.accept_var_updates(
                    fgraph_updated_vars(fgraph, inputs))

        # some other configeration here
        # ...

    def create(self, input_storage=None, trustme=False):
    """
    Create a function.

    Input storage is the 'value' attribute of each In instances
    """

        # construct input_storage_list and default list
        for i, ((input, indices, subinputs), input_storage_i) in enumerate(zip(self.indices, input_storage)):
            # a lot of codes here.

        """
        Q: What's indices?
        List of (SymbolicInput, incide, [SymbolicInput..]). The first one is the 
        input vaiable; the incide is the index of the input in the input list; 
        the [SymIn...] the relevant input(?); 
        According to the document, the last two is deprecated. So it can be regarded as list of SymbolicInput.
    
        Q: What's defaults?
        A: List of 3-tuples. Each tuple corresponds to one input_storage. 
        ( 
          Bool: Is this input required at each function call?,  
          Bool: Should this inputs value be reverted to default value after each call? 
          AnyType: The value(storage) associated with this input.
        )
        """

        # call make_thunk() from linker and get fn
        try:
            theano.config.traceback.limit = 0
            _fn, _i, _o = self.linker.make_thunk(input_storage=input_storage_lists)
            # ^   ^   ^ => (function, input_containers, output_containers)
            # where function is a thunk that operates on the returned variables.
            # Because the map_storag() in make_thunk()
            # from here on, the input/output_storage represent all I/O of all relative nodes
            # ALso, storage is container, Instead of SymbolicKit
        finally:
            theano.config.traceback.limit = limit_orig

        # get a function, here function_builder() is the constructor
        # of class Function.
        fn = self.function_builder(_fn, _i, _o, self.indices, self.outputs,
                    defaults, self.unpack_single, self.return_none, self.output_keys, self)
        return fn

What’s theano.function?

Each function is a callable object. theano.function is not a python function. Instead, it a class with method __call__(). Every funciton stores its own fgraph, maker, storages and many other configurations. However, the core of a function is a function fn() returned by linker.make_thunk(). Every time a function is called, it will first verify the input data, and then call self.fn() to get output values.

Now I know how is a function borned. Also, I know that to complete my missions, I need to focus more on FunctionMaker and Function rather that orig_func() and pfunc(). However, there still exist some question, such as: What does make_thunk() do? and What is In(), Out() and container? In the next post, I will have a look at this and other relative data structures.

So, the buggy judging system of python is unbearable, therefore I just turned to C++ and expected a better experience. Also, I need to learn C++ for my future career. So, a good start. This post contains following problems:

• Reverse words
• Eval RPN
• Tree Traversal

Reverse words

Before solving this problem I never tried using std::string, I thought string operation in C++ is as hard as C. However, standard library really ease my pains. In fact, with the help of std, I think coding with C++ is much more easier and happier than coding with Ruby and Python now.

Question:

Given an input string, reverse the string word by word.

Basic logic:

The idea is simple, find each word in the sentence, push then in the stack and pop back after dealing the whole sentence. Be careful to the spaces in the head or tails of the sentence and the repeated spaces.

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

class Solution {
public:
    void reverseWords( string &s )
    {
        // get the words in reverse order
        vector<string> words;
        split( s, ' ', words);
        // reconstruct
        s = "";
        if( words.size() == 0 )return;
        for( int i=0; i<words.size();i++)
        {
            s.append(words[i]);
            s.append(" ");
        }
        // delete last space
        s.erase( s.length()-1, -1);

    }

    void split( string &s, char c, vector<string> &v )
    {
        int begin, last;
        // first word
        begin = s.length() -1 ;
        last  = s.find_last_of( c, begin );
        if( s.substr( last+1, begin-last) != "")
        {
            v.push_back(s.substr( last+1, begin-last));
        }
        // find next words
        while( last > 0 and begin != -1 )
        {
            // find a word 
            begin = last - 1;
            last  = s.find_last_of( c, begin );
            // if it's repeated split character, skip it
            while( last == begin )
            {
                begin = last - 1;
                last  = s.find_last_of( c, begin );
            }
            // skip if is last space
            if( s.substr( last+1, begin-last) != "")
            {
                v.push_back(s.substr( last+1, begin-last));
            }
        }
    }
};

evalRPN

Question:

Evaluate the value of an arithmetic expression in Reverse Polish Notation. For example: [“2”, “1”, “+”, “3”, “*”] -> ((2 + 1) * 3) -> 9

Basic logic:

Also simple idea: Iterater through the list, push numbers to a stack. Everytime we meet operaor, pop top 2 numbers and calculate the result, push the result to the stack. Finally, there will be only one number in the stack, which is the reuslt.

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

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        vector<int> resultStack;
        string symbol;
        int left, right, result;
        bool isOperator;
        for(int i=0; i<tokens.size();i++)
        {
            symbol = tokens[i];
            isOperator =  symbol=="+"||symbol=="-"||symbol=="*"||symbol=="/";
            if( ! isOperator )
                resultStack.push_back(std::stoi(symbol));
            else
            {
                right = resultStack.back();
                resultStack.pop_back();
                left = resultStack.back();
                resultStack.pop_back();
                if(symbol=="+")
                    result = left + right;
                else if(symbol =="-")
                    result = left - right;
                else if(symbol=="*")
                    result = left * right;
                else if(symbol=="/")
                    result = left / right;
                else
                    cout << "ERROR";
                resultStack.push_back(result);
            }
        }
        return resultStack.back();
    }
};

Tree traversal

Basic logic:

Basic algo. There are 3 kind of traversal method: postorder, preorder and inorder.

PostOrder

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

using namespace std;

class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> v;
        if( root == NULL){
            return v;
        }
        else{
            if( root->left != NULL ){
                travel( root->left, v );
            }
            if( root->right != NULL){
                travel( root->right, v );
            }
            v.push_back(root->val);
            return v;
        }
    }
    void travel( TreeNode *node, vector<int> &v ){
        if( node->left != NULL ){
            travel( node->left, v );
        }
        if( node->right != NULL){
            travel( node->right, v );
        }
        v.push_back(node->val);
    }
};

PreOrder

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

using namespace std;

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> v;
        if( root == NULL ){
            return v;
        }
        v.push_back(root->val);
        if( root->left ){
            travel( root->left, v );
        }
        if( root->right ){
            travel( root->right, v);
        }
        return v;
    }

    void travel(TreeNode *node, vector<int> &v){
        v.push_back(node->val);
        if( node->left ){
            travel( node->left, v );
        }
        if( node->right ){
            travel( node->right, v);
        }
    }
};

I collected a bunches of leetcode code solutions and now put them in one post. This post contains the following questions:

* BST Iterator
* Factorial Trailing Zeros
* Excel number
* Decimal
* Find Peak Element
* Min stack
* Majority elements
* Trailing zeros
* Tree Travel

Also, after realing leetcode online judge have numerous bug in python test case, I decided to turn to C++. So, here comes the solutions.

BST Iterator

Question:

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST. Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Basic logic:

The smallest value is will be on the left-most node, therefore the first thing to do is to dive to the deepest ad left-most of the tree. Next we can return the value of the middle node, then its left node. A list of nodes on path should be maintain to avoid return repeated value.

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

class BSTIterator:
    # @param root, a binary search tree's root node
    def __init__(self, root):
        # ancestors of current node, 
        self.ancestors = []

        # current node, initialized by root
        self.current = None

        # current point to the  smallest value
        self.current = root
        self.dive()

    # @return a boolean, whether we have a next smallest number
    def hasNext(self):
        return self.current != None

    def hasLeft(self):
        return self.hasNext()

    def hasRight(self):
        return self.hasNext()

    # @return an integer, the next smallest number
    def next(self):
        # every time we dive first,
        # so the smallest value is the current node
        rval = self.current.val

        if not self.hasRight():
            # if no right nodes
            # the next smallest value will be current node's parent
            if len(self.ancestors) == 0:
                self.current = None
            else:
                self.current = self.ancestors.pop()
        else:
            # if there is right node,  it's value will smaller than parent's, 
            # so step into it, then dive to left-most
            self.current = self.current.right
            self.dive()

        return rval

    def dive(self):
        while self.hasLeft():
            self.ancestors.append( self.current )
            self.current = self.current.left

Excel column number

Qusetion

Given Excel column number, return the corresponding digit number

Basic logic

A conversion of number systems( thought not a typical one) . First we map characters to numbers, them multiply digit in the Nth location with 26^n, sum and get the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    # @param s, a string
    # @return an integer
    def __init__(self):
        self.map ='ABCDEFGHIJKLMNOPQRSTUVWXYZ'

    def titleToNumber(self, s):
        rval = 0
        for i in xrange(len(s)):
            # need to revese the string
            rval += self.char2Int(s[ len(s) - i -1])*(26**i)
        return rval

    def char2Int(self, char):
        return self.map.index(char)+1

Majority element

Question:

Given an array of size n, find the majority element. The majority element is the element that appears more than n/2 times.

Basic logic:

Use a counter(map) to calculate how many times each elements has occured and return if times > length/2.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    # @param num, a list of integers
    # @return an integer
    def majorityElement(self, num):
        map = {}
        length = float(len(num))
        for n in num:
            try:
                map[n] += 1
            except:
                map[n] = 1
            if map[n] >= length/2:
                return n

Trailing zeros.

Question:

Given an integer n, return the number of trailing zeroes in n!.

Basic logics:

This is more a math problem than a code problem. Notice that 1 x 2 x 3 ... x 5 ... x 10 ... with every 5( or n x 5 ) there must be a 2(ornx2). And the trailing zeros must be the result of (2x5)^n. Therefore, the problem becomes ‘How many 5 are there in it’s factors’. ( Need to rewrite this paragraph )

1
2
3
4
5
6
7
8
9

class Solution:
    # @return an integer
    def trailingZeroes(self, n):
        num = 0
        k = 1
        while 5**k <= n:
            num += int(n/(5**k))
            k += 1
        return num

Find peak elements

Questions

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

Basic logic

Easy problem, just iter over and compare each element with its neighbours. If the num[i] can equals num[i+], we first deduplicate, and then compare. Need some attentions on the conner case( length = 0,1 or the peak occurs on the head or tails)

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

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        if len(num) == 1:
            return num[0]
        elif len(num) == 2:
            return min(num[0],num[1])
        else:
            # deduplicate
            while len(num) > 1 and num[0] == num[-1]:
                num.pop()
            for i in xrange(len(num)):
                try:
                    if num[i] == num[i+1]:
                        num.pop(i)
                except:
                    break
            return self.findMinNoRepeat(num)

    def findMinNoRepeat(self, num):
        if len(num) == 1:
            return num[0]
        elif len(num) == 2:
            return min(num[0],num[1])
        else:
            buf = []
            index = 0
            length = len(num)
            for i in xrange(3):
                buf.append(num[index])
                index += 1
            index -= 1

            while True:
                if self.isMax(buf):
                    return buf[1]
                else:
                    index += 1
                    index %= length
                    if num[index] != buf[-1]:
                        buf.pop(0)
                        buf.append(num[index])

    def isMax(self, buf):
        return buf[1]<buf[0] and buf[2]>buf[1]

Min Stack

question

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

* push(x) -- Push element x onto stack.
* pop() -- Removes the element on top of the stack.
* top() -- Get the top element.
* getMin() -- Retrieve the minimum element in the stack.

Basic logic

The key is to maintain double stack: one for normal push() and pop(), the other for the operation getMin(). When a new min value is pushed, we also push it to the min_stack, when it pops, we also pop it from min_stack. So the minimum value is always on the top of min_stack.

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

class MinStack:
    def __init__(self, node = None):
        self.stack = []
        self.minStack = []

    # @param x, an integer
    # @return an integer
    def push(self, x):
        self.stack.append(x)
        if self.minStack == [] or x <= self.minStack[-1]:
            self.minStack.append(x)

    # @return nothing
    def pop(self):
        val = self.stack.pop()
        if val == self.minStack[-1]:
            self.minStack.pop()

    # @return an integer
    def top(self):
        return self.stack[-1]

    # @return an integer
    def getMin(self):
        return self.minStack[-1]

Fraction to Recurring Decimal

Question

Basic logics.

Easy job, just a little bit tedious. By implementing a long divide, we can easily find the answer. Remember to store every ( quotient，remainder )pairs so that we can know when it starts repeat itself. The python test case is wrong. See this post. After this solution, I turned to C++, which should have better judge 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

class Solution():
    def __init__(self):
        pass
    # @return a string
    def fractionToDecimal(self, numerator, denominator):
        # corner case
        if numerator == 0:
            return '0'

        # if no decimal number
        if numerator % denominator == 0:
            return str( numerator/denominator )
        else:
            # reduction of a fraction, not necessary
            fraction = 2
            while True:
                while fraction <= min( abs(numerator), abs(denominator) ):
                    if numerator % fraction == 0 and denominator % fraction == 0:
                        numerator /= fraction
                        denominator /= fraction
                        break
                    fraction += 1

                # if it's end, end it. else ,restart again
                if fraction >= min( abs(numerator), abs(denominator) ):
                    break
                fraction = 2

            # Decomposition quality factor to find if demimal repeated itself, not necessary.
            denom = abs(denominator)
            while denom % 2 == 0:
                    denom /= 2
            while denom % 5 == 0:
                    denom /=5
            repeated = denom != 1

            result_list = []
            # get the symbol of final result
            if numerator*denominator < 0:
                result_list += [('-','-')]
            numerator = abs(numerator)
            denominator = abs (denominator)

            # start long divide loop( core algo )
            add_dot = True
            index = 0
            while True:
                # long divide
                quotient = numerator / denominator
                remainder = numerator % denominator
                numerator = remainder

                # check if repreated, if not, ready for the next division
                if (remainder, quotient) in result_list:
                    repreat_start_locaation = result_list.index((remainder, quotient))
                    result_list.insert( repreat_start_locaation, ( '(', '(' ) )
                    result_list.append( ( ')' , ')' ) )
                    break

                # append this result of division
                result_list.append( (remainder, quotient) )
                # if remainder is 0, it's not a repreated number                    
                if remainder == 0:
                    break
                if add_dot:
                    result_list.append( ('.','.') )
                    add_dot = False
                numerator *= 10

                index += 1
                if index > 100:
                    break


            # construck result
            result_list.reverse()
            result_str = ''
            while len(result_list) > 0:
                remainder, quotient = result_list.pop()
                result_str += str(quotient)
            return result_str