Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm a little rusty with dates but here's a solution in Java. getLatestPeriodId() getPeriodDate() both run in O(1) - constant time. If the date range could span multiple years then getPeriodDate() is designed to run in O(log(n)) time where n is the number of days in the range

import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.Date;
import java.util.GregorianCalendar;
import java.util.TimeZone;

public class MerchantDateUtil {
	static SimpleDateFormat dateFormat = new SimpleDateFormat("MM/dd/yyyy");
	static boolean DEBUG = false;

	public static void main(String[] args) throws Exception {
		dateFormat.setTimeZone(TimeZone.getTimeZone("UTC"));
		Date start = (Date) dateFormat.parse("1/3/2016");
		int periodId = getLatestPeriodId(start);
		System.out.printf("Period Id for %s is %d\n", dateFormat.format(start), periodId);

		int p1 = 2, p2 = 47;
		Date[] dates = getPeriodDateRange(p1, p2);
		System.out.printf("Period date range %d to %d is %s to %s\n", p1, p2, dateFormat.format(dates[0]),
				dateFormat.format(dates[1]));
	}

	public static int getLatestPeriodId(Date d) {
		// DateFormat df2 = (DateFormat)dateFormat.clone();
		Calendar cal = (Calendar) dateFormat.getCalendar().clone();
		cal.setTime(d);

		if (DEBUG)
			System.out.printf("finding period for date: %s \n", dateFormat.format(cal.getTime()));

		// Determine the day of the week Sunday - 1..7 - Saturday
		int weekDay = cal.get(Calendar.DAY_OF_WEEK) % 7;

		// Determine the day of the year
		int yearDay = cal.get(Calendar.DAY_OF_YEAR);

		int monthNumber = cal.get(Calendar.MONTH) + 1;

		// The year looks like this XsXXXXXXs...XXsXX
		// Process it like this: .....XsXXXXXXs 
		// - Pad the beginning of the year with the Jan 1 day of week 
		// - subtract the day of week from the end
		// - Divide by 7 and that is the number of saturdays
		// Formulas:
		// s = (weekDay + yearDay - startDay) / 7 	=> Number of saturdays
		// ms = saturdayMonths(date) 				=> Months which start on a saturday
		// s + monthNumber - ms 					=> period number for the date
		int year = cal.get(Calendar.YEAR);

		// Get jan 1 day of week
		Calendar jan1DayOfYear = (Calendar) dateFormat.getCalendar().clone();
		jan1DayOfYear.set(year, 0, 1);
		int jan1DayOfWeek = jan1DayOfYear.get(Calendar.DAY_OF_WEEK); 

		int s = (jan1DayOfWeek % 7 + yearDay - weekDay) / 7;
		int ms = 0;

		for (int i = 0; i < monthNumber; i++) {
			cal.set(year, i, 1);
			ms += cal.get(Calendar.DAY_OF_WEEK) == Calendar.SATURDAY ? 1 : 0;
		}
		return s + monthNumber - ms;
	}

	public static Date getPeriodDate(int period) {
		// Leverage getLatestPeriodId and use a logarithmic search to find the
		// date for this period id. 
		Calendar cal = (Calendar) dateFormat.getCalendar().clone();
		int guess = 365 / 2, range = guess;
		int periodId = 0;
		while (periodId != period) {
			cal.set(Calendar.DAY_OF_YEAR, guess);
			periodId = getLatestPeriodId(cal.getTime());
			if (DEBUG)
				System.out.printf("Period: %d date:%s\n", periodId, dateFormat.format(cal.getTime()));
			range = range < 2 ? 1 : range / 2;
			guess += (periodId < period) ? range : -1 * range;
		}

		// Day of week can be anything so normalize it to the last saturday
		int weekDay = cal.get(Calendar.DAY_OF_WEEK);
		if (cal.get(Calendar.DAY_OF_MONTH) != 1)
			cal.add(Calendar.DAY_OF_YEAR, weekDay < Calendar.SATURDAY ? -1 * weekDay : 0);
		return cal.getTime();
	}

	public static Date[] getPeriodDateRange(int start, int end) {
		return new Date[] { getPeriodDate(start), getPeriodDate(end) };
	}
}

- Greg Purdy May 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a solution in Java. You can adapt it to C. I'm a little rusty with dates since all the new Calendar and TimeZone stuff was added to Java. getLatestPeriodId() getPeriodDate() both run in O(1) - constant time. If the date range could span multiple years then getPeriodDate() is designed to run in O(log(n)) time where n is the number of days in the range

