Archive

Tag Archives: space

Snapsack problem refers to the situation you want to find a combination of items that can fill up a container. Each items should be attached with a value, and there should be a target value that means a container is filled up. For example, a container has 25 spaces and there are items that will take 1, 5, 7, 6, 4 or 10 spaces. You have to find all the combinations that fit the container.

Question

Given a integers m and n, generate all combination within 1 to n that would give the sum m. For example, for m=5 and n=5, the combinations are {5}, {4+1}, {3+2}.

Solution

This is a knapsack problem.

# knapsack that store the found combination
knapsack = array

# find combination of 1..n with sum target
find_combination(target, n)
    if target <= 0 or n <= 0 then return
    if target == n then found()

    # put n to knapsack, find combination involves n
    push n to knapsack
    remain = target - n
    find_combination(remain, n-1)

    # remove n from knapsack, find combination involves n-1
    pop knapsack
    find combination(target, n-1)

Sample

# knapsack that store the found combination
knapsack = []

# what to do with found combination in knapsack
def found(n):
    for number in knapsack: print "%d +" % number,
    print n

# find combination
def find_combination(target, n):
    if n <= 0 or target <= 0: return
    if n == target: found(n)

    # find combinations with n
    knapsack.append(n)
    find_combination(target - n, n - 1)

    # find combinations without n
    knapsack.pop()
    find_combination(target, n - 1)

# find combination of 25 with 1..20
find_combination(25, 20)
#include <iostream>
#include <list>
using namespace std;

list<int> knapsack;

void found(int n)
{
	// reverse print
	for (list<int>::const_iterator item = knapsack.begin(); item != knapsack.end(); item++)
		printf("%d + ", *item);
	printf("%dn", n);
}

void find_combination(int target, int n)
{
	if (n <= 0 || target <= 0) return;
	if (n == target) found(n);
	knapsack.push_back(n);
	find_combination(target - n, n - 1);
	knapsack.pop_back();
	find_combination(target, n - 1);
}

int main()
{
	find_combination(25, 20);
}
import java.util.Stack;

public class InterviewPractice21
{
	private static Stack<Integer> snapsack = new Stack<Integer>();

	private static void found(int n)
	{
		for (int item : snapsack) System.out.printf("%d + ", item);
		System.out.printf("%dn", n);
	}

	private static void find_combination(int target, int n)
	{
		if (target <= 0 || n <= 0) return;
		if (n == target) found(n);
		snapsack.push(n);
		find_combination(target - n, n - 1);
		snapsack.pop();
		find_combination(target, n - 1);
	}

	public static void main(String[] args)
	{
		find_combination(25, 20);
	}
}

Question

Simple task, reverse words in a sentence.

Solution

In Python, this can be simple because of the build-in functions. We can just split the sentence by spaces, reverse the list, and join them with spaces again.

In C++, this can be complicated. The following might be one of the possible answers. We have to scan from the head to tail, and find the position that a word starts and ends. Then reverse the letters in this word. At the end, reverse all the letters in the whole sentence.

Examples

# function to reverse a sentence
def reverse_sentence(sentence):
    return ' '.join(reversed(sentence.split()))

# main
print reverse_sentence("I am a student.")
print reverse_sentence("Testing 1 2 3")
#include <iostream>

using namespace std;

// function to reverse a word, in place
void reverse_word(string* word, int begin, int end)
{
	while (begin < end) {
		char letter = word->at(begin);
		word->at(begin) = word->at(end);
		word->at(end) = letter;
		begin++;
		end--;
	}
}

// function to reverse a sentence, in place
void reverse_sentence(string* sentence)
{
	int length = sentence->size();
	int pointer = 0;
	// for each character
	for (int i = 0; i < sentence->size(); i++) {
		// find word head
		if (pointer == -1) {
			if (sentence->at(i) != ' ') pointer = i;
			continue;
		}
		// find word tail
		if (sentence->at(i) == ' ') {
			reverse_word(sentence, pointer, i - 1);
			pointer = -1;
		}
		// end of string
		if (i == length - 1) {
			reverse_word(sentence, pointer, i - 1);
		}
	}
	// reverse letters for the whole sentence
	reverse_word(sentence, 0, sentence->size() - 1);
}

