Друзья, которые недавно готовятся к интервью, могут обратить внимание на мою колонку-Помогите осенним рекрутам, надеюсь, это поможет вам
предисловие
Незадолго до того, как прошли золотые три серебряных и четыре серебряных, и он собирается снова набираться, поэтому я написал эту статью для всех, от друга, который только что участвовал в байт-интервью и прошел собеседование с высоким баллом, кроме байтового предложения., Он также прошел собеседования таких компаний, как JD.com, Baidu и Tencent Alibaba, так что его опыт по-прежнему ценен. Друзья, которые собираются участвовать в осеннем наборе, могут его собрать и использовать в качестве ссылка Если вы действительно заинтересованы в вашем интервью, я благодарен за некоторую помощь.
Я также взял все материалы, которые он использовал перед интервью, и я могу бесплатно поделиться ими с друзьями, которым они нужны, просто нажмите, чтобы получить!
Нечего сказать, сиди и держись, поехали!
Одна сторона и две стороны соединены вместе, три стороны разделены на долгое время, потому что это после Первомая, а ч сторона - это один день после трех сторон.
Одна сторона: 45 минут
Проект: представьте требования проекта, дизайнерские идеи и основные технологии (поскольку мы спрашивали о проектах, связанных с ИИ, поэтому я не стал больше спрашивать о технологиях).
1. ЯВА
1. Алгоритм сборки мусора
Типичные алгоритмы сборки мусора
Спецификация JVM не определяет, как работает сборщик мусора, и каждый поставщик может реализовать сборщик мусора по-разному. Здесь обсуждаются несколько распространенных алгоритмов GC.
Марк-развертка
Самый простой алгоритм сборки мусора делится на два этапа: маркировку и очистку. Фаза маркировки помечает все объекты, которые необходимо вернуть, а фаза очистки восстанавливает пространство, занимаемое помеченными объектами. Как показано на рисунке:
Из рисунка видно, что самая большая проблема этого алгоритма заключается в том, что память сильно фрагментирована, и может возникнуть проблема, связанная с тем, что большие объекты не смогут найти полезное пространство в будущем.
Алгоритм копирования (Copying)
Алгоритм, предложенный для решения дефекта фрагментации памяти алгоритма Mark-Sweep. Разделите память на два блока одинакового размера в соответствии с объемом памяти. Используйте только один из них за раз.Когда этот блок памяти заполнится, скопируйте уцелевшие объекты в другой блок и очистите используемую память, как показано на рисунке:
Хотя этот алгоритм прост в реализации, обладает высокой эффективностью использования памяти и не подвержен фрагментации, самая большая проблема заключается в том, что доступная память сжимается до половины исходной. А если уцелевших объектов будет больше, то эффективность алгоритма Копирования сильно снизится.
Марк-Компакт
Объединив два вышеуказанных алгоритма, предлагается избежать дефектов. Фаза маркировки аналогична алгоритму Mark-Sweep: вместо очистки объектов после маркировки уцелевшие объекты перемещаются в один конец памяти. Затем объекты за пределами конечной границы удаляются. Как показано на рисунке:
Коллекция поколений
Метод сбора поколений в настоящее время используется большинством JVM. Его основная идея состоит в том, чтобы разделить память на разные домены в соответствии с различными жизненными циклами выживания объекта. Как правило, куча GC делится на Tenured/Old Generation и Young Generation. Характерной чертой старого поколения является то, что при каждой сборке мусора необходимо собирать лишь небольшое количество объектов, а характеристикой нового поколения является то, что при каждой сборке мусора необходимо собирать большое количество мусора, поэтому могут использоваться разные алгоритмы. быть выбраны в соответствии с различными регионами.
В настоящее время большинство JVM GC используют алгоритм копирования для нового поколения, потому что каждая сборка мусора в новом поколении должна высвобождать большую часть объектов, то есть копируемых операций относительно немного, а нового поколения обычно нет. делится в соотношении 1:1. Как правило, новое поколение делится на большее пространство Эдема и два меньших пространства Выживших (Из космоса, В космос).Каждый раз, когда пространство Эдема и одно из пространств Выживших используются, при переработке используются два пространства. объекты копируются в другое пространство Survivor.
В старом поколении используется алгоритм Mark-Compact, поскольку каждый раз восстанавливается лишь небольшое количество объектов.
Кроме того, не забывайте о постоянном поколении в области методов, упомянутой в статье Основы Java: виртуальная машина Java (JVM). Он используется для хранения классов, констант, описаний методов и т. д. Коллекция вечного поколения в основном состоит из выброшенных констант и бесполезных классов.
Выделение памяти для объектов происходит в основном в пространстве Эдема нового поколения и в пространстве из пространства выжившего (часть, где выживший в данный момент хранит объект), а в некоторых случаях она будет напрямую выделена старому поколению. . При недостатке райского пространства и из космоса нового поколения будет происходить GC.После GC уцелевшие объекты в райских зонах и из космического пространства будут перемещены в райское пространство, а затем в райское пространство и из космоса будет убрано.
Если To Space недостаточно для хранения объекта, объект сохраняется в старом поколении. После GC используются Eden Space и To Space и так далее. Когда объект покидает GC в области Survivor, его возраст будет +1. По умолчанию объекты, возраст которых достигает 15 лет, будут перемещены в старое поколение.
типичный сборщик мусора
Алгоритм сборки мусора является теоретической основой сборщика мусора, а сборщик мусора — его конкретной реализацией. Ниже описаны несколько сборщиков мусора, предоставляемых виртуальной машиной HotSpot.
3.1. Serial/Serial Old
Самый старый сборщик, однопоточный сборщик, должен приостанавливать все пользовательские потоки, когда он используется для сборки мусора. Serial — это сборщик для нового поколения, использующий алгоритм копирования, а Serial Old — это сборщик для старого поколения, использующий алгоритм Mark-Compact. Преимущество в том, что это просто и эффективно, а недостаток в том, что пользовательский поток необходимо приостановить.
ParNew
Многопоточная версия Serial/Serial Old, использующая несколько потоков для сборки мусора.
Parallel Scavenge
Параллельному сборщику нового поколения не нужно приостанавливать другие потоки во время повторного использования, и он использует алгоритм копирования. Этот коллектор отличается от первых двух коллекторов главным образом достижением управляемой пропускной способности.
Parallel Old
Версия Parallel Scavenge старого поколения, использующая алгоритм Mark-Compact и многопоточность.
CMS
Сборщик Current Mark Sweep — это параллельный сборщик, целью которого является приостановка сбора в минимальное время, поэтому он использует алгоритм Mark-Sweep.
G1
Технология сбора мусора G1 (Garbage First) — это передовое достижение, представляющее собой сборщик, ориентированный на сервер, который может в полной мере использовать ЦП и многоядерную среду. — это параллельный и параллельный сборщик, который моделирует предсказуемое время паузы.
2. Разница между cms и g1
CMS: сборщик с целью получения кратчайшего времени приостановки сбора на основе параллельной реализации «развертки меток».
процесс:
1. Начальная отметка: эксклюзивный PUC, отмечайте только те объекты, с которыми GCroots может напрямую ассоциироваться.
2. Параллельная маркировка: может выполняться параллельно с пользовательскими потоками, помечая все достижимые объекты.
3. Перемаркировка: эксклюзивный ЦП (STW), маркировка и исправление объектов мусора, созданных пользовательским потоком, работающим на параллельной фазе маркировки.
4. Параллельная очистка: может выполняться параллельно с пользовательскими потоками для очистки мусора.
преимущество:
Параллелизм, низкая пауза
недостаток:
1. Очень чувствителен к ЦП: хотя пользовательский поток не будет приостановлен в параллельной фазе, это замедлит работу приложения, поскольку занимает часть потока.
2. Невозможно справиться с плавающим мусором: на последнем этапе процесса параллельной очистки округ пользователя также будет генерировать мусор, но эта часть мусора находится после маркировки, поэтому ее можно очистить только после следующего сбора мусора, эта часть мусор называется плавающим мусором
3. CMS использует метод «пометить-очистить» для генерации большого количества фрагментов пространства.Когда фрагментов слишком много, это доставит много хлопот с выделением большого объектного пространства.Часто остается еще много пространство в старом возрасте, но не может Чтобы найти достаточно большое непрерывное пространство для размещения текущего объекта, вы должны заранее запустить FullGC.Чтобы решить эту проблему, CMS предоставляет параметр переключателя, который используется для запуска процесса слияние и сортировка фрагментов памяти, когда CMS не выдерживает FullGC, но процесс сортировки памяти не может быть параллельным, фрагментация пространства ушла, но время паузы увеличилось
G1: сборщик мусора для серверных приложений.
Функции:
1. Параллельность с параллелизмом: G1 может в полной мере использовать аппаратные преимущества ЦП и многоядерной среды, а также использовать несколько ЦП (ЦП или ядро ЦП), чтобы сократить время паузы Stop-The-World. Некоторым другим сборщикам изначально необходимо приостановить действие GC, выполняемое потоком Java, но сборщик G1 все же может позволить программе Java продолжать выполнение параллельным образом.
2. Коллекция поколений: Концепция коллекции поколений все еще сохраняется в G1. Хотя G1 может управлять всей кучей GC независимо, без сотрудничества с другими сборщиками, он может по-разному обрабатывать вновь созданные объекты и старые объекты, которые сохранились в течение некоторого времени и пережили несколько GC, чтобы получить лучшие эффекты коллекции. То есть G1 может управлять новым поколением и старым поколением самостоятельно.
3. Пространственная интеграция: поскольку G1 использует концепцию независимой области (Region), G1 основана на алгоритме «маркировки-сортировки» для достижения сбора с общей точки зрения и основана на алгоритме «копирования» из с локальной (двух областей) точки зрения, но в любом случае оба алгоритма означают, что при работе G1 не происходит фрагментация пространства памяти.
4. Предсказуемая пауза: это еще одно важное преимущество G1 перед CMS.Уменьшение времени паузы является общей задачей G1 и CMS, но в дополнение к достижению низкой паузы, G1 также может установить предсказуемую модель времени паузы, которая может использовать это чтобы явно указать, что квант времени длиной M миллисекунд не должен тратить более N миллисекунд на сборку мусора
3. Как справиться с остановкой мира
Это одно или два предложения непонятны.Заинтересованные друзья могут поискать учебник в Интернете.
4. Определить, жив ли объект
Обычно есть два способа определить, жив ли объект:
подсчет ссылок: Каждый объект имеет атрибут счетчика ссылок.При добавлении новой ссылки счетчик увеличивается на 1. Когда ссылка освобождается, счетчик уменьшается на 1. Когда счетчик равен 0, его можно перезапустить. Этот метод прост и не может решить проблему циклической ссылки объектов друг на друга.
Анализ достижимости: Поиск вниз от корней GC, и путь, пройденный поиском, называется цепочкой ссылок. Когда у объекта нет цепочки ссылок, связанной с корнями GC, объект считается недоступным. Недоступный объект.
В языке Java корни GC включают:
Объекты, на которые есть ссылки в стеке виртуальной машины.
Объект, на который ссылается объект статического свойства класса в области методов.
Объект, на который ссылается константа в области метода.
Объекты, на которые ссылается JNI в собственном стеке методов.
2. Компьютерная сеть:
1. Трехстороннее рукопожатие TCP, четырехсторонний волновой процесс и различные состояния
трехстороннее рукопожатиеПервое рукопожатие: хост A отправляет битовый код syn=1 и случайным образом генерирует на сервер пакет данных с порядковым номером = 10001. Хост B известен как SYN=1, и A запрашивает установление соединения. , статус SYN_SENT; Второе рукопожатие: хост B должен подтвердить онлайн-информацию после получения запроса и отправляет номер подтверждения = (seq + 1 хоста A), syn = 1, ack = 1 и случайным образом генерирует пакет seq = 20001. При этом время статус меняется с LISTEN на SYN_RECV; Третье рукопожатие: после того, как хост А получит его, проверьте правильность номера подтверждения, то есть, отправлен ли номер последовательности +1 в первый раз, и равен ли битовый код подтверждения 1, если он правильный, хост А отправьте номер подтверждения = (последовательность узла B + 1), подтверждение = 1, после того как узел B получит его и подтвердит значение последовательности и подтверждение = 1, соединение будет установлено успешно, и обе стороны будут в состоянии ESTABLISHED.
После завершения трехэтапного рукопожатия хост A и хост B начинают передавать данные
-
Каждое название штата и значение
ЗАКРЫТО: Об этом нечего сказать, это исходное состояние. ПРОСЛУШИВАНИЕ: Это также очень простое для понимания состояние, указывающее, что SOCKET на стороне сервера находится в состоянии прослушивания и может принимать соединения. SYN_RECV: Это состояние указывает на то, что сообщение SYN было получено. В нормальных условиях это состояние является промежуточным состоянием во время трехстороннего сеанса рукопожатия SOCKET на стороне сервера при установлении TCP-соединения. Оно очень кратковременно. В основном , с netstat вряд ли можно увидеть это состояние, если только специально не писать клиентконтрольная работаПрограмма намеренно не отправляет последнее сообщение ACK в процессе трех рукопожатий TCP. Следовательно, в этом состоянии после получения сообщения ACK от клиента он перейдет в состояние ESTABLISHED. SYN_SENT: это состояние повторяет SYN_RECV, когда клиент SOCKET выполняет соединение CONNECT, он сначала отправляет сообщение SYN, поэтому он переходит в состояние SYN_SENT и ждет, пока сервер отправит второе сообщение в трехстороннем рукопожатии. Состояние SYN_SENT указывает, что клиент отправил сообщение SYN. ESTABLISHED: Это легко понять, это означает, что соединение установлено.
-
помахал четыре раза
FIN_WAIT_1: Это состояние нужно хорошо объяснить.На самом деле реальное значение состояний FIN_WAIT_1 и FIN_WAIT_2 — это ожидание FIN-сообщения другой стороны. Разница между этими двумя состояниями заключается в следующем: состояние FIN_WAIT_1 на самом деле, когда SOCKET находится в состоянии ESTABLISHED, он хочет активно закрыть соединение и отправляет сообщение FIN другой стороне.В это время SOCKET входит в состояние FIN_WAIT_1. Когда другая сторона отвечает на сообщение ACK, она переходит в состояние FIN_WAIT_2.Конечно, при нормальных обстоятельствах другая сторона должна немедленно ответить на сообщение ACK независимо от ситуации.Поэтому состояние FIN_WAIT_1, как правило, сложнее см. Статус FIN_WAIT_2 иногда можно увидеть с помощью netstat.
FIN_WAIT_2: Это состояние было подробно объяснено выше.На самом деле SOCKET в состоянии FIN_WAIT_2 представляет собой полусоединение, то есть одна сторона запрашивает закрыть соединение, но также сообщает другой стороне, что у меня еще есть данные для отправить вам на данный момент Закройте соединение.
TIME_WAIT: Указывает, что получено сообщение FIN от другой стороны и отправлено сообщение ACK.После 2MSL он может вернуться в доступное состояние CLOSED. Если в состоянии FIN_WAIT_1, когда сообщение с флагом FIN и флагом ACK получено от другой стороны, она может напрямую перейти в состояние TIME_WAIT, минуя состояние FIN_WAIT_2.
ЗАКРЫТИЕ: Это совершенно особое состояние, оно должно быть редким в реальных ситуациях и относится к относительно редкому состоянию исключения. В обычных обстоятельствах, когда вы отправляете сообщение FIN, само собой разумеется, что вы должны сначала получить (или одновременно получить) сообщение ACK другой стороны, а затем получить сообщение FIN другой стороны. Однако состояние CLOSING означает, что после отправки сообщения FIN вы не получили сообщение ACK от другой стороны, а вместо этого получили сообщение FIN от другой стороны. При каких обстоятельствах это происходит? На самом деле, подумав, нетрудно прийти к выводу: то есть, если обе стороны одновременно закрывают SOCKET, то будет ситуация, когда обе стороны отправляют FIN-сообщения одновременно, то есть появится состояние CLOSING, указывающее, что обе стороны закрывают соединение SOCKET.
CLOSE_WAIT: значение этого состояния на самом деле означает, что он ожидает закрытия. Как понять это? Когда другая сторона закрывает SOCKET и отправляет себе сообщение FIN, ваша система, несомненно, ответит другой стороне сообщением ACK, а затем войдет в состояние CLOSE_WAIT. Далее, что вам действительно нужно рассмотреть, так это посмотреть, есть ли у вас еще данные для отправки другой стороне.Если нет, то вы можете закрыть SOCKET и отправить сообщение FIN другой стороне, то есть закрыть соединение. Итак, вы находитесь в состоянии CLOSE_WAIT, и вам нужно дождаться, пока вы закроете соединение. LAST_ACK: Это состояние относительно легко понять, оно пассивно закрывает сторону и ожидает сообщения ACK от другой стороны после отправки сообщения FIN. Когда сообщение ACK получено, он может войти в доступное состояние CLOSED.
-
Почему установление протокола соединения представляет собой трехстороннее рукопожатие, а закрытие соединения — четырехстороннее рукопожатие?? Это связано с тем, что когда SOCKET в состоянии LISTEN сервера получает запрос на установление соединения сообщения SYN, он может отправить ACK и SYN (ACK действует как ответ, а SYN действует как синхронизация) в одном пакете для отправки. Но при закрытии соединения, при получении уведомления о FIN-сообщении другой стороны, это просто означает, что у другой стороны нет данных для отправки вам; но не все ваши данные отправляются другой стороне, поэтому вы не обязательно сразу закрываете SOCKET. , то есть вам также может потребоваться отправить некоторые данные другой стороне, а затем отправить другой стороне сообщение FIN, чтобы указать, что вы согласны с тем, что соединение теперь может быть закрыто, поэтому сообщение ACK и сообщение FIN здесь отправляется отдельно в большинстве случаев.
-
Почему состояние TIME_WAIT должно ждать 2MSL перед возвратом в состояние CLOSED?? Потому что хотя обе стороны соглашаются закрыть соединение, и 4 сообщения рукопожатия были отправлены, разумно вернуться в состояние CLOSED напрямую (так же, как из состояния SYN_SENT в состояние ESTABLISH), но мы должны представить, что сеть ненадежна, вы не можете гарантировать, что последнее сообщение ACK, отправленное вами (клиентом), будет получено другой стороной, то есть SOCKET в состоянии LAST_ACK другой стороны может повторно отправить сообщение FIN из-за тайм-аут и не может получить сообщение ACK, поэтому роль состояния TIME_WAIT заключается в повторной передаче сообщений ACK, которые могут быть потеряны.
-
Требуется ли 4 волны для закрытия TCP-соединения? Не обязательно, 4 волны для закрытия TCP-соединения — самый безопасный способ. Но иногда нам не нравится состояние TIME_WAIT (например, когда значение MSL установлено слишком большим, слишком много TCP-соединений в состоянии TIME_WAIT на стороне сервера, уменьшение количества этих записей может быстрее закрыть соединение и высвободить больше ресурсов для новых подключений). В это время мы можем предотвратить переход SOCKET в состояние TIME_WAIT после закрытия(), установив флаг SO_LINGER переменной SOCKET. В это время TCP-соединение будет принудительно прервано путем отправки RST (заменяет обычный метод завершения четырехэтапного рукопожатия TCP). Но это не очень хорошая идея, TIME_WAIT нам часто выгодно.
2. Какой этап трехэтапного рукопожатия соответствует принятию соединения, прослушиванию
- Функция Connect(): блокирующая функция для установления соединения с родительским сервером через трехстороннее рукопожатие TCP.
Клиент активно подключается к серверу.Метод подключения устанавливается через трехстороннее рукопожатие TCP, чтобы уведомить ядро Linux для автоматического завершения соединения трехстороннего рукопожатия TCP.Если соединение установлено успешно, это 0, а ошибка возвращается значение равно -1.
Как правило, функция подключения клиента по умолчанию блокирует поведение до тех пор, пока фаза трехэтапного рукопожатия не будет успешной.
2. Функция listen() на стороне сервера: не блокирующая функция: Функция: сообщает ядру Linux длину сокета и соответствующую очередь сокета.
Он пассивно подключен и прослушивает запросы от разных клиентов.Функция прослушивания имеет только функцию превращения socketfd в сокет прослушивания пассивного соединения.Параметр backlog используется для установки длины очереди в ядре.
3.accept() блокировка функции: вынуть завершенное соединение из очереди в установленном состоянии.Если в очереди нет завершенного соединения, оно будет заблокировано до тех пор, пока пользовательское соединение, завершившее соединение в очереди, не будет удалено.
Вопрос 1: Что делать, если сервер вовремя не вызывает функцию accept, чтобы забрать очередь, завершившую соединение?
После того, как очередь соединений сервера заполнена, сервер не будет отвечать на синхронизацию, которая устанавливает новое соединение, поэтому соединение клиента вернет ETIMEDOUT. Но на самом деле Linux не такой: когда очередь TCP-соединения заполнена, Linux не откажет в соединении, как сказано в книге, а задержит соединение.
3. Операционная система:
1. компоновка программы linux c
Программа по существу состоит из трех сегментов: сегмента BSS, сегмента данных и текстового сегмента. Видно, что исполняемая программа делится на три части: сегмент кода, область данных и неинициализированная область данных при ее сохранении (не загрузке в память).
- Сегмент BSS (область неинициализированных данных): в архитектуре, использующей сегментированное управление памятью, сегмент BSS (сегмент bss) обычно относится к области памяти, используемой для хранения неинициализированных глобальных переменных в программе. BSS — это аббревиатура от Block Started by Symbol на английском языке. Сегмент BSS относится к выделению статической памяти.
- Сегмент данных: в архитектуре, использующей сегментированное управление памятью, сегмент данных обычно относится к области памяти, используемой для хранения инициализированных глобальных переменных в программе. Сегмент данных представляет собой выделение статической памяти.
- Сегмент кода: в архитектуре, использующей сегментированное управление памятью, сегмент кода (текстовый сегмент) обычно относится к области памяти, используемой для хранения кода выполнения программы. Размер этой части области был определен до запуска программы.и область памяти доступна только для чтения. В сегменте кода также могут быть некоторые постоянные переменные только для чтения, такие как строковые константы и т. д.
Объектный файл, сгенерированный после компиляции программы, содержит как минимум эти три сегмента, общая структура этих трех сегментов следующая:
Текстовый сегмент и сегмент данных были выделены во время компиляции, иСегмент BSS не занимает размер исполняемого файла, его получает линкер для получения памяти.
Содержимое сегмента bss (неинициализированные данные) не хранится в программных файлах на диске. Причина этого в том, что ядро устанавливает их в 0 до запуска программы. В файле программы необходимо сохранить только текстовый сегмент и сегмент данных инициализации.
Сегмент данных (инициализированные данные) выделяет место для данных, и данные сохраняются в целевой файл.
Сегмент данных содержит инициализированные глобальные переменные и их значения. Размер сегмента BSS получается из исполняемого файла, а затем компоновщик получает блок памяти этого размера сразу после сегмента данных. Когда эта память попадает в адресное пространство программы, она вся очищается.Вся секция, содержащая сегмент данных и сегмент BSS, теперь обычно называется областью данных.
Исполняемая программа имеет еще две области во время работы: область стека и область кучи.
(4) Область стека: она автоматически освобождается компилятором и хранит значения параметров и локальные переменные функции. Всякий раз, когда вызывается функция, возвращаемый тип функции и некоторая информация о вызове помещаются в стек. Затем вызываемая функция выделяет место в стеке для своих автоматических и временных переменных. Каждый раз при вызове функции используется новый стек. Область стека увеличивается от старших битов адреса к младшим битам адреса. Это непрерывная область памяти. Максимальная емкость предварительно определяется системой. Когда используемое пространство стека превышает этот предел, будет выведен запрос о переполнении, и получить его из стека.Места мало.
(5) Область кучи: используется для динамического выделения памяти, расположенной в адресной области между BSS и стеком. Выделяется и освобождается программистом. Куча увеличивается от младших битов адреса к старшим битам адреса, используя цепную структуру хранения. Частый вызов malloc/free приводит к разрыву памяти, что приводит к фрагментации. При выделении места в куче библиотечная функция ищет доступное достаточно большое пространство по определенному алгоритму. Поэтому эффективность кучи гораздо ниже, чем у стека.
На следующем рисунке будет отражено соответствующее пространство для хранения исходного файла c:
В это время программа в память не ставится, а только хранится на жестком диске.В это время bss места не занимает. bss получает место в памяти во время компоновки.
На следующем рисунке показана работающая программа, то есть схема хранения программы, когда она находится в памяти:
4. Вопросы разведки:
Монета неравномерная, как оформить ее как честную монету (отбраковка выборки)Этот вопрос оставлен для того, чтобы вы задумались и развеяли свои мысли.В конце концов, кого не запугивала головоломка!
пять,Алгоритмы и структуры данных:
Сортировка кучи Процесс сборки и сортировки кучи
Просто упомяните это здесь строить кучу Переключение вниз с первого нелистового узла (то есть каждая корректировка заключается в выборе наибольшего из родительского узла, левого дочернего узла и правого дочернего узла для обмена с родительским узлом (после обмена замененные дочерние узлы могут быть вызваны ) Узел не удовлетворяет характеру кучи, поэтому переставляемые дочерние узлы необходимо перенастраивать после каждого обмена).После того, как начальная куча доступна, можно выполнять сортировку) Сортировать Процесс сортировки — это операция извлечения верхнего элемента кучи и деталей реализации (обмен местами верхнего элемента кучи и хвостового элемента кучи и корректировки верхнего элемента кучи вниз по куче — в каждом процесс регулировки, когда он не регулируется вниз, это конец регулировки. ). Порядок извлечения: первый нелистовой узел, второй нелистовой узел... вплоть до вершины кучи
Я также спросил о временной сложности настройки кучи, и я не буду вдаваться в подробности.
порванный вручную:
самая длинная неповторяющаяся подстрока
идеи и решения
Идея 1: Насильственный метод.Насильственный метод не будет использоваться в реальном решении проблем.Это не значит, что мы можем его игнорировать.
Индекс начинается с первого символа строки, а следующие символы добавляются к набору по очереди. Если символ уже существует в наборе, цикл завершается, и размер записывается после завершения внутреннего цикла. Каждый бит строки вычисляется таким образом, и наибольший полученный размер является ответом.
Код выглядит следующим образом (не Java тоже может понять, я прокомментировал синтаксис ключа, то же самое ниже)
public int lengthOfLongestSubstring(String s) {
int maxLen = 0;
for(int i = 0; i < s.length(); i++){
// 创建一个存放字符的集合
HashSet<Character> set = new HashSet<>();
for(int j = i; j < s.length(); j++) {
// 判断集合是否存在第 j 个字符
if(set.contains(s.charAt(j)))
break;
set.add(s.charAt(j));
}
maxLen = Math.max(maxLen,set.size());
}
return maxLen;
}
Здесь выложено только это одно решение, там много интересных решений, тоже можно разойтись.
Вторая сторона: 1 час 10 минут
Проект: Идеи дизайна, самая большая проблема, с которой столкнулись, как обеспечить глобальную уникальность первичного ключа в распределенной ситуации (проект уже давно болтается....) Вопрос сценария: Как обеспечить производительность, когда большое количество хостов отправляют сообщения на сервер (в то время я не понимал смысла, поэтому я говорил о модели ввода-вывода, и меня спросили, использовал ли я когда-либо epoll)
компьютерная сеть:
1. Один и тот же tcp трижды четырежды старые восемь акций
Я говорил это раньше, пропусти это здесь
2. Принцип реализации TCP Keep Alive
По сути, принцип работы keepalive — это сердцебиение пакета, встроенного в TCP. Возьмем, к примеру, серверную сторону: если текущая серверная сторона обнаружит отсутствие передачи данных в течение определенного периода времени (по умолчанию 7 200 000 миллисекунд, что составляет 2 часа), она отправит клиенту пакет проверки активности. стороны (пакет проверки активности — это ACK, а текущий порядковый номер TCP минус один), клиент должен находиться в одной из следующих трех ситуаций:
-
Сторона клиента все еще существует, и сетевое соединение находится в хорошем состоянии. В этот момент клиентская сторона вернет ACK. Сервер сбрасывает таймер после получения ACK и отправляет зонд через 2 часа. Если есть передача данных по соединению в течение 2 часов, то задержать время на 2 часа.
-
Клиент был отключен аварийно или сеть была отключена. В обоих случаях клиентская сторона не будет отвечать. Сервер не получает ответа на отправленный ему зонд и повторяет пакет проверки активности через определенное время (система по умолчанию 1000 мс) и повторяет его определенное количество раз (система 2000 XP 2003 по умолчанию 5 раз система дефолтная после Висты) 10 раз).
-
Раньше клиент вылетал, но он был перезапущен. В этом случае сервер получит ответ на свою проверку живучести, но ответ будет сбросом, в результате чего сервер разорвет соединение.
3. липкий пакет TCP
Блог Woohoo.cn на.com/year77626523…
Три стороны: 1 час
Проект: расспросили обо всех проектах, дизайнерских идеях и столкнулись с самой большой трудностью.
Вы можете рассказать правду о своем опыте в этом, нечего сказать
операционная система:
1. Пересмотрел malloc, который не ответил хорошо (из-за схемы памяти, алгоритма распределения списка свободных блоков и системных вызовов все сказано снова)
2.copyonwrite
идея копирования при записи
Копирование при записи (CopyOnWrite, сокращенно COW) — это общая стратегия оптимизации в области компьютерного программирования. Основная идея заключается в том, что если несколько вызывающих объектов (Callers) одновременно получают доступ к одному и тому же ресурсу (например, к памяти или хранилищу данных на диске), они совместно получат один и тот же указатель на один и тот же ресурс, пока вызывающий объект не изменит ресурс. будет фактически копировать частную копию вызывающему объекту только тогда, когда содержимое присутствует, в то время как исходные ресурсы, видимые другими вызывающими объектами, остаются неизменными. Этот процесс прозрачен для других вызывающих абонентов. Основное преимущество этого подхода заключается в том, что если вызывающая сторона не изменит ресурс, частная копия не будет создана, поэтому несколько вызывающих сторон могут совместно использовать один и тот же ресурс только для операций чтения.
Проще говоря, технология копирования при записи заключается в том, что когда разные процессы обращаются к одному и тому же ресурсу, только операция обновления копирует новые данные, обновляет и заменяет их, в противном случае все обращаются к одному и тому же ресурсу.
Контейнер CopyOnWriteArrayList/CopyOnWriteArraySet JDK использует идею COW Как это работает? Проще говоря, когда вы запрашиваете, вам не нужно блокировать и получать доступ к нему случайно.Только при обновлении копия будет скопирована из исходных данных, затем копия будет изменена, и, наконец, исходные данные будут заменены с текущей копией. В то же время, что и операция модификации, операция чтения не будет заблокирована, а продолжит чтение старых данных. Это следует отличать от блокировки чтения-записи.
Анализ исходного кода
Давайте сначала взглянем на метод add() в CopyOnWriteArrayList, который на самом деле очень прост: блокировка при доступе, копирование копии, сначала работа с копией, а затем замена существующих данных этой копией.
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
Метод get(int index) CopyOnWriteArrayList представляет собой обычный доступ без блокировки.
public E get(int index) {
return get(getArray(), index);
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
return (E) a[index];
}
плюсы и минусы
1. Преимущества
Для некоторых данных, которые больше читаются и меньше записываются, практика копирования при записи очень хороша, например, данные с очень небольшим количеством изменений, такие как конфигурация, черный список, логистический адрес и т. д. Это реализация без блокировки. Это может помочь нам достичь более высокой параллелизма программы.
CopyOnWriteArrayList безопасен для параллелизма и работает лучше, чем Vector. Vector — это метод добавления, удаления, изменения и проверки с помощью synchronized для обеспечения синхронизации.Однако при выполнении каждого метода должна быть получена блокировка, и производительность будет сильно снижена.CopyOnWriteArrayList добавляет блокировки только на добавление, удаление, и изменяет, но читает без блокировки.По производительности лучше Вектора.
2. Недостатки
Проблемы согласованности данных. Эта реализация обеспечивает только окончательную согласованность данных, при добавлении к скопированным данным, но не замене, старые данные все равно считываются.
Проблема с использованием памяти. Если объект относительно большой, частая замена будет потреблять память, что вызовет проблемы со сборщиком мусора в Java.На данный момент мы должны рассмотреть другие контейнеры, такие как ConcurrentHashMap
компьютерная сеть:
1. Как обеспечить надежную передачу udp на прикладном уровне 2. Разница между https и http и механизм рукопожатия ssl https 3. Почему https использует комбинацию симметричного и асимметричного шифрования
Вопросы для мозгового штурма:
1. От rand5 до rand7 считается отказом от выборки, что очень похоже на идею одной стороны 2. Есть 32 камня одинакового размера, и есть шкала, сколько раз хотя бы вы сможете найти камень с наибольшей массой? второй по величине А как насчет энного по величине
Оторвать рукой:
Serpentine, пересекающий массив
Чат:
Какие книги вы обычно читаете и какие технические сайты вы читаете? как долго можно риторический вопрос
часовая поверхность
Об этом и говорить нечего.Если не можешь говорить о технике, просто болтай вскользь, не болтай до смерти.
Я был немного удивлен, что меня не спросили о базе данных.Ведь база данных была самой подготовленной.Видно было, что отдел придавал большое значение операционной системе и компьютерной сети, и алгоритмы были доступны ли они разорванные вручную или орально, так что на них все равно нужно было обратить внимание.
Времени мало. Если у вас есть время, наверстать остальное. Давай сначала сделаем это, Руи Сибай! Не забудьте взять информацию
Горячие статьи в прошлом:
- Краткое изложение основ Java
- Серия по настройке производительности (JVM, MySQL, Nginx и Tomcat)
- От выгона до пяти предложений по 30 000+
- Анализ 100 проектов Java с исходным кодом и учебными документами!
end