#preinterview 1

5 questions from preinterview 1

1.md

Дана функция (статический метод) на языке Java:
[Given a function (static method) in java:]

static int myfunc(int[] a) {
     int x = 0;
     for (int i = 0; i < a.length; i++) {
	 for (int j = i; j < a.length; j++) {
	     if (a[j] != a[i]) {
		 if (j - i > x) {
		     x = j - i;
		 }
		 i = j - 1;
		 break;
	     }
	 }
     }
     return x;
}

Q: Что делает эта функция?
Q: [What does this function do?]
A: Функция ищет максимальную длину непрерывной последовательности одинаковых элементов в массиве.
A: [Function finds maximum length of continuous sequence of equals elements in given array.]

Q: Какая у неё алгоритмическая сложность?
Q: [What is its algorithmic complexity?]
A: O(n(n+1)/2) => O(n^2)

Q: Есть ли в этой функции логические дефекты? Если да, то какие?
Q: [Does this function have logical defects? If so, which ones?]
A: Да, есть:
Функция возвращает 0, если массив состоит из одинаковых элементов, в этом случае логичнее возвращать длину массива.
Не корректное определение максимальной длины последовательности при ее расположении в конце массива.
A: [Yes it has.]
[Funtion returns 0, if input array countains only equal elements. In this case is more logical to return the length of input array.]
[Incorrect calculation of maximum length of sequence, if its localted at the end of array.]

Q: Можно ли как-то улучшить данный код? Если да, напишите улучшенный вариант.
Q: [Can this code be improved? If so, write an imporev version.]
A: see https://github.com/vnmtwo/Tasks/blob/master/Tasks/ArrayOperations.cs
method: public static int MaxEqualSequenceLength<T>(T[] array)

 static int myfunc(int[] a) {
    int v=a[0];
    int maxc=1;
    int c=1;
   
    for (int i=1; i<a.length; i++){
        if (a[i]==v) c++;
        else{
            v=a[i];
            if (maxc<c) maxc=c;
            c=1;
        }
    }
   
    if (maxc>c) return maxc;
    else return c;
 }

Q: Какая алгоритмическая сложность у вашего варианта?
Q: [What is the algoritmic complexity of your version?]
A: O(n)

2.md

Q: Даны векторы A и B с координатами, соответственно, (x1, y1, z1) и (x2, y2, z2). Как узнать, перпендикулярны ли они друг другу?
Q: [Given vectors A and B with corresponded coordinates (x1, y1, z1) и (x2, y2, z2). How do you know if they are perpendicular to each other?]

A: Проверить, равно ли скалярное произведение этих векторов нулю.
x1x2 + y1y2 + z1z2 = 0;
A: [Check if the scalar product of these vectors is equal to 0.]
[x1x2 + y1y2 + z1z2 = 0;]

3.md

Q: Один поезд выехал из пункта А в пункт Б, одновременно с ним другой поезд выехал из пункта Б в пункт А. Поезда двигаются с постоянными скоростями. Они встретились в 15 часов, машинисты на ходу помахали друг другу из окон, и продолжили двигаться к своим конечным пунктам. Первый поезд доехал до своего пункта назначения через 9 часов после встречи, а второй до своего - через 16 часов после встречи. Во сколько они стартовали?
Q: [One train left point A for point B, at the same time another train left point B for point A. Trains move at constant speeds. They met at 15 o'clock, the machinists waved to each other from the windows on the move, and continued to move towards their final destinations.] [The first train reached its destination 9 hours after the meeting, and the second reached its destination 16 hours after the meeting. What time did they start?]

A:
Скорости поездов: V1, V2
Путь А-Б: S
Время от начала движения до встречи: x
Составим систему уравнений:

V1 = S/(x+9)
V2 = S/(x+16)
S = V1x+V2x

Решив систему уравнений получаем x = 12
Ответ: в 3 часа.

A:
Train speeds: V1, V2
Distance A-B: S
Time from start to meeting: x
Let compose systemof equations:

V1 = S/(x+9)
V2 = S/(x+16)
S = V1x+V2x

Solved the system of equations, we get x = 12
Answer: at 3 o'clock.

4.md

Q: Казино предлагает вам сыграть в игру: вы бросаете два 6-гранных игральных кубика, и получаете приз в зависимости от выпавшей на них суммы очков:
12 очков: 100 рублей
11 очков: 90 рублей
10 очков: 80 рублей
9 очков: 50 рублей
от 2 до 8 очков: 0 рублей
Сколько вы согласны заплатить за возможность один раз сыграть в такую игру?
Q: The casino invites you to play a game: you roll two 6-sided dice and get a prize depending on the amount of points that fell on them: 12 points: 100 rubles 11 points: 90 rubles 10 points: 80 rubles 9 points: 50 rubles from 2 to 8 points: 0 rubles How much are you willing to pay for the opportunity to play such a game once?

A: При условии игры один раз (в жизни) шанс потерять ставку равен 26/36 = 0,72. Это достаточно большой шанс, я согласен заплатить 0 рублей за такую игру. Если я неправильно понял задачу и можно сыграть несколько раз, то можно надеяться на теорию вероятностей. Рассчитаем мат. ожидание выигрыша:
(1/36)*100+(2/36)*90+(3/36)*80+(4/36)*50 = 20
Таким образом, чтобы выиграть, плата за игру должна быть меньше 20 рублей.

A: Under the condition of playing once (in life), the chance of losing the bet is 26/36 = 0,72. This is a fairly big chance, I agree to pay 0 rubles for such a game.
If I misunderstood the problem and you can play several times, then you can rely on the theory of probability. Let's calculate math. expectation of winning:
(1/36)*100+(2/36)*90+(3/36)*80+(4/36)*50 = 20
Thus, in order to win, the bet must be less than 20 rubles.

5.md

Q: Напишите функцию, которая принимает на вход массив строк, и возвращает такой же массив, но без тех строк, которых в исходном массиве было чётное количество. Решение должно быть оптимизировано по скорости работы. Писать можно на любом из популярных высокоуровневых языков программирования (выбранный язык нужно указать).
Q: Write the function that takes an array of strings as input and returns the same array, but without the strings that are in the original array there was an even number. The solution must be optimized for speed. You can write in any of the popular high-level programming languages (the selected language must be specified).

A: see https://github.com/vnmtwo/Tasks/blob/master/Tasks/ArrayOperations.cs
method: public static T[] RemoveEvenCounted<T>(T[] array)

С#  (.Net Standard 1.0 +) 
static string[] RemoveEvenCounted(string[] a)
{
    Dictionary<string, bool> d = new Dictionary<string, bool>(a.Length);

    for (int i=0; i<a.Length; i++) // O(n)
    {
        if (d.ContainsKey(a[i])) // O(1)
            d[a[i]]=!d[a[i]];
        else
            d.Add(a[i], true); // O(1)      
    }

    string[] output = new string[a.Length];
    int n = 0;

    for (int i = 0; i < a.Length; i++) //O(n)
    {
        if (d[a[i]]) //O(1)
            output[n++] = a[i];
    }

    Array.Resize(ref output, n); //O(n)

    return output;
}

Q: Оцените алгоритмическую сложность своей реализации.
Q: Assess the algorithmic complexity of your implementation.
A: O(3n) => O(n)