Questions d'entretien

Entretien de Software Engineer



Given a sorted list of numbers which has had some k numbers moved from the front of the list to the end of the list, write a program to find k (in O(log n) time)


Réponses aux questions d'entretien

2 réponse(s)


Find the pivot index and then k = n - (pivotIndex)

Pivot le


Binary search: Look for an instance where value of mid is larger than value of mid+1. This way mid+1 is your pivot index and k = n - pivotIndex. Complexity: O(lg n) - better than linear searching.

SubHuman le

Ajouter des réponses ou des commentaires

Pour commenter ceci, connectez-vous ou inscrivez-vous.