Archive

Tag Archives: name

1. Open a terminal window.

2. At the input prompt you will see this structure:
“`
nicholas@computer-name:~$ _
“`

3. So you have to edit the hostname file:
“`
sudo nano /etc/hostname
“`

4. When prompted, enter the administrator password and hit Enter.

5. The hostname file will open, showing the current computer name. Replace the name with the desired new name.

6. Hit Ctrl+X to save and exit.

7. New name will show when you open a new terminal window.

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

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]

%d bloggers like this: