Skip to main content

Posts

Showing posts from December, 2014

First post using stackedit

Welcome to StackEdit! Hey! I’m your first Markdown document in StackEdit1. Don’t delete me, I’m very helpful! I can be recovered anyway in the Utils tab of the Settings dialog.
Documents StackEdit stores your documents in your browser, which means all your documents are automatically saved locally and are accessible offline!
Note:
StackEdit is accessible offline after the application has been loaded for the first time.Your local documents are not shared between different browsers or computers.Clearing your browser’s data may delete all your local documents! Make sure your documents are synchronized with Google Drive or Dropbox (check out the Synchronization section). Create a document The document panel is accessible using the button in the navigation bar. You can create a new document by clicking New document in the document panel.
Switch to another document All your local documents are listed in the document panel. You can switch from one to another by clicking a document in the li…

How to check if a linked list is cyclic or not

It is a regular interview question: given a one - direction linked list, how to check if there is a cycle inside the list or not.

As usual, you will receive a pointer to the head of the list, and you write a function to return a Boolean value which indicates there is a cycle inside the list or not.

The obvious way is creating another list / array to store all the elements of the list you visited, but in some cases it is not possible.

You can always use this approach, even in the case the node element has no data but a pointer to the next one. If so, you can just store the pointer (i.e, the address).

But of course it is not the intention of the interview. If the interviewer asked you to write an algorithm with time complexity is O(n) or space complexity is O(1), the above approach is not suitable.

There is a better algorithm: using two pointers, one fast and one slow. Slow pointer moves one element per iteration, while fast pointer moves two. If they meet, it means there is a cycle, a…

Finding a room of the princess

There is an interview question as following:

There are 17 rooms line up from 1 to 17. There is a princess who start at a room, then every night she will move to the room next to the previous one (i.e, she has to move to the left or right room - she cannot say at the same room).

You are a beast who has to find the princess to be back a prince. Every night, you can open one and only one room to check if the princess is inside or not. You have 30 nights to find the princess, otherwise ... boom!

Below is the number of the room the beast (or the future prince) should follow to check during 30 nights:

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

Explaining why it is a good strategy might be an interesting task for the reader.

I wrote a small application to simulate this strategy at: http://www.codeskulptor.org/#user38_wKWpYR0yZ3_2.py

Probably you cannot run the simulation online, but you can get the Python code and try in your computer.

What doors are closed?

There is an interesting interview question, which has been asked at many US companies.
There are 500 doors, initially closed. There are 500 people, one by one goes through all the doors.
The 1st person change the status of all the doors (i.e, open all of them). The 2nd person change the status of all the doors with number can divide to 2 (i.e, he will change the status of doors number 2, 4, 6, 8, 10, ... 500) The 3rd person change the status of doors 3, 6, 9, ... ... The 500th person change the status of the door 500
Change the status means: close the opening door, and open the closing door.
The question is: in the end, how many doors are close?
You can solve this problem by using mathematics, but it may be faster to simulate it.
You can check my simulation at: http://www.codeskulptor.org/#user38_rrZv4nVRno_1.py and easy to see, the opening doors are the doors with the number are square number.

Monty Hall problem: simulation with Python

You probably know about Monty Hall paradox. If not, you can read more about it at: http://en.wikipedia.org/wiki/Monty_Hall_problem

But if you do not feel happy with some probability calculation, you may want to see should we really change the door.

I wrote a small Python application to simulate Monty Hall problem.

You can access the program at:

http://www.codeskulptor.org/#user38_hxSeBAZW5H_1.py

You can see, after running 100 000 times, the change to win if you switch the door is approximately 2/3:


So now you can trust probability calculation.

Getting started with Cryptpad in Ubuntu: step by step

Cryptpad is an open source collaborative editor which is hosted at: https://github.com/cjdelisle/cryptpad

It is easy to clone the github repository and start to try, but if you are a newbie, there maybe some difficulties.

Suppose that you have a clean Ubuntu machine, and want to try with Cryptpad, you can follow these steps:

1. Download mongodb for Linux:

https://www.mongodb.org/downloads

2. Unzip the file you got to a location you want. You will start mongodb from there, or add this directory to your PATH variable so you can start mongodb from anywhere.

3. Suppose that you chose the easier way, i.e start mongodb from its directory.

4. Open Terminal (Ctrl + Alt + T for shortcut), move to the directory of mongodb

5. Type:
mkdir db
mongod --dbpath=./db

These above commands will first, create a directory 'db' insider the directory mongodb, then start mongodb server.

6. Keep the terminal with mongodb server running

7. Open another terminal (Ctrl + Shift + T to open a new tab, lik…

How to install NodeJS in Ubuntu

NodeJS provided installation file for MS Windows and Mac OS, but maybe you will not find a similar package for Ubuntu.

There are some instructions on the Internet which guide you installed NodeJS by using default repository of Ubuntu, or add more PPA, but probably you will receive an older version of NodeJS. (For instance, today I tried the instruction as: https://www.digitalocean.com/community/tutorials/how-to-install-node-js-on-an-ubuntu-14-04-server but I only got NodeJS 0.10.25, when the latest one is 0.10.33)

Actually, installing NodeJS in Ubuntu is very easy, maybe easiest among other operating systems.

1. Go to:

http://nodejs.org/download/

2. Depends on your operating system, download Linux Binaries file 32 - or 64 - bit.

3. Unzip the file you downloaded

tar xzvf node-v0.10.33-darwin-x64.tar.gz

4. Modify the file ~/.bashrc by adding the following line to the end of the file:

export PATH=$PATH:/path/to/bin/directory/of/node/you/downloaded

5. Restart terminal, or reload the bash…

How to auto indent in vim

For many years, vim still be one of the most common editor for developers.

There are (too) many shortcuts and commands for vim to remember, so sometimes it is quite difficult.

For auto indent, one feature I feel very important, especially when you copied the code from somewhere:

1G=G

1G: move to the first line
=: auto indent
G: go to end of file