понедельник, 23 марта 2009 г.

реализовать atoi на интервью

на developers.org.ua заметил впечатления от проходжения интервью в R&D центр самсунга в Киеве, если опустить общее негативное впечатление програмера от самого процесса, и то что судя по цифрам набрать они пытаються по-дешевле,то из интересного там упоминание одного из вопросов - написать atoi на бумажке,
Вот мой вариант сделаный на коленках (проверка на переполнение опущена) в основном из спортивного интереса(своеобразная разминка от багфиксинга). Алгоритм - первое что пришло в голову, возможно есть и более эфективные:

#define SPACE_SYM ' '
#define MINUS_SYM '-'
 
int atoi_custom(char* src)
{
    int result = 0; //really returns int value
    char* current_symbol = src;
    int digit_indx = 1;
 
    if (!src)
        return 0;
    //let`s treat first word in string as a decimal number
    bool first_symb_found = false;
    // second part of the IF expression can be optimized, 
    //but it is more human readable as is 
    while(*current_symbol != 0 && 
           (SPACE_SYM != *current_symbol || !first_symb_found))
    {
            //ignore leading spaces
        if(!first_symb_found && *current_symbol != SPACE_SYM)
            first_symb_found = true;
        current_symbol++;
    }
      //string not found, exit
    if(current_symbol == src)
        return 0;
 
    for(current_symbol--; 
          current_symbol >= src && SPACE_SYM != *current_symbol;
          digit_indx*=10, current_symbol--)    
    {
        //process negative integers, leading '-' is symbol of it.
        if(MINUS_SYM == *current_symbol)
        {
            if(src == current_symbol ||
                     SPACE_SYM == *(current_symbol - 1))
                return (int)(-1 * result);
            else
                return 0;//incorrect syntax
        }
        //convert symbol into integer, 0 is 0x30, 1 is 0x31, etc
        int val = (int)*current_symbol - 0x30; 
        if(val <0 || val >9)//it is not a number
            return 0;        
        result += val * digit_indx;
    }
    return result;
}

7 комментариев:

Анонимный комментирует...

Вообще немного настараживает озабоченность автора тем что его да ещё и код писать заставили, а он, понимаеш, об архитектуре и подходах говорить собирался

afonia комментирует...

Здравствуйте! Нужно по капле выдавливать из себя раба :-)

int atoi2(char *c)
{
int val = 0, sign = 1, i = 0;

while(c[i] != '0') {
if (c[i] == '-')
sign = -1;
if (c[i] >= '0' && c[i] <= '9')
break;
i++;
}

for( ; c[i] >= '0' && c[i] <= '9'; i++) {
val = 10*val + c[i] - '0';
}

return val*sign;
}

Xv комментирует...

Нечем было заняться, решил С вспомнить. Интересно со сколькими ошибками вспомнилось))) Даже не компилил
int atoi_custom(char* src)
{
//check incoming null
if(src == null)
{
return 0;
}
int inlen = strlen(src);
//check incoming length > 0
if(inlen == 0)
{
return 0;
}
//check sign
bool is_negative = (src[0]=='-');
//clean input, leave only digits
char* cleaned = new char(inlen);
int cleaned_index = 0;
for(int i = 0; i < inlen; i++)
{
if(is_digit(src[i]))
{
cleaned[cleaned_index++]=src[i];
}
}
cleaned[cleaned_index] = 0;
int digits_count = cleaned_index;
cleaned_index = strlen(cleaned) - 1;
int first_digit_code = (int)('0');
int tenpower = 0;
int res = 0;
while(cleaned_index > 0)
{
res += ((int)(cleaned[cleaned_index]) - first_digit_code) * pow(10,tenpower);
cleaned_index--;
tenpower++;
}
delete cleaned;
return (is_negative)?(-res):(res);
}

cencio комментирует...

2Xv
это не С вcпомнил, а с++ ;)

2afonia
работать не будет ;) работа с i неправильная, в цикле фок нужно делать --i, и нужно условие, чтобы индекс не убежал дальше начала строки

Анонимный комментирует...

правильный ответ -- ПНХ:

* локаль(язык + культура + кодировка) IN, локаль OUT,
* диапазон настроек,
* платформа,
* наличие библиотек,
* сроки реализации,
* требования по скорости/безопасности/переносимости etc.
* доступ к Google и прочим *Forge

реализация - от 5LOC до 420KLOC (ICU)

Анонимный комментирует...

да, добавляем контекст и уточняем ,
"прадв ли что.."
^ assert(0 == strcmp(charstr,itoa(atoi(charstr))))

_wqwa комментирует...

Я сам в своё время проводил немало собеседований; недавно побывал в самсунге на интервью. Мои выводы: да, они пытаются заинтересовать работой, а не зарплатой -- это с одной стороны. С другой стороны -- вполне нормально на интервью написать 10 строк кода на бумажке, не вижу в этом ничего зазорного. С третьей -- не очень хорошо рассказывать о задачках на интервью, и выкладывать их решение -- неэтично по отношению к компании. Если человек проводит 20 интервью в неделю, он не в состоянии каждый раз генерировать уникальные задачи, а такой публикацией Вы мешаете ему работать. Это моё мнение, я не претендую на абсолютную правоту.