[구인] C++ Senior Programmer

SK C&C E-PRJ팀에서는 C++ Senior Programmer를 모집합니다.

* 담당 업무
항공 사진을 이용한 3D Mirror World Production System 개발
cluster 로 이루어진 production system 에서 동작할 대용량 이미지 처리 s/w 구현

* 지원 자격 및 우대 사항
성별/연령/학력 불문

C++ 전문 개발 경력 5년 이상
C/C++ Expert
팀 작업에 익숙하고 다른 사람들과의 커뮤니케이션에 문제가 없는 자
영문 기술 문서 읽기에 익숙하신 분
다양한 상용/공개 라이브러리를 사용해본 경험자 우대
GIS/Computer Graphics/Computer Vision/Numerical Analysis 경험자 우대

* 대우
정직원

* 연봉
추후 협의

* 복리후생
연금/보험 : 국민연금, 고용보험, 산재보험, 건강보험
휴무/휴가 : 주5일 근무, 연차, 정기 휴가
보상 제도 : 인센티브제
건강관리 지원 : 건강검진, 본인 의료비 지원
생활안정 지원 : 자녀 학자금 지원, 직원대출제도
생활편의 지원 : 사원식당, 통근버스 운행
경조사 지원 : 각종 경조금, 경조휴가제
교육/여가 지원 : 자기계발비 지원
기타 : 사내 헬스 센터/의무실/어린이집 운영

* 전형 절차
기술 필기 -> 실무자 면접 -> 임원진 면접 -> 합격자 발표

* 기술 필기
다음의 문제 중 4문제 이상을 풀어 source code를 메일로 제출
C++ 을 사용할 것. STL/MFC 사용하지 말 것.

• The 3n + 1 problem
• Prime Ring Problem
  
• The Settlers of Catan
  
• Anagram
  
• Wormholes
• Re-connecting Computer Sites
• Password Search
• 2D Representations
• Telephone Directory Alphabetization
• Dividing up
• Overlapping Air Traffic Control Zones
• Caesar Cypher

* 제출 서류 (담당자에게 이메일 제출)
기술 필기 시험 결과 (program source code)
이력서
Project 경력 기술서

* 담당자













* 기타
E-PRJ팀은 개발자를 구인 중입니다. programming을 직접 하실 분만 지원 부탁드립니다. (PM 직군은 신규 채용 예정이 없습니다.)
문의 사항이 있으신 분은 담당자에게 연락 부탁드립니다.

회사 이메일 주소가 안되시는 분은 개인 이메일 주소 naraofbaram at gmail.com 으로 보내주시기 바랍니다.

[Job Offer] Program Manager

The SK C&C 3D Mirror World team is looking for program managers (PM) for creating a 3D virtual globe of the Earth. The successful PM has a graduate degree, preferable a PhD in a field closely related to the subject such as computer vision, photogrammetry, or GIS combined with 5+ years of relevant industry experience.

Expected are in-depth knowledge of digital image processing, digital photogrammetry, 2D and 3D geometry, multiple view geometry and a proven track record in developing software algorithm. Experience with true ortho-imagery, close range photogrammetry and oblique aerial imagery are especially relevant for this position.

To apply, please send resume and salary history/requirements in word/pdf documents to naraofbaram@skcc.com .

[Job Offer] C++ Senior Programmer

SK C&C, a Korean IT outsourcing and SI consulting company is seeking for Programmer / Senior Programmer for newly developing Earth Browser Project. The ideal applicant will be proficient in programming C++, specialized for Computer Vision / Photogrammetry. We are looking for a highly skilled, experienced, self-motivated and creative programmer who has solid coding, troubleshooting and analytical skills, an in-depth knowledge of C++ and who thrives on delivering unique solutions to customers within an advanced product incubation environment.

Requirements :

* Expert C++ programming skills

* 5+ years of professional software development

* MS or PhD in Computer Science, Applied Math or a related technical field

* Excellent verbal and written communication skills in English

* Self-motivation

Plusses :

* Expertise in developing state of the art 3D reconstruction algorithms from still photo or video data using a combination of computer vision and photogrammetric methodologies

* Familiarity with image processing, mapping, and geospatial technologies

* Graduate level study of computer vision, numerical analysis, and probability related disciplines

To apply, please send resume, salary history/requirements in word/pdf documents, and answers from following questions - from at least 3 questions - in plain text to naraofbaram@skcc.com .

• The 3n + 1 problem
• Prime Ring Problem
  
• The Settlers of Catan
  
• Anagram
  
• Wormholes
• Re-connecting Computer Sites
• Password Search
• 2D Representations
• Telephone Directory Alphabetization
• Dividing up
• Overlapping Air Traffic Control Zones
• Caesar Cypher

Re-connecting Computer Sites

Consider the problem of selecting a set T of high-speed lines for connecting N computer sites, from a universe of M high-speed lines each connecting a pair of computer sites. Each high-speed line has a given monthly cost, and the objective is to minimize the total cost of connecting the N computer sites, where the total cost is the sum of the cost of each line included in set T. Consider further that this problem has been solved earlier for the set of N computer sites and M high-speed lines, but that a few K new high-speed lines have recently become available.

Your objective is to compute the new set T' that may yield a cost lower than the original set T, due to the additional K new high-speed lines and when M+K high-speed lines are available.

Input

The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line.

The input is organized as follows:

• A line containing the number N of computer sites, with 1 <= N <= 1000000, and where each computer site is referred by a number i, 1 <= i <= N.
• The set T of previously chosen high-speed lines, consisting of N-1 lines, each describing a high-speed line, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers.
• A line containing the number K of new additional lines, 1 <= K <= 10.
• K lines, each describing a new high-speed line, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers.
• A line containing the number M of originally available high-speed lines, with N-1 <= M <= N (N-1) / 2.
• M lines, each describing one of the originally available high-speed lines, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The output file must have one line containing the original cost of connecting the Ncomputer sites with M high-speed lines and another line containing the new cost of connecting the N computer sites with M+K high-speed lines. If the new cost equals the original cost, the same value is written twice.

Sample Input

5 

1 2 5 

1 3 5 

1 4 5 

1 5 5 

1

2 3 2 

6 

1 2 5 

1 3 5 

1 4 5 

1 5 5 

3 4 8 

4 5 8 

Sample Output

20 

17 

Password Search

Being able to send encoded messages during World War II was very important to the Allies. The messages were always sent after being encoded with a known password. Having a fixed password was of course insecure, thus there was a need to change it frequently. However, a mechanism was necessary to send the new password. One of the mathematicians working in the cryptographic team had a clever idea that was to send the password hidden within the message itself. The interesting point was that the receiver of the message only had to know the size of the password and then search for the password within the received text.

A password with size N can be found by searching the text for the most frequent substring with N characters. After finding the password, all the substrings that coincide with the password are removed from the encoded text. Now, the password can be used to decode the message.

Problem

Your mission has been simplified as you are only requested to write a program that, given the size of the password and the encoded message, determines the password following the strategy given above.

To illustrate your task, consider the following example in which the password size is three (N=3) and the text message is just baababacb. The password would then be aba because this is the substring with size 3 that appears most often in the whole text (it appears twice) while the other six different substrings appear only once (baa ; aab ; bab ; bac ; acb).

Input

The input file contains several test cases, each of them consists of one line with the size of the password, 0 < N ≤10, followed by the text representing the encoded message. To simplify things, you can assume that the text only includes lower case letters.

Output

For each test case, your program should print as output a line with the password string.

Sample Input

3 baababacb 

Sample Output

aba   

2D Representations

2D Representations

Background

   A 2D raster image is defined by a matrix of points or pixels. In a black and white raster image, each pixel (a matrix element) can be black (full) or white (empty). There are several methods known to represent a raster image. Two of them, are the "Quadtree" and the "Run Length code".
   In a Quadtree, the matrix is preferably square with a length that is a power of two. One image is represented following a recursive visit: the image is divided in four image cells (accordingly to the order shown in Figure 1) and each cell is evaluated to be Full, Empty, or Partial. When a Partial cell is found, it is recursively subdivided in four cells and the same principle is repeated again and again until the cell is completely Full or completely Empty. The structure of a quadtree is a tree of nodes and each node can have from zero to four descendents (see Figure 1).

Figure 1 - One image, the order of visit and the quadtree

   In the Run Length code, pixels are grouped in series of empty pixels, full pixels and empty pixels again, etc. In this way, the image can be represented as a series of numbers, being each number of pixels in a group (we can assume that the first group is composed of full pixels). Using the image of Figure 1 as an example, the run length code is: 0, 20, 4, 4, 9, 1, 1, 1, 4, 1, 1, 2, 4, 4, 4, 4 (considering the lower left pixel as the first one).

Problem

   Given an image in the form of a quadtree, the problem is to obtain the correspondent run length code. The image maximum size is 256*256 and the origin of coordinates is the lower left pixel.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

   The first line of the input contains the length of the image and the second line contains the number of nodes Nto be considered (both in integer format). Each one of the following N lines describes a different node (in sequence, starting with node 1), with four fields separated by a space. Each field may be one character F (full) or E (empty) or a number that is the index of a descendent node.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

   One line with the run length code of the given image (integers separated by a space). Note that the first group is assumed to be Full.

Sample Input
1

8
5
E 2 F 3
E E F F
4 5 E E
F E E F
F E E E

Sample Output
0 20 4 4 9 1 1 1 4 1 1 2 4 4 4 4

 

Telephone Directory Alphabetization

Based on its success in contracting previous software development efforts to programming contest teams, the String & Tin Can (S&TC) Telephone Company has now decided to produce its telephone directories internally. Your team has been hired to develop a program that will take subscriber names and telephone numbers and alphabetize them into a list for printing.

Telephone directories have traditionally used special conventions for alphabetization, and S&TC wants your program to use these conventions. Each subscriber listing consists of one or more ``words,'' where each word is separated from the others by spaces or non-alphanumeric characters. Directories only use the letters A through Z for sorting, ignoring case. Therefore, names that include words comprised of digits or capital letters require special processing.

A listing may contain a word that is a decimal number. Listings with numbers in them appear in the alphabetized list in the same location they would if the numbers were spelled out in English. For example, ``50 Star Company'' might appear just before ``Fifty Star Vending'' in the list. Numbers are permitted to be in the range 0-999,999,999. Letters and digits will not appear together in the same word.

All special (non-alphanumeric) characters are to be treated as spaces. ``Penny-Wise Corporation'' would appear after ``Penny Saver,'' but before ``Pennypinching Company.'' Multiple spaces or non-alphanumeric characters are treated as a single space when sorting. Special characters will not appear at the beginning of a listing.

Words that are comprised of all capital letters are assumed to be initials or acronyms, and are treated as if spaces appeared between each letter. Hence, ``KAT Shop'' would appear at the beginning of the K listings, before ``K-B Enterprises'' and ``K Warehouse''.

Input 

Input to your program will be a list of subscribers, one per line. The first seven digits will be the telephone number, and the rest of the line will be the name of the subscriber as it is to appear in the telephone directory.

Output 

Your program is to alphabetically sort the subscriber names according to the rules above and print the listing in order. Each line should contain the subscriber name as it appeared in the input in the first 52 positions, left justified and space filled, followed by the seven digit telephone number (including a space between the third and fourth digits) in columns 56 through 63. The telephone number is to be immediately followed by the end of line.

Your program need not handle more than 1,000 subscribers-none of the towns S&TC serves in Swamp County have populations larger than that.

Sample Input 

8936251KAT Shop 

7362812Penny Saver, Inc. 

7251887Kate's Company 

8372974Fine Foods 

9273664Five Star Vending 

3523984K-B Enterprises 

723621899 Cents Only Store 

Sample Output 

Fine Foods                                             837 2974 

Five Star Vending                                      927 3664 

KAT Shop                                               893 6251 

K-B Enterprises                                        352 3984 

Kate's Company                                         725 1887 

99 Cents Only Store                                    723 6218 

Penny Saver, Inc.                                      736 2812 

Dividing up

Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbles so that each of them gets the same total value.

Unfortunately, they realize that it might be impossible to divide the marbles in this way (even if the total value of all marbles is even). For example, if there are one marble of value 1, one of value 3 and two of value 4, then they cannot be split into sets of equal value. So, they ask you to write a program that checks whether there is a fair partition of the marbles.

Input 

Each line in the input file describes one collection of marbles to be divided. The lines consist of six non-negative integers , where n_i is the number of marbles of value i. So, the example from above would be described by the input-line ``1 0 1 2 0 0''. The maximum total number of marbles will be 20000.

The last line of the input file will be ``0 0 0 0 0 0''; do not process this line.

Output 

For each colletcion, output ``Collection #k:'', where k is the number of the test case, and then either ``Can be divided.'' or ``Can't be divided.''.

Output a blank line after each test case.

Sample Input 

1 0 1 2 0 0 

1 0 0 0 1 1 

0 0 0 0 0 0 

Sample Output 

Collection #1: 

Can't be divided.  

Collection #2: 

Can be divided. 

Overlapping Air Traffic Control Zones

Optimization of air traffic flow is one of the essential ways for airlines to maintain economic viability. All too often, however, weather and other anomalous conditions disrupt air traffic flow resulting in significant costs. Automation systems for optimizing flows are not currently able to quickly reconfigure when path planning must account for dynamic conditions such as moving weather systems. Human intervention is usually used to decide route modifications.

Decisions on route modification for one aircraft must take into account neighboring aircraft safe zones in order to minimize possible collision risks. We will consider a 3D model in which the safe zone for one aircraft is represented as a parallelepiped.

Evaluation of aircraft collision risks, in this model, can be done by calculating the volume of the intersecting safe zones of the aircrafts in a given air traffic control zone. In other words, we need to be able to determine the volume of intersecting parallelepipeds.

Problem

Consider a number of parallelepipeds in space, having all the edges parallel to the axes. Your task is to write a program that outputs the volume occupied simultaneously by two or more parallelepipeds. Each parallelepiped is characterized by 6 integer values, the coordinates of two of its vertices

(x₁,y₁,z₁), (x₂, y₂,z₂) with x₁ < x₂, y₁ < y₂ and z₁ < z₂

Input

The input file contains several test cases, each of them consists of an integer 0 ≤ n ≥ 15 in the first line followed by n lines of 6-tuples of integers describing the parallelepipeds. The total area occupied does not exceed 5x10⁸.

Output

For each test case, output on a line by itself an integer corresponding to the total volume occupied simultaneously by two or more parallelepipeds.

Sample Input

  5
 1 1 3 3 3
   1 1 1 3 3 3
   1 1 1 3 3 3
   400000000 400000000 400000000 400000001 400000001 400000002
   400000000 400000000 400000000 400000002 400000004 400000001 

Sample Output

  9

Caesar Cypher

One of the earliest encrypting systems is attributed to Julius Caesar: if the letter to be encrypted is the Nth letter in the alphabet, replace it with the (N+K)th where K is some fixed integer (Caesar used K = 3). We usually treat a space as zero and all arithemtic is then done modulo 27. Thus for K = 1 the message `ATTACK AT DAWN' becomes `BUUBDLABUAEBXO'.

Decrypting such a message is trivial since one only needs to try 26 different values of K. This process is aided by knowledge of the language, since then one can determine when the decrypted text forms recognisable words. If one does not know the language, then a dictionary would be necessary.

Write a program that will read in a dictionary and some encrypted text, determine the value of K that was used, and then decrypt the cyphertext to produce the original message. The original message contained only letters and spaces and has been encrypted using the above method. The most suitable value of K will be the one which produces the most matches with the words in the dictionary.

Input 

Input will consist of a dictionary and the encrypted text. The dictionary will consist of no more than 100 lines each containing a word in uppercase characters and not more than 20 characters in length. The dictionary portion will be terminated by a line consisting of a single `#'. The encrypted text will follow immediately and will consist of a single line containing no more than 250 characters. Note that the dictionary will not necessarily contain all the words in the original text, although it will certainly contain a large portion of them. It may also contain words that are not in the original text. The dictionary will not appear in any particular order.

Output 

Output will consist of the decrypted text. Lines should be as long as possible, but not exceeding 60 characters and no word may cross a linebreak.

Sample Input 

THIS DAWN THAT THE ZORRO OTHER AT THING # BUUBDLA PSSPABUAEBXO 

Sample Output 

ATTACK ZORRO AT DAWN