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

Интревью проходило в виде LiveMeeting screencast и всегда состояло из 3 частей:

1. Рассказать про свои последние проекты, какие наиболее трудные задачи пришлось решать и т.п. - вобщем твой background.

2. Теоретические вопросы - тут можно ожидать чего угодно, но часто спрашивают .Net, ООП, паттерны программирования и многопоточное программирование.

3. Задача - необходимо в расшаренном окне notepada заимплементировать кукую-либо функцию. Вот как раз о таких задачах и пойдеи речь ниже. Все задачи из реальных интервью с авторской имплементацией.


Задача 1.

Дана сигнатура функции, которая по функционалу аналогична .Net String.LastIndexOf. Необходимо ее реализовать (язык C#, С++ на выбор). У string есть только два метода - .length и

Моя реализация ниже, из недостатков, которые вижу сейчас:
1. отсутствует try/catch
2. в блоке 'Args checking' лучше поменять местами строчки проверки аргуметов.

// TODO write comment
int find_last_of(string str, string substr)
{
#region Args checking

if (str == null) return -1;

if (String.isNullOrEmpty(substr)) throw new ArgumentException("substr", "string to search can't be null or empry")
// I consider we can use isNullOrEmpty (if not we can use null and .length<=0)

#endregion

for(int idxStr = str.length-substr.Lenght; idxStr >= 0; idxStr--)
{
bool isContains = true;

for(int idxSubstr = 0; idxSubstr < substr.Lenght; idxSubstr++)
{
// case sensitive search
if (str[idxStr+idxSubstr] != substr[idxSubstr])
{
isContains = false;
break;
}
}

if (isContains) return idxStr;
}

return -1;
}

Задача 2.

Implement the 2 following functions SearchForward and SearchBackward

string target = "this is a string which contains a text";
string pattern = "xyz"; // any pattern you choose
List listForward = SearchForward(pattern, target);
List listBackward = SearchBackward(pattern, target);

They must return a list of indices where the pattern are found in the target string
NOTE that when searching backward, I want to search the pattern backward as well
e.g. target = "sergey, sergey and yegres";
pattern = "sergey";
In this case, you will get
listForward = 0, 8
listBackward = 24

Решение

static List SearchForward(string pattern, string target)
{
List result = new List ();
int i = target.IndexOf(pattern);

while (i != -1)
{
result.Add(i);
i = target.IndexOf(pattern, i + 1);
}

return result;
}

static List SearchBackward(string pattern, string target)
{
char[] charArray = target.ToCharArray();
Array.Reverse(charArray);
string revertedTarget = new string(charArray);
List forwardResults = SearchForward(pattern, revertedTarget);
List result = new List ();
foreach (int i in forwardResults)
{
result.Add(target.Length - 1 - i);
}
return result;
}

Задача 3.

Необходимо заимплементировать очередь, которая содержит именна людей (максимальный размер - 100). В 90 % времени содержит 95 элементов.
Почти полный аналог моей задачи на другом интревью: Coding Question2: Implement a circular queue of integers of user-specified size using a simple array. Provide routines to initialize(), enqueue() and dequeue() the queue.

Решение

///
/// Implements CircularQueue
/// Thread safe
///
public class CircularQueue
{
///
/// Buffer used for queue elements
///
private int[] queue;

///
/// Queue head position
///
private int head;

///
/// Queue tail position
///
private int tail;

///
/// Current count of lements in queue
///
private int count;

///
/// Thread syhcjronization object
///
private object locker;

///
/// Ctr
///
/// Buffer size
public CircularQueue(int size)
{
try
{
initialize(size);
}
catch (Exception e)
{
//TODO: process exception
throw;
}
}

///
/// Performs queue initialization
///
/// Buffer size
private void initialize(int size)
{
try
{
queue = new int[size];
head = -1;
tail = -1;
count = 0;

locker = new object();
}
catch (Exception e)
{
//TODO: process exception
throw;
}
}

///
/// Enqueues value
///
/// Value to add to queue
public void enqueue(int value)
{
try
{
lock (locker)
{

if (count == queue.Length)
{
throw new ApplicationException("queue is full");
}

if (++tail >= queue.Length)
{
tail = 0;
}

queue[tail] = value;

count++;
}
}
catch (Exception e)
{
//TODO: process exception
throw;
}
}

///
/// Dequeues value
///
/// Queue head value
public int dequeue()
{
try
{
lock (locker)
{
if (count <= 0) { throw new ApplicationException("queue is empty"); } if (++head >= queue.Length)
{
head = 0;
}

count--;

return queue[head];
}
}
catch (Exception e)
{
//TODO: process exception
throw;
}
}
}

Надеюсь, кому-нибудь пригодится и удачи на интервью! :)

Чтение завершенной записи блога на http://feedproxy.google.com/~r/sgrebnov/~3/Amhe3TN7fnA/microsoft.html>

---

отправлено 08-09-2010 4:35 от Sergei Grebnov