import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.Date;
import java.util.GregorianCalendar;
import java.util.TimeZone;

public class MerchantDateUtil {
	static SimpleDateFormat dateFormat = new SimpleDateFormat("MM/dd/yyyy");
	static boolean DEBUG = false;

	public static void main(String[] args) throws Exception {
		dateFormat.setTimeZone(TimeZone.getTimeZone("UTC"));
		Date start = (Date) dateFormat.parse("1/3/2016");
		int periodId = getLatestPeriodId(start);
		System.out.printf("Period Id for %s is %d\n", dateFormat.format(start), periodId);

		int p1 = 2, p2 = 47;
		Date[] dates = getPeriodDateRange(p1, p2);
		System.out.printf("Period date range %d to %d is %s to %s\n", p1, p2, dateFormat.format(dates[0]),
				dateFormat.format(dates[1]));
	}

	public static int getLatestPeriodId(Date d) {
		// DateFormat df2 = (DateFormat)dateFormat.clone();
		Calendar cal = (Calendar) dateFormat.getCalendar().clone();
		cal.setTime(d);

		if (DEBUG)
			System.out.printf("finding period for date: %s \n", dateFormat.format(cal.getTime()));

		// Determine the day of the week Sunday - 1..7 - Saturday
		int weekDay = cal.get(Calendar.DAY_OF_WEEK) % 7;

		// Determine the day of the year
		int yearDay = cal.get(Calendar.DAY_OF_YEAR);

		int monthNumber = cal.get(Calendar.MONTH) + 1;

		// The year looks like this XsXXXXXXs...XXsXX
		// Process it like this: .....XsXXXXXXs 
		// - Pad the beginning of the year with the Jan 1 day of week 
		// - subtract the day of week from the end
		// - Divide by 7 and that is the number of saturdays
		// Formulas:
		// s = (weekDay + yearDay - startDay) / 7 	=> Number of saturdays
		// ms = saturdayMonths(date) 				=> Months which start on a saturday
		// s + monthNumber - ms 					=> period number for the date
		int year = cal.get(Calendar.YEAR);

		// Get jan 1 day of week
		Calendar jan1DayOfYear = (Calendar) dateFormat.getCalendar().clone();
		jan1DayOfYear.set(year, 0, 1);
		int jan1DayOfWeek = jan1DayOfYear.get(Calendar.DAY_OF_WEEK); 

		int s = (jan1DayOfWeek % 7 + yearDay - weekDay) / 7;
		int ms = 0;

		for (int i = 0; i < monthNumber; i++) {
			cal.set(year, i, 1);
			ms += cal.get(Calendar.DAY_OF_WEEK) == Calendar.SATURDAY ? 1 : 0;
		}
		return s + monthNumber - ms;
	}

	public static Date getPeriodDate(int period) {
		// Leverage getLatestPeriodId and use a logarithmic search to find the
		// date for this period id. 
		Calendar cal = (Calendar) dateFormat.getCalendar().clone();
		int guess = 365 / 2, range = guess;
		int periodId = 0;
		while (periodId != period) {
			cal.set(Calendar.DAY_OF_YEAR, guess);
			periodId = getLatestPeriodId(cal.getTime());
			if (DEBUG)
				System.out.printf("Period: %d date:%s\n", periodId, dateFormat.format(cal.getTime()));
			range = range < 2 ? 1 : range / 2;
			guess += (periodId < period) ? range : -1 * range;
		}

		// Day of week can be anything so normalize it to the last saturday
		int weekDay = cal.get(Calendar.DAY_OF_WEEK);
		if (cal.get(Calendar.DAY_OF_MONTH) != 1)
			cal.add(Calendar.DAY_OF_YEAR, weekDay < Calendar.SATURDAY ? -1 * weekDay : 0);
		return cal.getTime();
	}

	public static Date[] getPeriodDateRange(int start, int end) {
		return new Date[] { getPeriodDate(start), getPeriodDate(end) };
	}
}

- greg.purdy May 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry about the duplicates. Oh, BTW, since Oct 1 is a Saturday I subtract months that begin on a Saturday from the result using the counter named "ms":

for (int i = 0; i < monthNumber; i++) {
			cal.set(year, i, 1);
			ms += cal.get(Calendar.DAY_OF_WEEK) == Calendar.SATURDAY ? 1 : 0;
		}

- greg.purdy May 03, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More