Здравствуйте, alexanderfedin, Вы писали:
A>Вдогонку: A>Вы работаете диспетчером в службе ремонта телевизоров и вам поступают звонки от "домохозяек". Итак, звонок: "У меня не работает телевизор!" A>Попытайтесь провести предварительное интервью клиента с целью выяснить причину неисправности. Опишите процесс выяснения по методу черного ящика с учетом того, что вы разговариваете с неспециалистом и процесс общения проходит по телефону.
— У меня не работает телевизор.
— Он включается?
— Да
— Какие признаки неисправности? Черная картинка/помехи/плохая яркость/баланс цветов/не работает пульт дистанционного управления?
— Черная картинка.
— На каких каналах черная картинка?
— На всех.
— Вы уверены, что телевизор сейчас включен?
— Да
— Каким образом вы переключаете программы? через пульт или кнопками на телевизоре?
— Через пульт
— На экране появляются номера каналов, когда вы переключаете?
— Нет
— Попробуйте переключать программы с помощью кнопок на телевизоре
— Тут их много
— Вам нужны кнопки рядом с которыми нарисованы стрелки, нажимайте все по несколько раз
— Не помогает
— На экране появляются номера каналов, когда вы переключаете?
— Да, спасибо заработало
— Вам нужно поменять батарейки в пульте дистанционного управления.
(по всей видимости домохозяйка переключила на канал AV)
— У меня не работает телевизор!
— Он включается?
— Нет
— Вы уверены, что он не включается? На телевизоре горят какие-либо красные, зеленые или другие огоньки?
— Нет
— Вы уверены, что телевизор подключен к сети? Проверьте еще раз, возможно кто-нибудь отключил его от сети.
— Он включен.
— Проверьте, работают ли другие электроприборы в вашем доме, возможно отключили электричество.
— Приборы работают.
— Вы включаете телевизор через пульт ДУ или кнопкой на телевизоре.
— Через пульт ДУ.
— Попробуйте включить телевизор, нажав на кнопку на самом телевизоре.
— Нажала, не включается
— На телевизоре загорелись какие-нибудь огоньки?
— Да, загорелся красный.
— Попробуйте включить телевизор нажав на кнопку на пульте ДУ
— Да, включился, спасибо.
Здравствуйте, Noobi, Вы писали: N>Это возможно, если Пилот летит в точку, находящуюся с другой стороны планеты (прямо "под ним") — туда все равно, как лететь, и любая точка на пов-ти планеты может находиться на дуге, которую пилот может описать для попадания на другой конец планеты.
Только вот одна загвоздка, земля не круглая
Здравствуйте, Aptekar, Вы писали:
A>Здравствуйте, Noobi, Вы писали: N>>Это возможно, если Пилот летит в точку, находящуюся с другой стороны планеты (прямо "под ним") — туда все равно, как лететь, и любая точка на пов-ти планеты может находиться на дуге, которую пилот может описать для попадания на другой конец планеты. A>Только вот одна загвоздка, земля не круглая
Ну в таком случае можно лететь с Северного полюса на Южный, или наоборот, если принимать Землю "сдавленной" по краям
Pavel Dvorkin wrote: > > Здравствуйте, kittown, Вы писали: > >> > 8. Написать функцию обмена значений двух целых переменных с >> > минимальными затратами памяти и времени. Примечание: >> > команды/функции обмена значений переменных не существует > > K>Баянище. a = b — a; b = b — a; a = a + b; > > Некорректное решение. На IBM PC это будет работать, так как на нем нет > переполнения с фиксированной точкой. На других машинах может вызвать > исключение.
Во-1, перед ответом полезно почитать весь тред — ничего нового не
сказано. Во-2, это все равно будет работать на определенном
множестве значений. Для них это решение корректно, нехватает
лишь оговорки про ограниченность множества. Собственно как
и при практически любой арифметической операции.
Предлагаю вашему вниманию вопросы и задачи, которые когда-либо были мне заданы на интервью. Надеюсь, что это может кому-то помочь либо интервьюировать, либо пройти интервью . Если у кого-то есть подобные задачи и вопросы — присоединяйтесь.
Ответов сейчас давать не буду, предоставляя возможность подумать.
Итак: Имеется односвязанный список и указатель на элемент, который подлежит удалению из этого списка. Вопрос: как удалить элемент, не имея указателя на голову списка и/или предшествующие элементы?
Имеется односвязанный список, из которого нужно удалить последний элемент. Указатель на последний элемент имеется. Вопрос: как удалить элемент, не имея указателя на голову списка и/или предшествующие элементы?
Имеется односвязанный список. Найти N-ый с конца элемент односвязанного списка с минимальой сложностью алгоритма и потребляемой памяти.
Имеется односвязанный список. Выяснить с минимальными затратами, не является ли этот список закольцованным.
Имеется односвязанный список. Написать функцию реверса этого списка.
Написать функцию реверса строки.
Написать функцию реверса битов в байте.
Написать функцию обмена значений двух целых переменных с минимальными затратами памяти и времени. Примечание: команды/функции обмена значений переменных не существует.
Один бизнесмен отправляется на собственном реактивном самолете из пункта А в пункт Б. Его приятель просит высадить его в в пункте В. Первый соглашается это сделать, не спрашивая, где должна быть посадка, утверждая, что где бы ни была эта точка, он не затратит ни одного часа лишнего времени. Может ли это быть правдой, если время на посадку/взлет не учитывается? Привести пример.
Пока все, что смог вспомнить.
24.02.05 12:44: Перенесено модератором из 'Работа — поиск и предложение'. — Хитрик Денис
И еще — это от Symantec (уж не знаю, зачем именно так...):
Engineer Programming Challenge Problem:
Given a simple virtual machine that has:
1. A program memory where the machine language bytes are stored (a pointer to this buffer will be passed in to your RunProgram function). The interpreter should run the program starting with the instruction at offset 0.
2. A register file of 10 DWORD registers which all start out with a value of 0.
3. A memory of 1024 bytes in size, with all bytes starting out with a value of 0.
4. And the following instruction set:
MOV R#, value Moves the immediate value into the specified register
Encoding: 0x00, byte destregnum, dword value (little-endian form)
LOAD R#, R# Loads the little-endian DWORD from memory at the location specified by the value of the second register and places the value into the first register.
Encoding: 0x01, byte destreg, byte memindexreg
STORE R#, R# Stores the DWORD value in the second register into the memory at the location specified by the value in the first register.
Encoding: 0x02, byte memindexreg, byte srcreg
ADD R#, R# Adds the value in the second register to the value in the first register and stores the result in the first register.
Encoding: 0x03, byte destregnum, byte srcregnum
JE R#, R#,dwOff Compares the value in the first specified register to the value in the second specified register. If the first value is equal to the second value then jump to the specified absolute offset and continue executing instructions. Otherwise continue with the next instruction. The offset is absolute from the top of the program.
Encoding: 0x04, byte regnum, byte regnum, dword offset value in little-endian form
JMP dwOff Jump to the specified absolute offset and continue executing instructions. The offset is absolute from the top of the program.
Encoding: 0x05, dword offset value in little-endian form
IN R# Input a decimal # from the user and store into the specified register
Encoding: 0x06, byte regnum
OUT R# Prints out the value of the specified register in decimal form
Encoding: 0x07, byte regnum
HLT Terminates the current program.
Encoding: 0x08 (no other parameters)
Challenge part 1: In one hour, write a well-structured C + + class to interpret this machine language and run well-formed machine-language programs passed in to your class.
Challenge part 2: If you have time left over, write a recursive function in this machine language to compute a factorial. Show a declaration like the one below (“unsigned char abyProgram[] = …”) with your solution.
For example, the following program would write out the numbers between 0 and 9:
alexanderfedin wrote: > > Итак: > > 1. Имеется односвязанный список и указатель на элемент, который > подлежит удалению из этого списка. Вопрос: как удалить элемент, не > имея указателя на голову списка и/или предшествующие элементы?
Заменить значение элемента значением последующего, чтобы указывал на
тот, на который указывал последующий. Удалить "старый" последующий.
> 2. Имеется односвязанный список, из которого нужно удалить последний > элемент. Указатель на последний элемент имеется. Вопрос: как > удалить элемент, не имея указателя на голову списка и/или > предшествующие элементы?
Если список циклический, очевидно. Если в элементе можно пометить,
что это пустой конец списка, тоже очевидно. В противном случае нельзя
получить указатель на предыдущий элемент, нужный для фиксации нового
конца списка.
Но "просто удалить" элемент (free, delete) можно конечно всегда.
> 3. Имеется односвязанный список. Найти N-ый с конца элемент > односвязанного списка с минимальой сложностью алгоритма и > потребляемой памяти.
Два указателя движутся от начала к концу списка, второй опаздывает
от первого на N элементов.
> 4. Имеется односвязанный список. Выяснить с минимальными затратами, > не является ли этот список закольцованным.
Бегущий указатель и сравнение с указателем на голову списка. Наблюдал
большое обсуждение этого вопроса, но не помню из-за чего.
> 5. Имеется односвязанный список. Написать функцию реверса этого списка. > 6. Написать функцию реверса строки. > 7. Написать функцию реверса битов в байте.
Просто кодерские задачки. Еще и от языка зависит.
> 8. Написать функцию обмена значений двух целых переменных с > минимальными затратами памяти и времени. Примечание: > команды/функции обмена значений переменных не существует
Баянище. a = b — a; b = b — a; a = a + b;
> 9. Один бизнесмен отправляется на собственном реактивном самолете из > пункта А в пункт Б. Его приятель просит высадить его в в пункте В. > Первый соглашается это сделать, не спрашивая, где должна быть > посадка, утверждая, что где бы ни была эта точка, он не затратит > ни одного часа лишнего времени. Может ли это быть правдой, если > время на посадку/взлет не учитывается? Привести пример.
Раньше не встречал, но наверно пункты А и Б находятся на противоположных
точках з. шара ?
>> 4. Имеется односвязанный список. Выяснить с минимальными затратами, >> не является ли этот список закольцованным.
K>Бегущий указатель и сравнение с указателем на голову списка. Наблюдал K>большое обсуждение этого вопроса, но не помню из-за чего.
в общем виде, 2 указателя, один перемещается вдвое быстрее другого (на случай если кольцо в середине)
>> 8. Написать функцию обмена значений двух целых переменных с >> минимальными затратами памяти и времени. Примечание: >> команды/функции обмена значений переменных не существует
K>Баянище. a = b — a; b = b — a; a = a + b;
Ещё ксоркой можно. Но на самом деле всё равно временный объект будет создан (в самом тривиальном случае это будет регистр процессора). Так что выгода такого изврата очень сомнительна.
Здравствуйте, kittown, Вы писали:
K>alexanderfedin wrote: >> >> Итак: >> >> 1. Имеется односвязанный список и указатель на элемент, который >> подлежит удалению из этого списка. Вопрос: как удалить элемент, не >> имея указателя на голову списка и/или предшествующие элементы?
K>Заменить значение элемента значением последующего, чтобы указывал на K>тот, на который указывал последующий. Удалить "старый" последующий.
Здравствуйте, alexanderfedin, Вы писали:
A>Предлагаю вашему вниманию вопросы и задачи, которые когда-либо были мне заданы на интервью. Надеюсь, что это может кому-то помочь либо интервьюировать, либо пройти интервью . Если у кого-то есть подобные задачи и вопросы — присоединяйтесь.
ЗA>Один бизнесмен отправляется на собственном реактивном самолете из пункта А в пункт Б. Его приятель просит высадить его в в пункте В. Первый соглашается это сделать, не спрашивая, где должна быть посадка, утверждая, что где бы ни была эта точка, он не затратит ни одного часа лишнего времени. Может ли это быть правдой, если время на посадку/взлет не учитывается? Привести пример.
Это возможно, если Пилот летит в точку, находящуюся с другой стороны планеты (прямо "под ним") — туда все равно, как лететь, и любая точка на пов-ти планеты может находиться на дуге, которую пилот может описать для попадания на другой конец планеты.
Здравствуйте, kittown, Вы писали:
>> 4. Имеется односвязанный список. Выяснить с минимальными затратами, >> не является ли этот список закольцованным.
K>Бегущий указатель и сравнение с указателем на голову списка. Наблюдал K>большое обсуждение этого вопроса, но не помню из-за чего.
Вероятно, я неполно сформулировал условия задачи. Дело в том, что "конец" списка указывает не на его "начало", а на его, скажем, "середину". и сравнивать элемент с головой списка... ммм... бесполезно...
Здравствуйте, Aptekar, Вы писали:
A>Здравствуйте, Noobi, Вы писали: N>>Это возможно, если Пилот летит в точку, находящуюся с другой стороны планеты (прямо "под ним") — туда все равно, как лететь, и любая точка на пов-ти планеты может находиться на дуге, которую пилот может описать для попадания на другой конец планеты. A>Только вот одна загвоздка, земля не круглая
А бывают ли вообще круглые планеты? (может быть, они на др. планете — не сказано про Землю)
Про обмен двух целых переменных — решений миллион. Наиболее простой вариант — запихнуть информацию об обеих переменных в одну переменную — так что эта переменная является функцией от обоих переменных. Например.
1)
A=5;
B=10;
B = A*B = 5*10 = 50;
A = B/A = 50/5 = 10;
B = B/A = 50/10 = 5;
Здравствуйте, kittown, Вы писали:
K>alexanderfedin wrote: >> >> Итак: >> >> 1. Имеется односвязанный список и указатель на элемент, который >> подлежит удалению из этого списка. Вопрос: как удалить элемент, не >> имея указателя на голову списка и/или предшествующие элементы?
K>Заменить значение элемента значением последующего, чтобы указывал на K>тот, на который указывал последующий. Удалить "старый" последующий.
если тот который надо удалить последний в списке
>> 2. Имеется односвязанный список, из которого нужно удалить последний >> элемент. Указатель на последний элемент имеется. Вопрос: как >> удалить элемент, не имея указателя на голову списка и/или >> предшествующие элементы?
K>Если список циклический, очевидно. Если в элементе можно пометить, K>что это пустой конец списка, тоже очевидно. В противном случае нельзя K>получить указатель на предыдущий элемент, нужный для фиксации нового K>конца списка.
K>Но "просто удалить" элемент (free, delete) можно конечно всегда.
>> 3. Имеется односвязанный список. Найти N-ый с конца элемент >> односвязанного списка с минимальой сложностью алгоритма и >> потребляемой памяти.
K>Два указателя движутся от начала к концу списка, второй опаздывает K>от первого на N элементов.
>> 4. Имеется односвязанный список. Выяснить с минимальными затратами, >> не является ли этот список закольцованным.
K>Бегущий указатель и сравнение с указателем на голову списка. Наблюдал K>большое обсуждение этого вопроса, но не помню из-за чего.
>> 5. Имеется односвязанный список. Написать функцию реверса этого списка. >> 6. Написать функцию реверса строки. >> 7. Написать функцию реверса битов в байте.
K>Просто кодерские задачки. Еще и от языка зависит.
>> 8. Написать функцию обмена значений двух целых переменных с >> минимальными затратами памяти и времени. Примечание: >> команды/функции обмена значений переменных не существует
K>Баянище. a = b — a; b = b — a; a = a + b;
>> 9. Один бизнесмен отправляется на собственном реактивном самолете из >> пункта А в пункт Б. Его приятель просит высадить его в в пункте В. >> Первый соглашается это сделать, не спрашивая, где должна быть >> посадка, утверждая, что где бы ни была эта точка, он не затратит >> ни одного часа лишнего времени. Может ли это быть правдой, если >> время на посадку/взлет не учитывается? Привести пример.
K>Раньше не встречал, но наверно пункты А и Б находятся на противоположных K>точках з. шара ?
K>Mikhail
Здравствуйте, alexanderfedin, Вы писали:
A>Предлагаю вашему вниманию вопросы и задачи, которые когда-либо были мне заданы на интервью. Надеюсь, что это может кому-то помочь либо интервьюировать, либо пройти интервью . Если у кого-то есть подобные задачи и вопросы — присоединяйтесь.
Вдогонку:
Вы работаете диспетчером в службе ремонта телевизоров и вам поступают звонки от "домохозяек". Итак, звонок: "У меня не работает телевизор!"
Попытайтесь провести предварительное интервью клиента с целью выяснить причину неисправности. Опишите процесс выяснения по методу черного ящика с учетом того, что вы разговариваете с неспециалистом и процесс общения проходит по телефону.
Здравствуйте, Aptekar, Вы писали:
A>Здравствуйте, Noobi, Вы писали: N>>Это возможно, если Пилот летит в точку, находящуюся с другой стороны планеты (прямо "под ним") — туда все равно, как лететь, и любая точка на пов-ти планеты может находиться на дуге, которую пилот может описать для попадания на другой конец планеты. A>Только вот одна загвоздка, земля не круглая
Экваториальный радиус больше полярного на ~20км, а с учетом того, что реактивные самолеты летают на высоте ~10км, Землю можно считать шаром.
Но загвоздка есть в том, что Земля вертиться, а сл-но "туда" не все равно как лететь. Т.о. для того, чтоб попасть на запад, мы можем пролететь некоторое расстояние на север, а потом такое-же на юг. В принципе, при таком раскладе можно принебречь силой кориолиса.
term1976 wrote: > >> > 1. Имеется односвязанный список и указатель на элемент, который >> > подлежит удалению из этого списка. Вопрос: как удалить элемент, не >> > имея указателя на голову списка и/или предшествующие элементы? > > K>Заменить значение элемента значением последующего, чтобы указывал на > K>тот, на который указывал последующий. Удалить "старый" последующий. > > если тот который надо удалить последний в списке
Эта проблема сводится к задачке N2.
>> > 2. Имеется односвязанный список, из которого нужно удалить последний >> > элемент. Указатель на последний элемент имеется. Вопрос: как >> > удалить элемент, не имея указателя на голову списка и/или >> > предшествующие элементы? > > K>Если список циклический, очевидно. Если в элементе можно пометить, > K>что это пустой конец списка, тоже очевидно. В противном случае нельзя > K>получить указатель на предыдущий элемент, нужный для фиксации нового > K>конца списка. > > K>Но "просто удалить" элемент (free, delete) можно конечно всегда.
Кстати, я везде забыл самый простой ответ — "дернуть метод у контейнера"
BU>Но загвоздка есть в том, что Земля вертиться, а сл-но "туда" не все равно как лететь.
Но ведь вместе с землей вращается и атмосфера, опираясь на которую летит самолет!
A>Имеется односвязанный список и указатель на элемент, который подлежит удалению из этого списка. Вопрос: как удалить элемент, не имея указателя на голову списка и/или предшествующие элементы?
Условие:
struct element
{
struct element *pElementNext;
int value;
};
elementCollection[n].pElementNext указывает на elementCollection[m]
Решение.
int element_delete_by_ref( struct element *pCurrentElement )
{
struct element *pNextElement;
pNextElement = pCurrentElement->pElementNext;
pCurrentElement->value = pNextElement->value;
pCurrentElement->pElementNext = pNextElement->pElementNext;
return 0;
}
Здравствуйте, alexanderfedin, Вы писали:
>Написать функцию обмена значений двух целых переменных с минимальными затратами памяти и времени. Примечание: команды/функции обмена значений переменных не существует.
Здравствуйте, kittown, Вы писали:
K>AntZ wrote: >> >> А можно так >> A = A xor B >> B = A xor B >> A = A xor B >> >> красиво, да?
K>Через XOR наверно даже более правильно (корректность решения K>не проверял), потому что не надо думать о переполнении.
K>Mikhail
Это просто работает. В C/C++/C#/Java/etc. пишут даже такую устоявшуюся конструкцию (представляю, как на меня сейчас набросятся апологеты стандарта С++, говоря, что "поведение не определено"):
Здравствуйте, alexanderfedin, Вы писали:
A>Это просто работает. В C/C++/C#/Java/etc. пишут даже такую устоявшуюся конструкцию (представляю, как на меня сейчас набросятся апологеты стандарта С++, говоря, что "поведение не определено"): A>
A>a ^= b ^= a ^= b;
A>
Причем почему не определено — многие не знают, или знают неправильно
A>>Это просто работает. В C/C++/C#/Java/etc. пишут даже такую устоявшуюся конструкцию (представляю, как на меня сейчас набросятся апологеты стандарта С++, говоря, что "поведение не определено"): A>>
A>>a ^= b ^= a ^= b;
A>>
Д>Причем почему не определено — многие не знают, или знают неправильно
Здравствуйте, mihoshi, Вы писали:
M>А если скобки расставить?
это не поможет
причина в том, что здесь в промежутке между sequence points значение переменной меняется больше одного раза
скобки за sequence point не считаются
Скажу сразу и честно , мне бы такео решение в голову не пришло .
Такой трюк сводит на нет почти все преимущества от использования списка, а именно не позволяет зранить указатель на элемент. Поэтому если бы мне показали такое решение я бы постарасля выяснить , понимает ли человек ЧТО он загубил пол месяца работы и пустил их на отладку в большом проэкте ?
P.S. Для ограниченного к- ва задач такое решение может оказаться приемлемым , но счас не могу даже сказать для каких.
Здравствуйте, minorlogic, Вы писали:
M> Такой трюк сводит на нет почти все преимущества от использования списка, а именно не позволяет зранить указатель на элемент. Поэтому если бы мне показали
Хм... если ты внимательно смотрел код, то все указатели сохраняются. А "убитые" элементы можно помечать специальным маркером и они будут использоваться в дальнейшем, т.о. не происходит утечки или потери памяти. ИМХО код достаточно быстрый и удобный и пригоден для решения любых задач.
Обоснуйте свою точку зрения, почему и как "не позволяет зранить указатель на элемент". Ваше решение?
"Roman Pushkin" <30082@users.rsdn.ru> wrote in message news:1043065@news.rsdn.ru... >. Примечание: команды/функции обмена значений переменных не существует.
> xchg eax, ebx
Здравствуйте, kittown, Вы писали:
K>alexanderfedin wrote: >>... >> 3. Имеется односвязанный список. Найти N-ый с конца элемент >> односвязанного списка с минимальой сложностью алгоритма и >> потребляемой памяти.
K>Два указателя движутся от начала к концу списка, второй опаздывает K>от первого на N элементов.
Это частный случай, в общем случае будет так:
Указатель через каждые K ячеек запоминает текущий элемент, что потребует наличие циклического буфера с N/K ячейками.
Когда будет найден конец списка, второй указатель начнет движение от первого элемента в буфере и пройдет столькоже, сколько первый указатель прошел после последней запомненой ячейки (пройти потребуется, в среднем, еще K/2 ячейки).
m> Если в программе некий указатель указывал на value то после такого m> удаления указатель будет показывать на мусор.
Почему тогда в проекте используются свои реализации стандартных СД без правил присущих обращению с итераторами в stl?
Slime wrote: > >> > 3. Имеется односвязанный список. Найти N-ый с конца элемент >> > односвязанного списка с минимальой сложностью алгоритма и >> > потребляемой памяти. > > K>Два указателя движутся от начала к концу списка, второй опаздывает > K>от первого на N элементов. > > Это частный случай, в общем случае будет так: > Указатель через каждые K ячеек запоминает текущий элемент, что потребует > наличие циклического буфера с N/K ячейками. > Когда будет найден конец списка, второй указатель начнет движение от > первого элемента в буфере и пройдет столькоже, сколько первый указатель > прошел после последней запомненой ячейки (пройти потребуется, в среднем, > еще K/2 ячейки).
Где же оно более общее ? Оно как раз более частное. Оно предполагает,
например, что элемент можно куда-то сохранить или взять на него ссылку.
Еще оно предполагает, что можно возобновить движение с произвольного
элемента.
Собственно заменяем в моем решение указатели на итераторы, и можно
легко придумать ряд случаев, когда ваше решение будет неприемлемо,
и как минимум один, когда будет неприемлемо мое (нет возможности
пустить два итератора).
Здравствуйте, SkyDance, Вы писали:
>>. Примечание: команды/функции обмена значений переменных не существует. >> xchg eax, ebx SD>Забавные у вас решения.
Здравствуйте, minorlogic, Вы писали:
M>Если в программе некий указатель указывал на value то после такого удаления указатель будет показывать на мусор.
Вы невнимательно читали мой предыдущий пост:
"А \"убитые\" элементы можно помечать специальным маркером и они будут использоваться в дальнейшем"
Здравствуйте, alexanderfedin, Вы писали:
A>Имеется односвязанный список, из которого нужно удалить последний элемент. Указатель на последний элемент имеется. Вопрос: как удалить элемент, не имея указателя на голову списка и/или предшествующие элементы?
BU>>Но загвоздка есть в том, что Земля вертиться, а сл-но "туда" не все равно как лететь. V>Но ведь вместе с землей вращается и атмосфера, опираясь на которую летит самолет!
Это не важно RTFM 'Сила Кориолиса' 2m[VxW] =0 при V=0
int element_print_all( struct element *pCurrentElement)
{
struct element *pNextElement = pCurrentElement;
while(pNextElement->pElementNext != NULL)
{
printf("%d\n",pNextElement->value);
pNextElement = pNextElement->pElementNext;
}
// print last element
printf("%d\n",pNextElement->value);
return 0;
}
Основным преимуществом списка есть удаление и вставка в произвольном месте последовательности.
Обычно это место определяется указателем на елемент списка , например так
int add( struct element *pCurrentElement, struct element *pNewElement)
{
struct element *pNextElement;
pNewElement->pElementNext = pCurrentElement->pElementNext;
pCurrentElement->pElementNext = pNewElement;
return 0;
}
int main(void)
{
elementsCollection[0].value = 1;
elementsCollection[0].pElementNext = &elementsCollection[1];
Здравствуйте, Roman Pushkin, Вы писали:
RP>Здравствуйте, alexanderfedin, Вы писали:
A>>Имеется односвязанный список, из которого нужно удалить последний элемент. Указатель на последний элемент имеется. Вопрос: как удалить элемент, не имея указателя на голову списка и/или предшествующие элементы?
RP>Кто-нибудь знает как решить задачку?
ты уверен что у нее есть решение? не вижу возможности добраться до предыдущего элемента — после физического удаления элемента будет нарушена ссылочная целостноть. К постановке задачи не подкопаешься — разве что список циклический.
Здравствуйте, Roman Pushkin, Вы писали:
RP>Здравствуйте, minorlogic, Вы писали:
RP><skipped>
M>>ЧТО имеено нам даст пометка элементов ?
RP>Ну ты утомил меня, парень В общем, раз ты такой крутой, буду рад увидеть твой вариант (читай внимательно задание). Точка.
Странный тон , учитывая что мы не знакомы не НАХОДИТЕ ЛИ ?
По предыдущему посту я не понял , ВЫ согласны с тем что это решение имеет некоторые побочные эфекты, или это значит что я пишу полную чушь, которую даже не стоит коментировать ?
В любом случае я тоже устал писать одно и тоже в третий раз .
Здравствуйте, minorlogic, Вы писали:
M>Странный тон , учитывая что мы не знакомы не НАХОДИТЕ ЛИ ? M>По предыдущему посту я не понял , ВЫ согласны с тем что это решение имеет некоторые побочные эфекты, или это значит что я пишу полную чушь, которую даже не стоит коментировать ?
M>В любом случае я тоже устал писать одно и тоже в третий раз .
Я признаю, что я зря родился на свет, согласен что я грубиян, ничтожество, бездарность и моральный урод. Но это уже, кажется, оффтоп.
А по существу — решением было создать функцию (!), а не программировать второе издание System.Collections
Здравствуйте, kliff, Вы писали:
A>>>Имеется односвязанный список, из которого нужно удалить последний элемент. Указатель на последний элемент имеется. Вопрос: как удалить элемент, не имея указателя на голову списка и/или предшествующие элементы?
RP>>Кто-нибудь знает как решить задачку?
K>ты уверен что у нее есть решение? не вижу возможности добраться до предыдущего элемента — после физического удаления элемента будет нарушена ссылочная целостноть. К постановке задачи не подкопаешься — разве что список циклический.
Внесу некоторую ясность: я спросил про циклический список, но мастдаец заметил, что "может быть список и циклический, но размер его таков, что итерирование по нему займет слишком много времени" (дословно). Я предложил либо маркер на элементе списка, либо элементы — матрешки (wrappers), у которых можно заменить содержимое: был Node, стал NullNode.
Такой ответ его вполне удовлетворил.
Здравствуйте, alexanderfedin, Вы писали:
A>Предлагаю вашему вниманию вопросы и задачи, которые когда-либо были мне заданы на интервью. Надеюсь, что это может кому-то помочь либо интервьюировать, либо пройти интервью . Если у кого-то есть подобные задачи и вопросы — присоединяйтесь. A>Ответов сейчас давать не буду, предоставляя возможность подумать.
Здравствуйте, alexanderfedin, Вы писали:
A>Предлагаю вашему вниманию вопросы и задачи, которые когда-либо были мне заданы на интервью. Надеюсь, что это может кому-то помочь либо интервьюировать, либо пройти интервью . Если у кого-то есть подобные задачи и вопросы — присоединяйтесь.
Совсем свежее, с face-to-face интервью у Майкрософта: Есть счетчик километража в автомобиле. И вот, одному ненормальному пришло в голову сделать разряды этого счетчика не по основанию 10, а для каждого разряда своё: 4, 6, 2, 7, 10, 3. Вопрос: как это реализовать и какие тест кейзы вы можете предложить для такого счетчика?
Имеется сортированный односвязанный список. Вставить в него новый элемент.
Имеется числовая последовательность: 1, 1, 2, 3, 5, 8, 13,.. Написать алгоритм для продолжения последовательности.
Имеется список точек на плоскости с целочисленными координатами. Найти первые такие две точки, чтобы точка, лежащая посередине между ними, имела целочисленные координаты. Написать максимально простой алгоритм.
>> 8. Написать функцию обмена значений двух целых переменных с >> минимальными затратами памяти и времени. Примечание: >> команды/функции обмена значений переменных не существует
K>Баянище. a = b — a; b = b — a; a = a + b;
Некорректное решение. На IBM PC это будет работать, так как на нем нет переполнения с фиксированной точкой. На других машинах может вызвать исключение.
а вот какое тестовое задание было у меня 2 года назад: написать программу, которая использует метаданные MS SQL Server. используя системные таблицы сервера нужно было вывести список баз, список таблиц, список полей в таблицах,....
Здравствуйте, _Hooter, Вы писали:
_H>Здравствуйте, alexanderfedin, Вы писали:
A>>Если у кого-то есть подобные задачи и вопросы — присоединяйтесь.
_H>Один из стандартных вопросов на знание SQL:
_H>Есть таблица с ключевым полем ID. Ключевое поле содержит челые числа. Например, 1, 2, 3, 4, 7, 8, 10, 11,...
_H>Задание: написать запрос для нахождения "дырки" в последовательности идентификаторов.
вот что я сваял за пару минут. возвращает не ВСЕ дырки, а НЕКОТОРЫЕ.
есть ли оптимальнее решение?
//создаем таблицу
create table #test (id int)
//заполняем значениями
insert #test(id) values (2)
insert #test(id) values (3)
insert #test(id) values (4)
insert #test(id) values (7)
insert #test(id) values (8)
insert #test(id) values (9)
//собственно решение
select t1.id + 1
from #test t1
where
t1.id != (select max(id) from #test)
and
not exists
(
select 1 from #test t2 where t2.id = t1.id + 1
)
//удаляем таблицу
drop table #test
Здравствуйте, nopal, Вы писали:
N>Здравствуйте, alexanderfedin, Вы писали:
N>а вот какое тестовое задание было у меня 2 года назад: написать программу, которая использует метаданные MS SQL Server. используя системные таблицы сервера нужно было вывести список баз, список таблиц, список полей в таблицах,....
я думаю такое можно задавать только администратору бд
Здравствуйте, ilya_ny, Вы писали:
_H>>Есть таблица с ключевым полем ID. Ключевое поле содержит челые числа. Например, 1, 2, 3, 4, 7, 8, 10, 11,... _H>>Задание: написать запрос для нахождения "дырки" в последовательности идентификаторов.
_>вот что я сваял за пару минут. возвращает не ВСЕ дырки, а НЕКОТОРЫЕ. _>есть ли оптимальнее решение? _>
_>
_>//собственно решение
_>select t1.id + 1
_>from #test t1
_>where
_>t1.id != (select max(id) from #test)
_>and
_>not exists
_>(
_> select 1 from #test t2 where t2.id = t1.id + 1
_>)
_>
_>
Често говоря, я не совсем понял, что значит "некоторые", так как не разбирался в твоем решении. Скорее всего оно правильное.
Но надо написать запрос для нахождения не "дырок", а "дырки". Всего одной.
Я должен уточнить: с помощью запроса надо найти первую "дырку" в последовательности. Если отсутствие этого уточнения кого-то ввело в заблуждение — прошу прощения.
А решение такое:
select min(f1.id)
from table1 f1 left join table1 f2 on f1.id + 1= f2.id
where f2.id is null;
Или нечто похожее. Но идея, надеюсь, понятна...
После выполнения запроса поле будет содержать некое значение, которое будет на 1 меньше, чем значение первой дырки.
Здравствуйте, _Hooter, Вы писали:
_H>Често говоря, я не совсем понял, что значит "некоторые", так как не разбирался в твоем решении. Скорее всего оно правильное.
некоторые — это значит, что если пропущено больше два и более чисел подряд, то вернется первое пропущенное, а не все пропущенные.
Пример: 1, 2, 5, 6, 9, 10
пропущены (3, 4) и (7, 8)
вернутся 3 и 7
_H>Но надо написать запрос для нахождения не "дырок", а "дырки". Всего одной.
_H>Я должен уточнить: с помощью запроса надо найти первую "дырку" в последовательности. Если отсутствие этого уточнения кого-то ввело в заблуждение — прошу прощения.
Если в моем рещениие написать min, то будет твой-же результат
твое рещение почти верно — надо min(f1.id + 1) возвращать, а не min(f1.id)
ну и конечо оно проще
select f1.id + 1
from #test f1 left join #test f2 on f1.id + 1= f2.id
where f2.id is null
>>> 8. Написать функцию обмена значений двух целых переменных с >>> минимальными затратами памяти и времени. Примечание: >>> команды/функции обмена значений переменных не существует
K>>Баянище. a = b — a; b = b — a; a = a + b;
_>Ещё ксоркой можно. Но на самом деле всё равно временный объект будет создан (в самом тривиальном случае это будет регистр процессора). Так что выгода такого изврата очень сомнительна.
Я бы сделал вот так: a = b ^ a; b = a ^ b; a = a ^ b;
Работать будет быстрее и будет исключена вероятность потери данных при больших значениях.
Здравствуйте, alexanderfedin, Вы писали:
A>Имеется сортированный односвязанный список. Вставить в него новый элемент.
Список:
+-----+ +-----+ +-----+
| a |->| b |->| c |->...
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
^ => | a |->| b |->| z |->| c |->...
| +-----+ +-----+ +-----+ +-----+
+-----+
| z |
+-----+
b <= z <= c (по возрастанию)
b >= z >= c (по убыванию)
#include <iostream>
unsigned GetNextFibonachi(unsigned current)
{
static unsigned previous = 8;
unsigned res = current + previous;
previous = current;
return res;
}
int main()
{
for(int i = 13; i < 1000; )
{
i = GetNextFibonachi(i);
std::cout << i << std::endl;
}
return 0;
}
A>Имеется список точек на плоскости с целочисленными координатами. Найти первые такие две точки, чтобы точка, лежащая посередине между ними, имела целочисленные координаты. Написать максимально простой алгоритм.
Что-то типа этого:
#include <iostream>
#include <utility>
int main()
{
typedef std::pair<int, int> coord;
coord points[2][2];
bool found[2][2] = {false};
for(int i = 0; i < 5; i++) // достаточно первых пяти точек
{
int x, y, xt, yt;
std::cin >> x >> y; // пусть координаты подаются на stdin
xt = x & 1, yt = y & 1; // выясняем чётностьif(found[xt][yt])
{
std::cout << '(' << x << "; " << y << ") - ("
<< points[xt][yt].first << "; " << points[xt][yt].second << ")\n";
break;
}
else
{
points[xt][yt] = std::make_pair(x, y);
found[xt][yt] = true;
}
}
return 0;
}
>> 2. Имеется односвязанный список, из которого нужно удалить последний >> элемент. Указатель на последний элемент имеется. Вопрос: как >> удалить элемент, не имея указателя на голову списка и/или >> предшествующие элементы?
K>Если список циклический, очевидно. Если в элементе можно пометить, K>что это пустой конец списка, тоже очевидно. В противном случае нельзя K>получить указатель на предыдущий элемент, нужный для фиксации нового K>конца списка.
K>Но "просто удалить" элемент (free, delete) можно конечно всегда.
Не всегда Напишешь пример для С# и java?
... << RSDN@Home 1.1.3 stable >> Winamp: silent
Новости очень смешные. Зря вы не смотрите. Как будто за наркоманами подсматриваешь. Только тетка с погодой в завязке.
There is no such thing as a winnable war.
>> 4. Имеется односвязанный список. Выяснить с минимальными затратами, >> не является ли этот список закольцованным.
K>Бегущий указатель и сравнение с указателем на голову списка. Наблюдал K>большое обсуждение этого вопроса, но не помню из-за чего.
Может, из-за того, что закольцован список может быть не только через голову?
... << RSDN@Home 1.1.3 stable >> Winamp: silent
Новости очень смешные. Зря вы не смотрите. Как будто за наркоманами подсматриваешь. Только тетка с погодой в завязке.
There is no such thing as a winnable war.
Eugeny__ wrote: > >> > 2. Имеется односвязанный список, из которого нужно удалить последний >> > элемент. Указатель на последний элемент имеется. Вопрос: как >> > удалить элемент, не имея указателя на голову списка и/или >> > предшествующие элементы? > > K>Если список циклический, очевидно. Если в элементе можно пометить, > K>что это пустой конец списка, тоже очевидно. В противном случае нельзя > K>получить указатель на предыдущий элемент, нужный для фиксации нового > K>конца списка. > > K>Но "просто удалить" элемент (free, delete) можно конечно всегда. > > Не всегда Напишешь пример для С# и java?
Процитированная фраза хитрая — она может быть переписана для delete
как "операцию delete можно вызвать в любом участке кода" и
аналогично для free. Эха характеристика операции как таковой.
В Java аналогичной операции нет вообще, поэтому о ее свойствах
ничего сказать нельзя.
Eugeny__ wrote: > > Здравствуйте, kittown, Вы писали: > >> > 4. Имеется односвязанный список. Выяснить с минимальными затратами, >> > не является ли этот список закольцованным. > > K>Бегущий указатель и сравнение с указателем на голову списка. Наблюдал > K>большое обсуждение этого вопроса, но не помню из-за чего. > > Может, из-за того, что закольцован список может быть не только через голову?
Первая версия оценки ситуации. Как сказал бы один из знакомых
профессоров — это программная ошибка. Программный дедлок он
относит туда же.
Вторая версия оценки ситуации. Закольцован у нас получается не список,
а произвольная часть списка, т.е. слово "закольцован" понимается
шире чем обычно. Таким образом, разногласие возникает из-за
разного толкования термина "закольцован". Поскольку разногласие
в толковании очень вероятно, и это достаточно очевидно, то имеем
небрежно и неточно записанное условие задачи постановщиком.
Вобщем, я бы остановился на небрежности постановщика.