FUN with problems: 2013

6. More to read:
http://www.php.net/manual/en/book.gearman.php
http://toys.lerdorf.com/archives/51-Playing-with-Gearman.html
https://www.rssinclude.com/blog/36_how_to_run_php_scripts_in_html_or_htm_files

7. Running on a web browser:
a. create a script to be executed, name it cal.php
and "chmod 500" to it
b. in same folder, created a file to be displayed, name it hello.php
and now open the browser address: http://127.0.0.1/hello.php
it should work, provided there's a gearman worker already up.

Wednesday, July 10, 2013

The peripheral stuff

feedback system: helpscout : https://www.helpscout.net/
ticket system: redmine: http://www.redmine.org/
monitoring heartbeat: http://www.linux-ha.org/wiki/Main_Page
Qgis, amazon aws

Monday, July 8, 2013

OpenTripPlanner

Getting OpenTripPlanner to work and more:

1. Download, configure and test run on http
https://github.com/openplans/OpenTripPlanner/wiki/TwoMinutes

note: once the browser opens http://localhost:8080/opentripplanner-webapp
the background maybe empty. On the far right of the page, click the "+" sign. Then under "Base Layer" and choose "Open Street Map" (or others, instead of the default "Mapbox Steets")

2. Test the Stand-alone mode, which is used as an API
https://github.com/openplans/OpenTripPlanner/wiki

3. Json or Xml (default) result can be generated:
https://github.com/openplans/OpenTripPlanner/wiki/JsonOrXml

EXAMPLE:
curl --header "Accept: application/json" "http://maps5.trimet.org/osm?mode=BICYCLE&toPlace=45.504966%2C-122.654349&fromPlace=45.5115225%2C-122.647633"
vs.
curl --header "Accept: application/xml" "http://maps5.trimet.org/osm?mode=BICYCLE&toPlace=45.504966%2C-122.654349&fromPlace=45.5115225%2C-122.647633"

4. Build graphs:
https://github.com/openplans/OpenTripPlanner/wiki/GraphBuilder

protoc protobuf Protocol Buffers

This blog entry lists the process to use google's Protoco Buffers, on x64 Linux Mint 14.

1. Download protobuf-2.5.0.tar.bz2 from
https://code.google.com/p/protobuf/downloads/list

2. Extract the file anywhere.

3. Under the extracted folder, run

$./configure
$make
$make check
$sudo make install

4. View the README file in the folder, and test some common:

$pkg-config --cflags protobuf # print compiler flags
$pkg-config --libs protobuf # print linker flags
$pkg-config --cflags --libs protobuf # print both

5. Download a proto file. e.g. from
https://developers.google.com/transit/gtfs-realtime/gtfs-realtime-proto

6. Go to the proto file folder and generate the C++ header and source file:

$protoc gtfs-realtime.proto --cpp_out=./

Ref: https://developers.google.com/protocol-buffers/docs/proto

7. If there are some errors, check the environment variables

$export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib $export PKG_CONFIG_PATH=/usr/local/lib/pkgconfig

Ref: http://blog.csdn.net/programmer_h/article/details/8890800

8. Write a sample main file:

#include <iostream>
#include <string>
#include <fstream>
#include "gtfs-realtime.pb.h"
using namespace std;

int main()
{
   fstream file("alert2.dat");
   string outline;
   getline(file, outline);
   cout <&lt outline << endl;
}

9. Download a sample encoded binary data file: e.g.
http://www.bart.gov/dev/gtrtfs/alerts.aspx

10. Compile:

$clang++ main.cpp gtfs-realtime.pb.cc `pkg-config --cflags --libs protobuf`

Wednesday, June 26, 2013

const volatile

http://www.daniweb.com/software-development/c/threads/187964/const-volatile

When const volatile are used together:

const means the program can not modify the value volatile means the value may be arbitrarily modified outside the program.
the two are separate and not mutually exclusive.
use them together, for instance, in the case of reading a hardware status register. const prevents the value from being stomped on, while volatile tells the compiler that this value can be changed at any time external to the program.
this const volatile will thus satisfy both requirements and prevent an optimizing compiler from incorrectly optimizing the code, that it would do if only "const" were used.

Let's take an example
const volatile usigned int *REG_A = (usigned int *) init_hardware_n_return_address of REG_A();
In the above snippet function "init_hardware_n_return_address of REG_A()" modifies the content of the REG_A( register A say) of a peripheral device , say after initiatialising it ( which cause the content of R/W register REG_A modified by peripheral itself) and returns the address of REG_A to the program .

The assignment in the above snippet implies here that content of REG_A can be modifiable only be external sources like peripheral hardware itself and and your code is not supposed to modify the content of REG_A .
Also whenever such variable is encountered compiler should "load " it value every time instead of doing any code optimasation
Typically memory mapped variables are one consumers for such usage

Declaring a variable as const indicates the compiler that the variable will never be changed(either by the program/external entity like a peripheral device.
Declaring a variable as volatile indicates the compiler that the variable might be changed dynamically (by an external entity or by our program). Hence whenever we are accessing that variable, compiler will not perform optimization and will fetch the value from its address(which will cost us a few more cpu cycles).
Now Declaring a variable as a const volatile, we indicate the compiler that variable cant be modified by the program but can be modified by an external entity.
The usage of const volatile is more predominant in Device Driver Programming.

Monday, June 10, 2013

tools

sudo apt-get install libxml2-dev
sudo apt-get install libcurl4-openssl-dev
sudo apt-get install libmysql++-dev
sudo apt-get install cimg-dev
sudo apt-cache search libjpeg-dev
sudo apt-get install libgearman-dev

clang bug chrono and thread

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53841

chrono thread bug fix for:

linux error: no matching constructor for initialization of 'duration'

using the Suggested fix:

- const chrono::nanoseconds __delta = __atime - __c_entry;
- const __clock_t::time_point __s_atime = __s_entry
+ __delta; + const auto __delta = __atime - __c_entry;
+ const auto __s_atime = __s_entry
+ __delta; in file condition_variable

@ line 110 in /usr/include/c++/4.7

After install something, link them to /usr/local/bin, /usr/local/include, /usr/local/share so that the system path can find them anywhere

Monday, May 6, 2013

Start valgrind

Profiler under linux64

1. Install
http://www.cprogramming.com/debugging/valgrind.html
Download from http://www.valgrind.org/downloads/valgrind-3.8.1.tar.bz2
Then

$ bzip2 -d valgrind-XYZ.tar.bz2
$ tar -xf valgrind-XYZ.tar

$ ./configure
$ make
$ make install

Then need to install the glibc-debuginfo

$ sudo apt-get install valgrind

2. Write a C++ program
http://jblevins.org/log/valgrind

#include <stdlib.h>

void f(void)
{
     int* x = (int*)malloc(10 * sizeof(int));
     x[10] = 0;        // problem 1: heap block overrun
}                    // problem 2: memory leak -- x not freed

int main(void)
{
     f();
     return 0;
}

3. Compile it with -g debug flag on

4. run

$ valgrind ./a.out

Sunday, April 14, 2013

C/C++ with Gearman (as worker)

The document is very vague about how to register a function. It turned out that the prototype/signature of the function gearman_worker_fn is very import:

typedef void*( gearman_worker_fn)(gearman_job_st *job, void *context, size_t *result_size, gearman_return_t *ret_ptr)

And since all the online document links are broken, I had to create using Doxygen, under folder /usr/local/include/libgearman-1.0

#include <iostream>
#include <libgearman/gearman.h>
#include <cstring>

using namespace std;

 void* gworker_fn_demon(gearman_job_st *job, void *context, size_t *result_size, gearman_return_t *ret_ptr)
{
   auto jobptr = gearman_job_workload(job);//this takes the data from the client
   if (jobptr) std::cout << "job: " << (char*) jobptr << std::endl;
  *ret_ptr = GEARMAN_SUCCESS ;
  *result_size = 6;

  cout<<"job received"<<endl;
  //char* result = new char[100];//bug here: free/new mismatch reported from valgrind
char* result = (char*)malloc(100 * sizeof(char));
for(int ii = 0; ii < 4; ++ii){
  result[ii] = 'a' + ii;
 }
 result[4] = '\n';
 result[5] = '\0';
 return result;//the memory is freed at client side

 }


int main()
{
 auto status_print = [](gearman_return_t gserver_code){
   cout<<gserver_code<< " --  "; 
   if (gearman_success(gserver_code)) cout<<"success";
   if (gearman_failed(gserver_code)) cout<<"failed";
   if (gearman_continue(gserver_code)) cout<<"continue";
   cout<<endl;
 };

 gearman_worker_st* gworker = gearman_worker_create(NULL);
 

 
 const char* ghost = "127.0.0.1";
 in_port_t gport = 4730;

 gearman_return_t gs_code = gearman_worker_add_server(gworker, ghost, gport);

 status_print(gs_code);


 const char* function_name = "wwcc";
 unsigned timeout = 0;
 void * job_context = NULL;

 gs_code = gearman_worker_add_function(gworker,function_name, timeout, gworker_fn_demon, job_context);

 status_print(gs_code);



 gs_code = gearman_worker_work(gworker);

 status_print(gs_code);

 

 gearman_worker_free(gworker);


 cout<<"done"<<endl;
 return 0;
}

Python with Gearman (as worker)

http://pythonhosted.org/gearman/worker.html

#!/usr/bin/python
import gearman
import time
def check_request_status(job_request):
    if job_request.complete:
        print ("Job finished! ")
        print (job_request.result)
    elif job_request.timed_out:
        print ("Job timed out!")
    elif job_request.state == JOB_UNKNOWN:
        print ("Job connection failed!" )

gm_worker = gearman.GearmanWorker(['localhost:4730'])

def task_listener(gearman_worker, gearman_job):
    return gearman_job.data + ' from listener\n'

gm_worker.set_client_id('whatever iid');
gm_worker.register_task('wwcc', task_listener)

gm_worker.work()

Saturday, April 13, 2013

C/C++ with gearman (as client)

gearman library (libgearman) can be directly called in C/C++ programs. (gearmand --version 1.1.5)

http://gearman.info/libgearman/examples.html

And my makefile:

a.out:callrev.cpp
clang++ -o $@ $^ -std=c++11 -lgearman

Together with the worker command from last post, here is a complete C++ program as a client:

#include <libgearman/gearman.h>
#include <iostream>
#include <cstring>
using namespace std;

int main(){
 gearman_client_st* gclient = gearman_client_create(NULL);
 gearman_return_t gsc = gearman_client_add_server(gclient, "127.0.0.1",4730);

 auto status_print = [](gearman_return_t gserver_code){
  cout<<gserver_code<< " --  "; 
  if (gearman_success(gserver_code)) cout<<"success";
  if (gearman_failed(gserver_code)) cout<<"failed";
  if (gearman_continue(gserver_code)) cout<<"continue";
  cout<<endl;
 };

 status_print(gsc);

 const char* function_name = "wwcc";

 const char* unique = "whatever unique";
 const char* workload = "aa bb cc";
 size_t workload_size = strlen(workload);
 size_t result_size;
 gearman_return_t return_code;
 void* value = gearman_client_do(gclient, function_name, unique, workload, workload_size, &result_size, &return_code);

 status_print(return_code);
 const char* result = static_cast<char*>(value);
 cout<<result<<endl;


 free(value);
 gearman_client_free(gclient);
 
 return 0;
}

Python with Gearman (as client)

My planned structure: C++ as the worker in the backend, Python as the client at the front end, and Gearman is the agent in between.

Now test the front end.

1. Start up gearmand server and and sample worker. (word counter, from last post)

2. Install python-gearman module:
http://www.geeksww.com/tutorials/web_development/python/installation/how_to_install_python_gearman_client_module.php

3. Write a test python file:
http://www.saltycrane.com/blog/2010/04/notes-using-gearman-with-python/
http://pythonhosted.org/gearman/client.html

#!/usr/bin/python
import gearman
def check_request_status(job_request):
    if job_request.complete:
        print ("Job finished! ")
    elif job_request.timed_out:
        print ("Job timed out!")
    elif job_request.state == JOB_UNKNOWN:
        print ("Job connection failed!" )

gm_client = gearman.GearmanClient(['localhost:4730', 'otherhost:4730'])

# See gearman/job.py to see attributes on the GearmanJobRequest
# Defaults to PRIORITY_NONE, background=False (synchronous task), wait_until_complete=True
completed_job_request = gm_client.submit_job("wwcc", "arbitrary binary data")
check_request_status(completed_job_request)

Here the #! version should be matching the default python used by gearman module. I typed #!/usr/bin/python3.3, which would not work.

Start with Gearman

1. Install gearman, server and client:

$ sudo apt-get install gearman-job-server

2. Creat gearmand log file:

$ mkdir ~/log/gearmand
$ touch ~/log/gearmand/gearmand.log
$ cd ~/log/gearmand

3. Start gearman server on localhost (127.0.0.1), port 4730

$ gearmand --log-file gearmand.log --listen 127.0.0.1 --port=4730 --verbose=INFO

4. Register gearman worker (with funciton name wwcc):

$ gearman -w -h 127.0.0.1 -p 4730 -f wwcc -- wc -l

5. Send data/request from a gearman client:

$ gearman -h 127.0.0.1 -p 4730 -f wwcc < /etc/passwd
$ gearman -h 127.0.0.1 -p 4730 -f wwcc "hello world"

6. The stdout on terminal shows the result, something like:

48 78 2409
0 2 11

For default localhost:4730, step 3 can be simplified to, (in addtion, running in background):

$gearmand -d -l gearmand.log

http://gearman.org/getting_started
http://stackoverflow.com/questions/6995202/problem-with-gearman-gearman-could-not-connect
http://stackoverflow.com/questions/14526086/gearman-issues-php-cli

$man gearman
$man gearmand
$gearmand -h
$man gearadmin

Related error messages:

gearmand: Could not open log file "/usr/local/var/log/gearmand.log", from "/home", switching to stderr. (Permission denied)

This means the access to gearmand.log file is limited (owned by root?). Creating a new log file solves this problem (step 2 above).

gearman: gearman_client_run_tasks : flush(GEARMAN_COULD_NOT_CONNECT) localhost:0 -> libgearman/connection.cc:672

The gearmand server is not running, or binds to a different address:port than requested. (step 3 above)

gearmand: unknown option -v

The -v option is not suppored in new versions. use: --verbose=INFO (step 3 above)

ERROR 2013-04-13 22:15:55.000000 [ main ] Timeout occured when calling bind() for 0.0.0.0:4730 -> libgearman-server/gearmand.cc:616

The listen to address is bad. Specify localhost by -h 127.0.0.1 (step3,4,5 above)

gearmand: error while loading shared libraries: libboost_program_options.so.1.48.0: cannot open shared object file: No such file or directory

$sudo apt-get install libboost-program-options1.48.0
After some updates, the old boost lib was autoremoved. Just reinstall it and problem solved.

Thursday, March 21, 2013

create library in C/C++

http://www.yolinux.com/TUTORIALS/LibraryArchives-StaticAndDynamic.html

Friday, March 8, 2013

Mount USB external drive on Linux

1. Plug in the USB disk.

2. Under
/dev/disk/by-label
find the device info, e.g.
Seagate\x20Backup\x20Plus\x20Drive -> ../../usb_bk

(or, simple $ lsusb)

3. sudo makedir /mnt/usb_bk

4. cd ../..

5. mount sdb1 /mnt/usb_bk

Now, the disk shows up under /mnt/usb_bk

6. (optional)
To make it auto mount, first confirm the mount parameters:
$mount
it should show the mount type:

/dev/sdb1 on /mnt/usb_bk type fuseblk (rw,nosuid,nodev,allow_other,blksize=4096)

Then edit /etc/fstab

/dev/sdb1       /mnt/usb_bk          fuseblk    defaults        0       0

http://linuxconfig.org/Howto_mount_USB_drive_in_Linux

http://myubuntublog.wordpress.com/2009/05/25/auto-mount-usb-hard-drive-at-boot/

ARECA backup tool

1. Install Java
sudo apt-get install openjdk-7-jdk openjdk-7-jre icedtea-7-plugin

2. Download and install areca:
http://www.areca-backup.org/

Thursday, March 7, 2013

clang 3.2

compile from source code. Follow the instructions on:
http://clang.llvm.org/get_started.html

Note: the ./configure line is changed to
$ CC=gcc CXX=g++ ../llvm/configure

OR, apt-get install
http://askubuntu.com/questions/261636/how-do-i-backport-install-a-newer-version-of-clang

Tuesday, March 5, 2013

Recursive global replace

find ./ -type f -exec \
sed -i 's/\<map\>/unordered_map/g' {} +

under a folder, do an exact match, and recursively replace to a new word.

The motivation was this: I want to upgrade my source code to C++11. To be more efficient, all the old <map> header and usage, which is log(n), should be replaced by the new hash function in <unordered_map>. But there are other names with prefix or postfix "map", which should not be changed.

Monday, February 25, 2013

The CImg LIb Hello World

http://kiharalab.org/genPortrait/src/CImg-1.2.5/documentation/reference/group__cimg__structure.html

Friday, February 22, 2013

xml intro

First impression to XML parsing using RapidXML lib in C++
http://rapidxml.sourceforge.net/

Example XML from here:
http://msdn.microsoft.com/en-us/library/windows/desktop/ms762271%28v=vs.85%29.aspx

Test code under the same folder of the RapidXML:

#include <iostream>
#include <sstream>
#include <fstream>

#include "rapidxml/rapidxml.hpp"
#include "rapidxml/rapidxml_print.hpp"


using namespace std;
using namespace rapidxml;

 char *buffer_file( const char *filename, size_t *buffer_len = NULL )
 {
  //open file.  note: it is important to say binary here, otherwise it does conversion that may change the length!
  std::fstream file( filename, std::ios::in|::std::ios::binary );
  if( !file ) return NULL;

  //read the size...
  file.seekg(0, std::ios::end);
  size_t length = (size_t)file.tellg();
  if( buffer_len ) *buffer_len = length;
  file.seekg(0, std::ios::beg);
  
  //read into memory buffer..
  char *filebuf = new char[length+1];
  file.read(filebuf, length);
  filebuf[length] = '\0'; //make it null-terminated
  file.close();
  return filebuf;
 }


int main(int argc, char* argv[]) {
    char* xml = buffer_file("books.xml");

    //Parse the original document
    xml_document<> doc;
    doc.parse<0>(xml);
    xml_node<> * node = doc.first_node();
    cout << "Name of my first node is: " << node->name() << "\n";
for( xml_node<>* node_ptr = node->first_node("book"); node_ptr != NULL; node_ptr = node_ptr->next_sibling())

    cout<< "node name : " << node_ptr->first_attribute("id")->value()<< endl;
    return 0;
}

Sunday, February 17, 2013

HTC Thunderbolt bricked

Hold Power Key + Volume Down, boot to the list

http://androidforums.com/evo-4g-all-things-root/146246-hboot-driver-help.html
http://unrevoked.com/rootwiki/doku.php/public/windows_hboot_driver_install?

Select Recovery, and reboot (press Power Key). This lead to the ClockWork (if rooted)

Wipe Cache
http://www.droidforums.net/forum/thunderbolt-tech-support/147167-how-get-rid-ota-forced-reboots-rooted-phone.html

Then reboot. See an Error: Update Failed message at start up, which is good. Click "Cancel".

Thursday, February 14, 2013

Word Ladder

//passed small test, but not big test yet

class Solution {
    unordered_set<string> dict;//short dictionary
    bool off_by_one(string const& s1, string const& s2){
      int counter = 0;
      for(unsigned int ii = 0; ii < s1.length(); ++ii){
        if (s1[ii] != s2[ii]) ++counter;
        if (counter >= 2) return false;
      }
      return (1 == counter);
    }
    
    class Node{
        public:
          Node(string name):word(name),parent(0){}
          string word;
          vector<Node*> children;
          Node* parent;
    };
    
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int const word_length = start.length();
        for(auto word:dict){
            if (word.length() == word_length)
            this->dict.insert(word);
        }
        return mutationPath(start,end).size();
    }
    
    vector<string> mutationPath(string const& source, string const& dest){
    
      vector<string> result;
      Node* sp = new Node(source);
      if (source!=dest)dict.erase(source);
      deque<Node*> frontier;
      frontier.push_back(sp);
      while(!frontier.empty()){
        Node* node = frontier.front(); frontier.pop_front();
        string const word = node->word;
        for (auto it = dict.begin(); it != dict.end();){
          string const neighbor(*it);
          if (off_by_one(word, neighbor)){
            if (dest == neighbor){
              result.push_back(neighbor);
              while(node){
                result.push_back(node->word);
                node = node->parent;
              }
              return vector<string>(result.rbegin(),result.rend());
            }
            dict.erase(it++);
            auto it_n = new Node(neighbor);
            node->children.push_back(it_n);
            node->children.back()->parent = node;
            frontier.push_back(it_n);
          }else ++it;
        }//for it
      }//while not empty
      return result;
      //--------------------------
    }
};

//Another way, but still does not pass the big test

class Solution {
    struct Node{
        string name;
        int count;
        Node(string n, int cnt = 0):name(n),count(cnt){}
    };
    string const alphabet{"abcdefghijklmnopqrstuvwxyz"};
    vector<string> neighborList(string const& word){
        vector<string> neighbors;
        for(int ii = 0; ii < word.length(); ++ii){
            int const firstLength = ii;
            int const secondLength = word.length() - firstLength - 1;
            string firstPart = word.substr(0,firstLength);
            string secondPart = word.substr(ii+1, secondLength);
            for(char c:alphabet){
                if (c != word[ii]) neighbors.push_back(firstPart+c+secondPart);
            }
        }
        return neighbors;
    }
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        set<string> sdict;//short dict
        int const word_length = start.length();
        for(auto word: dict){
            if (word.length() != word_length) continue;
            sdict.insert(word);
        }
        deque<Node> frontier{Node(start)};
        while(!frontier.empty()){
            Node currentNode = frontier.front();
            frontier.pop_front();
            vector<string> neighbors = neighborList(currentNode.name);
            for(string neighbor_candidate: neighbors){
                set<string>::iterator it = sdict.find(neighbor_candidate);
                if (it != sdict.end()){
                    if (end == neighbor_candidate) return currentNode.count+2;
                    frontier.push_back(Node(neighbor_candidate, currentNode.count+1));
                    sdict.erase(it);
                }
            }
        }
        return 0;
    }
};

