Archive

Tag Archives: lg

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

Construct an algorithm so that the Nth item of  Fibonacci Sequence can be found in the shortest time. Definition of Fibonacci Sequence is:

     = 0              , when n = 0
f(n) = 1              , when n = 1
     = f(n-1) + f(n-2), when n > 1

Solution

There are many solutions for this, the simplest way is to use recursive function.

fibonacci(n)
  if n equals 0 then return 0
  else if n equals 1 then return 1
  else return fibonacci(n-1) + fibonacci(n-2)

There is another way actually, through using loops. The time complexity is O(n).

fibonacci(n)
  if n equals 0 then return 0
  else if n equals 1 then return 1
  fib_n_minus_2 = 0
  fib_n_minus_1 = 1
  fib_n = 0
  for i equals 2 to n
    fib_n = fib_n_minus_1 + fib_n_minus_2
    fib_n_minus_2 = fib_n_minus_1
    fib_n_minus_1 = fib_n
  return fib_n

Consider

Consider there is a list containing N numbers, and which formed a ring. That is, item n+1 is item 1. Construct an algorithm such that it traverses through the ring, and remove the Mth item. Repeat this process until there is only one number left in the ring and then output this number. For example, in the list {10, 11, 12}, and the remove the 3th item in every loop. Then in the first loop, 12 will be removed, followed by 10. Therefore the last surviving number is 11.

Solution

In python, it’s easy because it has build-in function to resize an array. We can construct an array, then pop the Kth item in every loop, where K = M mod Length of List.

Example

# last in list
def last_remain_number_in_list(list, m):
    length = len(list)
    while len(list) > 1:
        index = m % len(list)
        list.pop(index)
    return list.pop()

# main, answer is 5
list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print last_remain_number_in_list(list, 8)
#include <stdio.h>

int main()
{
    int i,k,m,n,num[50],*p;
    printf("input number of person:n=");
    scanf("%d",&n);

    printf("input number of the quit:m=");   //留下->18题
    scanf("%d",&m);                          //留下->18题

       p=num;
    for(i=0;i<n;i++)
        *(p+i)=i+1;    //给每个人编号
    i=0;   //报数
    k=0;   //此处为3
//    m=0;   //m为退出人数                     //去掉->18题
    while(m<n-1)
    {
        if(*(p+i)!=0)
            k++;
        if(k==3)
        {
            *(p+i)=0;    //退出,对应的数组元素置为0
            k=0;
            m++;
        }
        i++;
        if(i==n)
            i=0;
    }
    while(*p==0)
        p++;
    printf("The last one is NO.%d/n",*p);
}
int LastRemaining_Solution2(int n, unsigned int m)
{
      // invalid input
      if(n <= 0 || m < 0)
            return -1;

      // if there are only one integer in the circle initially,
      // of course the last remaining one is 0
      int lastinteger = 0;

      // find the last remaining one in the circle with n integers
      for (int i = 2; i <= n; i ++)
            lastinteger = (lastinteger + m) % i;

      return lastinteger;
}

Question

Given a string, write an algorithm to find the character inside that appeared only once. For example, the result for string “abaccdeff” is b.

Solution

We can use a hashtable to count the appearance times for each character. Then rescan the hashtable for the character that appeared only once. These two step take O(n) each, therefore the overall time complexity is O(n).

# function to find char appeared once
def find_appeared_once(string):
    hashtable = {} # a hashtable

    # loop for each char in string
    for char in string:
        if char not in hashtable:
            hashtable[char] = 1
        else:
            hashtable[char] += 1

    # find the item appeared only once
    for char, count in hashtable.items():
        if count == 1:
            return char

# main
print find_appeared_once('abaccdeff')

 

#include <iostream.h>
#include <string.h>

char FirstNotRepeatingChar(char* pString)
{
      if(!pString)
            return 0;

      const int tableSize = 256;
      unsigned int hashTable[tableSize];
      for(unsigned int i = 0; i < tableSize; ++ i)
            hashTable[i] = 0;

      char* pHashKey = pString;
      while(*(pHashKey) != '/0')
            hashTable[*(pHashKey++)] ++;

      pHashKey = pString;
      while(*pHashKey != '/0')
      {
            if(hashTable[*pHashKey] == 1)
                  return *pHashKey;

            pHashKey++;
      }

      return *pHashKey;
}

int main()
{
    cout<<"请输入一串字符:"<<endl;
    char s[100];
    cin>>s;
    char* ps=s;
    cout<<FirstNotRepeatingChar(ps)<<endl;
    return 0;
}

//////////////////////////////////////////
请输入一串字符:
abaccdeff
b
Press any key to continue
///////////////////////////////////////////

 

 

Question

Verify whether all nodes have the same value in a binary tree.

Solution

We can traverse the tree with our usual way, like depth-first or breadth-first algorithm. Then pass a value, probably the root value, to compare with the visiting node.

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 while visiting the node
def visit(node, value):
    return node.value == value

# reflect a binary tree
def depth_first_traversal(root):
    stack = [root]
    value = root.value
    result = True
    while len(stack) > 0:
        node = stack.pop()
        result = visit(node, value)
        if result == False: break
        if node.left: stack.append(node.left)
        if node.right: stack.append(node.right)
    return result

# a binary tree with all values to be 1
node_05 = bst_node(1)
node_07 = bst_node(1)
node_09 = bst_node(1)
node_11 = bst_node(1)
node_06 = bst_node(1, node_05, node_07)
node_10 = bst_node(1, node_09, node_11)
node_08 = bst_node(1, node_06, node_10)

# main
root = node_08
print depth_first_traversal(root)
%d bloggers like this: