Отказ от ответственности Журнал Заметки Галерея

Галерея

Как-то я задумался, что тестовые задания, которые требуют выполнять софтверные фирмы при приеме на работу, это много времени и труда, который пропадает даром. Действительно, созданный при этом программный код служит только для проверки знаний, но потом выбрасывается в мусор.

Чтобы как-то исправить эту несправедливость, я решил публиковать у себя на сайте решения подобных задач, а также просить авторов описывать процесс прохождения собеседования, чтобы кто-нибудь да мог воспользоваться полученным опытом и затраченными усилиями.

Ниже одна из таких статей.

Как я проходил собеседование на должность джава-программиста в фирме Luckyware Pro (с решением задачи)

Недавно мне довелось проходить собеседование на должность java-программиста в компании Luckyware Pro. Собеседование проходило в несколько этапов, каждый из которых тестировал определенные навыки из области программирования, владения иностранным языком и т.д.

1. Первый этап был очным. Мне позвонили и пригласили посетить офис компании для прохождения собеседования. В назначенный час я встретился с менеджером по персоналу, и с этого началось многоэтапное, как оказалось впоследствии, собеседование. После нескольких общих вопросов (где учусь, на каком курсе, почему выбрал эту работу и т.д.) мне выдали листик с тестовыми заданиями.

На листике было указан самый низкий уровень сложности, и задания действительно оказались весьма несложными. Большинство задач представляли собой фрагменты программного кода с вопросом, какое действие данная программа выполняет.После того, как я выполнил данные тестовые задания, мне предложили более высокий уровень сложности. Здесь вопросы были посложней, хотя суть оставалась примерно та же – указать результат выполнения программы, исправить ошибки в коде и т.д. Каких-то особых знаний языка задачи не проверяли, скорей решались логически (был, например, фрагмент кода, который вычислял простые числа). Ответив не на все вопросы, я отправился домой с не самыми оптимистичными ожиданиями, однако уже через несколько дней мне позвонили и сказали, что я прошел первый этап собеседования и теперь нужно готовиться ко второму.

2. Данный этап был заочным, и он же являлся самым трудоемким и времязатратным среди всех. На электронную почту мне пришла задача, решение к которой нужно было предоставить в виде работающей программы на java.

Полное условие задачи на английском:


Testing task

Testing task is to write a program according to the specification below.
Additionally it is needed to write a report in English for that task. The report would contain the task definition (functional specification), the description of implementation (design specification) and test instructions.
It can also contain installation instructions. All that and the source code of the program and everything needed to check it is to be sent by mail to us before the time specified separately.

It is expected the program to be written in Java 1.6.
The documentation should specify which environment was used to develop the program.

It is recommended to respect the specified requirements of the task. Every mismatch to the requirements should be proved. Pay attention to the style of coding and documentation. And, the main requirement is that the program must work correctly on various possible input data. 

The task

Program is console application that verifies if wall of some configuration can be constructed from some set of bricks. 

In the fig. 1 there is an example of wall configuration on the left side and a set of bricks on the right: 4 bricks of  length 1, 6 bricks of length 2 and 1 brick of length 3.


Fig. 1.

While building the wall bricks are to be always put horizontally; so a brick’s height is always 1.
Brick’s length can be from 1 to 8. The configuration of wall is not limited: it can break into several parts, can seem unstable, can have holes, etc.
As you can see from Fig 1, the wall in figure 1 can be built using the specified set of bricks.
One variant of doing that is shown.
In fig 2 there is an example when you cannot build the specified wall using the specified set of bricks.



The description of wall and bricks is presented in simple text format and can be read from file or from standard input. The result of verification is printed to standard output, either "yes" (wall can be constructed) or "no" (wall can not be constructed). The wall can have arbitrary shape, being basically just the number of linear blocks of various lengths. Each brick has the linear form and discrete length from 1 to 8.

The format for input data is as follows:
1: width and height of wall's shape matrix - two positive integers W and H separated by space on their own line.
2: wall's shape matrix - H strings each of length W, formed just of '1' and '0' symbols with every string on its own line.
3: the count of bricks' sorts - the positive integer C.
4: list of bricks - C lines each containing two positive integers separated by space - length of brick and count of such the bricks in the set.

Example of source data:
6 3
101101
111111
111111
3
1 4
2 6
3 1

Example of program output:

yes

Вот краткое описание:

Необходимо создать программу, которая проверяла бы, возможно ли составить стену определенной формы из заданного набора кирпичиков.

Вот простейший пример: слева показана форма стены, а справа – набор кирпичиков, которые есть в нашем распоряжении.

Кирпичики могут располагаться только горизонтально, то есть высота каждого всегда равна единице. Длина варьируется от 1 до 8. Форма стены не ограничена – она может быть разделена на несколько частей, может иметь просветы и т.д.

Описание стены и набора кирпичиков происходит в текстовой форме, в отдельном файле. Формат ввода данных следующий:

1. Ширина и высота стены, два числа больше 0, разделенные пробелами

2. Матрица стены, размером ширина на высоту. Матрица состоит из единиц и нулей, позиции с единицей при построении стены должны будут покрываться кирпичиками, позиции с нулем – пустые места.

3. Количество разных видов кирпичиков (цифра от 1 до 8).

4. Список кирпичиков - набор строчек, каждая из которых представляет собой два числа разделенных пробелом – длину кирпичика и количество таких деталей в нашем распоряжении.

Пример:


    6 3
    101101
    111111
    111111
    3
    1 4
    2 6
    3 1

На выходе программа должна печатать yes, если стена может быть собрана из данного набора кирпичиков и no, если, соответственно, невозможно собрать стену.

Данная задача была решена методом подбора, который осуществляется рекурсивной функцией. Перед осуществлением подбора проводится несколько проверок, которые служат для ускорения работы программы и уменьшения количества шагов, необходимых для построения стены.

Вначале проверяется, достаточно ли у нас кирпичиков, чтобы выстроить стену нужного размера, то есть суммарная длина нашего набора деталей сравнивается с площадью стены. Если кирпичиков в сумме меньше, чем нужно для построения стены, то программа сразу выводит no.

Дальше вся стена «разворачивается» в строку, так как высота всех кирпичиков равна единице, то мы в любом случае не сможем переносить детали с одного «этажа» стены на другой, а потому мы можем представить ее в виде линии с промежутками. В числовом виде данная линия превращается в массив, который хранит в виде целых чисел длины всех промежутков, которые необходимо заполнить кирпичиками (то есть позиций, обозначенных в матрице единицами).

Когда создан массив, представляющий форму стены, мы ищем совпадения между длинами промежутков в массиве и длинной отдельных кирпичиков из нашего набора. В случае совпадения (то есть мы нашли промежуток в три единицы, и у нас есть деталь длиной ровно три), мы немедленно размещаем данный кирпичик в указанный промежуток. Мы имеем право так поступать, потому как данный промежуток все равно должен быть в итоге заполнен, а заполнен он может быть двумя способами: деталью, точно совпадающей по размеру или более мелкими деталями. Но более мелкие детали могут нам пригодиться в случае если мы найдем более короткие промежутки (например, длиной два), а вот кирпичик длиной в три единицы туда уже не поместится. То есть, например, детали длиной 1 и 2 смогут заменить деталь длиной 3 на любой позиции, а вот деталь длиной 3 не везде заменит более мелкие кирпичики. Поэтому основной принцип в том, что при точном совпадении длины промежутка с длиной детали нужно немедленно размещать деталь в данный промежуток.

Функция, выполняющая вышеуказанную проверку, размещает часть деталей, и теперь остается только методом грубого подбора размещать оставшиеся детали, пока стена, наконец, не будет собрана. Это действие выполняется функцией placeOneElement() Если стену собрать так и не удалось, то программа выведет no. Если собрать удастся, то программа выведет, соответственно, yes.

Исходный код программы:


import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.regex.Pattern;


public class tst {
	
	public static int getIntegerFromString(String s, int index) //Function which parses given string to find
	//number in it. Index can be 1 or 2 which allows finding first or second integer in this string
	{	String substring;
		int spacePosition = s.indexOf(" ");
		if (spacePosition == -1) 
		{	if (index == 1) substring = s;
			else throw new IndexOutOfBoundsException("Index can be 1 or 2");
		}
		else
		{
			if(index == 1) substring=s.substring(0, spacePosition);
			else if(index == 2) substring=s.substring(spacePosition + 1);
			else throw new IndexOutOfBoundsException("Index can be 1 or 2");
		}	
		return Integer.parseInt(substring.trim());
	}
	
	public static void parseLine(String s) throws IOException //Function, which parses wall matrix's row to get
	//separated blocks of bricks from there. All blocks are wrote in the static array.
	{
		int gap = 0;
		for (int i = 0; i < s.length(); i++)
		{
			if (s.charAt(i) == '1') gap++;
			else if (s.charAt(i) == '0')
			{	
				if(gap > 0)
				{
					map[mapLen++] = gap;
					gap = 0;
				}
			}
			else throw new IOException("Wall format is incorrect");
		}
		if(gap > 0) map[mapLen++] = gap;	
	}
	public static void placeMatchingBlocks() //A function which places bricks into those gaps in the wall
	//which exactly match length of the brick
	{
		for(int i = 0; i < mapLen; i++)
		{
			int gapLen = map[i];
			if (gapLen <= maxBrickSize) {								
				if(bricks[gapLen - 1] > 0) {
					map[i] = 0;
					bricks[gapLen - 1]--;
					wallSizeInPixel -= gapLen;
				}	
			}
		}	
	}
		
	
	public static boolean isEnoughBlocks() //This function checks if we have enough block lengthen to build the wall
	{
		int pixelCount = 0;
		int pixelRequire = 0;
		
		for (int i = 0; i < maxBrickSize; i++) pixelCount += bricks[i] * (i + 1);//We sum all lengthens of bricks
		
		for (int i = 0; i < mapLen; i++) pixelRequire += map[i];//and all lengthens of gaps in the wall
		
		wallSizeInPixel = pixelRequire;
		
		return pixelCount >= pixelRequire;
	}
	public static void getDataFromFile (String filename) throws IOException //Function that reads necessary data
	//from the file
	{
		File file = new File(filename);
		BufferedReader reader = new BufferedReader(new FileReader(file));
		
		String line;
		line = reader.readLine().trim(); //We use trim() to work with data separated with too much spaces
		
		int width, height;
	    width = getIntegerFromString(line, 1); 
	    height = getIntegerFromString(line, 2);
	    
	    if(width <= 0 || height <= 0) 
	    {	
	    	reader.close();
	    	throw new IOException("your width or height are not positive numbers");
	    }
	    
	    map=new int[width * height]; //Create array with enough size to store matrix in line
	  
	    
		for(int i = 0; i < height; i++)
		{
			line = reader.readLine().trim();
			parseLine(line);	
		}
		
		line = reader.readLine().trim();
	    int count = getIntegerFromString(line, 1);
	    
		for (int i = 0; i < maxBrickSize; i++) bricks[i] = 0; //At start number of all bricks equals 0
		
	    while(count-- > 0) //then we read information about available bricks from the file
	    {
	    	line = reader.readLine().trim();
	    	int len = getIntegerFromString(line, 1);
	    	bricks[len - 1] = getIntegerFromString(line, 2);    	
	    }
	    
	    reader.close();
	}
	
	public static boolean placeOneElement(){ //Recursive function, which tries to build the wall by brute-force search
		
		for (int i = maxBrickSize - 1; i >= 0; i--)//It takes every brick starting with the longest one and tries
			//to place it somewhere, if there are available bricks of this kind
			//After brick is placed somewhere, function calls itself. If during the process of building
			//wall size becomes 0 it means that we built the wall and function returns true
			//If after full search wall wasn't built, function returns false
		{
			if (bricks[i] > 0)
			{
				for(int j = 0; j < mapLen; j++)
				{
					if(i+1 <= map[j]) 
					{
						map[j] -= (i + 1);
						bricks[i]--;
						wallSizeInPixel -= (i + 1);
						if(wallSizeInPixel == 0) return true;
						else 
						{
							if(placeOneElement()) return true;
							map[j] += (i + 1);
							bricks[i]++;
							wallSizeInPixel += (i + 1);
						}	
					}
				}
			
			}
		}
		return false;
	}
	
static int wallSizeInPixel; //Number of uncovered "1" in our wall matrix
static int[] bricks = new int[8]; //Array which contains number of available bricks. 
//Brick length matches array index+1
static int[] map; //Array which contains lengthens of all gaps in the wall
static int maxBrickSize = 8; //Constant which matches maximum available size of block
static int mapLen = 0; //Number of bricks in the wall

public static void main(String [] args)
{
	if (args.length != 1) { //Check if we have a file to open
		System.out.println("Using:  ");
		return;
	}
	try{
		getDataFromFile(args[0]); //Get necessary data from file
		
		if(!isEnoughBlocks()) System.out.println("No"); //Check if we have enough blocks to build the wall
		else
		{
			
			placeMatchingBlocks();	//Place blocks which exactly match bricks in the wall
			if(wallSizeInPixel == 0) System.out.println("Yes");	
			else if(placeOneElement()) System.out.println("Yes"); //Place the rest of blocks to build the wall
			else System.out.println("No"); //Print "No" in case we didn't finish the wall, 
		}
	} 
	catch(Exception e)
	{
		System.out.println(e.toString());
	}
}		


3. Через несколько дней после того как я отправил решение задачи, мне позвонили и пригласили поучаствовать в третьем этапе собеседования. Он тоже был заочным и достаточно мелким и быстро выполняемым. Нужно было узнать, сколько максимум мониторов может быть присоединено к определенному ноутбуку, и отправить ответ на электронную почту в течение 30 минут. Данный этап не создал какие-либо трудности, в такой форме лишь тестировали умение находить информацию в интернете.

4. Четвертый этап – проверка знаний английского языка. Данный этап уже был очным. Нужно было перевести текст с английского на русский, после чего было предложено прослушать минутный фрагмент речи на английском о новейших методах тестирования и пересказать его.

5. После прохождение четвертого этапа предстоял пятый, тоже очный. Задание по телефону не сообщили, а по пришествии в офис оказалось, что оно состоит в нахождение ошибок, предварительно внесенных в код программы, представленной на втором этапе. С данной задачей я справился не до конца, и, соответственно, могу лишь предполагать, существуют ли следующие этапы собеседования.

Через неделю после прохождения пятого этапа мне позвонили и сказали, что я не прошел данный этап собеседования и попросили прийти через год.

Дима, студент

< Еще

 
Реклама

www.alvis.com.ua
Котлы, водонагреватели, радиаторы и все необходимое для их установки

m-t.com.ua
Плитка, сантехника, низкие цены

www.rdsrv.org
Программа для удаленного администрирования компьютеров

журнал - заметки - галерея Все материалы на сайте являются собственностью автора © kuzmin@it.kharkov.ua +380504010794