Nam H. Pham

This is a very interesting question I found in CareerCup.com (link):

Given an unsorted array of n numbers, find the number that appears more than n/2 times. Do it in O(n) time and O(1) space.

First, I did not come up with the solution. The solution is described here.

Second, the idea is as follow: If there exists a major element M which appears more than n/2 times, all of the other elements can be paired with this element M. It means that if we crossed out each instance of element M with another element different from M, only instances of M are left.

In short, we need to maintain a counting variable count and a current candidate of major element M:

+ if count == 0 -> assign M to current element

+ else if M == current element -> count++

- else if M != current element -> count –;

After this loop, the candidate of major element is stored in M and it appears at least count time. Please note that M is only the element that seems to appear more than other elements. It does not mean it’s a major element. For example: given 1 2 3 -> M will be 3 which is not a major element.

Therefore, we need to count again all instances of element M to verify the number of occurrence is larger than n/2.

Here is the pseudo code for this algorithm:

FindMajorElement A[1..n]
//init
count = 1
M = A[1];

//find the candidate
for (int i = 2;i <= n;i++)
     if (count == 0) M = A[i];
     else if (A[i] == M) count++;
     else if count--;

count = 0; //reset the variable to number of instance M

//verify
for (int i = 1;i <= n;i++)      if (M == A[i]) count++; //return if (count >= n/2) return M
else return null;

That’s it

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

Hi,

Today I am trying to solve two interesting problems in String Permutations:

1. Generate all permutation of a string with assumption that all characters are unique.

2. Generate all permutation of a string without a “uniqueness” assumption like above.

Read more…