Author Archives: Ming

make string a postfix notation

Imagine x is an operand and * is a binary operator. We say a string of x and * follows Reverse Polish notation if it is a postfix notation. 

For example strings xx*, x, and xx*xx** follow Reverse Polish notation. 

Given a string of x and *, how many insert, delete, and replace operations are needed to make the string follow the RPN. 

For example, xx* need 0 operation to follow RPN since it already follows RPN. 
x*x needs two operations to become xx* which follows RPN. 
*xx* needs one operation to become xx* which follows RPN. 

Your algorithm should work for a string of size up to 100.

 

题目

1: 8  (0 1 1 1 1)
2: 7   (1 1 1 2 2)
3: 7  (1 1 1 2 2)
4: 9  (1 2 2 2 2)
5: 8  (1 1 2 2 2)

9: 11 (2 3 2 2 2)
10: 7 (1 1 1 2 2)
11: 8 (1 1 2 2 2)

17: 14 (2 3 3 3 3)
18: 13 (2 2 3 3 3)

total: 92

do 4 each day

35. 求一个矩阵中最大的二维矩阵(元素和最大)

求一个矩阵中最大的二维矩阵(元素和最大).如:
1 20 3 4
2 34 5 1
1 15 3 0
中最大的是:
45
53
要求:(1)写出算法;(2)分析时间复杂度;(3)用 C 写出关键代码

http://en.wikipedia.org/wiki/Maximum_subarray_problem

 

tasks scheduled on servers

Reference: http://www.careercup.com/question?id=4847342612119552

There are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is not hit. Write a program to see if all of the given tasks can be scheduled or not on the servers? 

Ex: 
Servers capacity limits: 8, 16, 8, 32 
Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8 
For this example, the program should say ‘true’. 

Ex2: 
Server capacity limits: 1, 3 
Task capacity needs: 4 
For this example, program should return false.

 

Flip bits in a range and print number of ‘1’s

http://churmura.com/algorithms/vmware-online-coding-test-for-us-recruitments-hyderabad-event/69549/

 

No. 16 – Maximal Length of Incremental Subsequences

Problem: Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

Reference: http://codercareer.blogspot.com/2011/10/no-16-maximum-length-of-incremental.html

 

No. 25 – Edit Distance

Reference: http://codercareer.blogspot.com/2011/12/no-25-edit-distance.html

Problem: Implement a function which gets the edit distance of two input strings. There are three types of edit operations: insertion, deletion and substitution. Edit distance is the minimal number of edit operations to modify a string from one to the other.

For example, the edit distance between “Saturday” and “Sunday” is 3, since the following three edit operations are required to modify one into the other:

  1. Saturday → Sturday (deletion of ‘a’)
  2. Sturday→ Surday (deletion of ‘t’)
  3. Surday → Sunday (substitution of ‘n’ for ‘r’)

There is no way to achieve it with fewer than three operations.

 

No. 43 – Minimal Number of Palindromes on a String

Problem: A string can be partitioned into some substrings, such that each substring is a palindrome. For example, there are a few strategies to split the string “abbab” into palindrome substrings, such as: “abba”|”b”, “a”|”b”|”bab” and “a”|”bb”|”a”|”b”.

Given a string str, please get the minimal numbers of splits to partition it into palindromes. The minimal number of splits to partition the string “abbab” into a set of palindromes is 1.

参考:http://codercareer.blogspot.com/2013/02/no-43-minimal-number-of-splits-on-string.html