Archive

Tag Archives: nicholas workshop

it’s been a while since the last post. After coming to new york, I have been very busy on my study, personal projects and (of course) playing around. studying in new york university is harsh, but not as hard as i think. I met nice people, hanged out with my beloved new friends. I even found people having great interests in technologies and software development.

I am trying to work on instamusic as long as i have time. I also shared my project of javascript injector with my friend, and hoping to expand service and functions that it can have. I am grateful to see that there are still many people using my applications and sending emails to me. thank you very much and i will try my best to make something new.

with love, a photo in central park is nice.

peace.

DSC053452

Question

Define a stack structure with “min” function — a function to get the minimum value within the stack. The time complexity of min, push and pop functions must be O(1).

Solution

結合鍊錶一起做。首先我做插入以下數字: 10, 7, 3, 3, 8, 5, 2, 6

0: 10 -> NULL (MIN=10, POS=0)
1: 7  -> [0]  (MIN=7,  POS=1) // 用數組表示堆棧,第0個元素表示棧底
2: 3  -> [1]  (MIN=3,  POS=2)
3: 3  -> [2]  (MIN=3,  POS=3)
4: 8  -> NULL (MIN=3,  POS=3) // 技巧在這裡,因為8比當前的MIN大,所以彈出8不會影響當前的MIN
5: 5  -> NULL (MIN=3,  POS=3)
6: 2  -> [2]  (MIN=2,  POS=6) // 如果2出棧了,那麼3就是MIN
7: 6  -> [6]

出棧的話採用類似方法修正。

所以,藉助輔助棧,保存最小值,且隨時更新輔助棧中的元素。push第一個元素進A,也把它push進B,當向Apush的元素比B中的元素小, 則也push進B,即更新B。否則,不動B,保存原值。向棧A push元素時,順序由下至上。輔助棧B中,始終保存著最小的元素。

然後,當pop A中的元素小於B中棧頂元素時,則也要pop B中棧頂元素。

Samples

The following is an optimized implementation.  Repeated minimum value will not be stored through comparing values while pushing or popping values.

#include <vector>
#include <cassert>

using namespace std;

/**
 * Class defining a new type of stack supporting any datatype.
 */
template <typename T>
class StackWithMin
{
private:
    vector<T> dataStack; // stacks to store data
    vector<size_t> minStack; // stack to store position of minimum value

public:

    /**
     * Push data to the stack at the same time update the minimum stack if the
     * new data is smaller then the current minimum value. Throw exception if
     *  stack is empty.
     */
    void push(T data) {
        dataStack.push_back(data);
        if (minStack.empty() || data < dataStack[minStack.back()])
            minStack.push_back(dataStack.size()-1);
    }

    /**
     * Pop data to the stack at the same time pop from the min stack if it is
     * popping the minimum value. Throw exception if stack is empty.
     */
    void pop() {
        assert(!dataStack.empty());
        if (dataStack.back() == dataStack[minStack.back()])
            minStack.pop_back();
        dataStack.pop_back();
    }

    /**
     * return the current minimum value.
     */
    T min() {
        assert(!dataStack.empty() && !minStack.empty());
        return dataStack[minStack.back()];
    }
};

/**
 * Main program
 */
int main()
{
    StackWithMin<int> stack = StackWithMin<int>();
    stack.push(10);
    stack.push(7);
    stack.push(3);
    stack.push(3);
    stack.push(8);
    stack.push(5);
    stack.push(2);
    stack.push(6);
    printf("Minimum value: %dn", stack.min());
}
import java.util.Stack;

public class Pactice02 {

    public static void main(String[] args) {
        System.out.println("Hello World!");
        AdvancedStack stack = new AdvancedStack();
        stack.push(10);
        stack.push(7);
        stack.push(3);
        stack.push(3);
        stack.push(8);
        stack.push(5);
        stack.push(2);
        stack.push(6);
        System.out.println("Minimum value: "+ stack.getMinimum());
        stack.pop();
        System.out.println("Minimum value: "+ stack.getMinimum());
        stack.pop();
        System.out.println("Minimum value: "+ stack.getMinimum());
        stack.pop();
        System.out.println("Minimum value: "+ stack.getMinimum());
    }

    public static class AdvancedStack extends Stack {

        private Stack mMinimumStack = new Stack();

        @Override
        public E push(E item) {
            if (mMinimumStack.empty() || item.doubleValue()  0) {
                return mMinimumStack.peek();
            }
            return null;
        }
    }
}

Questiontree

Convert binary search tree into doubly linked list. It’s required not to create any new node, but only turning pointers.

Solution

The following shows the concept of this question.

        8
      /   
    6       0       ->     5 = 6 = 7 = 8 = 9 = 0 = 1
   /      / 
  5   7   9    1

First, since node for both binary tree and doubly linked list have left and right node, they can use the same node structure. Then, looking the doubly linked list as a normal linked list, it is actually a in-order depth-first traversal result.

Sample Codes

 

# node structure
class Node:
    value = None
    left = None
    right = None

    # constructor
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# what to do with a node.
def visit(node):
    global node_temp
    global node_root
    if not node_temp: node_root = node  # head
    else: node_temp.right = node  # make right of temp to this
    node.left = node_temp  # make temp to this left
    node_temp = node  # next node

# bfs traversal
def depth_first_recursive_traversal_in_order(node):
    if node is None: return
    depth_first_recursive_traversal_in_order(node.left)
    visit(node)
    depth_first_recursive_traversal_in_order(node.right)

# a binary tree and display how was it before reflection
node_5 = Node(5)
node_7 = Node(7)
node_9 = Node(9)
node_1 = Node(1)
node_6 = Node(6, node_5, node_7)
node_0 = Node(0, node_9, node_1)
node_8 = Node(8, node_6, node_0)

# conversion
node_root = node_8
node_temp = None
depth_first_recursive_traversal_in_order(node_root)

# answer should be: 5 6 7 8 9 0 1
node_temp = node_root
while node_temp:
    print node_temp.value,
    node_temp = node_temp.right
public class InterviewPractice1
{
    // global
    static Node node_root = null;
    static Node node_temp = null;

    // node structure
    private static class Node
    {
        private int value;
        private Node left;
        private Node right;

        public Node(int value, Node left, Node right)
        {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    // visit
    private static void visit(Node node)
    {
        if (node_temp == null) node_root = node; // set head
        else node_temp.right = node; // make right of temp to this node
        node.left = node_temp; // make temp to the left of this node
        node_temp = node; // next node

    }

    // depth first, recursive
    private static void depth_first_recursive_traversal_in_order(Node node)
    {
        if (node == null) return;
        depth_first_recursive_traversal_in_order(node.left);
        visit(node);
        depth_first_recursive_traversal_in_order(node.right);
    }

    // main
    public static void main(String[] args)
    {
        // tree
        Node node_5 = new Node(5, null, null);
        Node node_7 = new Node(7, null, null);
        Node node_9 = new Node(9, null, null);
        Node node_1 = new Node(1, null, null);
        Node node_6 = new Node(6, node_5, node_7);
        Node node_0 = new Node(0, node_9, node_1);
        Node node_8 = new Node(8, node_6, node_0);

        // run
        node_root = node_8;
        depth_first_recursive_traversal_in_order(node_root);

        // the result should be 5 6 7 8 9 0 1
        node_temp = node_root;
        while (node_temp != null) {
            System.out.print(node_temp.value + " ");
            node_temp = node_temp.right;
        }
    }
}
#include <iostream>

struct Node
{
    int value;
    Node *left;
    Node *right;

    Node(int value, Node *left = NULL, Node *right = NULL)
    {
        this->value = value;
        this->left = left;
        this->right = right;
    }
};

Node *node_root = NULL;
Node *node_temp = NULL;

void visit(Node *node)
{
    if (node_temp == NULL) node_root = node;  // set head
    else node_temp->right = node;  // make right of them to this node
    node->left = node_temp;  // make temp to the left of this node
    node_temp = node;  // next node
}

void depth_first_recursive_traversal_in_order(Node *node)
{
    if (!node) return;
    depth_first_recursive_traversal_in_order(node->left);
    visit(node);
    depth_first_recursive_traversal_in_order(node->right);
}

int main()
{
    // tree
    Node *node_5 = new Node(5);
    Node *node_7 = new Node(7);
    Node *node_9 = new Node(9);
    Node *node_1 = new Node(1);
    Node *node_6 = new Node(6, node_5, node_7);
    Node *node_0 = new Node(0, node_9, node_1);
    Node *node_8 = new Node(8, node_6, node_0);

    // conversion
    node_root = node_8;
    node_temp = NULL; // null
    depth_first_recursive_traversal_in_order(node_8);

    // answer should be: 5 6 7 8 9 0 1
    node_temp = node_root;
    while (node_temp) {
        printf("%d ", node_temp->value);
        node_temp = node_temp->right;
    }
}

shot

What’s happening

One day, when I opened up terminal as usual, it showed [Process completed] and just terminated. I could not type any thing, run any scripts and work on my project. Even worse, this made me unable to install programs into my computer because many installations need to run shell scripts. Okay, I searched over the internet and there was no solution for that. I even peaked many parts in the Mac OSX system to see if there were any mis-configuration, of course nothing helps. After all, I though if there is nothing wrong, it must be  something done with my /bin/bash. And after I upgraded my bash, my lovely terminal came back!

[expand title=”Let’s fix it” tag=”h5″ trigclass=”arrowright”]

Change shell’s default execution

The truth is, when you open terminal, it execute /bin/bash. As it is not working now, we need another environment for us to execute stuff. Open “Terminal->Preference”, and change “Shells open with” manually to “/bin/sh”.

Change What Shell Opens

Update /bin/bash

Now we are going to download the latest version of bash and replace the old one. Open up a new terminal and now you are able to execute commands. Copy and paste the following codes into the terminal, they will automatically handle everything for you.

	curl -LO ftp://ftp.cwru.edu/pub/bash/bash-4.2.tar.gz
	tar zxvf bash-4.2.tar.gz
	cd bash-4.2
	./configure &amp;&amp; make &amp;&amp; sudo make install
	chsh -s /usr/local/bin/bash {user_name}
	sudo bash -c &quot;echo /usr/local/bin/bash &gt;&gt; /private/etc/shells&quot;
	cd /bin
	sudo mv bash bash-old
	sudo ln -s /usr/local/bin/bash bash
	
Once done

Go to “Terminal->Preference” again and change :Shells open with: back to “Default login shell”. Enjoy!

[/expand]

[expand title=”Detailed explanations” tag=”h5″ trigclass=”arrowright”]

What I did?

Okay, I admit that I did something to the system sometimes ago. I was doing some experiments on “sandboxing” and played with “chroot jail” stuff before. That is, I need to create an environment with restricted support to the program I run. So I wrote a sandbox, configured it’s root to a ‘secure’ place (anywhere not the actual root), and copy essential executables to that new root. Well, so far I think I didn’t do anything harm to the system, but I might corrupt the /bin/bash when I copied it to the sandbox root.

Diagnosis

Shell will run the following files before letting user to do anything. Check everyone to see if there are any misconfigurations.

  • ~/.bash_profile (for /bin/bash)
  • ~/.profile (for /bin/sh)
  • /etc/profile (for /bin/sh)
  • /etc/bashrc (for /bin/bash)
  • (google for more)

To play with, add some echoes to see if they works. Btw, I love nano more than vi, so try out “sudo nano /etc/bashrc”.

Playing with Shell
Another thing

The code above updates your bash to version 4.2. To check if there is any new version, go to the ftp.
ftp://ftp.cwru.edu/pub/bash/

Reference

http://techscienceinterest.blogspot.com/2010/05/change-to-new-bash-shell-41-for-mac-os.html


[/expand]

For both server and website developing, I usually use Xampp’s Apache to create a localhost server. However, I hate to put my important files in the htdocs inside Apache. Instead I would rather put the folder inside Documents, and make a link to htdocs.

First, create a symbolic link from your actual folder to htdocs. For example, ln -s /Users/Nicholas/Documents/Xampp Workspace /Applications/Xampp/xamppfiles/htdocs/nicholas.

<Image Pending>

However, this is not done because the owner of your directory is Nicholas, but not “nobody”. Also, we cannot change the folder’s owner to nobody as this is actually an illegal owner. So what we gonna do is add Nicholas as the user in Apache. [Caution: This can actually create a security issue on your computer, since now the Xampp can access files of the user Nicholas]
<Image Pending>

To do that, add “user Nicholas” to the end /Applications/Xampp/xamppfiles/etc/httpd.conf. Then restart Xampp.
<Image Pending>

Actually, this website was my portfolio webpage before becoming a wordpress. It is moved to here: nicholasworkshop.com/portfolio. Using wordpress, I put the old webpage aside and always forgot to transfer the information from it to the front page. Anyway, I hope this can remind me of the projects and webpages I created.

To capture screen in BlackBerry PlayBook, just hold the volume Up and Down buttons together. After a camera shutter sound, a screen image in the format JPG will be saved in Pictures Camera folder.

blackberry-playbook

%d bloggers like this: