Algorithm

A collection of 37 posts

Algorithm

0/1 Knapsack Problem Dynamic Programming

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. Drawing graph int[] plot(

Algorithm

Dynamic Programming

1. Come up with a recursive function 2. Memorize the intermediate results 3. Make it bottom up

Algorithm

Palindrome

Definition of Palindrome left-to-right, and right-to-left, and it’s the same. For examples: Abba A man, a plan, a canal - Panama! Solution You need 2 pointers, one at the beginning, another one in the end. Move them one by one towards the center and check if it's palindrome. boolean

Algorithm

Breathe First Traversal

In the iterative way You can only do breathe first traversal in iterative way. Though you can still make it recursive by calling itself in each loop, but you will not benefit from it. It is similar to doing depth first traversal, instead you use a FIFO queue to store

Algorithm

Depth First Traversal

There are 4 ways to do a depth first traversal, depends on how you would like to do it. Define Node static class Node { int value; Node left, right; } Depth First Recursive Traversal (Pre-order) static boolean depthFirstTraversal_preOrder(Node node) { if (node == null) return true; if (!visit(node)) return false;

Algorithm

Snapsack Problem

Snapsack problem refers to the situation you want to find a combination of items that can fill up a container. Each items should be attached with a value, and there should be a target value that means a container is filled up. For example, a container has 25 spaces and

Algorithm

Universal Value Binary Tree

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,

Algorithm

Vending Machine

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

Algorithm

Identify Prime Numbers

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

Algorithm

Remove Node from Singly Linked List

Question How do you remove a node from a singly linked list, given only that node? Head node is not given. Solution Set next of this node to the next of the next node. node->next = node->next->next; Reference * Glassdoor

Algorithm

Counting One in Binary Expression

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

Algorithm

Right-rotate String

Question Write a program to right-rotate a string by m characters. Right-rotating a string means moving m characters at the left of string to the right. Is it required the time complexity is O(n) and helper memory size is O(1). For example, right-rotate “abcdefghi” by 3 characters gives

Algorithm

Longest Consecutive Digits

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

Algorithm

Reverse a Linked List

Question Reverse a linked list. Sample # node structure class Node: value = None next = None def __init__(self, value, next_node=None): self.value = value self.next = next_node # reverse the linked list and return the head node def reverse_linked_list(head): reversed_head = None last_node = None node = head

Algorithm

Card Guessing

Question Consider there are 4 blue and 4 red cards. Host gets 2 cards randomly, no one knows what cards they are. Then he places 2 random cards at the forehead of each player A, B and C. Players do not know the color of their own cards, but know

Algorithm

Summing Combinations

Question Given a integers m and n, generate all combination within 1 to n that would give the sum m. For example, for m=5 and n=5, the combinations are {5}, {4+1}, {3+2}. Solution This is a knapsack problem. #knapsack that store the found combination knapsack = array

Algorithm

Find the Heavier Marble

Question You have 9 marbles. 8 marbles weigh 1 ounce each, & one marble weighs 1.5 ounces. You are unable to determine which is the heavier marble by looking at them. You have a weighing scale that consists of 2 pans, but the scale is only good for 2 total

Algorithm

Convert String to Integer

Question Convert the inputted string to an integer. For example, “345” will output 345. Solution Though it looks simple, in fact it is pretty tricky. First we need to make the concept clear. 1. Scan each character from the left to right, then multiply the previously obtained integer by ten

Algorithm

Fastest Way to Calculate Fibonacci Sequence

Question Construct an algorithm so that the Nth item of Fibonacci Sequence can be found in the shortest time. Definition of Fibonacci Sequence is: f(n) = 0 , when n = 0 f(n) = 1 , when n = 1 f(n) = f(n-1) + f(n-2), when n > 1 Solution There are many solutions

Algorithm

Last Surviving Number in Loop

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

Algorithm

Find The String Appeared Once

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.

Algorithm

Verify Binary Tree with Same Value

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

Remove Duplicates In List

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

Find Any Loops in Linked List

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

Print Binary Tree Layer-by-layer

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=