Archive

Archive for March, 2010

Calculate week-day names for future date

March 24th, 2010 NamPham No comments

This is very very old problem I encountered when I was in high school. It is good to bring it back :)

Given current date with the week-day name i.e. 03/24/2010 Wednesday. Calculate the week-day names for future date ?

For example: what is the week-day name for 01/01/3999 ? (The answer is Friday)

The idea is simple: just calculate the number of days between two dates.
The small problem is how to come up with a clean algorithm to solve both case: same year or different years.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
#include <iostream>
using namespace std;
 
bool isLeapYear(int year){
	return (year % 4 == 0 && year%100 != 0 || year%400 == 0);
}
int main(){
	int cDay = 24,cMonth = 3,cYear = 2010,cWeekDay = 4-2;
	int fDay = 1,fMonth = 1,fYear = 2011,fWeekDay = 0;
	int months[] = {31,28,31,30,31,30,31,31,30,31,30,31};
	char* weekDays[] = {"Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};
	int cLeft = 0, fLeft = 0, totalDays = 0;
 
	//calculate the days left for current
	if (isLeapYear(cYear)) months[1] = 29;
	else months[1] = 28;
	cLeft = -cDay;
	for (int i = cMonth;i <= 11;i++)
		cLeft += months[i-1];
 
	//calculate the days left for future
	if (isLeapYear(fYear)) months[1] = 29;
	else months[1] = 28;
	fLeft = -fDay;
	for (int i = fMonth;i <= 11; i++)
		fLeft += months[i-1];
 
	//calculate the days between two years
	for (int year = cYear+1;year <= fYear;year ++) // <= fYear is important key !!!
		if (isLeapYear(year))
			totalDays += 366;
		else totalDays += 365;
 
	totalDays += cLeft - fLeft; // final formular
 
	fWeekDay = (cWeekDay + totalDays) % 7;
 
	cout << "Future WeekDay is " << weekDays[fWeekDay] << endl;
 
	system("pause");	
	return 0;
}
Categories: Algorithms, C/C++ Tags:

Format a string: remove redundant space characters

March 15th, 2010 NamPham 2 comments

Today, I came across one interesting question about string format:

“Format a string so that each word is separated each other by exactly one space. Also there is no preceding and trailing  spaces before the first and last word. Try to optimize it without using additional arrays, just some temporary variables.

For exampe:

“____________” -> “”

“ABCD” -> “ABCD”

“AB__CD” -> “AB_CD”

“______A__B______C_D______” -> “A_B_C_D”

My idea is using two indexes iterating through each character in a String. One index is just used to iterate each character. One index is keep track the length of format string.

Here is the sample code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//input: a String, convert it to array. 
//output: return formated String
        public String removeBlanks(String str){
		int strLength = str.length();
		char[] seq = new char[strLength+1];
		int length = -1;
		for (int i = 0; i < strLength; i++)
			if (str.charAt(i) != ' ' || (length >= 0 && seq[length] != ' '))
				seq[++length] = str.charAt(i);
 
		if (length == -1) return ""; // empty string
 
		if (seq[length] != ' ') 
			return new String(seq,0,length+1);
		else //remove trailing blank
			return new String(seq,0,length);
	}
Categories: Daily Life Tags:

How to compute the square root

March 12th, 2010 NamPham No comments

Hi,

I cam across the Wikipedia page talking about methods of computing square roots (here). Very interesting.

Here is a method that Babylonian used – so simple and clear to understand.

1. Given number n

2. Roughly approximate n1 ~ √n ( worst case n1 = n)

3. Repeat this step

n2 = n1;

n1 = (n2 + n/n2) / 2;

until |n1-n2| < eps

4. Return n1;

Read more…

Categories: Daily Life Tags: