As perguntas de nível médio combinam duas ideias: ordenar e depois varrer, um dicionário mais uma lista encadeada, contar mais ordenar. Quem entrevista observa como você escolhe as estruturas de dados e se consegue dizer quanto custa cada operação. Espere uma pergunta complementar em cada uma: "e se a entrada for enorme?", "dá para fazer get e put em O(1)?", "e com uma entrada inválida?".
Trabalhe como faria na sala: diga como é a entrada, escolha primeiro os casos de borda (entrada vazia, um item, duplicados, valores grandes), diga o tempo e o espaço de que a sua solução precisa e só então programe. Cada problema tem testes ocultos justamente sobre esses casos de borda.