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.

/* Copyleft: Ming Lin <minggr@gmail.com> */
/* http://www.careercup.com/question?id=5762415492857856 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX 300
int cache[MAX][MAX];

int postfix(char *expr, int i, int j)
{
	char c = expr[j];
	int min;
	int tmp;
	int k;

	if (cache[i][j] != -1)
		return cache[i][j];

	if (i == j) {
		if (expr[i] == '*') {
			cache[i][j] = 1;
			return cache[i][j];
		} else {
			cache[i][j] = 0;
			return cache[i][j];
		}
	}

	// why need?
	if (i + 1 == j) {
		if (expr[i] == '*' && expr[j] == '*') {
			cache[i][j] = 2;
			return cache[i][j];
		}
		if (expr[i] == '*' && expr[j] == 'X') {
			cache[i][j] = 1;
			return cache[i][j];
		}
		if (expr[i] == 'X' && expr[j] == '*') {
			cache[i][j] = 1;
			return cache[i][j];
		}
		if (expr[i] == 'X' && expr[j] == 'X') {
			cache[i][j] = 1;
			return cache[i][j];
		}
	}

	min = INT_MAX;
	if (c == '*') {
		for (k = i; k <= j-2; k++) {
			tmp = postfix(expr, i, k) + postfix(expr, k+1, j-1);
			if (tmp < min)
				min = tmp;
		}
	} else {
		//replace 'X' with '*'
		for (k = i; k <= j-2; k++) {
			tmp = postfix(expr, i, k) + postfix(expr, k+1, j-1) + 1;
			if (tmp < min)
				min = tmp;
		}

		//delete 'X'
		tmp = postfix(expr, i, j-1) + 1;
		if (tmp < min)
			min = tmp;

		//add '*'
		for (k = i; k <= j-1; k++) {
			tmp = postfix(expr, i, k) + postfix(expr, k+1, j) + 1;
			if (tmp < min)
				min = tmp;
		}
	}

	cache[i][j] = min;
	return cache[i][j];
}

void init_cache(void)
{
	int i, j;

	for (i = 0; i < MAX; i++)
		for (j = 0; j < MAX; j++)
			cache[i][j] = -1;
}

int main()
{
	char expr[MAX];
	int j;

	init_cache();
	
	while (1) {
		scanf("%s", expr);
		j = strlen(expr) - 1;
		printf("%d\n", postfix(expr, 0, j));
	}
	return 0;
}

 

题目

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

/* Copyleft: Ming Lin <minggr@gmail.com> */
/* Reference: http://www.algorithmist.com/index.php/UVa_108 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DIMENSION 2

int **alloc_prefix_matrix(int row, int col)
{
	int **two_d_array;
	int *data;
	int len;
	int r;
	int i;

	r = row - DIMENSION + 1;
	two_d_array = malloc(sizeof(int*) * r);	
	len = sizeof(int) * r * col;
	data = malloc(len);
	memset(data, 0, len);

	for (i = 0; i < r; i++)
		two_d_array[i] = data + i * col;

	return two_d_array;
}

/*
 * prefix sum: http://en.wikipedia.org/wiki/Prefix_sum
 */
void calculate_prefix_matrix(int matrix[3][5], int row, int col, int **prefix_matrix)
{
	int r, c;
	int i;

	for (c = 0; c < col; c++) {
		for (r = 0; r < row - DIMENSION + 1; r++) {
			if (r == 0) {
				for (i = 0; i < DIMENSION; i++)
					prefix_matrix[0][c] += matrix[i][c];
			} else
				prefix_matrix[r][c] = prefix_matrix[r-1][c] - matrix[r-1][c] + matrix[r+DIMENSION-1][c];
		}
	}
}

int max_sub_1d_array(int **prefix_matrix, int cur_row, int total_col)
{
	int max;
	int cur;
	int c;

	max = 0;
	for (c = 0; c < DIMENSION; c++) {
		max += prefix_matrix[cur_row][c];
	}
	cur = max;

	for (c = 1; c < total_col - DIMENSION + 1; c++) {
		cur = cur - prefix_matrix[cur_row][c-1] + prefix_matrix[cur_row][c+DIMENSION-1];
		if (cur > max)
			max = cur;
	}

	return max;
}

int max_sub_2d_array(int **prefix_matrix, int row, int col)
{
	int max;
	int r;

	max = max_sub_1d_array(prefix_matrix, 0, col);
	for (r = 1; r < row; r++) {
		int tmp = max_sub_1d_array(prefix_matrix, r, col);
		if (tmp > max)
			max = tmp;
	}

	return max;
}

int main()
{
	int matrix[3][5] = {{1, 2, 0, 3, 4}, {2, 3, 4, 5, 1}, {1, 1, 5, 3, 0}};
	int row = 3;
	int col = 5;
	int **prefix_matrix;
	int max;

	prefix_matrix = alloc_prefix_matrix(row, col);
	calculate_prefix_matrix(matrix, row, col, prefix_matrix);
	max = max_sub_2d_array(prefix_matrix, row - DIMENSION + 1, col);
	printf("max=%d\n", max);
	
	return 0;
}

 

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.

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NUM 8
int stack[NUM];
int top = -1;
#if 1
int server_capacity[NUM] = {8, 16, 8, 32};
int task_capacity[NUM] = {18, 4, 8, 4, 6, 6, 8, 8};
int servers = 4;
int tasks = 8;
#else
int server_capacity[NUM] = {1, 3};
int task_capacity[NUM] = {4};
int servers = 2;
int tasks = 1;
#endif

void dump_stack(void)
{
	int task, server;
	int i;

	for (i = 0; i <= top; i++) {
		task = i;
		server = stack[i];
		printf("(task %d(%d) -> server %d(%d))\n", task, task_capacity[task], server, server_capacity[server]);
	}
}

void dump_server(int n)
{
	int i;

	for (i = 0; i < n; i++)
		printf("%d ", server_capacity[i]);
	printf("\n");
}

int backtracing(int servers, int tasks, int s)
{
	int r = 0;
	int i;

	top++;	
	stack[top] = s;
	server_capacity[s] -= task_capacity[top];

	if (server_capacity[s] < 0)
		goto exit;

	if (top == tasks-1) {
		r = 1;
		goto exit;
	}

	for (i = 0; i < servers; i++) {
		r = backtracing(servers, tasks, i);
		if (r)
			break;
	}

exit:
	server_capacity[s] += task_capacity[top];
	top--;

	return r;
}

int main()
{
	int i;

	for (i = 0; i < servers; i++) {
		if (backtracing(servers, tasks, i)) {
			printf("true\n");
			dump_server(servers);
			top = tasks-1;
			dump_stack();
		}
	}

	return 0;
}

 

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/

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>

int count[100][100];

int flip_bits(int data[], int n)
{
	int len, i, j;
	int max = -1;
	int bits = 0;

	for (i = 0; i < n; i++)
		if (data[i] == 1)
			bits++;

	for (len = 1; len <= n; len++) {
		for (i = 0; i <= n-len; i++) {
			j = i+len-1;
			if (len == 1) {
				if (data[j] == 0)
					count[i][j] = bits + 1;
				else
					count[i][j] = bits - 1;
			} else {
				if (data[j] == 0)
					count[i][j] = count[i][j-1] + 1; 
				else
					count[i][j] = count[i][j-1] - 1; 
			}

			//printf("count[%d][%d]: %d\n", i, j, count[i][j]);
				
			if (max == -1 || count[i][j] > max)
				max =  count[i][j];
		}
	}

	return max;
}

int main()
{
	int data[] = {1, 0, 0, 1, 0, 0, 1, 0};
	int n = 8;

	printf("%d\n", flip_bits(data, n));

	return 0;
}

 

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

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>
#include <stdlib.h>

int maximal(int data[], int n)
{
	int *max;
	int i, j;
	int m, r;
	int cur;

	max = malloc(sizeof(int)*n);

	r = -1;
	max[0] = 1;
	for (i = 1; i < n; i++) {
		m = -1;
		for (j = 0; j < i; j++) {
			if (data[i] > data[j]) {
				cur = max[j] + 1;
			} else
				cur = 1;
			if (m == -1 || cur > m)
				m = cur;
		}
		max[i] = m;

		if (r == -1 || max[i] > r)
			r = max[i];
	}

	free(max);
	return r;
}

int main()
{
	int data[] = {7,2,3,1,5,8,9,6};
	int n = 8;

	printf("%d\n", maximal(data, n));

	return 0;
}

 

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.

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int **alloc_two_d(int row, int col)
{
	int **two_d;
	int i, j;

	two_d = malloc(sizeof(int*) * row);
	for (i = 0; i < row; i++)
		two_d[i] = malloc(sizeof(int) * col);

	for (i = 0; i < row; i++)
		for (j = 0; j < col; j++)
			two_d[i][j] = -1;

	return two_d;
}

int edit_distance(char *str1, char *str2)
{
	int **array;
	int len1, len2;
	int i, j;

	len1 = strlen(str1);
	len2 = strlen(str2);
	array = alloc_two_d(len1+1, len2+1);

	for (i = 0; i <= len1; i++) {
		for (j = 0; j <= len2; j++) {
			if (i == 0)
				array[i][j] = j;
			else if (j == 0)
				array[i][j] = i;
			else {
				if (str1[i-1] == str2[j-1])
					array[i][j] = array[i-1][j-1];
				else {
					int min;	

					min = array[i-1][j];
					if (array[i][j-1] < min)
						min = array[i][j-1];
					if (array[i-1][j-1] < min)
						min = array[i-1][j-1];
					
					array[i][j] = min + 1;
				}
			}
		}
	}

	return array[len1][len2];
}

int main()
{
	char *str1 = "Saturday";
	char *str2 = "Sunday";

	printf("%d\n", edit_distance(str1, str2));

	return 0;
}

 

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

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>

int is_palindrome(char *s, char *e)
{
	while (s < e) {
		if (*s != *e)
			return 0;
		s++;
		e--;
	}

	return 1;
}

void myprint(char *s, char *e, int n)
{
	while (s != e) {
		putchar(*s++);
	}
	printf(": %d\n", n);
}

int split(char *str)
{
	char *s1, *s2;
	char *p;
	int n;

	n = 0;
	p = str+1;
	s1 = str;
	s2 = NULL;
	while (*p) {
		myprint(str, p, n);
		if (s2 != NULL) {
			if (is_palindrome(s1, p)) {
				s2 = NULL;
				n--;
			} else if (is_palindrome(s2, p)) {
				/* do nothing */
			} else {
				s1 = s2;
				s2 = p;
				n++;
			}
		} else {
			if (is_palindrome(s1, p)) {
				/* do nothing */
			} else {
				s2 = p;
				n++;
			}
		}
		p++;
	}

	return n;
}

int main()
{
	char str[] = "abbabccddxx";

	printf("str %s, splits: %d\n", str, split(str));

	return 0;
}