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

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épondre

Réponse de l'entretien

2 réponses

0

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
0

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 aonecode.com 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 aonecoding@gmail.com with any questions. Thanks!

aonecode.com, le 23 août 2017

Ajouter des réponses ou des commentaires

Pour commenter ceci, se connecter ou s'inscrire