Algorithm
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
Algorithm
Question Write an algorithm to remove duplicated node from a linked list. Solution with O(n²) There are many ways to do it. For the first one, as the simplest one, we could use 2 loops to compare each element with all other elements. However, this takes forever: O(n²
Algorithm
Question Validate a linked list whether there is a loop in it. That is, there is a node in a linked list with the next pointer pointing to a node ahead in the same linked list. This is the question I encountered in 2013 spring, from a Yahoo phone interview.
Algorithm
Question Print a binary tree layer-by-layer from top to bottom, and from left to right for each layer. Solution Yes, it’s a simple task. We can use breadth-first search, and which means we need a queue. Example # node structure class bst_node: def __init__(self, value, left=None, right=
Algorithm
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
Algorithm
Question Given a sorted integer list and an integer, find two integer in the list such that the sum of the two integers equals the given integer. It is required that the time complexity must be O(n). For example, the sorted integer list is {1, 2, 4, 7, 11,
Algorithm
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. Then move P2 to the next (K+
Algorithm
Question Get the greatest distance between two nodes in a binary tree. Assume links between nodes are bidirectional. Distance is defined as the amount of nodes connected along the path linked two nodes. Write an algorithm to calculate distance between two nodes. Take the figure at the right, the greatest
Algorithm
Question Simple task, reverse words in a sentence. Solution In Python, this can be simple because of the build-in functions. We can just split the sentence by spaces, reverse the list, and join them with spaces again. In C++, this can be complicated. The following might be one of the
Algorithm
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
Algorithm
Question Given 2 linked list head pointers, determine whether they intersect at some point. Solution First of all, linked list can have loop or not, and this gives 3 possible situations. 1. For the 2 loops head pointer 1 and head pointer 2, move pointer 1 at normal speed, and
Algorithm
Question A self-descriptive number is an integer n in given base b is b digits long in which each digit at position p (the most significant digit being at position 0 and the least significant at position b – 1) counts how many times a digit p is in n. For