Algoritmo de Floyd [fechado]

É possível (esperado) que um indivíduo descubra (nunca o tinha visto antes) o algoritmo se solicitado em uma entrevista? Que outros problemas têm soluções igualmente interessantes?

Edit: Devido à confusão do algoritmo real a que me refiro, é o algoritmo de descoberta de ciclo do Floyd , também conhecido como algoritmo de tartaruga e lebre.

Bem, nada é impossível como eles dizem.

No entanto, se você nunca ouviu falar de Dijkstra ou Flloyd, é quase impossível descobrir isso no espaço de uma única entrevista.

As pessoas passam a vida inteira desenvolvendo um único algoritmo, apenas no caso de você estar pensando sobre isso.

Não, não é. Levou anos para os maiores matemáticos / cientistas da computação de seu tempo formularem esses algoritmos; você não fará o mesmo em 2 minutos enquanto estiver sob pressão.

Para a segunda parte da sua pergunta ... Bem, eu realmente não sei o que você considera interessante aqui. Se seus algoritmos, estruturas de dados e combinatória do que você gosta, basta ler "A arte ou programação de computadores", não fica muito melhor do que isso.

Os entrevistadores podem fazer uma pergunta impossível ou sem sentido para ver suas reações.

Eles estão apenas querendo entender sua abordagem dos problemas, não necessariamente o próprio conhecimento.

Há tantas informações disponíveis para reter, que o importante é a competência do Google e como consumir informações de uma mangueira de incêndio.

Como @ fanatic23 disse, se você nunca ouviu falar de Dijsktra, é muito difícil descobrir o algoritmo de Floyd, no entanto, se você estudou graficamente, Floyd é um dos algoritmos básicos. Se você estiver procurando posições de trabalho que exijam que você tenha algumas habilidades algorítmicas competentes, recomendamos que você leia pelo menos alguns algoritmos considerados importantes ao usar gráficos:

• DFS e BFS para atravessar o gráfico
• Kruskal e Prim para obter um MST
• Dijsktra é um dos mais importantes no problema do caminho
• Floyd - Warshall e Bellman-Ford são os outros importantes no problema do caminho

Com esses quatro tópicos, você pode navegar por qualquer pergunta básica a média do gráfico em uma entrevista.

Como esta é uma pergunta de entrevista, você sempre deve se perguntar a pergunta mais importante primeiro:

O que um empregador em potencial pode esperar de um candidato típico e como posso me sair melhor?

Obviamente, quase ninguém (e certamente não um candidato prototípico) será capaz de realizar trabalhos que levaram cientistas brilhantes anos dentro dos limites de tempo de uma entrevista. Então não é isso que eles esperam de você.

O que mais o empregador poderia esperar?

• Você já deve conhecer o algoritmo. Isso é simples e chato. Você pode dizer isso e muito provavelmente o tópico será alterado, porque não há muito mais a ser aprendido sobre você (do ponto de vista do empregador).

• Você pode não conhecer o algoritmo. Este é realmente o estado típico do candidato, e se isso é esperado, qual deve ser o resultado? Considere a perspectiva da empresa aqui e você descobrirá que provavelmente não é uma coisa boa se um candidato não puder afirmar o óbvio: eu não conheço esse algoritmo. Se você começar a dar frases vagas e falar sobre o problema real aqui, terá uma má impressão. Portanto, o objetivo principal de fazer essa pergunta não é esperar que você seja capaz de responder, mas testar sua reação ao encontrar coisas que você não conhece.

• Você pode não conhecer o algoritmo, mas ... voltando à pergunta original acima: como você pode fazer melhor? Você pode conhecer algoritmos semelhantes, portanto, explique as semelhanças que reconhece (por exemplo, o algoritmo Tortoise + Hare de Floyd usa uma abordagem semelhante ao algoritmo de Polard-Rho). Você pode ter habilidades impressionantes de leitura / compreensão de código, etc. É claro que essa parte é a mais difícil, mas, novamente, só estará disponível se você for realmente melhor do que o candidato médio, o que, por definição, facilita as coisas.

É possível (esperado) que um indivíduo descubra (nunca o tinha visto antes) o algoritmo se solicitado em uma entrevista?

É possível? Isso depende do algoritmo e do candidato. Eu diria que a grande maioria dos candidatos lutaria para realmente fazer esse tipo de coisa. (Se esses problemas eram simples assim, por que alguém seria famoso por tê-los resolvido?)

Isso é esperado? Isso depende dos pontos fracos do entrevistador e de suas expectativas em relação aos candidatos. Eu diria que, se eles realmente esperam que os candidatos consigam fazer esse tipo de coisa em uma entrevista, eles terão que entrevistar muitos candidatos. Uma pergunta como essa é mais provável de ser feita para ver como o candidato trabalha / pensa sob pressão.

Que outros problemas têm soluções igualmente interessantes?

Eu não vou responder a isso. Em vez disso, vou dizer que:

• A probabilidade de você (como candidato) fazer isso é pequena, para um trabalho típico. No entanto, se você estiver se candidatando a um trabalho de TI especializado em que exista um requisito específico para conhecer algoritmos específicos, pode ser solicitado que você os explique.

• Pouco adianta aprender a derivar algoritmos, caso seja solicitado. (Ou "trapaça", conhecendo o algoritmo de antemão.) Se você realmente for solicitado a fazer isso, tente o seu melhor ... sabendo que a maioria dos outros candidatos provavelmente também enfrentará dificuldades.

• É útil conhecer uma série de algoritmos, ou pelo menos conhecê-los , porque eles podem se mostrar úteis em seu trabalho. No entanto, isso depende muito do campo de TI em que você trabalhará.