Tuesday, February 12, 2013

Doxygen Graph

1. Install doxygen
2. Install graphviz
3. Set DOT path
export PATH=$PATH:/usr/lib/graphviz

4. Create Doxyfile
doxygen -g

5. Configurate Doxyfile: http://www-scf.usc.edu/~peterchd/doxygen/
vi Doxyfile

EXTRACT_ALL = YES

Extract documentation even from those elements you haven't yet commented.

INLINE_SOURCE = YES

Extract the relevant parts of the source and associate them with your description.

HAVE_DOT = YES

Use Graphviz for class and collaboration diagrammes.

CALL_GRAPH = YES

Generate a dependency graph for functions and methods.

GENERATE_LATEX = NO

Skip generating LaTeX sources for PDF.

RECURSIVE = YES

6. Run doxygen in the working folder

7. Open index.html under ./html

Gearman - Ubuntu 12.04

1. Pre-Install

You will need to install the following packages in order to build Gearman.

sudo apt-get install –yes gcc

sudo apt-get install –yes autoconf

sudo apt-get install –yes bison

sudo apt-get install –yes flex

sudo apt-get install –yes libtool

sudo apt-get install –yes make

sudo apt-get install –yes libboost-all-dev

sudo apt-get install –yes libcurl4-openssl-dev curl