// main part
int main()
{
	string text = "I am a student.";
	reverse_sentence(&text);
	cout << text << endl;
}
public class InterviewPractice10
{
	private static String reverse_sentence(String sentence)
	{
		String[] splited = sentence.split(" ");
		StringBuilder builder = new StringBuilder();
		for (int i = splited.length - 1; i >= 0; i--) {
			builder.append(splited[i]);
			if (i > 0) builder.append(" ");
		}
		return builder.toString();
	}

	public static void main(String[] args)
	{
		System.out.println(reverse_sentence("I am a student."));
		System.out.println(reverse_sentence("Testing 1 2 3"));
	}
}

Question

腾讯面试题:
给你10分钟时间,根据上排给出十个数,在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下:
【0,1,2,3,4,5,6,7,8,9】

Solution

初看此题,貌似很难,10分钟过去了,可能有的人,题目都还没看懂。

举一个例子,
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0在下排出现了6次,1在下排出现了2次,
2在下排出现了1次,3在下排出现了0次….
以此类推..

Sample Code

[expand title=”Sample Code in C++” tag=”h4″]

//数值: 0,1,2,3,4,5,6,7,8,9
//分配: 6,2,1,0,0,0,1,0,0,0

#include <iostream>

using namespace std;

#define len 10

class NumberTB
{
private:
    int top[len];
    int bottom[len];
    bool success;
public:
    NumberTB();
    int* getBottom();
    void setNextBottom();
    int getFrequecy(int num);
};

NumberTB::NumberTB()
{
    success = false;
    //format top
    for(int i=0;i<len;i++)
    {
        top[i] = i;
    }
}

int* NumberTB::getBottom()
{
    int i = 0;
    while(!success)
    {
        i++;
        setNextBottom();
    }
    return bottom;
}

//set next bottom
void NumberTB::setNextBottom()
{
    bool reB = true;

    for(int i=0;i<len;i++)
    {
        int frequecy = getFrequecy(i);

        if(bottom[i] != frequecy)
        {
            bottom[i] = frequecy;
            reB = false;
        }
    }
    success = reB;
}

//get frequency in bottom
int NumberTB::getFrequecy(int num)   //此处的num即指上排的数 i
{
    int count = 0;

    for(int i=0;i<len;i++)
    {
        if(bottom[i] == num)
            count++;
    }
    return count;    //cout即对应 frequecy
}

int main()
{
    NumberTB nTB;
    int* result= nTB.getBottom();

    for(int i=0;i<len;i++)
    {
        cout<<*result++<<endl;
    }
    return 0;
}
///////////////////////////////////////////
// 运行结果:
// 6
// 2
// 1
// 0
// 0
// 0
// 1
// 0
// 0
// 0
// Press any key to continue
/////////////////////////////////////////

[/expand]

Question

输入n个整数,输出其中最小的k个。
例如输入1,2,3,4,5,6,7和8这8个数字,
则最小的4个数字为1,2,3和4。

Sample Code

[expand title=”Sample Code in C++” tag=”h4″]

#include <iostream>
using namespace std;

class MinK
{
private:
    int *array;
    int size;

    void shiftDown(int *ret,int pos,int length) {
        int t=ret[pos];
        for(int s=2*pos+1;s<=length;s=2*s+1) {
            if(s<length&&ret[s]<ret[s+1]) ++s;
            if(t<ret[s]) {
                ret[pos]=ret[s];
                pos=s;
            }
            else break;
        }
        ret[pos]=t;
    }

public:

    MinK(int *arr,int si):
        array(arr), size(si) {}

    bool kmin(int k,int*& ret)
    {
        if(k>size) {
            ret=NULL;
            return false;
        }
        else {
            ret=new int[k--];
            int i;
            for(i=0;i<=k;++i) ret[i] = array[i];
            for(int j=(k-1)/2;j>=0;--j) shiftDown(ret,j,k);
            for(;i<size;++i) {
            if(array[i]<ret[0]) {
                    ret[0]=array[i];
                    shiftDown(ret,0,k);
                }
            }
            return true;
        }
    }

    void remove(int*& ret){
        delete[] ret;
        ret=NULL;
    }
};

int main()
{
    int array[]={1,2,3,4,5,6,7,8};
    MinK mink(array,sizeof(array)/sizeof(array[0]));
    int *ret;
    int k=4;
    if(mink.kmin(k,ret)) {
        for(int i=0;i<k;++i)
            cout<<ret[i]<<endl;
        mink.remove(ret);
    }
    return 0;
}

[/expand]

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

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>

%d bloggers like this: