Archive

Tag Archives: construct

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

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

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)

Question

Given a linked list, find the Kth last node in a linked list. The last 0th node is the tail node in the linked list.

Solution

Easy task. Construct 2 pointers: P1 and P2. First, both of them are set to head. Move P2 to the next Kth node.

Example

# node structure
class node:
    data = None
    next = None
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

# get item
def get_item(head, k):
    pointer_1 = head
    pointer_2 = head
    for i in xrange(k+1):
        if pointer_2 is not None:
            pointer_2 = pointer_2.next
    while pointer_2 is not None:
        pointer_1 = pointer_1.next
        pointer_2 = pointer_2.next
    return pointer_1

# linked list
node_9 = node(9)
node_8 = node(8, node_9)
node_7 = node(7, node_8)
node_6 = node(6, node_7)
node_5 = node(5, node_6)
node_4 = node(4, node_5)
node_3 = node(3, node_4)
node_2 = node(2, node_3)
node_1 = node(1, node_2)

# main
head = node_1
print get_item(head, 0).data
print get_item(head, 9).data
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

struct ListNode
{
    char data;
    ListNode* next;
};
ListNode* head,*p,*q;
ListNode *pone,*ptwo;

ListNode* fun(ListNode *head,int k)
{
    pone = ptwo = head;
    for(int i=0;i<=k-1;i++)
        ptwo=ptwo->next;
    while(ptwo!=NULL)
    {
        pone=pone->next;
        ptwo=ptwo->next;
    }
    return pone;
}

int main()
{
    char c;
    head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;
    p = head;
    while(c !='0')
    {
        q = (ListNode*)malloc(sizeof(ListNode));
        q->data = c;
        q->next = NULL;
        p->next = q;
        p = p->next;
        c = getchar();
    }
    cout<<"---------------"<<endl;
    cout<<fun(head,2)->data<<endl;

    return 0;
}

/////////////////////////////
1254863210
---------------
2
Press any key to continue
////////////////////////////

9

Question

Construct an algorithm to verify if a set of numbers is the post-order search result of a binary search tree. Let the figure at the right hand side as an example, the algorithm will return true if {5, 7, 6, 9, 11, 10, 8}. However, it will return false if the input is {7, 4, 6, 5}.

Solution

Actually, a post-order search of the whole tree would do the job. First, perform a depth-first search from the leftmost leave, and push each element into a stack.

Reference

Wikipedia

Pseudocode

postorder(node)
    if node == null then return
    postorder(node.left)
    postorder(node.right)
    visit(node)

Samples

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

def postorder(node, test_seq):
    if node is None: return True
    if not postorder(node.left, test_seq): return False
    if not postorder(node.right, test_seq): return False
    return visit(node, test_seq)

def visit(node, test_seq):
    front = test_seq.pop(0) # front item
    return front == node.value

node_5 = bst_node(5)
node_7 = bst_node(7)
node_9 = bst_node(9)
node_11 = bst_node(11)
node_6 = bst_node(6, node_5, node_7)
node_10 = bst_node(10, node_9, node_11)
node_8 = bst_node(8, node_6, node_10)
root = node_8

test_seq_1 = [5, 7, 6, 9, 11, 10, 8]
test_seq_2 = [7, 4, 6, 5]

print postorder(root, test_seq_1)
print postorder(root, test_seq_2)
bool verifySquenceOfBST(int squence[], int length)
{
      if(squence == NULL || length <= 0)
            return false;

      // root of a BST is at the end of post order traversal squence
      int root = squence[length - 1];

      // the nodes in left sub-tree are less than the root
      int i = 0;
      for(; i < length - 1; ++ i)
      {
            if(squence[i] > root)
                  break;
      }

      // the nodes in the right sub-tree are greater than the root
      int j = i;
      for(; j < length - 1; ++ j)
      {
            if(squence[j] < root)
                  return false;
      }

      // verify whether the left sub-tree is a BST
      bool left = true;
      if(i > 0)
            left = verifySquenceOfBST(squence, i);

      // verify whether the right sub-tree is a BST
      bool right = true;
      if(i < length - 1)
            right = verifySquenceOfBST(squence + i, length - i - 1);

      return (left && right);
}

Questiontree

Convert binary search tree into doubly linked list. It’s required not to create any new node, but only turning pointers.

Solution

