필기시험 문제 풀이: 5 텐 센트 필기시험 문제: 통계 포럼 온라인 인원수 분포

1669 단어 면접 필기시험
5 텐 센트 필기시험 문제: 통계 포럼 온라인 인원수 분포
한 포럼 의 온라인 인원 을 구 합 니 다. 만약 에 한 포럼 이 있다 고 가정 하면 등록 ID 는 2 억 개가 있 고 모든 ID 는 로그 인 에서 탈퇴 까지 로그 파일 에 로그 인 시간 과 종료 시간 을 기록 합 니 다. 알고리즘 을 써 서 하루 동안 포럼 의 사용자 온라인 분 포 를 통계 하고 샘플링 입도 가 초 입 니 다.
x 좌표 길이: 시간 은 초 단위 이 고 x 좌표 의 길 이 는 24 * 60 * 60 = 86400 이다.
y 좌표 길이: 2 억 명의 사용자, y 좌 표 는 최 장 2 억, int 는 최대 21 억 으로 int 로 계산 할 수 있 습 니 다.
배열 AR 로 통계: int [] ar = new int [86400];
로 그 는 시간 순 으로 기록 되 어 있 기 때문에 존재 하지 않 는 다 고 가정 할 수 있 습 니 다. 앞의 기록 은 뒤의 시간 보다 앞 선다 고 가정 할 수 있 습 니 다. 즉, 앞 을 초과 할 때 는 이전 시간 으로 간주 할 수 있 습 니 다.그러면 n + 1 초 는 n 초의 로그 인 l 을 빼 고 로그 인 k 를 추가 합 니 다.a [n + 1] = a [n] - m + k m 는 이 초 에 로그 인 하고 k 는 이 초 에 꺼 냅 니 다. n = 0 시, a [0] = 0 - m + k.
 
코드 작성 은 다음 과 같 습 니 다:
 
package com.chruan.test;

public class Online {
	private static final int LOGIN = 0;

	public static void main(String[] args) {

		statOnline();

	}
	/**
	 *           
	 * @return
	 */
	public static int[] statOnline() {
		int[] ar = new int[86400];
		int lasttime = -1;
		int onlineNum = 0;
		int idx = 0;
		int max=24*60*60;//86400;//     
		while (true) {
			if (idx >= max) {//   
				ar[max-1] = onlineNum;
				break;
			}
			int time = readTimeSec();//    [0-86400]
			int log = readLog();//login or logout
			while (idx < time) {//           
				ar[idx++] = onlineNum;
			}
			if (time > lasttime) {//       。
				if (idx == 0) {
					onlineNum = 0;
				} else
					onlineNum = ar[idx - 1];
				lasttime = time;
			}
			if (log == LOGIN) {//     
				onlineNum++;
			} else {
				onlineNum--;
			}
			idx++;
		}
		return ar;
	}
	

	private static int readTimeSec() {
		return 0;
	}
}

좋은 웹페이지 즐겨찾기