Interview Practice 24 – 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 while node: next_node = node.next if next_node…

Read more...

Interview Practice 22 – 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 those of other players. They…

Read more...

Interview Practice 21 – 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 # find combination of 1..n with sum target…

Read more...

Interview Pizzle 1 – 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 weighings. How can you determine which marble is the heaviest…

Read more...

Interview Practice 20 – 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 before adding the scanned digit…

Read more...

Interview Practice 19 – 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: = 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…

Read more...

Interview Practice 18 – 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 and then output this number. For…

Read more...

Interview Practice 17 – 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. These two step take O(n)…

Read more...

Interview Practice Extra 03 – 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 left = None right…

Read more...

Interview Practice Extra 02 – Duplicates in List

Question Write an algorithm to remove duplicated node from a linked list. Solution 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²). The second way Reference http://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/

Read more...