Archive

Tag Archives: function

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

Given a number, find the number of 1 in the number’s binary expression. For example, binary express of 10 is 1010. So the number of 1 in it is 2.

Solution

To solve this, we can check each bit by shifting the bits one by one.

1. 1010 -> check 0
2. 101 -> check 1
3. 10 -> check 0
4. 1 -> check 1

So how to check it? we could use the AND function.

1. 1010 -> check 1010 & 1 = 0
2. 101 -> check 101 & 1 = 1 -> counter + 1
3. 10 -> check 10 & 1 = 0
4. 1 -> check 1 & 1 = 1 -> counter + 1

However, negative number will put this program into infinite loop. For example, shifting -10 (0xFFFFFFF6) several times gives 0xFFFFFFFF. Then shifting 0xFFFFFFFF will give 0xFFFFFFFF and makes infinite loops. Therefore instead of shifting the inputting number, we should shift the comparing number.

1. 1010 -> check 1010 & 1 = 0
2. 1010-> check 1010 & 10 = 1 -> counter + 1
3. 1010 -> check 1010 & 100 = 0
4. 1010 -> check 1010 & 1000 = 1 -> counter + 1

Sample

Question

Given a function prototype: int continumax(char *output_string,char *input_string). Implement it to find the longest consecutive digits. This function must return the length of the longest digits. The found longest digits should be written to the memory location that output_string is pointing. For example, if input_string is “abcd12345ed125ss123456789”, function returns 9 and output_string becomes “123456789”.

Solution

This question must be implemented in C/C++. Just skip letters, count the length and save the head position to a temp pointer.

Sample

#include <iostream>

int continumax(char *output_string, char *input_string)
{
	int max_length = 0;
	char *max_string = new char[sizeof(input_string)];

	while (true) {

		// skip all non-digit characters
		while (*input_string != 0 && (*input_string < '0' || *input_string > '9')) input_string++;
		if (*input_string == 0) break;

		// current char is digit
		int length = 0;
		char *temp_string = input_string;
		while (*input_string!=0 && *input_string >= '0' && *input_string <= '9') {
			length++;
			input_string++;
		}

		// check if this is longer
		if (length > max_length) {
			max_length = length;
			max_string = temp_string;
		}
	}

	// write maximum string to output and add null to end.
	int i;
	for (i = 0; i < max_length; i++) output_string[i] = max_string[i];
	output_string[i] = 0;

	return max_length;
}

int main()
{
	char input[] = "abcd12345ed125ss123456789";
	char *output = new char[sizeof(input)];
	int length = continumax(output, input);
	printf("Length: %dn", length);
	printf("Output: %sn", output);
}

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

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);  //若有右子树,把它的右子树压入栈中
    }
}

Reference

Pre-order Tree Transversal (Wikipedia)

%d bloggers like this: