Archive

Tag Archives: code

Unable to install Homebrew with this?

ruby -e "$(curl -fsSL https://raw.github.com/Homebrew/homebrew/go/install)"

What’s happened

-e:70: warning: Insecure world writable dir /usr/local/bin in PATH, mode 040777
==> This script will install:
/usr/local/bin/brew
/usr/local/Library/...
/usr/local/share/man/man1/brew.1

Press RETURN to continue or any other key to abort
==> /usr/bin/sudo /bin/chmod g+rwx /Library/Caches/Homebrew
Password:
==> Downloading and installing Homebrew...
remote: Counting objects: 192274, done.
remote: Compressing objects: 100% (52298/52298), done.
remote: Total 192274 (delta 138823), reused 192246 (delta 138803)
Receiving objects: 100% (192274/192274), 38.59 MiB | 189 KiB/s, done.
Resolving deltas: 100% (138823/138823), done.
From https://github.com/Homebrew/homebrew
 * [new branch]      master     -> origin/master
error: unable to unlink old 'Library/Aliases/0mq' (Permission denied)
error: unable to unlink old 'Library/Aliases/4store' (Permission denied)
error: unable to unlink old 'Library/Aliases/Secret Rabbit Code' (Permission denied)
error: unable to unlink old 'Library/Aliases/ag' (Permission denied)
error: unable to unlink old 'Library/Aliases/alut' (Permission denied)
error: unable to unlink old 'Library/Aliases/android' (Permission denied)
error: unable to unlink old 'Library/Aliases/apache-activemq' (Permission denied)
error: unable to unlink old 'Library/Aliases/apache-fop' (Permission denied)
error: unable to unlink old 'Library/Aliases/aws-as' (Permission denied)
error: unable to unlink old 'Library/Aliases/aws-mon' (Permission denied)
error: unable to unlink old 'Library/Aliases/beanstalkd' (Permission denied)
error: unable to unlink old 'Library/Aliases/bjam' (Permission denied)
error: unable to unlink old 'Library/Aliases/boehmgc' (Permission denied)
error: unable to unlink old 'Library/Aliases/boost-jam' (Permission denied)
error: unable to create symlink Library/Aliases/boot2docker-cli (Permission denied)
error: unable to unlink old 'Library/Aliases/bzr' (Permission denied)
error: unable to unlink old 'Library/Aliases/cowthink' (Permission denied)
error: unable to unlink old 'Library/Aliases/cpanm' (Permission denied)
error: unable to unlink old 'Library/Aliases/csvfix' (Permission denied)
error: unable to unlink old 'Library/Aliases/ctags-exuberant' (Permission denied)
error: unable to unlink old 'Library/Aliases/db' (Permission denied)
error: unable to unlink old 'Library/Aliases/dbus' (Permission denied)
error: unable to unlink old 'Library/Aliases/dejagnu' (Permission denied)
error: unable to unlink old 'Library/Aliases/eyeD3' (Permission denied)
error: unable to unlink old 'Library/Aliases/fastcgi' (Permission denied)
error: unable to unlink old 'Library/Aliases/fishfish' (Permission denied)
error: unable to unlink old 'Library/Aliases/fluidsynth' (Permission denied)
error: unable to unlink old 'Library/Aliases/gearmand' (Permission denied)
error: unable to unlink old 'Library/Aliases/git-tig' (Permission denied)
error: unable to unlink old 'Library/Aliases/gnu-scientific-library' (Permission denied)
error: unable to unlink old 'Library/Aliases/google-go' (Permission denied)
error: unable to unlink old 'Library/Aliases/gperftools' (Permission denied)
error: unable to unlink old 'Library/Aliases/gpg' (Permission denied)
error: unable to unlink old 'Library/Aliases/gpg2' (Permission denied)
error: unable to unlink old 'Library/Aliases/gs' (Permission denied)
error: unable to unlink old 'Library/Aliases/gtk' (Permission denied)
error: unable to unlink old 'Library/Aliases/gtypist' (Permission denied)
error: unable to unlink old 'Library/Aliases/hashdeep' (Permission denied)
error: unable to unlink old 'Library/Aliases/heroku' (Permission denied)
error: unable to unlink old 'Library/Aliases/hg' (Permission denied)
error: unable to unlink old 'Library/Aliases/htop' (Permission denied)
error: unable to unlink old 'Library/Aliases/hudson' (Permission denied)
error: unable to unlink old 'Library/Aliases/ipsum' (Permission denied)
error: unable to unlink old 'Library/Aliases/jocr' (Permission denied)
error: unable to unlink old 'Library/Aliases/lcms' (Permission denied)
error: unable to unlink old 'Library/Aliases/lcms2' (Permission denied)
error: unable to unlink old 'Library/Aliases/leg' (Permission denied)
error: unable to unlink old 'Library/Aliases/libcryptopp' (Permission denied)
error: unable to unlink old 'Library/Aliases/libgd' (Permission denied)
error: unable to unlink old 'Library/Aliases/libgeoip' (Permission denied)
error: unable to unlink old 'Library/Aliases/libjpeg' (Permission denied)
error: unable to unlink old 'Library/Aliases/libjpeg-turbo' (Permission denied)
error: unable to unlink old 'Library/Aliases/libjpg' (Permission denied)
error: unable to unlink old 'Library/Aliases/liblabjackusb' (Permission denied)
error: unable to unlink old 'Library/Aliases/libmad' (Permission denied)
error: unable to unlink old 'Library/Aliases/libmcrypt' (Permission denied)
error: unable to unlink old 'Library/Aliases/libnettle' (Permission denied)
error: unable to unlink old 'Library/Aliases/liboggz' (Permission denied)
error: unable to unlink old 'Library/Aliases/libqrencode' (Permission denied)
error: unable to unlink old 'Library/Aliases/libtag' (Permission denied)
error: unable to unlink old 'Library/Aliases/libtasn' (Permission denied)
error: unable to unlink old 'Library/Aliases/libtcnative' (Permission denied)
error: unable to unlink old 'Library/Aliases/littlecms' (Permission denied)
error: unable to unlink old 'Library/Aliases/mc' (Permission denied)
error: unable to unlink old 'Library/Aliases/mediainfo' (Permission denied)
error: unable to unlink old 'Library/Aliases/mongo' (Permission denied)
error: unable to unlink old 'Library/Aliases/mosh' (Permission denied)
error: unable to unlink old 'Library/Aliases/mp4box' (Permission denied)
error: unable to unlink old 'Library/Aliases/mpich' (Permission denied)
error: unable to unlink old 'Library/Aliases/myrepos' (Permission denied)
error: unable to unlink old 'Library/Aliases/node.js' (Permission denied)
error: unable to unlink old 'Library/Aliases/nodejs' (Permission denied)
error: unable to unlink old 'Library/Aliases/npm' (Permission denied)
error: unable to unlink old 'Library/Aliases/nsis' (Permission denied)
error: unable to unlink old 'Library/Aliases/o-caml' (Permission denied)
error: unable to unlink old 'Library/Aliases/ocaml' (Permission denied)
error: unable to unlink old 'Library/Aliases/ocio' (Permission denied)
error: unable to unlink old 'Library/Aliases/offlineimap' (Permission denied)
error: unable to unlink old 'Library/Aliases/ooc' (Permission denied)
error: unable to unlink old 'Library/Aliases/openmpi' (Permission denied)
error: unable to unlink old 'Library/Aliases/openocd' (Permission denied)
error: unable to unlink old 'Library/Aliases/pgrep' (Permission denied)
error: unable to unlink old 'Library/Aliases/pipeviewer' (Permission denied)
error: unable to unlink old 'Library/Aliases/pkgconfig' (Permission denied)
error: unable to unlink old 'Library/Aliases/pkill' (Permission denied)
error: unable to unlink old 'Library/Aliases/pocketsphinx' (Permission denied)
error: unable to unlink old 'Library/Aliases/postgres' (Permission denied)
error: unable to create symlink Library/Aliases/pt (Permission denied)
error: unable to unlink old 'Library/Aliases/qt4' (Permission denied)
error: unable to unlink old 'Library/Aliases/shell-fm' (Permission denied)
error: unable to unlink old 'Library/Aliases/slang' (Permission denied)
error: unable to unlink old 'Library/Aliases/sphinxbase' (Permission denied)
error: unable to unlink old 'Library/Aliases/sqlite3' (Permission denied)
error: unable to unlink old 'Library/Aliases/stax-sdk' (Permission denied)
error: unable to unlink old 'Library/Aliases/style' (Permission denied)
error: unable to unlink old 'Library/Aliases/svn' (Permission denied)
error: unable to unlink old 'Library/Aliases/tinyfugue' (Permission denied)
error: unable to create symlink Library/Aliases/twemproxy (Permission denied)
error: unable to unlink old 'Library/Aliases/twolame' (Permission denied)
error: unable to unlink old 'Library/Aliases/unix2dos' (Permission denied)
error: unable to unlink old 'Library/Aliases/urxvt' (Permission denied)
error: unable to unlink old 'Library/Aliases/usb-multiplex-daemon' (Permission denied)
error: unable to create symlink Library/Aliases/vid.stab (Permission denied)
error: unable to unlink old 'Library/Aliases/wxwidgets' (Permission denied)
error: unable to unlink old 'Library/Aliases/xmlsec1' (Permission denied)
error: unable to unlink old 'Library/Aliases/zmq' (Permission denied)
error: unable to unlink old 'Library/Contributions/brew_bash_completion.sh' (Permission denied)
error: unable to unlink old 'Library/Contributions/brew_fish_completion.fish' (Permission denied)
error: unable to unlink old 'Library/Contributions/brew_zsh_completion.zsh' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-aspell-dictionaries.rb' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-beer.rb' (Permission denied)
error: unable to create file Library/Contributions/cmd/brew-bundle-dir.rb (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-bundle.rb' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-cleanup-installed' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-gist-logs.rb' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-graph' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-man' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-profile.rb' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-pull.rb' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-server' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-services.rb' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-switch.rb' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-tap-readme.rb' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-test-bot.rb' (Permission denied)
error: unable to create file Library/Contributions/cmd/brew-versions.rb (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/brew-which.rb' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/git' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/public/bootstrap.min.css' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/public/glyphicons-halflings-white.png' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/public/glyphicons-halflings.png' (Permission denied)
error: unable to unlink old 'Library/Contributions/cmd/svn' (Permission denied)
error: unable to unlink old 'Library/Contributions/example-formula.rb' (Permission denied)
error: unable to unlink old 'Library/Contributions/manpages/brew.1.md' (Permission denied)
error: unable to unlink old 'Library/ENV/3.2.6' (Permission denied)
error: unable to unlink old 'Library/ENV/4.2' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/ant' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/apr-1-config' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/bsdmake' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/c++' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/c89' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/c99' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/cc' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/clang' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/clang++' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/cpp' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/g++' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/g++-4.2' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/g++-4.3' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/g++-4.4' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/g++-4.5' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/g++-4.6' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/g++-4.7' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/g++-4.8' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/g++-4.9' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/gcc' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/gcc-4.2' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/gcc-4.3' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/gcc-4.4' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/gcc-4.5' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/gcc-4.6' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/gcc-4.7' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/gcc-4.8' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/gcc-4.9' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/git' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/gmake' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/i686-apple-darwin11-llvm-g++-4.2' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/i686-apple-darwin11-llvm-gcc-4.2' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/ld' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/llvm-g++' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/llvm-g++-4.2' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/llvm-gcc' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/llvm-gcc-4.2' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/make' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/mig' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/pod2man' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/sed' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/svn' (Permission denied)
error: unable to unlink old 'Library/ENV/4.3/xcrun' (Permission denied)
fatal: cannot create directory at 'Library/ENV/pkgconfig/10.10': Permission denied
Failed during: git reset --hard origin/master

Reason

Probably you have multiple users on your computer. And you uninstalled the old Homebrew and trying to re-install it.

Solution

Theorotically you can remove the directory /usr/local/Library but this will happens again when you try to use Homebrew with another user. It is better to change the permission of directory with this:

sudo chmod -R 775 /usr/local/Library

and after a successful install, you better fix the permission for another directory. This directory may appear after you run some ruby commands.

sudo chmod -R 775 /usr/local/Cellar

 

Question

Design an algorithm to verify that a tree is a universal value binary tree. Universal value binary tree means all value in that tree is the same.

Solution

There is two approach for this problem. One is with recursive function and another is with iterative function. For this problem, iterative function makes simpler answer. However, we have to learn using recursive function because in production code recursive function uses memory more efficiently while compared to iterative function.

Sample

# 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

# iterative way to solve this problem
def iteratively_verify_universal_value_binary_tree(root):
    stack = [root]
    while len(stack) > 0:
        node = stack.pop()
        if node.value != root.value: return False
        if node.left: stack.append(node.left)
        if node.right: stack.append(node.right)
    return True

# recursive method to solve this problem
def recursively_verify_universal_value_binary_tree(node, root_value=None):
    if not node: return True
    if not root_value: root_value = node.value  # set root value to compared with
    left_is_universal = recursively_verify_universal_value_binary_tree(node.left, root_value)  # get left result
    right_is_universal = recursively_verify_universal_value_binary_tree(node.right, root_value)  # get right result
    this_is_universal = node.value == root_value  # get this result
    return left_is_universal and right_is_universal and this_is_universal  # combine result

# trees
universal_value_tree = Node(1, Node(1, Node(1), Node(1)), Node(1, Node(1), Node(1)))
non_universal_value_tree = Node(1, Node(1, Node(1), Node(2)), Node(1, Node(1), Node(1)))

# testing
print iteratively_verify_universal_value_binary_tree(universal_value_tree)  # true
print iteratively_verify_universal_value_binary_tree(non_universal_value_tree)  # false
print recursively_verify_universal_value_binary_tree(universal_value_tree)  # true
print recursively_verify_universal_value_binary_tree(non_universal_value_tree)  # false

 

Question

This is an actual question I encountered in an Amazon phone interview in November 2013. You are going to design the money changing algorithm for a vending machine. That is, after any purchase, the machine makes change to users with a combination of coins. And the machine only have 3 types of coins: nickel (5 cents), dime (10 cents) and quarter (25 cents). Coins with higher values are preferred in the change.

Solution

Well this is actually a simple question, I could just fill the sum from the highest value coin to the lowest. However I chose to use a simplified version of knapsack algorithm. Whatever, they both works.

Sample

# coin values
coins = [25, 10, 5]

# simple solution for this problem
def simple_solution(sum):
    combination = []
    for coin in coins:
        for i in xrange(sum / coin): combination.append(coin)
        sum %= coin
    return combination

# result: [25, 25, 10, 5]
print simple_solution(65)

 

9

Question

Construct an algorithm to verify if a set of numbers is the post-order search result of a binary search tree. Let the figure at the right hand side as an example, the algorithm will return true if {5, 7, 6, 9, 11, 10, 8}. However, it will return false if the input is {7, 4, 6, 5}.

Solution

Actually, a post-order search of the whole tree would do the job. First, perform a depth-first search from the leftmost leave, and push each element into a stack.

Reference

Wikipedia

Pseudocode

postorder(node)
    if node == null then return
    postorder(node.left)
    postorder(node.right)
    visit(node)

Samples

class bst_node:
    value = None
    left = None
    right = None
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def postorder(node, test_seq):
    if node is None: return True
    if not postorder(node.left, test_seq): return False
    if not postorder(node.right, test_seq): return False
    return visit(node, test_seq)

def visit(node, test_seq):
    front = test_seq.pop(0) # front item
    return front == node.value

node_5 = bst_node(5)
node_7 = bst_node(7)
node_9 = bst_node(9)
node_11 = bst_node(11)
node_6 = bst_node(6, node_5, node_7)
node_10 = bst_node(10, node_9, node_11)
node_8 = bst_node(8, node_6, node_10)
root = node_8

test_seq_1 = [5, 7, 6, 9, 11, 10, 8]
test_seq_2 = [7, 4, 6, 5]

print postorder(root, test_seq_1)
print postorder(root, test_seq_2)
bool verifySquenceOfBST(int squence[], int length)
{
      if(squence == NULL || length <= 0)
            return false;

      // root of a BST is at the end of post order traversal squence
      int root = squence[length - 1];

      // the nodes in left sub-tree are less than the root
      int i = 0;
      for(; i < length - 1; ++ i)
      {
            if(squence[i] > root)
                  break;
      }

      // the nodes in the right sub-tree are greater than the root
      int j = i;
      for(; j < length - 1; ++ j)
      {
            if(squence[j] < root)
                  return false;
      }

      // verify whether the left sub-tree is a BST
      bool left = true;
      if(i > 0)
            left = verifySquenceOfBST(squence, i);

      // verify whether the right sub-tree is a BST
      bool right = true;
      if(i < length - 1)
            right = verifySquenceOfBST(squence + i, length - i - 1);

      return (left && right);
}

Question

Given 2 linked list head pointers, determine whether they intersect at some point.

Solution

First of all, linked list can have loop or not, and this gives 3 possible situations.

1. For the 2 loops head pointer 1 and head pointer 2, move pointer 1 at normal speed, and pointer 2 at double speed. If they intersect, node will be the same at some point. Otherwise infinity loop occurs. (need to be fixed)

2. For 2 straight linked list, they would have the same tails if they intersect.

3. For a loop and a straight list, use the first algorithm and let the loop to move at double speed. If they don’t intersect, tail of the straight list will end the checking.

So one of the key idea is to check if a linked list is loop. Since loop may start not at the head, we can not use head pointer as the checking reference. We could instead use the algorithm 1 against itself, if it has loop the 2 moving pointer will meet at some point.

Sample Code

# node structure
class Node:
    value = None
    next = None

    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

# check if the list has loop
def is_loop(head):
    if not head: return False
    slow_trace = fast_tract = head
    while fast_tract and fast_tract.next:
        slow_trace = slow_trace.next
        fast_tract = fast_tract.next.next
        if slow_trace == fast_tract: return True
    return False

# check meet up if list is loop
def check_meet_up_with_loop(head_1, head_2):
    # todo: infinite loop if not meeting up
    while head_1 != head_2 and head_1 and head_2:
        head_1 = head_1.next
        head_2 = head_2.next
        if head_2.next: head_2 = head_2.next
    return head_1 == head_2 and head_1 is not None and head_2 is not None

# check meet up if list is not loop
def check_meet_up_without_loop(head_1, head_2):
    tail_1 = head_1
    tail_2 = head_2
    while tail_1.next: tail_1 = tail_1.next
    while tail_2.next: tail_2 = tail_2.next
    return tail_1 == tail_2

# list 1
node_9 = Node(9)
node_8 = Node(8, node_9)  # meet of list 1 and 2
node_7 = Node(7, node_8)
node_6 = Node(6, node_7)
node_5 = Node(5, node_6)
head_1 = node_5
print is_loop(head_1) == False

# list 2, will meet with list 1
node_4 = Node(4, node_8)
node_3 = Node(3, node_4)
node_2 = Node(2, node_3)
head_2 = node_2
print is_loop(head_2) == False

# list 3, separate list
node_1 = Node(1)
node_0 = Node(0, node_1)
head_3 = node_0
print is_loop(head_3) == False

# list 4 with loop
node_15 = Node(15)
node_14 = Node(14, node_15)
node_13 = Node(13, node_14)
node_12 = Node(12, node_13)
node_11 = Node(11, node_12)
node_15.next = node_11
head_4 = node_11
print is_loop(head_4)  # true

# list 5 same loop with 4
node_25 = Node(25, node_14)
node_24 = Node(24, node_25)
head_5 = node_24
print is_loop(head_5)  # true

# list 6, separate loop
node_35 = Node(35)
node_34 = Node(34, node_35)
node_35.next = node_34
head_6 = node_34
print is_loop(head_6)  # true

# checking
print
print check_meet_up_without_loop(head_1, head_2) == True
print check_meet_up_without_loop(head_1, head_3) == False
print check_meet_up_with_loop(head_4, head_5) == True
print check_meet_up_with_loop(head_4, head_6) == False
#include <iostream>

// node structure
struct Node
{
	int value;
	Node *next;

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

// check if the list has loop
bool is_loop(Node *head)
{
	if (!head) return false;
	Node *slow_trace = head;
	Node *fast_tract = head;
	while (fast_tract && fast_tract->next) {
		slow_trace = slow_trace->next;
		fast_tract = fast_tract->next->next;
		if (slow_trace == fast_tract) return true;
	}
	return false;
}

// check meet up if list is loop
bool check_meet_up_with_loop(Node *head_1, Node *head_2)
{
	// todo: infinite loop if not meeting up
	while (head_1 != head_2 && head_1 && head_2) {
		head_1 = head_1->next;
		head_2 = head_2->next;
		if (head_2->next) head_2 = head_2->next;
	}
	return head_1 == head_2 && head_1 && head_2;
}

// check meet up if list is not loop
bool check_meet_up_without_loop(Node *head_1, Node *head_2)
{
	Node *tail_1 = head_1;
	Node *tail_2 = head_2;
	while (tail_1->next) tail_1 = tail_1->next;
	while (tail_2->next) tail_2 = tail_2->next;
	return tail_1 == tail_2;
}

int main()
{
	// list 1
	Node *node_9 = new Node(9);
	Node *node_8 = new Node(8, node_9);  // meet of list 1 and 2
	Node *node_7 = new Node(7, node_8);
	Node *node_6 = new Node(6, node_7);
	Node *node_5 = new Node(5, node_6);
	Node *head_1 = node_5;
	printf("%sn", is_loop(head_1) == false ? "true" : "false");

	// list 2, will meet with list 1
	Node *node_4 = new Node(4, node_8);
	Node *node_3 = new Node(3, node_4);
	Node *node_2 = new Node(2, node_3);
	Node *head_2 = node_2;
	printf("%sn", is_loop(head_2) == false ? "true" : "false");

	// list 3, separate list
	Node *node_1 = new Node(1);
	Node *node_0 = new Node(0, node_1);
	Node *head_3 = node_0;
	printf("%sn", is_loop(head_3) == false ? "true" : "false");

	// list 4 with loop
	Node *node_15 = new Node(15);
	Node *node_14 = new Node(14, node_15);
	Node *node_13 = new Node(13, node_14);
	Node *node_12 = new Node(12, node_13);
	Node *node_11 = new Node(11, node_12);
	node_15->next = node_11;
	Node *head_4 = node_11;
	printf("%sn", is_loop(head_4) ? "true" : "false");  // true

	// list 5 same loop with 4
	Node *node_25 = new Node(25, node_14);
	Node *node_24 = new Node(24, node_25);
	Node *head_5 = node_24;
	printf("%sn", is_loop(head_5) ? "true" : "false");  // true

	// list 6, separate loop
	Node *node_35 = new Node(35);
	Node *node_34 = new Node(34, node_35);
	node_35->next = node_34;
	Node *head_6 = node_34;
	printf("%sn", is_loop(head_6) ? "true" : "false");  // true

	// checking
	printf("%sn", check_meet_up_without_loop(head_1, head_2) == true ? "true" : "false");
	printf("%sn", check_meet_up_without_loop(head_1, head_3) == false ? "true" : "false");
	printf("%sn", check_meet_up_with_loop(head_4, head_5) == true ? "true" : "false");
	printf("%sn", check_meet_up_with_loop(head_4, head_6) == false ? "true" : "false");
}

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]

%d bloggers like this: