Программирование : Вопрос 1 : 17

Есть односвязный список. Каждый элемент списка содержит указатель на следующий элемент (next). Нам известен указатель на первый элемент списка (root). Необходимо без использования каких-либо дополнительных структур данных и без изменения структуры элементов списка определить зациклен ли данный список.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

public static boolean isCycleList(Item root){ 
        Item first = root;     
        while(first.getNext() != null){ 
            Item subFirst = root; 
            do { 
                if (subFirst == first.getNext()) 
                    return true; 
                subFirst = subFirst.getNext(); 
            } 
            while (subFirst != first.getNext());         
            first = first.getNext(); 
        } 
        return false; 
    } 

Есть односвязный список. Каждый элемент списка содержит указатель на следующий элемент (next). Нам известен указатель на первый элемент списка (root). Необходимо без использования каких-либо дополнительных структур данных и без изменения структуры элементов списка определить зациклен ли данный список.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

public static boolean isCycleList(Item root){ 
        Item first = root;     
        while(first.getNext() != null){ 
            Item subFirst = root; 
            do { 
                if (subFirst == first.getNext()) 
                    return true; 
                subFirst = subFirst.getNext(); 
            } 
            while (subFirst != first.getNext());         
            first = first.getNext(); 
        } 
        return false; 
    } 

Часто прямо спрашивают, как лучше всего посчитать сумму от 1 до n. Могут также ограничить/подсказать запретом на использование цикла.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Самый простой вариант, который приходит в голову - это с использованием цикла: (все примеры кода на Java)

public int sum(int n){ 
        int sum = 0; 
        for(int i=1;i<=n; i++) 
            sum+=i; 
        return sum; 
    } 


Но скорее всего (99%) такой ответ не прокатит. Проверяющему как правило нужен один из вариантов:

Вариант 1

 public int sum(int n){ 
        return n*(n+1)/2; 
}

Формула суммы n членов арифметической прогрессии. 3 арифметических действия вместо цикла. Лучше. Проще. Быстрее.

Вариант 2
Иногда проверяющий очень хочет увидеть...

 public int sum(int n){        
        return (n>1) ? n+sum(n-1): n; 
} 


Рекурсию!

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

Часто прямо спрашивают, как лучше всего посчитать сумму от 1 до n. Могут также ограничить/подсказать запретом на использование цикла.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Самый простой вариант, который приходит в голову - это с использованием цикла: (все примеры кода на Java)

public int sum(int n){ 
        int sum = 0; 
        for(int i=1;i<=n; i++) 
            sum+=i; 
        return sum; 
    } 


Но скорее всего (99%) такой ответ не прокатит. Проверяющему как правило нужен один из вариантов:

Вариант 1

 public int sum(int n){ 
        return n*(n+1)/2; 
}

Формула суммы n членов арифметической прогрессии. 3 арифметических действия вместо цикла. Лучше. Проще. Быстрее.

Вариант 2
Иногда проверяющий очень хочет увидеть...

 public int sum(int n){        
        return (n>1) ? n+sum(n-1): n; 
} 


Рекурсию!

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

Дан массив целых чисел, размерностью N: int[] m = new int[N], который заполнен числами от 1 до N в произвольном порядке. Из массива убрали одно число. Как за один проход по массиву определить, какое именно число убрали?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Проходим в цикле по массиву и считаем сумму его элементов. Зная, что в массиве находятся числа от 1 до N можем посчитать исходную сумму элементов массива. Найдя сумму элементов в массиве, вычитаем ее из исходной(сумма чисел от 1 до N). Получаем число, которое убрали.

public static int getRemoveItem(int[] arr, int capacity) { 
int arrSum = 0; 
int totalSum = 0; 
 
for(int i = 1; i <= capacity; i++){ 
totalSum += i; 
} 
for (int i = 0; i < arr.length; i++) { 
arrSum += arr[i]; 
} 
return totalSum - arrSum; 
} 

Дан массив целых чисел, размерностью N: int[] m = new int[N], который заполнен числами от 1 до N в произвольном порядке. Из массива убрали одно число. Как за один проход по массиву определить, какое именно число убрали?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Проходим в цикле по массиву и считаем сумму его элементов. Зная, что в массиве находятся числа от 1 до N можем посчитать исходную сумму элементов массива. Найдя сумму элементов в массиве, вычитаем ее из исходной(сумма чисел от 1 до N). Получаем число, которое убрали.

public static int getRemoveItem(int[] arr, int capacity) { 
int arrSum = 0; 
int totalSum = 0; 
 
for(int i = 1; i <= capacity; i++){ 
totalSum += i; 
} 
for (int i = 0; i < arr.length; i++) { 
arrSum += arr[i]; 
} 
return totalSum - arrSum; 
} 

Довольно популярная на собеседованиях задача - написать свою реализацию стандартной функции strrev.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Некоторые решают выделить новый буфер, что неэффективно. Вот одна из реализаций.

void strrev( char *string ) 
{ 
       //объявим указатель на конец строки 
       char *last = string[ strlen( string ) ]; 
        
       for( char temp; string != last && string != --last; string++ ) 
       { 
              temp = *string; 
              *string = *last; 
              *last = temp; 
       } 
} 


Часто дополнительным условием задачи является "...не используя буферную переменную". В таком случае решение такое:

void strrev( char *string ) 
{ 
       //объявим указатель на конец строки 
       char *last = string[ strlen( string ) ]; 
        
       for( ; string != last && string != --last; string++ ) 
       { 
              *string ^= *last; 
              *last ^= *string; 
              *string ^= *last; 
       } 
} 


В последнем случае приходится выполнять 3 операции присваивания, 3 операции копирования и 3 операции побитового исключающего или, когда как в первом примере всего 3 операции присваивания. Стоит ли потеря эффективности ( даже столь пустяковая ) экономии одного байта - вопрос спорный.

Довольно популярная на собеседованиях задача - написать свою реализацию стандартной функции strrev.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Некоторые решают выделить новый буфер, что неэффективно. Вот одна из реализаций.

void strrev( char *string ) 
{ 
       //объявим указатель на конец строки 
       char *last = string[ strlen( string ) ]; 
        
       for( char temp; string != last && string != --last; string++ ) 
       { 
              temp = *string; 
              *string = *last; 
              *last = temp; 
       } 
} 


Часто дополнительным условием задачи является "...не используя буферную переменную". В таком случае решение такое:

void strrev( char *string ) 
{ 
       //объявим указатель на конец строки 
       char *last = string[ strlen( string ) ]; 
        
       for( ; string != last && string != --last; string++ ) 
       { 
              *string ^= *last; 
              *last ^= *string; 
              *string ^= *last; 
       } 
} 


В последнем случае приходится выполнять 3 операции присваивания, 3 операции копирования и 3 операции побитового исключающего или, когда как в первом примере всего 3 операции присваивания. Стоит ли потеря эффективности ( даже столь пустяковая ) экономии одного байта - вопрос спорный.

Известно, что поезд едет по окружности. В каждом вагоне содержится выключатель(одновременно включатель) света. Вы очнулись в одном из вагонов и можете ходить из вагона в вагон, включать и выключать свет. Как определить замкнут поезд или нет? 

(Какие-либо данные о состоянии светильников в вагонах у вас априори отсутствуют)

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

int rightIndex = 0;
int leftIndex = 0;

1) пройти влево на один вагон относительно вагона, в котором герой очнулся, перевести свет в состояние "выкл", запомнить номер вагона leftIndex =-1 
пройти вправо на один вагон относительно вагона, в котором герой очнулся, перевести свет в состояние "вкл". rightIndex = 1

2)пройти влево на два вагона относительно вагона, в котором герой очнулся, перевести свет в состояние "выкл", запомнить номер вагона leftIndex =-2
пройти вправо на два вагона относительно вагона, в котором герой очнулся, перевести свет в состояние "вкл". rightIndex = 2

3) и т.д.
Действуя таким образом, герой либо доберется до конца поезда с одной из сторон, либо в уже пройденном месте обнаружит неправильное положение света.

Известно, что поезд едет по окружности. В каждом вагоне содержится выключатель(одновременно включатель) света. Вы очнулись в одном из вагонов и можете ходить из вагона в вагон, включать и выключать свет. Как определить замкнут поезд или нет? 

(Какие-либо данные о состоянии светильников в вагонах у вас априори отсутствуют)

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

int rightIndex = 0;
int leftIndex = 0;

1) пройти влево на один вагон относительно вагона, в котором герой очнулся, перевести свет в состояние "выкл", запомнить номер вагона leftIndex =-1 
пройти вправо на один вагон относительно вагона, в котором герой очнулся, перевести свет в состояние "вкл". rightIndex = 1

2)пройти влево на два вагона относительно вагона, в котором герой очнулся, перевести свет в состояние "выкл", запомнить номер вагона leftIndex =-2
пройти вправо на два вагона относительно вагона, в котором герой очнулся, перевести свет в состояние "вкл". rightIndex = 2

3) и т.д.
Действуя таким образом, герой либо доберется до конца поезда с одной из сторон, либо в уже пройденном месте обнаружит неправильное положение света.

Дана строка, состоящий из слов и пробелов. Необходимо в каждом слове N-ую букву заменить на symbol за один проход по входной строке

Пример
Входная строка 
Returns a new string that is substring of this string
N = 2;
simbol = '#'
Вывод 
R#turns a n#w s#ring t#at i# s#bstring o# t#is s#ring

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Пример кода программы на С#

  class Program 
    { 
        // Входная строка 
        private static string _inputString = "Returns a new string that is substring of this string"; 
        // Символ-разделитель  
        private static char _splitterChar = ' '; 
        // Индекс заменяемой буквы 
        private static int _n = 2; 
        // Символ замены 
        private static char _symbol = '#'; 
 
        // Entry point 
        static void Main(string[] args) 
        { 
            Console.WriteLine(Do(_inputString)); 
            Console.ReadKey(); 
        } 
 
        // Функция замены  
        private static string Do(string inputString) 
        {  // В С# строки являються неизменяемым тепом, поэтому помещаем входную строку в StringBuilder 
            var stringBilder = new StringBuilder(inputString); 
            // index - счетчик букв в слове 
            var index = 0; 
            // Цикл по всем символам строки 
            for (var i = 0; i < stringBilder.Length; i++) 
            { 
                index++; 
                // обнуление index если текущий символ - пробел. 
                if (stringBilder[i] == _splitterChar) index = 0;  
                if (index == _n) 
                {// Если index равен _n  - найдено место замены. 
                    stringBilder[i] = _symbol; 
                } 
            } 
            // возвращаем извлеченную из  StringBuilder строку 
            return stringBilder.ToString(); 
        } 
 
    }

Дана строка, состоящий из слов и пробелов. Необходимо в каждом слове N-ую букву заменить на symbol за один проход по входной строке

Пример
Входная строка 
Returns a new string that is substring of this string
N = 2;
simbol = '#'
Вывод 
R#turns a n#w s#ring t#at i# s#bstring o# t#is s#ring

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Пример кода программы на С#

  class Program 
    { 
        // Входная строка 
        private static string _inputString = "Returns a new string that is substring of this string"; 
        // Символ-разделитель  
        private static char _splitterChar = ' '; 
        // Индекс заменяемой буквы 
        private static int _n = 2; 
        // Символ замены 
        private static char _symbol = '#'; 
 
        // Entry point 
        static void Main(string[] args) 
        { 
            Console.WriteLine(Do(_inputString)); 
            Console.ReadKey(); 
        } 
 
        // Функция замены  
        private static string Do(string inputString) 
        {  // В С# строки являються неизменяемым тепом, поэтому помещаем входную строку в StringBuilder 
            var stringBilder = new StringBuilder(inputString); 
            // index - счетчик букв в слове 
            var index = 0; 
            // Цикл по всем символам строки 
            for (var i = 0; i < stringBilder.Length; i++) 
            { 
                index++; 
                // обнуление index если текущий символ - пробел. 
                if (stringBilder[i] == _splitterChar) index = 0;  
                if (index == _n) 
                {// Если index равен _n  - найдено место замены. 
                    stringBilder[i] = _symbol; 
                } 
            } 
            // возвращаем извлеченную из  StringBuilder строку 
            return stringBilder.ToString(); 
        } 
 
    }

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

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Перебираем элементы массива пока они четные, как только обнаруживается нечетный элемент начинаем поиск первого четного с конца. Находим, меняем местами. На с++ это будет выглядеть так:

void swap(int*, int*);  
void swap(int* left, int* right){  
  
    int tmp = *right;  
    *right = *left;  
    *left = tmp;  
}  
  
int main(int argc, const char * argv[])  
{  
    int inputArray[] = {1,2,3,4,5,6,7,8};  
    int* arrayLeft = inputArray;  
    int* arrayRight = arrayLeft+sizeof(inputArray)/sizeof(int) - 1;  
      
while(arrayLeft < arrayRight){  
        if ((*arrayLeft) % 2 != 0) {  
            while ((*arrayRight) %2 != 0 && arrayLeft < arrayRight ) {  
                arrayRight--;  
            }  
            swap(arrayLeft, arrayRight);  
        }  
        arrayLeft++;  
    }  
    return 0;  
} 

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

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Перебираем элементы массива пока они четные, как только обнаруживается нечетный элемент начинаем поиск первого четного с конца. Находим, меняем местами. На с++ это будет выглядеть так:

void swap(int*, int*);  
void swap(int* left, int* right){  
  
    int tmp = *right;  
    *right = *left;  
    *left = tmp;  
}  
  
int main(int argc, const char * argv[])  
{  
    int inputArray[] = {1,2,3,4,5,6,7,8};  
    int* arrayLeft = inputArray;  
    int* arrayRight = arrayLeft+sizeof(inputArray)/sizeof(int) - 1;  
      
while(arrayLeft < arrayRight){  
        if ((*arrayLeft) % 2 != 0) {  
            while ((*arrayRight) %2 != 0 && arrayLeft < arrayRight ) {  
                arrayRight--;  
            }  
            swap(arrayLeft, arrayRight);  
        }  
        arrayLeft++;  
    }  
    return 0;  
} 

Какой проект Вы считаете наиболее ценным в своей практике?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

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

Оцените свой опыт и выберите наиболее понравившийся Вам проект, который когда-либо делали: не обязательно большой, не обязательно идеально выполненный, просто ценный для Вас. И расскажите, чем он ценен.

Наиболее ценный для меня проект был связан с Java, но не был реализован средствами Java. 

При внедрении корпоративной Java-системы c базой данных на Oracle возникла задача по оперативному переносу данных из одной локальной установки системы в другую. 

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

Это было возможно, поскольку система позволяла хранить историю транзакций и их содержание. Запуск процесса переноса организовали в периоды наименьшей загрузки базы – в ночное время. В итоге, результаты действий, выполненных пользователями на одной локальной установке системы, транзакция за транзакцией переносились в базу и становились видны пользователям на другой локальной установке системы. Обрыв процесса не нарушал целостность данных и был возобновляемым.

Какой проект Вы считаете наиболее ценным в своей практике?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

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

Оцените свой опыт и выберите наиболее понравившийся Вам проект, который когда-либо делали: не обязательно большой, не обязательно идеально выполненный, просто ценный для Вас. И расскажите, чем он ценен.

Наиболее ценный для меня проект был связан с Java, но не был реализован средствами Java. 

При внедрении корпоративной Java-системы c базой данных на Oracle возникла задача по оперативному переносу данных из одной локальной установки системы в другую. 

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

Это было возможно, поскольку система позволяла хранить историю транзакций и их содержание. Запуск процесса переноса организовали в периоды наименьшей загрузки базы – в ночное время. В итоге, результаты действий, выполненных пользователями на одной локальной установке системы, транзакция за транзакцией переносились в базу и становились видны пользователям на другой локальной установке системы. Обрыв процесса не нарушал целостность данных и был возобновляемым.

Придумайте алгоритм поиска n-го с конца элемента односвязного списка, сложность которого будет равна O(N). Алгоритм не должен использовать дополнительные структуры - массивы, списки и т.д., только примитивные типы. 
Исходные данные: "голова" односвязного списка и индекс (с конца) искомого элемента.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Реализация на java:

class ListItem{ 
    public int value = 0; 
    public ListItem NextItem = null; 
} 
 
class Sulution{ 
    public static ListItem Search(ListItem StartItem, int OffsetFromEnd){ 
        ListItem OffsetedItem = StartItem; 
        do{ 
            if (OffsetFromEnd == 0){ 
                OffsetedItem = OffsetedItem.NextItem; 
            } else { 
                OffsetFromEnd--; 
            } 
            StartItem = StartItem.NextItem; 
        } while (StartItem.NextItem != null); 
        return OffsetedItem; 
    } 
} 

Придумайте алгоритм поиска n-го с конца элемента односвязного списка, сложность которого будет равна O(N). Алгоритм не должен использовать дополнительные структуры - массивы, списки и т.д., только примитивные типы. 
Исходные данные: "голова" односвязного списка и индекс (с конца) искомого элемента.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Реализация на java:

class ListItem{ 
    public int value = 0; 
    public ListItem NextItem = null; 
} 
 
class Sulution{ 
    public static ListItem Search(ListItem StartItem, int OffsetFromEnd){ 
        ListItem OffsetedItem = StartItem; 
        do{ 
            if (OffsetFromEnd == 0){ 
                OffsetedItem = OffsetedItem.NextItem; 
            } else { 
                OffsetFromEnd--; 
            } 
            StartItem = StartItem.NextItem; 
        } while (StartItem.NextItem != null); 
        return OffsetedItem; 
    } 
} 

Почему перебор двумерного массива выполняется быстрее по строкам, чем по столбцам? 
Например:

// быстрее 
for (int i = 0; i < cols; i++) { 
  for (int j = 0; j < rows; j++) { 
    myArray[i][j] = 0; 
  } 
}

// медленнее 
for (int j = 0; j < cols; j++) { 
  for (int i = 0; i < rows; i++) { 
    myArray[i][j] = 0; 
  } 
}

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:
 

Адрес массива уже лежит где-нибудь в ebp и чтение очередной ячейки это всего лишь грубо говоря ebp+8(например, для доступа к интовому array[1]), но вот последовательное чтение строками является, что называется cash-friendly кодом, т.е при таком способе чтении из памяти содержимое ближних ячеек уже находятся в кеше процессора, который "быстрее" основной памяти, а при чтении столбцами происходит так называемые cash-miss, т.к. процессор обращается к тому участку, значения которого нет в кеше, из-за чего её приходится загружать, увеличивая время на чтение очередной порции информации из ОЗУ. Естественно, чем больше кеш-промахов, тем больше времени занимает перебор массива.

Почему перебор двумерного массива выполняется быстрее по строкам, чем по столбцам? 
Например:

// быстрее 
for (int i = 0; i < cols; i++) { 
  for (int j = 0; j < rows; j++) { 
    myArray[i][j] = 0; 
  } 
}

// медленнее 
for (int j = 0; j < cols; j++) { 
  for (int i = 0; i < rows; i++) { 
    myArray[i][j] = 0; 
  } 
}

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:
 

Адрес массива уже лежит где-нибудь в ebp и чтение очередной ячейки это всего лишь грубо говоря ebp+8(например, для доступа к интовому array[1]), но вот последовательное чтение строками является, что называется cash-friendly кодом, т.е при таком способе чтении из памяти содержимое ближних ячеек уже находятся в кеше процессора, который "быстрее" основной памяти, а при чтении столбцами происходит так называемые cash-miss, т.к. процессор обращается к тому участку, значения которого нет в кеше, из-за чего её приходится загружать, увеличивая время на чтение очередной порции информации из ОЗУ. Естественно, чем больше кеш-промахов, тем больше времени занимает перебор массива.

Дан массив целых чисел, размера N: int[] m = new int[N], который заполнен числами от 1 до N в произвольном порядке. Из массива убрали два числа. Как за один проход по массиву определить, какие именно числа убрали?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

class Program 
    { 
        public static int[] def( int[] arr, int N ) 
        { 
            int  
                arrSum = 0, arrP = 1, 
                TotalSumm = (N + 1) * N / 2,  
                TotalP=1; 
            for (int i = 1; i <= N; i++) 
                TotalP *= i; 
            for (int i = 0; i < arr.Length; i++) 
            { 
                arrSum += arr[i]; 
                arrP *= arr[i]==0? 1:arr[i]; 
            } 
            int A_plus_B = TotalSumm - arrSum; 
            int A_na_B = TotalP / arrP; 
 
            int A =(int) (A_plus_B + Math.Sqrt( A_plus_B*A_plus_B - 4*A_na_B + 0.0 ) )/2; 
            int B = A_plus_B - A; 
            int[] ret = { A, B }; 
            return ret; 
        } 
 
        static void Main(string[] args) 
        { 
            int[] test = { 1,2,3,4,5,6,7,0,0,10 }; 
            int [] result = def(test,10); 
            Console.Write(result[0] + " is A, " + result[1] + " is B"); 
            Console.ReadKey(); 
        } 
    }

Дан массив целых чисел, размера N: int[] m = new int[N], который заполнен числами от 1 до N в произвольном порядке. Из массива убрали два числа. Как за один проход по массиву определить, какие именно числа убрали?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

class Program 
    { 
        public static int[] def( int[] arr, int N ) 
        { 
            int  
                arrSum = 0, arrP = 1, 
                TotalSumm = (N + 1) * N / 2,  
                TotalP=1; 
            for (int i = 1; i <= N; i++) 
                TotalP *= i; 
            for (int i = 0; i < arr.Length; i++) 
            { 
                arrSum += arr[i]; 
                arrP *= arr[i]==0? 1:arr[i]; 
            } 
            int A_plus_B = TotalSumm - arrSum; 
            int A_na_B = TotalP / arrP; 
 
            int A =(int) (A_plus_B + Math.Sqrt( A_plus_B*A_plus_B - 4*A_na_B + 0.0 ) )/2; 
            int B = A_plus_B - A; 
            int[] ret = { A, B }; 
            return ret; 
        } 
 
        static void Main(string[] args) 
        { 
            int[] test = { 1,2,3,4,5,6,7,0,0,10 }; 
            int [] result = def(test,10); 
            Console.Write(result[0] + " is A, " + result[1] + " is B"); 
            Console.ReadKey(); 
        } 
    }

Какова архитектура вашего приложения, из каких компонентов оно состоит и как они связаны между собой?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Отвечу на этот вопрос на примере корпоративной системы IBM Maximo версий 7.1, 7.5. 

Один, очевидный, компонент системы – это база данных (БД). В данном случае это БД под управлением СУБД Oracle или Db2. Используемые таблицы можно разделить на два класса: таблицы данных и таблицы метаданных. Таблицы метаданных содержат определение структуры таблиц данных. 

Второй очевидный компонент системы – это бизнес-логика приложения. В данном случае java-классы. Примеры выполнения бизнес-логики: проверка ссылочной целостности бизнес-объектов, поддержка прав доступа, сохранение целостности информации в агрегированных объектах и т.п. Приложение при своей работе разворачивается на сервере приложений. В данном случае используется сервер приложений WebSphere. Сервер приложений предоставляет приложению необходимые ресурсы для работы – такие как стандартные библиотеки, java-машину, оперативную память и т.п.

Между этими двумя уровнями располагается прослойка служебных java-классов, специализированных java-библиотек и драйверов СУБД, используемых для извлечения бизнес-объектов и их сохранения после проверки целостности и выполнения связанных процедур. 

Третий очевидный компонент системы – это интерфейс пользователя. В данном случае – это интерактивная страница, отображаемая в web-браузере. Так называемый «тонкий клиент». Практически, для работы пользователя используется только web-браузер и java-машина для исполнения инструкций (jre).

Между уровнями бизнес-логики и интерфейса пользователя располагается уровень, обслуживаемый web-сервером. В данном случае это Http-сервер. Web-сервер получает запросы от web-браузера, обрабатывает их, и передает в ответ страницу. В данном случае страница передается в формате java-скрипта, исполняемого в браузере. При обработке и формировании страницы web-сервер обращается к уровню бизнес-логики приложения.

Какова архитектура вашего приложения, из каких компонентов оно состоит и как они связаны между собой?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Отвечу на этот вопрос на примере корпоративной системы IBM Maximo версий 7.1, 7.5. 

Один, очевидный, компонент системы – это база данных (БД). В данном случае это БД под управлением СУБД Oracle или Db2. Используемые таблицы можно разделить на два класса: таблицы данных и таблицы метаданных. Таблицы метаданных содержат определение структуры таблиц данных. 

Второй очевидный компонент системы – это бизнес-логика приложения. В данном случае java-классы. Примеры выполнения бизнес-логики: проверка ссылочной целостности бизнес-объектов, поддержка прав доступа, сохранение целостности информации в агрегированных объектах и т.п. Приложение при своей работе разворачивается на сервере приложений. В данном случае используется сервер приложений WebSphere. Сервер приложений предоставляет приложению необходимые ресурсы для работы – такие как стандартные библиотеки, java-машину, оперативную память и т.п.

Между этими двумя уровнями располагается прослойка служебных java-классов, специализированных java-библиотек и драйверов СУБД, используемых для извлечения бизнес-объектов и их сохранения после проверки целостности и выполнения связанных процедур. 

Третий очевидный компонент системы – это интерфейс пользователя. В данном случае – это интерактивная страница, отображаемая в web-браузере. Так называемый «тонкий клиент». Практически, для работы пользователя используется только web-браузер и java-машина для исполнения инструкций (jre).

Между уровнями бизнес-логики и интерфейса пользователя располагается уровень, обслуживаемый web-сервером. В данном случае это Http-сервер. Web-сервер получает запросы от web-браузера, обрабатывает их, и передает в ответ страницу. В данном случае страница передается в формате java-скрипта, исполняемого в браузере. При обработке и формировании страницы web-сервер обращается к уровню бизнес-логики приложения.

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

1 -> 2 
2 -> 4 
3 -> 5 
4 -> 8 
5 -> 6 
6 -> 9 
7 -> 11 
8 -> 16 
9 -> 10 
10 -> 12 
11 -> 13 
12 -> 17 
13 -> 14 
14 -> 19 
15 -> 23 
16 -> 32 
17 -> 18 
18 -> 20 
19 -> 21 

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Идея одна, вариантов много. Вот несколько возможных решений, иллюстрирующих ее:

uint64_t y = (x+(x&(-x)))|(((x+(x&(-x)))^x)/((x&(-x))<<2)); 


uint64_t y = ((x|(x-1))+1)+((x&((((x|(x-1))+1)^(x|(x-1)))>>2))/(x&(-x))); 

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

1 -> 2 
2 -> 4 
3 -> 5 
4 -> 8 
5 -> 6 
6 -> 9 
7 -> 11 
8 -> 16 
9 -> 10 
10 -> 12 
11 -> 13 
12 -> 17 
13 -> 14 
14 -> 19 
15 -> 23 
16 -> 32 
17 -> 18 
18 -> 20 
19 -> 21 

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Идея одна, вариантов много. Вот несколько возможных решений, иллюстрирующих ее:

uint64_t y = (x+(x&(-x)))|(((x+(x&(-x)))^x)/((x&(-x))<<2)); 


uint64_t y = ((x|(x-1))+1)+((x&((((x|(x-1))+1)^(x|(x-1)))>>2))/(x&(-x))); 

Заменить вычисление вида:

if (value > 0xFF) value = 0xFF; 
else if (value < 0) value = 0; 

на выражение, не содержащее операторы условий. Размер value 4 байта.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

value = (((((value << 23) >> 31) | value) & 0xFF) & ~(value >> 31)) & 0xFF; 

Рассмотрим вычисления для трех случаев:
1) значение положительное не больше 1 байта
2) положительное и больше 1 байта
3) отрицательное

(value << 23) 

Для 1) будет просто сдвиг бит. Для 2) при сдвиге первый бит встанет на бит знака и значение становится отрицательным. Для 3) обычный сдвиг, значение остаётся отрицательным

((value << 23) >> 31) 

Для 1) всегда будет нулевое значение
Для 2) и 3) все биты будут заполнены 1, т.к. при сдвиге вправо отрицательного числа, биты сдвигаются и бит знака заново устанавливается в 1

((((value << 23) >> 31) | value) & 0xFF) 

Для 1) будет value
Для 2) и 3) будет 0xFF

& ~(value >> 31) 

Для 1) и 2) положительных значений все биты будут все 1
Для 3) отрицательное будет 0

Заменить вычисление вида:

if (value > 0xFF) value = 0xFF; 
else if (value < 0) value = 0; 

на выражение, не содержащее операторы условий. Размер value 4 байта.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

value = (((((value << 23) >> 31) | value) & 0xFF) & ~(value >> 31)) & 0xFF; 

Рассмотрим вычисления для трех случаев:
1) значение положительное не больше 1 байта
2) положительное и больше 1 байта
3) отрицательное

(value << 23) 

Для 1) будет просто сдвиг бит. Для 2) при сдвиге первый бит встанет на бит знака и значение становится отрицательным. Для 3) обычный сдвиг, значение остаётся отрицательным

((value << 23) >> 31) 

Для 1) всегда будет нулевое значение
Для 2) и 3) все биты будут заполнены 1, т.к. при сдвиге вправо отрицательного числа, биты сдвигаются и бит знака заново устанавливается в 1

((((value << 23) >> 31) | value) & 0xFF) 

Для 1) будет value
Для 2) и 3) будет 0xFF

& ~(value >> 31) 

Для 1) и 2) положительных значений все биты будут все 1
Для 3) отрицательное будет 0

Реализуйте алгоритм вывода всех подмножеств некоторого множества, заданного массивом. Длинна массива < 20.

Пример:
массив ["a","b","c"]
вывод
a
b
c
ab
ac
bc
abc 

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Код на C#

    class Program 
    { 
        static string[] strings = new[] { "a", "b", "c", "d", "e", "f"}; 
        static void Main(string[] args) 
        { 
            // вычисляем значение максимального разряда  
            //(max = 1000000 в двоичной, где количесто нолей - мощность множества) 
            var max = 1 << strings.Length; 
            for (var i = 1; i < max; i++) 
            { 
                var num = i; 
                // каждое число меньшее max имеет вид 0000..0(6 чисел).  
                // Эти 6 чисел будут исменяться в сумме представляя все возможные варианты перебора 
                for (int j = 0; j < strings.Length; j++) 
                { 
                    // если единица - выводим 
                    if ((num&1)==1) Console.Write(strings[j]); 
                    // смещаем на 1 (100101 => 10010) 
                    num >>= 1; 
 
                } 
                // пример 5 = 000101 = (справа налево) strings[0] + strings[2] = "ac" 
                Console.WriteLine(); 
            } 
            Console.ReadKey(); 
        } 
    }

Реализуйте алгоритм вывода всех подмножеств некоторого множества, заданного массивом. Длинна массива < 20.

Пример:
массив ["a","b","c"]
вывод
a
b
c
ab
ac
bc
abc 

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Код на C#

    class Program 
    { 
        static string[] strings = new[] { "a", "b", "c", "d", "e", "f"}; 
        static void Main(string[] args) 
        { 
            // вычисляем значение максимального разряда  
            //(max = 1000000 в двоичной, где количесто нолей - мощность множества) 
            var max = 1 << strings.Length; 
            for (var i = 1; i < max; i++) 
            { 
                var num = i; 
                // каждое число меньшее max имеет вид 0000..0(6 чисел).  
                // Эти 6 чисел будут исменяться в сумме представляя все возможные варианты перебора 
                for (int j = 0; j < strings.Length; j++) 
                { 
                    // если единица - выводим 
                    if ((num&1)==1) Console.Write(strings[j]); 
                    // смещаем на 1 (100101 => 10010) 
                    num >>= 1; 
 
                } 
                // пример 5 = 000101 = (справа налево) strings[0] + strings[2] = "ac" 
                Console.WriteLine(); 
            } 
            Console.ReadKey(); 
        } 
    }

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

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Допустим есть две переменные a и b. Необходимо поменять местами их значения не используя буффера. 

Вариант 1 (написан на Java):
a = a - b;
b = a + b;
a = b - a;

Вариант 2 (написан на Java):
a = a^b;
b = a^b;
a = a^b;

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

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Допустим есть две переменные a и b. Необходимо поменять местами их значения не используя буффера. 

Вариант 1 (написан на Java):
a = a - b;
b = a + b;
a = b - a;

Вариант 2 (написан на Java):
a = a^b;
b = a^b;
a = a^b;

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

MOV – передвинуть паровоз вправо на единицу длины. Время выполнения – 1 такт процессора.
GOTO<метка> – переход к метке. Время выполнения – 1 такт процессора.
IFSTOP<команда1>
<команда2> – Если под паровозом остановка, выполнить <команду1> иначе <команду2>. Время выполнения – 2 такт процессора.
В процессоры паровозов загружается одна и та же программа и по команде синхронно начинает выполняться.

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

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

1. MOV 
2. IFSTOP GOTO 4 
3. GOTO 1 //часть комманды ifstop 
4. MOV 
5. GOTO 4 

Пояснение: цикл в строках 1-3 будет выполняться на обоих паровозах, пока левый паровоз не наедет на остановку. Тогда в его процессоре начнет выполняться цикл в строках 4 – 5, а процессор в правом паровозе продолжит выполнять цикл 1 - 3. При этом левый паровоз на единицу длинны передвинется за 2 такта, правый за 4, откуда следует, что рано или поздно паровозы столкнутся.

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

MOV – передвинуть паровоз вправо на единицу длины. Время выполнения – 1 такт процессора.
GOTO<метка> – переход к метке. Время выполнения – 1 такт процессора.
IFSTOP<команда1>
<команда2> – Если под паровозом остановка, выполнить <команду1> иначе <команду2>. Время выполнения – 2 такт процессора.
В процессоры паровозов загружается одна и та же программа и по команде синхронно начинает выполняться.

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

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

1. MOV 
2. IFSTOP GOTO 4 
3. GOTO 1 //часть комманды ifstop 
4. MOV 
5. GOTO 4 

Пояснение: цикл в строках 1-3 будет выполняться на обоих паровозах, пока левый паровоз не наедет на остановку. Тогда в его процессоре начнет выполняться цикл в строках 4 – 5, а процессор в правом паровозе продолжит выполнять цикл 1 - 3. При этом левый паровоз на единицу длинны передвинется за 2 такта, правый за 4, откуда следует, что рано или поздно паровозы столкнутся.