sudo apt-get install –yes libevent-dev

sudo apt-get install –yes memcached

sudo apt-get install –yes uuid-dev

sudo apt-get install –yes libsqlite3-dev

sudo apt-get install –yes libmysqlclient-dev

http://gearman.info/build/ubuntu.html

2. Download gearman and unpack, run ./configuehttp://gearman.org/getting_started

3. make and sudo make install

4. gearmand -d
gearmand -h

Saturday, February 9, 2013

GITHub remote SSH

https://help.github.com/articles/generating-ssh-keys

Follow the steps above. One edit: no need to install xclip, just
$cat id_rsa.hub

and copy paste the terminal.

Monday, January 21, 2013

Roman to Integer

Roman to Integer (link)Jan 15 '12

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

class Solution {
    int romanToDigit(char c){
        int r = 0;
        switch(c){
            case 'I': r = 1; break;
            case 'V': r = 5; break;
            case 'X': r = 10; break;
            case 'L': r = 50; break;
            case 'C': r = 100; break;
            case 'D': r = 500; break;
            case 'M': r = 1000; break;                
        }
        return r;
    }
public:
    int romanToInt(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.empty()) return 0;
        int num = romanToDigit(s[s.length()-1]);
        int prev = num;
        for(int ii = s.length() - 2; ii >= 0; --ii){
            int const digitNum = romanToDigit(s[ii]);
            if (digitNum < prev) num -= digitNum;
            else num += digitNum;
            prev = digitNum;
        }
        return num;
    }
};