The following shows the concept of this question.

        8
      /   
    6       0       ->     5 = 6 = 7 = 8 = 9 = 0 = 1
   /      / 
  5   7   9    1

First, since node for both binary tree and doubly linked list have left and right node, they can use the same node structure. Then, looking the doubly linked list as a normal linked list, it is actually a in-order depth-first traversal result.

Sample Codes

 

# 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

# what to do with a node.
def visit(node):
    global node_temp
    global node_root
    if not node_temp: node_root = node  # head
    else: node_temp.right = node  # make right of temp to this
    node.left = node_temp  # make temp to this left
    node_temp = node  # next node

# bfs traversal
def depth_first_recursive_traversal_in_order(node):
    if node is None: return
    depth_first_recursive_traversal_in_order(node.left)
    visit(node)
    depth_first_recursive_traversal_in_order(node.right)

# a binary tree and display how was it before reflection
node_5 = Node(5)
node_7 = Node(7)
node_9 = Node(9)
node_1 = Node(1)
node_6 = Node(6, node_5, node_7)
node_0 = Node(0, node_9, node_1)
node_8 = Node(8, node_6, node_0)

# conversion
node_root = node_8
node_temp = None
depth_first_recursive_traversal_in_order(node_root)

# answer should be: 5 6 7 8 9 0 1
node_temp = node_root
while node_temp:
    print node_temp.value,
    node_temp = node_temp.right
public class InterviewPractice1
{
    // global
    static Node node_root = null;
    static Node node_temp = null;

    // node structure
    private static class Node
    {
        private int value;
        private Node left;
        private Node right;

        public Node(int value, Node left, Node right)
        {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    // visit
    private static void visit(Node node)
    {
        if (node_temp == null) node_root = node; // set head
        else node_temp.right = node; // make right of temp to this node
        node.left = node_temp; // make temp to the left of this node
        node_temp = node; // next node

    }

    // depth first, recursive
    private static void depth_first_recursive_traversal_in_order(Node node)
    {
        if (node == null) return;
        depth_first_recursive_traversal_in_order(node.left);
        visit(node);
        depth_first_recursive_traversal_in_order(node.right);
    }

    // main
    public static void main(String[] args)
    {
        // tree
        Node node_5 = new Node(5, null, null);
        Node node_7 = new Node(7, null, null);
        Node node_9 = new Node(9, null, null);
        Node node_1 = new Node(1, null, null);
        Node node_6 = new Node(6, node_5, node_7);
        Node node_0 = new Node(0, node_9, node_1);
        Node node_8 = new Node(8, node_6, node_0);

        // run
        node_root = node_8;
        depth_first_recursive_traversal_in_order(node_root);

        // the result should be 5 6 7 8 9 0 1
        node_temp = node_root;
        while (node_temp != null) {
            System.out.print(node_temp.value + " ");
            node_temp = node_temp.right;
        }
    }
}
#include <iostream>

struct Node
{
    int value;
    Node *left;
    Node *right;

    Node(int value, Node *left = NULL, Node *right = NULL)
    {
        this->value = value;
        this->left = left;
        this->right = right;
    }
};

Node *node_root = NULL;
Node *node_temp = NULL;

void visit(Node *node)
{
    if (node_temp == NULL) node_root = node;  // set head
    else node_temp->right = node;  // make right of them to this node
    node->left = node_temp;  // make temp to the left of this node
    node_temp = node;  // next node
}

void depth_first_recursive_traversal_in_order(Node *node)
{
    if (!node) return;
    depth_first_recursive_traversal_in_order(node->left);
    visit(node);
    depth_first_recursive_traversal_in_order(node->right);
}

int main()
{
    // tree
    Node *node_5 = new Node(5);
    Node *node_7 = new Node(7);
    Node *node_9 = new Node(9);
    Node *node_1 = new Node(1);
    Node *node_6 = new Node(6, node_5, node_7);
    Node *node_0 = new Node(0, node_9, node_1);
    Node *node_8 = new Node(8, node_6, node_0);

    // conversion
    node_root = node_8;
    node_temp = NULL; // null
    depth_first_recursive_traversal_in_order(node_8);

    // answer should be: 5 6 7 8 9 0 1
    node_temp = node_root;
    while (node_temp) {
        printf("%d ", node_temp->value);
        node_temp = node_temp->right;
    }
}
%d bloggers like this: