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
Algorithm
Question Write an efficient program for printing k largest elements in an array. Elements in array can be in any order. For example, if given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program
Algorithm
Question 输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2， 因此输出为该子数组的和18。 From a set of positive and negative integers, find the longest sequence that makes the greatest sum. It is required to have the time complexity of O(n)
Unsorted
It’s been a while since the last post. After coming to new york, I have been very busy on my study, personal projects and (of course) playing around. studying in new york university is harsh, but not as hard as i think. I met nice people, hanged out with
Algorithm
Question Define a stack structure with “min” function — a function to get the minimum value within the stack. The time complexity of min, push and pop functions must be O(1). Solution Push data to the stack at the same time update the minimum stack if the new data is