Archive

Tag Archives: instamusic

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;
    }
}

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>

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

Hi there, its been a long time that InstaMusic haven’t been updated. Sorry for that because I had been so busy in working on a game project in my company. Anyway, I am quitting for the sake of pursuing a master degree. And finally I have time to implement what I thought up and designed!

An new application “InstaMusic Beta Channel” will show up in Android Play Store soon. This application aims to provide a cutting-edge version of InstaMusic. This app could be unstable, lots of force closes, however this helps me kill bugs in the program. For those who only wants a stable music playback, please download the original “InstaMusic”.

As a new version is coming out, I have created a feature list presenting the main improvements done or working on.

  1. Stability
    InstaMusic has been unstable for a long time. Music stops suddenly without telling. After a deep diagnosis, the core reason leading this bug is found, and a fix is patched! Music never stops now!
  2. Loading Speed
    Media loading speed has been a big concern for me while generating the music list. Long loading time affects user experience and might hinder other operations. Anyway, I have designed a new architecture specially for the list generation. This assured an optimised, low memory usage, synchronised and dynamic list generation.
  3. Jelly Bean Support (Working in Progress) 
    There are lots of new features and supports from platforms beginning from Android 4.0 such as notification controls and new theme styles. I am working on making use of those new features and to create a whole new user experience for users!
  4. Editable Playlists integrating with Favourite List (Working in Progress)
    In the next version of InstaMusic, Favorite List will be integrated into Playlist. The reason is… actually there is no reason to separate them lol.

Thank you for your supporting so far. Please comment below and tell me what you think on InstaMusic!

Thank you for checking out this tutorial. Reading the discussions in this post, seems like there is quite a number of people having troubles to take screenshots with Galaxy S2. To clear any confusions, I summarized some information and added as followings. Hope you could make it too. Fingers crossed.

First, make sure your Galaxy S2 is running Android version 4 or above.

Volume Down + Power Key will work fine.
Press both keys at the same time gently. In about 1 second, screen capture would be done. A notification and an animation would be shown too.

Edited on 12 July.


Press and hold power and volume down button together. This is the way to take screenshot in the new Android system 4.0 Ice Cream Sandwich. After the Samsung Galaxy S2 updated to this new version, it uses this method instead of the way mentioned in my old post.

%d bloggers like this: