Interview Practice: Leetcode 368. Largest Divisible Subset



Interview Practice: Leetcode 368. Largest Divisible Subset

This question is actually the modified version of "Longest Increasing Subsequence".
For my current number p, I check all the number that's larger than it and keep the max count from the numbers that can be divided by p.

Idea:
(1) Sort the array. Why? This can improve the efficiency. With sorted array, we can just compare the current number with the numbers after it. Otherwise, we need to compare all possible pairs.
(2) Create an array that store the count of numbers it can divide.
(3) Use two for loops. First we start from the largest number and go decreasingly. Second we start from the position of first for loop and go to the end of the array.
(4) For each number i, we check whether it can divide j. If yes, we compare the count in j with the max count we seen before. Keep the largest one.
(5) After compare number i with all number larger than it, we compare the count of i with the global max. If it's larger, keep the max count and the idx of i.
(6) We also keep another information. A map that point to the next number. What's this mean? If we have map i--> j , this means when we start from i, the longest path is go to j.
(7) In the end, we use the maxIdx and path mapping to reconstruct the path.


Read full article from Interview Practice: Leetcode 368. Largest Divisible Subset


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts