You can only do breathe first traversal in iterative way. Though you can still make it recursive by calling itself in each loop, but you will not benefit from it. It is similar to doing depth first traversal, instead you use a FIFO queue to store the nodes.

# Interview Practices

# Interview Practice Basic – Depth First Traversal

There are 4 ways to do a depth first traversal, depends on how you would like to do it.

# Interview Practice Basic – Snapsack Problem

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.

# Interview Practice Extra 07 – Universal Value Binary Tree

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

# 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