Values From List of Lists

Good day! I am approaching the end of my workday. My wife is in the kitchen preparing chocolate frosting for a chocolate cake she baked this morning. We were going to have a piece after lunch, but she was busy and did not get to the frosting.

Yesterday evening my wife and I watched the film No Time To Die which is the last James Bond movie with Daniel Craig. I am a 007 fan. Growing up I read all the novels by Ian Fleming who created the James Bond character. I have watched most of the James Bond  films on opening night. This time I decided to wait for the film to be streamed from home.

Of course, there were a few books by Ian Fleming but there are much more films. In other words, most of the films are not based on the original books.

The last two films with Daniel Craig are Spectre and No Time To Die. I did not like Spectre at all. In my rankings it was the worst James Bond film at the time. After watching the new release, I can say that I did not like it either. I would rank it a small notch above the previous movie.

I have not much to say about Daniel Craig. As an actor he can help the delivery of the script, but that is it. If the story and script are not good, the film will follow. Daniel Craig has grown too old to play the 007 role. This is why No Time To Die was the last James Bond film for him.

The original character of James Bond was not represented in this film. The film was slow and his feelings were out of character. The movie was about 2.75 hours in length. To be honest, towards the end I was checking my watch to estimate how much of the movie was left.

There is a film named Knives Out with Daniel Craig and one of the Bond girls Ana de Armas. My wife and I have watched that film a few times. The plot and delivery by most actors is right on. The same cannot be said about No Time to Die.

If you are a fan of James Bond as I am, you must watch the film and then make up your own mind. The taste in people regarding films is hard to quantify. Many times we watch a movie highly rated and it turns out to be a disaster. Not too many times have we experienced the opposite.

On a side note, I was not able to finish this post yesterday. Will complete it right now.

The main subject for this post is a problem that a software engineer and I were talking about earlier this week. I believe I have solved years ago a similar one in which arrays were used instead of lists.

Given a list of lists the lists holding integers 
in ascending order but skipping values,
return a list of all integers in ascending order.

Constraints:
o 2 <= k <= 5
o 0 <= n <= 30

We are given a list of lists. Each list holds integers in ascending order but not consecutive. Our mission, should we choose to accept it, would be to develop a function that will take as input a list of list and return a list with all integers in order. You should not expect that all numbers are in monotonically ascending order. Some numbers might not be in the lists. In our examples I decided to provide all integers in the range 1.. N. You should be able to modify the test scaffold and skip some integers.

The constraints contain small values. I also did this for ease of use while developing the solution. You should expect larger boundaries for `n` and `k`. Try to develop a solution that is not dependent on the current boundaries.

We will attempt to solve the problem using the Java programming language and the VSCode IDE on a Windows machine. You are welcome to use any other language, IDE or platform. It is quite simple to determine if your solution works. The results must be in a monotonically ascending order.

public List<Integer> orderedList(List<List<Integer>> lol) {
}

The signature for the function of interest is simple. We are provided with a list of lists of Integers and need to return a list with all the integers in ascending order.

To develop and test the solution we will need to create a test scaffold. It should generate and populate the list with lists holding different numbers of integers. Some lists may be empty.

main <<< k: 2
main <<< n: 8
main <<< lol: [[0, 1, 2, 4, 6], [3, 5, 7]]
main <<< result: [0, 1, 2, 3, 4, 5, 6, 7]


main <<< k: 5
main <<< n: 27
main <<< lol: [[9, 11], [6, 7, 15, 19, 22, 23, 24], [0, 1, 3, 8, 10, 14, 17, 18, 26], [2, 4, 12, 13, 16, 20, 25], [5, 21]]
main <<< result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]     


main <<< k: 5
main <<< n: 9
main <<< lol: [[2, 3], [5, 8], [0], [4, 7], [1, 6]]
main <<< result: [0, 1, 2, 3, 4, 5, 6, 7, 8]


main <<< k: 2
main <<< n: 3
main <<< lol: [[], [0, 1, 2]]
main <<< result: [0, 1, 2]

The test code generates `k` for the number of lists and `n` for the total number of integers.

With that information, the list of lists is populated and displayed. We are now ready to call the function of interest which should generate the output list, and then display it so we can verify if our solution works or not.

Note that each time the program runs, it will generate different values for `k` and `n`.

After all is said and done the test code displays the result list which should have all integer values in ascending order.

    /**
     * Test scaffold
     */
    public static void main(String[] args) {
        
        // **** determine the number of lists to use ****
        Random rand = new Random();
        int k       = 2 + rand.nextInt(4);

        // ???? ????
        System.out.println("main <<< k: " + k);

        // **** determine the number of integers to use ****
        int n = k + rand.nextInt(k * 5);

        // ???? ????
        System.out.println("main <<< n: " + n);

        // **** declare list of lists ****
        List<List<Integer>> lol = new ArrayList<List<Integer>>(k);

        // **** create lists ****
        for (int i = 0; i < k; i++)
            lol.add(new ArrayList<Integer>());

        // **** populate lists ****
        for (int i = 0; i < n; i++)
            lol.get(rand.nextInt(k)).add(i);

        // ???? ????
        System.out.println("main <<< lol: " + lol.toString()); 

        // **** ****
        System.out.println("main <<< result: " + inOrderList(lol).toString());
    }

We start by generating values for `n` and `k`.

We then declare the list of lists and create the specified lists. Note the lists are empty at this time.

We then populate the lists by selecting a list in a random fashion.

We then display the contents of the list of lists, call the function of interest, and display the result list.

    /**
     * Auxiliary class
     */
    static class Pair {
        public int val;
        public int qn;

        public Pair(int val, int qn) {
            this.val = val;
            this.qn = qn;
        }

        @Override
        public String toString() {
            return "" + val + "," + qn;
        }
    }

There is not a standard Pair class in Java. Different packages implement such classes. Since it is quite simple, we went ahead and “reinvented the wheel” by creating such an auxiliary class.

The class has two members, one for the integer value and the other for the queue number. I guess I should have named it lstNum or something like that, but I did not. Sorry about that.

I also implemented the toString() method to allow us to display pairs while developing the solution.

I understand that most interviews are as obscure as possible to promote interaction and clarifications. In addition most of the software engineers I know, spend a few minutes thinking about an approach and associated complexity but do not dive into details. Details are addressed during implementation. This is my preferred approach to develop software. Of course I implement tests to validate my code. That said; a third party needs to develop tests to check your code. This is the approach used by most (never generalize) websites that are used to solve problems. Your code passes the presented tests and then after you are comfortable with the solution, you submit the code for additional testing and approval.

    /**
     * Given a list of lists the lists holding integers 
     * in ascending order but skipping values,
     * return a list of all integers in ascending order.
     * 
     * Execution: O(n) - Space: O(k)
     */
    static public List<Integer> inOrderList(List<List<Integer>> lol) {

        // **** initialization ****
        int k                   = lol.size();
        List<Integer> result    = new ArrayList<Integer>();
        PriorityQueue<Pair> pq  = new PriorityQueue<>(
            k,
            (p1, p2) -> (p1.val - p2.val)
            );

        // **** take a value from each list (prime the priority queue) - O(k) ****
        for (int i = 0; i < lol.size(); i++) {

            // **** get list from lol ****
            List<Integer> lst = lol.get(i);

            // **** get val from this list (if possible) ****
            if (lst.isEmpty()) continue;
            int val = lst.remove(0);

            // **** build pair for priority queue ****
            Pair p = new Pair(val, i);

            // **** add pair to priority queue ****
            pq.add(p);
        }

        // **** build the output list - O(n - k) ****
        while (!pq.isEmpty()) {

            // **** get next pair from the priority queue ****
            Pair p = pq.poll();

            // **** add val to result list ****
            result.add(p.val);

            // **** get list from lol ****
            List<Integer> lst = lol.get(p.qn);
        
            // **** generate pair from this list (if possible) ****
            if (lst.isEmpty()) continue;
    
            // **** pair for priority queue ****
            p = new Pair(lst.remove(0), p.qn);

            // **** add pair to priority queue ****
            pq.add(p);
        }

        // **** return the result list ****
        return result;
    }

We start by initializing a few data structures. Of interest is the priority queue. We want elements to be pulled in ascending order. That is specified by the comparator.

We then populate the priority queue with a single element from each list. The elements in the priority queue are of type Pair. The first element holds the value from the list, and the second element the number of the list (or queue) from which the element was extracted.

Now we are ready to build the output list. Since the integers in all the lists are in ascending order, the priority queue must now hold the smallest value pair. We will pull it out of the priority queue, insert the value into the result list, and pull the next element from the same list as indicated by the pair. As long as we repeat this loop we should be able to get all integers from all lists in ascending order.

Please look at the code in the loop to make sure you can follow the algorithm. I will wait here … OK, you are back.

After the loop completes, all lists are empty and the values have been transferred to the results list which is returned by our function of interest.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge, and enhance your developer / engineering toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Enjoy;

John

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.