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.

# Tag Archives: refer

# Interview Practice Extra 06 – Vending Machine

### 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)

# Interview Practice Extra 05 – Identify Prime Numbers

### Question

Write an algorithm to identify prime numbers from a list of numbers ranging 0-100.

### Solution

The main question is actually to write a program to check if a number is prime. There are 4 situations.

1. If number is 0 or 1, it is not prime.

2. if the number is 2, it is prime.

3. if the number is even, it is not prime.

4. if number is greater than 3, and not divisible by all odd numbers (except 1) smaller than the square root of the input number, it is prime.

### Sample

public class InterviewPracticeExtra05 { private static boolean is_prime(int input) { if (input <= 1) return false; if (input == 2) return true; if (input % 2 == 0) return false; for (int i = 3; i * i <= input; i += 2) { if (input % i == 0) return false; } return true; } public static void main(String[] args) { for (int i = 0; i <= 100; i++) { if (is_prime(i)) System.out.println(i); } } }

### Reference

# Interview Practice Extra 04 – Remove Node from Singly Linked List

### Question

How do you remove a node from a singly linked list, given only that node? Head node is not given.

### Solution

Set next of this node to the next of the next node.

node->next = node->next->next;

Reference

# Interview Practice Extra 02 – Duplicates in List

### Question

Write an algorithm to remove duplicated node from a linked list.

### Solution

There are many ways to do it. For the first one, as the simplest one, we could use 2 loops to compare each element with all other elements. However, this takes forever: O(n²).

The second way

### Reference

http://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/

# Interview Practice 16 – Print Binary Tree Layer-by-layer

### Question

Print a binary tree layer-by-layer from top to bottom, and from left to right for each layer.

### Solution

Yes, it’s a simple task. We can use breadth-first search, and which means we need a queue, see reference.

levelorder(root) q = empty queue q.enqueue(root) while not q.empty do node := q.dequeue() visit(node) if node.left ≠ null then q.enqueue(node.left) if node.right ≠ null then q.enqueue(node.right)

### Example

# node structure 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 # what to do with a node. def visit(node): print node.value, # bfs traversal def breadth_first_traversal(root): queue = [root] while len(queue) > 0: node = queue.pop(0) # get the head item visit(node) if node.left: queue.append(node.left) if node.right: queue.append(node.right) # a binary tree and display how was it before reflection node_05 = bst_node(5) node_07 = bst_node(7) node_09 = bst_node(9) node_11 = bst_node(11) node_06 = bst_node(6, node_05, node_07) node_10 = bst_node(10, node_09, node_11) node_08 = bst_node(8, node_06, node_10) # answer should be: 8 6 10 5 7 9 11 root = node_08 breadth_first_traversal(root)

# Interview Practice 15 – Mirror Image of Binary Tree

### Question

Construct 2 algorithms to make mirror image of any binary tree inputs, one of them using recursive method, another one using looping method. Mirror image means a binary tree that is the horizontal reflection of the original tree.

### Solution

First, to do it in recursive method, we can perform pre-order traversal as usual, see preference. Then swap the left and right children for every node.

reflect(node) if node is null then return swap(node.left, node.right) if node.left is not null then reflect(node.left) if node.right is not null then reflect(node.right)

Second, to do it in looping method, we can make use of a stack. Put root node in the stack first. Then in a while-loop, as long as the stack isn’t empty, swap its children. Then put the children nodes into the stack.

reflect(root) if root is null then return stack.push(root) while stack is not empty, do node = stack.pop() swap(node.left, node.right) if node.left is not null then reflect(node.left) if node.right is not null then reflect(node.right)

### Example

# node structure 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 # swap node's children while visiting def visit(node): temp = node.left node.left = node.right node.right = temp # reflect a binary tree def depth_first_traversal(node): if not node: return visit(node) if node.left: depth_first_traversal(node.left) if node.right: depth_first_traversal(node.right) # debug function to print tree def print_tree(node, indent=''): print "%s-%s" % (indent, node.value) if node.left: print_tree(node.left, indent + ' ') if node.right: print_tree(node.right, indent + ' ') # a binary tree and display how was it before reflection node_05 = bst_node(5) node_07 = bst_node(7) node_09 = bst_node(9) node_11 = bst_node(11) node_06 = bst_node(6, node_05, node_07) node_10 = bst_node(10, node_09, node_11) node_08 = bst_node(8, node_06, node_10) root = node_08 print_tree(root) # do reflection depth_first_traversal(root) print_tree(root)

# node structure 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 # what to do in a loop, here swap the children def visit(node): temp = node.left node.left = node.right node.right = temp # reflect a binary tree def depth_first_traversal(root): if not root: return stack = [root] while len(stack) > 0: node = stack.pop() visit(node) if node.left: stack.append(node.left) if node.right: stack.append(node.right) # debug function to print tree def print_tree(node, indent=''): print "%s-%s" % (indent, node.value) if node.left: print_tree(node.left, indent + ' ') if node.right: print_tree(node.right, indent + ' ') # a binary tree and display how was it before reflection node_05 = bst_node(5) node_07 = bst_node(7) node_09 = bst_node(9) node_11 = bst_node(11) node_06 = bst_node(6, node_05, node_07) node_10 = bst_node(10, node_09, node_11) node_08 = bst_node(8, node_06, node_10) root = node_08 print_tree(root) # do reflection depth_first_traversal(root) print_tree(root)

struct BSTreeNode // a node in the binary search tree (BST) { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; //就是递归翻转树，有子树则递归翻转子树。 //July、2010/10/19 void Revertsetree(list *root) { if(!root) return; list *p; p=root->leftch; root->leftch=root->rightch; root->rightch=p; if(root->leftch) Revertsetree(root->leftch); if(root->rightch) Revertsetree(root->rightch); }

void Revertsetree(list *phead) { if(!phead) return; stack<list*> stacklist; stacklist.push(phead); //首先把树的头结点放入栈中。 while(stacklist.size()) //在循环中，只要栈不为空，弹出栈的栈顶结点，交换它的左右子树 { list* pnode=stacklist.top(); stacklist.pop(); list *ptemp; ptemp=pnode->leftch; pnode->leftch=pnode->rightch; pnode->rightch=ptemp; if(pnode->leftch) stacklist.push(pnode->leftch); //若有左子树，把它的左子树压入栈中 if(pnode->rightch) stacklist.push(pnode->rightch); //若有右子树，把它的右子树压入栈中 } }