Interview Practice Extra 05 – 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 number is 2, it is…

Read more...

Interview Practice 26 – String Right-rotation

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 “defghiabc”. Solution There are 2 ways to…

Read more...

Interview Practice 25 – 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 input_string is “abcd12345ed125ss123456789”, function returns 9 and output_string becomes “123456789”. Solution This…

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 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 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 10 – Reverse Sentence

Simple task, reverse words in a sentence.

Read more...

Interview Practice 02 – Stack with Minimum Function

定義棧的數據結構,要求添加一個min函數,能夠得到棧的最小元素。要求函數min、push以及pop的時間複雜度都是O(1)。

Read more...

Interview Practice 01 – Convert Binary Tree into Doubly Linked List

Question 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,…

Read more...

Find the User Agent Strings of any Mobile Devices

It’s quite often for a developer to make use of the user agent to determine what browser does a user used, especially for those who develop web services and websites. Recently I found a website which has a huge database of mobile device information, including the user agent string and even the functions supported in…

Read more...