Rotate Image

Rotate Image (link)Mar 18 '12

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (matrix.empty() || matrix[0].empty() ) return;
        int const max = matrix.size() - 1;
        int const quarter_col_size = matrix.size() / 2 + (matrix.size()%2);
        int const quarter_row_size = matrix.size() / 2;
        for(int row = 0; row < quarter_row_size; ++row){
            for(int col = 0; col < quarter_col_size; ++col){
                int const temp = matrix[row][col];
                matrix[row][col] = matrix[max-col][row];
                matrix[max-col][row] = matrix[max-row][max-col];
                matrix[max-row][max-col] = matrix[col][max-row];
                matrix[col][max-row] = temp;
            }
        }
    }
};

Friday, January 11, 2013

Rotate List

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!head || !head->next || !k) return head;
        ListNode* front = head;
        for(int ii = 0; ii < k; ++ii){
            front = front->next;
            if (!front) front = head;
        }
        ListNode* it = head;
        while(front->next){
            front = front->next;
            it = it->next;
            if (!it) it = head;
        }
        front->next = head;
        head = it->next;
        it->next = NULL;
        return head;
    }
};

Same Tree

Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!p || !q) return !p && !q;
        return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        
    }
};

Scramble String

Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

class Solution {//passed small only
public:
    bool isScramble(string s1, string s2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s1.size() == 1) return s1[0] == s2[0];
        if (s1.empty() || s1.compare(s2) == 0) return true;
        int const max_index = s1.length()-1;
        for(int ii = 1; ii <= max_index; ++ii){
            string const s1_left = s1.substr(0, ii);
            string const s1_right = s1.substr(ii, s1.length()-ii);
            string const s2_left1 = s2.substr(0,ii);
            string const s2_right1 = s2.substr(ii, s2.length()-ii);
            string const s2_left2 = s2.substr(s2.length()-ii, ii);
            string const s2_right2 = s2.substr(0, s2.length()-ii);
            if (isScramble(s1_left, s2_left1) && isScramble(s1_right, s2_right1) 
              || isScramble(s1_left, s2_left2) && isScramble(s1_right, s2_right2))
              return true;
        }
        return false;
    }
};

 class Solution {//passed large
    vector<vector<vector<int> > > record;
    string sa,sb;
public:
    bool process(int pos1, int pos2, int length){
        if (length == 1) return sa[pos1] == sb[pos2];
        if (length == 0) return true;
        if (record[pos1][pos2][length] == 1) return true;
        if (record[pos1][pos2][length] == -1) return false;
        for(int ii = 1; ii < length; ++ii){//ii is size_left
            int const size_right = length - ii;
            if (process(pos1, pos2, ii) && process(pos1+ii, pos2+ii, size_right) 
              || process(pos1, pos2+length-ii,ii) && process(pos1+ii, pos2, size_right)){
                record[pos1][pos2][length] = 1;              
                return true;
              }
        }
        record[pos1][pos2][length] = -1;
        return false;
    }

    bool isScramble(string s1, string s2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        sa = s1;
        sb = s2;
        record.clear();
        record.assign(s1.length()+1,vector<vector<int> >(s1.length()+1, vector<int>(s1.length()+1, 0)));

        return process(0,0,s1.length());
  }
};

sourcecode

Wednesday, July 17, 2013

Tuesday, July 16, 2013