Question d'entretien d'embauche Facebook: Find the length of the longes... |

Question d'entretien d'embauche

Entretien de Software Engineer New Grad

Find the length of the longest increasing subsequence (with

  gaps allowed) in a list

Réponse de l'entretien

2 réponses


Just used the standard dynamic programming approach. Apart from one line, my algorithm was identical to the DP 0-1 Knapsack solution.

Candidat à l'entretien, le 22 août 2017

O(nlogn) most optimal solution

    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length]; // initialized as Integer.MIN_VALUE
        int len = 0;
        for(int x : nums) {
            int i = Arrays.binarySearch(dp, 0, len, x);
            if(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++; //when x is the greatest by far
        return len;

Looking for interview experience sharing and coaching?

Visit for private lessons by FB, Google and Uber engineers

ONE TO ONE real-time coaching on SYSTEM DESIGN, ALGORITHMS, and mock interviews.

Feel free to email us with any questions. Thanks!, le 23 août 2017

Ajouter des réponses ou des commentaires

Pour commenter ceci, se connecter ou s'inscrire