Monthly Archives: July 2014

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;
}

 

No. 44 – Dynamic Programming on Stolen Values

Problem: There are n houses built in a line, each of which contains some value in it. A thief is going to steal the maximal value in these houses, but he cannot steal in two adjacent houses because the owner of a stolen house will tell his two neighbors on the left and right side. What is the maximal stolen value?

For example, if there are four houses with values {6, 1, 2, 7}, the maximal stolen value is 13 when the first and fourth houses are stolen.

参考:http://codercareer.blogspot.com/2013/02/no-44-maximal-stolen-values.html

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

#include <stdio.h>

int steal(int data[], int n)
{
	int stolen;
	int max;
	int i;

	max = data[0];
	stolen = 1;
	for (i = 1; i < n; i++) {
		if (stolen) {
			if (data[i] > data[i-1])
				max = max - data[i-1] + data[i];
			else
				stolen = 0;
		} else {
			max = max + data[i];
			stolen = 1;
		}
	}

	return max;
}

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

	printf("max steal: %d\n", steal(data, n));

	return 0;
}

 

No. 45 – Closest Node in a Binary Search Tree

Problem: Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k.

参考:http://codercareer.blogspot.com/2013/03/no-45-closest-node-in-binary-search-tree_2.html

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

#include <stdio.h>
#include "tree.h"

int distance(int i, int j)
{
	int d = i - j;

	if (d < 0)
		d = -d;

	return d;
}

struct node *closest_node(struct node *root, int key)
{
	struct node *n, *closest_n = NULL;
	int cur_d, min_d;

	cur_d = min_d = distance(root->data, key);

	n = root;
	while (n) {
		if (key == n->data)
			return n;

		cur_d = distance(n->data, key);
		if (n == root || cur_d < min_d) {
			min_d = cur_d;
			closest_n = n;
		}

		if (key > n->data)
			n = n->right;
		else
			n = n->left;
	}

	return closest_n;
}

int main()
{
	struct node *root, *closest;
	int postorder[] = {14, 21, 25, 31, 28, 24, 39, 36, 47, 41, 32};
	int n = 11;
	int key = 29;

	root = construct_bst(postorder, 0, n-1);	
	closest = closest_node(root, key);
	printf("key %d, closest %d\n", key, closest->data);

	return 0;
}

 

 

No. 46 – Nodes with Sum in a Binary Search Tree

Problem: Given a binary search tree, please check whether there are two nodes in it whose sum equals a given value.

参考:http://codercareer.blogspot.com/2013/03/no-46-nodes-with-sum-in-binary-search.html

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

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

struct stack {
	struct node **s;
	int top;
};

struct stack *stack_l, *stack_r;

struct node *most_left(struct node *root)
{
	struct node *n = root;

	while (n) {
		stack_l->s[stack_l->top++] = n;
		n = n->left;	
	}

	return n;
}

struct node *most_right(struct node *root)
{
	struct node *n = root;

	while (n) {
		stack_r->s[stack_r->top++] = n;
		n = n->right;	
	}

	return n;
}

int height(struct node *root)
{
	int l, r;

	if (!root)
		return 0;

	l = height(root->left);
	r = height(root->right);

	if (l > r)
		return l+1;
	else
		return r+1;
}

void init_stack(struct node *root)
{
	int h = height(root);

	stack_l = malloc(sizeof(struct stack));
	stack_r = malloc(sizeof(struct stack));
	stack_l->s = malloc(h * sizeof(struct node *));
	stack_r->s = malloc(h * sizeof(struct node *));
	stack_l->top = stack_r->top = 0;

	most_left(root);
	most_right(root);
}

struct node *next(struct stack *s)
{
	struct node *n;

	n = s->s[s->top-1];
	s->top--;

	n = n->right;
	while (n) {
		s->s[s->top++] = n;
		n = n->left;
	}

	if (s->top == 0)
		return NULL;
	else
		return s->s[s->top-1];
}

struct node *prev(struct stack *s)
{
	struct node *n;

	n = s->s[s->top-1];
	s->top--;

	n = n->left;
	while (n) {
		s->s[s->top++] = n;
		n = n->right;
	}

	if (s->top == 0)
		return NULL;
	else
		return s->s[s->top-1];
}

void print_next(struct stack *s)
{
	struct node *n;

	n = s->s[s->top - 1];
	do {
		printf("%d ", n->data); 
	} while (n = next(s));
	printf("\n");
}

void print_prev(struct stack *s)
{
	struct node *n;

	n = s->s[s->top - 1];
	do {
		printf("%d ", n->data); 
	} while (n = prev(s));
	printf("\n");
}

void sum(struct stack *ls, struct stack *rs, int k)
{
	struct node *ln, *rn;

	ln = ls->s[ls->top-1];
	rn = rs->s[rs->top-1];

	while (ln != rn) {
		if (ln->data + rn->data == k) {
			printf("key %d: %d + %d\n", k, ln->data, rn->data);
			break;
		}

		if (ln->data + rn->data > k)
			rn = prev(rs);
		else
			ln = next(ls);
	}

	if (ln == rn)
		printf("key %d: sum not found\n", k);
}

int main()
{
	struct node *root;
	int postorder[] = {5,7,6,9,11,10,8};
	int n = 7;
	int key;

	root = construct_bst(postorder, 0, n-1);

	print_tree(root);
	printf("\n");
	init_stack(root);
	//print_next(stack_l);
	//print_prev(stack_r);

	key = 22;
	sum(stack_l, stack_r, key);

	return 0;
}