Archive

Interview Practices

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.

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

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

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)

 

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

Glassdoor

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

Glassdoor

%d bloggers like this: