Meu professor passou um exercicio prático sobre Threads em Java que consiste em criar 4 Threads, onde cada uma percorra uma parte de um vetor, e a primeira Thread que encontrar um dado valor dentro desse vetor, deve informar as outras Threads que o objetivo ja foi concluido.
Bem, estou com duvida em como notificar as outras Thread que elas ja podem parar. Tentei bolar uma solução com interrupt() mas não consegui.
Alguém pode me dar uma luz do que devo fazer 
Talves o mais simples seja você ter um while dentro de cada Thread e nesse while voce compara se determinada variavel foi setada para parar.
Quando a primeira encontrar chama um metodo das classes das outras Threads informando que já encontrou.
Não sei se ajuda no seu caso,
Tem as aulas de nº 96 e 97, está última bem interessante.
Se nenhum destes 4 vídeos servir, ainda tem outro recurso:
Não existe nenhuma maneira de interromper uma thread preemptivamente em Java. Em outras palavras, você não consegue matar ou obrigar uma thread a parar de executar de forma forçada. A interrupção é muito mais um acordo do que uma ordem.
O que você deve fazer é criar uma espécie de protocolo. Pode ser algo assim: antes de ir para a próxima posição do vetor, você deve antes checar se a flag de interrupção da busca foi setada. Isso introduz um problema de condição de corrida: o acesso a essa variável deve ser sincronizado porque é alterado e lido por mais de uma thread. Se você não sincronizar, pode (e vai) acontecer de uma thread definir sinalizar a parada do serviço e as outras lerem valores desatualizados (mais conhecido como stale data), continuando o serviço de forma errada (o resultado já foi encontrado).
O método interrupt() meramente seta uma flag dentro do objeto Thread. Você pode checar essa flag constantemente dentro do seu Runnable ou na Thread mesmo. Inclusive, alguns métodos levam essa flag muito a sério, como o Thread.sleep por exemplo. Durante a execução desse método, se ele detectar que essa flag foi setada, ele lança uma InterruptedException e reseta o status da flag para false.
Como dito, a aula de nº 97 é a mais interessante, pois trata de objetos compartilhando a mesma informação, fazendo uso inclusive de sincronização: