저번에 타고난혀님께서 컴퓨터 프로그래밍에 열정이 많으신 것 같아서 제가 최근에 접한 흥미로운 프로그래밍 문제를 같이 공유해볼까 해서 글 올립니다.
혹시 별로 흥미없으시면 얘기해주세요. ^^ 이 문제는 제가 인터뷰 본 회사에서 가져온 문제입니다. 일단 전 프로그램 끝내고 보냈고요. 절대 다른 분의 도움을 받고자 하는것이 아닌 순수히 재미를 위해서 문제를 올립니다. 관심있으신분들도 한번 생각해보시면 재밌을거 같네요. ^^

The problem is to write a set of functions to manage a variable number of byte queues, each with variable length, in a small, fixed amount of memory. You should provide implementations of the following four functions:

Q * createQ(); //Creates a FIFO byte queue, returning a handle to it.
void destroyQ(Q * q); //Destroy an earlier created byte queue.
void enQ(Q * q, unsigned char b); //Adds a new byte to a queue.
unsigned char deQ(Q * q); //Pops the next byte off the FIFO queue.

So, the output from the following set of calls:

Q * q0 = createQ();
enQ(q0, 0);
enQ(q0, 1);
Q * q1 = createQ();
enQ(q1, 3);
enQ(q0, 2);
enQ(q1, 4);
printf(“%d”, deQ(q0));
printf(“%d\n”, deQ(q0));
enQ(q0, 5);
enQ(q1, 6);
printf(“%d”, deQ(q0));
printf(“%d\n”, deQ(q0));
destroyQ(q0);
printf(“%d”, deQ(q1));
printf(“%d”, deQ(q1));
printf(“%d\n”, deQ(q1));
destroyQ(q1);

should be:

0 1
2 5
3 4 6

You can define the type Q to be whatever you want.

Your code is not allowed to call malloc() or other heap management routines. Instead, all storage (other than local variables in your functions) should be done in a provided array:

unsigned char data[2048];

Memory efficiency is important. On average while your system is running, there will be a dozen or so queues with an average of 80 or so bytes in each queue. Your functions may be asked to create a larger number of queues with less bytes in each. Your functions may be asked to create a smaller number of queues with more bytes in each.

If you are unable to satisfy a request due to lack of memory, your code should call a provided failure function, which will not return:

void onOutOfMemory();

If the caller makes an illegal request, like attempting to deQ a byte from an empty queue, your code should call a provided failure function, which will not return:

void onIllegalOperation();

Worst-case performance when adding and removing bytes is more important than average-case performance.

There may be spikes in the number of queues allocated, or in the size of an individual queue. Your code should not assume a maximum number of bytes in a queue (other than that imposed by the total amount of memory available, of course!) You can assume that no more than 64 queues will be created at once.

참고로 다른분들도 아이디어 공유해도 됩니다. 다른분들의 의견도 같이 듣고 싶네요. ^^

이거들 너무 하신거 아니십니까?? 아 진짜 가뜩이나 지금 잃어 버린 기억 of 물리와 화학 펌프질 시키는것도 죽을맛인데 말이지요..

결국 펑션 구현 하는것인가요??..얼렁 인도인 친구 하나를 붙잡으로 고고..

전 Java로 짜보았습니다. 심심한 짜투리시간 잘보냈습니다.감솨~ㅋㅋ
Destory부분은 굳이 필요는 Java에선 필요는없겠지만, 그냥 요구하니까…
이 문제는 C를 위한것이었겠죠. -버그문의사절-

public class FIFO {

char[] data = new char[2048];
int pivot = 0;
/** Creates a new instance of FIFO */
protected FIFO() {
}

public static FIFO createQ() {
return new FIFO();
}

public static void destory(FIFO queue) {
queue.destoryData();
}

public static void enQ(FIFO queue, char b) {
queue.enQData(b);
}

public static char deQ(FIFO queue) {
return queue.deQData();
}

private char deQData() {
if (pivot<0) {
onIllegalOperation();
}
char first = data[0];
System.arraycopy(data,1,data,0,2046);
pivot–;
return first;
}

private void enQData(char b) {
if (pivot>=data.length)
onOutOfMemory();
data[pivot]=b;
pivot++;
}
/** execption handling*/
private void onIllegalOperation() throws IllegalArgumentException {
throw new IllegalArgumentException(“Illegal enQ”);
}
/** execption handling*/
private void onOutOfMemory() throws OutOfMemoryError {
throw new OutOfMemoryError(“Out of memory”);
}

private void destoryData() {
data=null;
}

public static void main(String[] str) {
FIFO q0 = FIFO.createQ();
FIFO.enQ(q0,’0′);
FIFO.enQ(q0,’1′);
FIFO q1 = FIFO.createQ();
FIFO.enQ(q1,’3′);
FIFO.enQ(q0,’2′);
FIFO.enQ(q1,’4′);
System.out.print(FIFO.deQ(q0));
System.out.println(FIFO.deQ(q0));
FIFO.enQ(q0,’5′);
FIFO.enQ(q1,’6′);
System.out.print(FIFO.deQ(q0));
System.out.println(FIFO.deQ(q0));
FIFO.destory(q0);
System.out.print(FIFO.deQ(q1));
System.out.print(FIFO.deQ(q1));
System.out.println(FIFO.deQ(q1));
FIFO.destory(q1);
}
}

넷빈님.^^ 틀린것 같습니다. 위에 보시면 동적으로 메모리를 할당하지 못한다고 되어 있습니다. 그리고 메모리 unsigned char data[2048] 안에서 큐가 생성되고 사라집니다. 메모리가 큐마다 똑같은 크기로 생성되고 파괴되고 그러면 안됩니다. 그래서 이문제가 첼링징 하죠..^^

헤헤헤..불합격이네..쩝.
감솨!ㅋㅋ 다음기회에 어플라이해야겠네요.

한번 나중에라도 생각해보세요.. 참 재밌는 문제인듯..저도 처음에 어떻게 할지 몰랐거든요..^^

몇분짜리 퀴즈였나요? 네, 나중에 다시 읽어볼께요. 회사일때문에 시간이 없어서….리~~(핑계..아땀난다…).

몇분짜리 퀴즈는 아니고요. 위에 적혀 있는대로 3시간정도안에 하라고 되어 있네요..저도 3시간안에는 못했지만..서리..제가 한 답도 맞는지 틀린지는 모릅니다. ^^

어이쿠..머리가 아프네요. 근데, 문제에있는 Q가 예전 학교에서 C배울때 나온 그 큐인가요? C나 C++ 프로그래밍하는 회사는 어플라이도 못하겠네요.

네 맞습니다. 싱크님.. FIFO(Fist input First output)입니다. 어느 한 언어를 확실히 알게되면 다른 언어도 금방 알게되는거 같더라고요. 싱크님도 일하게 되면 잘 하실겁니다. ^^

아, 그렇군요….그것도 기억이 가물가물해서…

와~ 다들 대단들 하시네요. 그래서 그 회사 붙으셨나요?

아뇨..^^..어제 이메일로 이문제가 도착해서 밤늦게까지 구현하고 그냥 잤습니다. 회사 붙는것과 상관없이 처음에 이문제가 이지 파이라고 생각했는데 자세히 읽어보니 만만치가 않더군요. 일단 요구 사항에 맞게 해서 보내긴 했는데 100프로 맞지는 않을거 같네요(요구사항을 하나 빼먹고 보냈어요..ㅠㅠ)..하여튼…사무엘님도 한번 해보세요. 재밌습니다. 이거말고 하나 더 있는데 그건 나중에..^^

예전의 모게임회사에서는 한시간을 주더니만, 둘중하나 코딩하라면서 Telnet서버와 Client를 만들고, 또하나는 Screen saver를 만들으라고 하더군요. 시간남는 사람은 두 개다 짜라고첨언이 있었는데요.

첫번째 문제를 시도하다가 1시간이 부족해서, 그냥 보냈던 기억납니다. 나중에 어떤분이 말하기를 그걸 둘다 한시간에 해결하는 사람도 있다하니, 경험있는 고수가 많다고 생각할수밖에 없겠단 생각이 들더군요. 그리고 그회사에서 연락없었습니다.ㅋㅋㅋ

예..출처가 게임회사입니다. ^^…저도 제가 만든 답이 맞다고 장담은 못하지만 아이디어는 맞는듯 합니다. ^^

여기에 게임 쪽 종사하는 분들도 꽤 있으신 것 같네요.

솔직히 정답이 궁금합니다. 헤헤..^^..트레이서님도 한번 도전을 해보심이..그럼 스트레스 해소가 되지 않을까요? 더 쌓일려나…헤헤..^^

저는 프로그래밍쪽에 손을 놓은지가 꽤 되서 이제는 소스만 보면 눈이 @.@ ; 답니다.
3일은 걸릴듯……

unsigned char data[2048]; 가 총 사용가능한 memory pool이고
Q object가 index와 length를 갖는 structure 변수라고 생각하고.
local 변수 endIndex = 0, numQ=0으로 setting하고

처음 Q를 만들면 Q* q= &data[endIndex] 가 되고 다음 사용가능한
endIndex는 endIndex += sizeof(Q)가 된다.
numQ++;

두번째 Q를 만들면 첫번째 Q의 데이터를 sizeof(Q) 만큼 move하고 q[0].start도 바꾸어 놓는다.

Q를 지울 때는 Q array를 shrink하고 나머지 data를 앞으로 옮겨 놓는다.

add할 때는 조작할 Q가 항상 맨 뒤로 move된 상태에서 endIndex뒤에서 add할 수 있게 만든다.
remove는 remove하자마자 Q table과 data를 앞으로 움직여 놓고 endIndex–하고

알고리즘님의 아이디어는 저랑 비슷한거 같네요. 근데 저기 index와 length의 데이터 타입이 unsigned char일경우 큐의 사이즈가 255 보다 클경우 문제가 있지 않을까요? 제가 이해한게 맞나요?

index와 length는 short이면 충분합니다. 그러면 sizeof(Q)는 4 bytes가 됩니다.
실제로는 data 맨 앞에 최대로 사용할 Q 만큼 Q array를 미리 잡아 놓고 쓰는게 효율적입니다.
그러면 endIndex = sizeof(Q)*maxQ;

전 일단 여분의 메모리를 하나 더 글로벌로 만들어서 알고리즘님처럼 각각의 큐의 정보를 저장하도록했었습니다. 시간이 많지 않으니 그렇게 fency하게 생각을 못하겠더군요. 제가 생각해보니 이문제의 키포인트는 split & merge가 아닌가 생각됩니다. 큐가 생기때 가장 빈공간을 가진 큐를 반으로 잘라 만들어내고 큐를 없앨때는 앞의 큐에다 합치는 동작이 키포인트였던것 같습니다. 알고리즘처럼 하나의 메모리에다 큐의 정보를 저장했어야 했는데 위의 64개의 큐가 맥시멈인것을 지나치고 구현하다보니 큐정보를 메모리 안에 넣는것을 생각못했네요. 역시 고수님들이 많군요. 좋은거 하나 배웠습니다. 감사합니다. ^^

곤플라이님// 뒤늦게 고백합니다..

솔직히 알고리듬..전혀 흥미로와지지가 않습니다요.. 제가 알고리듬 책 한권 읽어 버렸습니다(MIT에서 낸것도 봤지만) 항상 볼때마다.. 새롭습니다..

제가 생각하기엔 그걸 다 이해 하는 인간은 없을겁니다. 그냥 그런것이 있었구나 하고서는 실제 회사에선 그걸 이용하는 거지요. 저도 항상 볼때마다 새롭습니다. ^^…그럼 타고난혀님은 어느 분야에 흥미가 있으신지요?

저는 세상을 깜짝 놀라게할 프로그램에 흥미가 있습니다..힛힛..

제가 관심있는건 똑똑한 컴파일러 만들어서, 일반인들도 쉽게 프로그램을 만들수 있게 끌어 들이는 방법.. 아니면, 자동으로 특정값 범위내에서 다양한 조합으로 실행 가능한 바이너리 파일을 만들어 버리는 프로그램. 개인적으로 수학이 너무 저를 힘들게 해서, 수학을 없앨수 있는 방법이 없나..하고 삽질 중입니다..

그리고 밥벌어 먹기 위해서 어쩔수 없이 해야 하는건, 물리 엔진쪽 + 그래픽을 병합해야 할듯 하네요.

물리 + 수학 -_-..이 저를 괴롭힙니다.

ㅎㅎ..수학을 모르고도 프로그래밍으로 밥먹고 살수 있죠. 근데 physically based algorithm쪽으로 갈려면 수학모르면 먹고 살기 힘들죠.. 저도 수학을 많이 알지는 못하지만 그쪽에 재미를 느끼는데 머리가 안따가서 고생하고 있죠.(Linear, non-linear, ODE, FEM)ㅎㅎ..아주 머리 아프죠.

재미 있는 문제네요~ 알고리즘님 방식에서 조금만 더 고쳐 보겠습니다. ;

제가 이해한게 맞다면 알고리즘님 방식대로 하면 add 할때마다 조작하는 Q가 뒤로 움직이고 빈상태로 놔두니 앞에 빈공간이 좀 많이 생기겠지요.

메모리 efficiency 만을 따진다면 add 할때마다 data[endIndex] 에서 부터 원하는 position까지 다 뒤로 한칸씩 카피해주고 Q structure들을 업뎃해주면 더 좋을거 같습니다.

물론 이 방식은 알고리즘님것보단 add 할때 느려지겠지만 memory로 보자면 더 나을거 같군요..