#StackBounty: #python #python-3.x #flask #data-structures Sub-directory problem when making in-memory file system for Flask web app

Bounty: 50

I’m creating a virtual/in-memory file system as part of a Flask apps, where the user is creating files & folders and I’m saving them in a SQL DB and displaying the directory tree back to the user in the UI (think dropbox/google drive).

For reprex’ sake, the relevant metadata in both the ‘File’ and ‘Folder’ SQL tables would be: [‘object_id’, ‘parent_id’, ‘child_nodes’] where,

  • object_id = the unique identifier
  • parent_id = the parent object_id that a sub-file or sub-folder belongs to
  • child_nodes = the child object_ids of a parent

I created Project and File classes to handle internal methods & properties (excluded but necessary). So ideally I need the classes in my end solution.

The main problem I’m running into is appending sub-directories as child_nodes to directories. This is observable [in the commented out code at the bottom] when iterating from dir_list[1] to dir_list[2], where dir_list[1] would already have been appended to dir_list[0] and therefore wouldn’t reflect the following iteration.

Looking for any suggestion on how to implement this. I’m also entirely open to using different data structs altogether, so long as I can add metadata and format it the same way that FileDir.create_tree() does.

# Objects for organizing each struct -----
class File():
    def __init__(self, file_list):
        self.id = file_list[0]
        self.name = file_list[1]
        self.parent = file_list[2]
        self.directory = False

class Directory:
    def __init__(self, dir_list):
        self.id = dir_list [0]
        self.name = dir_list [1]
        self.parent = dir_list [2]
        self.child_nodes = []
        self.directory = True

    def add_file_node(self, node):

        node = {
                'id': node.id,
                'name':  node.name,
                'parent': self.parent,
                'is_dir': node.directory
            }
        self.child_nodes.append(node)

    def add_dir_node(self, node):

        node = {
                'id': node.id,
                'name':  node.name,
                'parent': self.parent,
                'is_dir': node.directory,
                'children': self.child_nodes
            }
        self.child_nodes.append(node)


    def return_tree(self):
        tree = {
            'name': self.name,
            'children': self.child_nodes,
            'parent': self.parent,
            'is_directory': self.directory
        }
        return tree



class FileDir():
    def __init__(self, dir_list):
        self.dir_list = dir_list
    def create_tree(self):
        tree = []
        for directory in self.dir_list:
            tree.append(directory.return_tree())
        return tree

# Example Data (formatted as 2d-list from my SQL query) -----
dir_list = [
         ['10001', 'dir_1', None],
         ['10002', 'dir_2', '10001'],
         ['10003', 'dir_3', '10002'],
         ['10004', 'dir_4', None]
     ]

file_list = [
         ['21110', 'file1.csv', None],
         ['21111', 'file2.csv', '10001'],
         ['21112', 'file3.csv', '10002'],
         ['21113', 'file3.csv', '10003']
     ]

dir_objs = [Directory(d) for d in dir_list]
file_objs = [File(f) for f in file_list]

for fil in file_objs:
    if fil.parent:
        for i, x in enumerate(dir_objs):
            if fil.parent == x.id:
                x.add_file_node(fil)


# TODO Append sub_folders
# ...
# 
# for d in dir_objs:
#    if d.parent:
#        for i, x in enumerate(dir_objs):
#            if d.parent == x.id:
#                x.add_dir_node(d)
#                dir_objs.remove(d)

tree = FileDir(dir_objs)
tree.create_tree()


Get this bounty!!!

#StackBounty: #algorithms #time-complexity #data-structures #sorting #arrays Find $k$'th smallest element in matrix with sorted rows

Bounty: 100

This is very hard question as mentioned on some site on google and firstly introduce on Interview Amazon Question.

We have an $mtimes n$ matrix in which all rows are sorted in ascending order and all elements are distinct. We want to find the $k$-th smallest element in this matrix.

There is an $O(m (log m + log n))$ algorithm for doing this!

I see lots of posts, especially here, but as Yuval Filmus mentioned in comments there are difference in large value of $k$.

We are familiar with median of medians method that throw half of elements with median, but here there is a very challenging question. How is this time complexity reached?

Update: this is exactly copy of one Ex. in Jeff Algorithms Book (Book Page 55 Ex: 21 Part C, Chapter Recursion :

enter image description here

As Yuval tell in comments, the previous question algorithms not complete so this is a good question for a complete algorithm in given time complexity.

Update 2: this is local multiple choice interview questions that we should choose the best option as the time complexity that I mentioned in my question (options listed here).

enter image description here


Get this bounty!!!

#StackBounty: #algorithms #time-complexity #data-structures #sorting #arrays Find $k$'th smallest element in matrix with sorted rows

Bounty: 100

This is very hard question as mentioned on some site on google and firstly introduce on Interview Amazon Question.

We have an $mtimes n$ matrix in which all rows are sorted in ascending order and all elements are distinct. We want to find the $k$-th smallest element in this matrix.

There is an $O(m (log m + log n))$ algorithm for doing this!

I see lots of posts, especially here, but as Yuval Filmus mentioned in comments there are difference in large value of $k$.

We are familiar with median of medians method that throw half of elements with median, but here there is a very challenging question. How is this time complexity reached?

Update: this is exactly copy of one Ex. in Jeff Algorithms Book (Book Page 55 Ex: 21 Part C, Chapter Recursion :

enter image description here

As Yuval tell in comments, the previous question algorithms not complete so this is a good question for a complete algorithm in given time complexity.

Update 2: this is local multiple choice interview questions that we should choose the best option as the time complexity that I mentioned in my question (options listed here).

enter image description here


Get this bounty!!!

#StackBounty: #algorithms #time-complexity #data-structures #sorting #arrays Find $k$'th smallest element in matrix with sorted rows

Bounty: 100

This is very hard question as mentioned on some site on google and firstly introduce on Interview Amazon Question.

We have an $mtimes n$ matrix in which all rows are sorted in ascending order and all elements are distinct. We want to find the $k$-th smallest element in this matrix.

There is an $O(m (log m + log n))$ algorithm for doing this!

I see lots of posts, especially here, but as Yuval Filmus mentioned in comments there are difference in large value of $k$.

We are familiar with median of medians method that throw half of elements with median, but here there is a very challenging question. How is this time complexity reached?

Update: this is exactly copy of one Ex. in Jeff Algorithms Book (Book Page 55 Ex: 21 Part C, Chapter Recursion :

enter image description here

As Yuval tell in comments, the previous question algorithms not complete so this is a good question for a complete algorithm in given time complexity.

Update 2: this is local multiple choice interview questions that we should choose the best option as the time complexity that I mentioned in my question (options listed here).

enter image description here


Get this bounty!!!

#StackBounty: #algorithms #time-complexity #data-structures #sorting #arrays Find $k$'th smallest element in matrix with sorted rows

Bounty: 100

This is very hard question as mentioned on some site on google and firstly introduce on Interview Amazon Question.

We have an $mtimes n$ matrix in which all rows are sorted in ascending order and all elements are distinct. We want to find the $k$-th smallest element in this matrix.

There is an $O(m (log m + log n))$ algorithm for doing this!

I see lots of posts, especially here, but as Yuval Filmus mentioned in comments there are difference in large value of $k$.

We are familiar with median of medians method that throw half of elements with median, but here there is a very challenging question. How is this time complexity reached?

Update: this is exactly copy of one Ex. in Jeff Algorithms Book (Book Page 55 Ex: 21 Part C, Chapter Recursion :

enter image description here

As Yuval tell in comments, the previous question algorithms not complete so this is a good question for a complete algorithm in given time complexity.

Update 2: this is local multiple choice interview questions that we should choose the best option as the time complexity that I mentioned in my question (options listed here).

enter image description here


Get this bounty!!!

#StackBounty: #algorithms #time-complexity #data-structures #sorting #arrays Find $k$'th smallest element in matrix with sorted rows

Bounty: 100

This is very hard question as mentioned on some site on google and firstly introduce on Interview Amazon Question.

We have an $mtimes n$ matrix in which all rows are sorted in ascending order and all elements are distinct. We want to find the $k$-th smallest element in this matrix.

There is an $O(m (log m + log n))$ algorithm for doing this!

I see lots of posts, especially here, but as Yuval Filmus mentioned in comments there are difference in large value of $k$.

We are familiar with median of medians method that throw half of elements with median, but here there is a very challenging question. How is this time complexity reached?

Update: this is exactly copy of one Ex. in Jeff Algorithms Book (Book Page 55 Ex: 21 Part C, Chapter Recursion :

enter image description here

As Yuval tell in comments, the previous question algorithms not complete so this is a good question for a complete algorithm in given time complexity.

Update 2: this is local multiple choice interview questions that we should choose the best option as the time complexity that I mentioned in my question (options listed here).

enter image description here


Get this bounty!!!

#StackBounty: #algorithms #time-complexity #data-structures #sorting #arrays Find $k$'th smallest element in matrix with sorted rows

Bounty: 100

This is very hard question as mentioned on some site on google and firstly introduce on Interview Amazon Question.

We have an $mtimes n$ matrix in which all rows are sorted in ascending order and all elements are distinct. We want to find the $k$-th smallest element in this matrix.

There is an $O(m (log m + log n))$ algorithm for doing this!

I see lots of posts, especially here, but as Yuval Filmus mentioned in comments there are difference in large value of $k$.

We are familiar with median of medians method that throw half of elements with median, but here there is a very challenging question. How is this time complexity reached?

Update: this is exactly copy of one Ex. in Jeff Algorithms Book (Book Page 55 Ex: 21 Part C, Chapter Recursion :

enter image description here

As Yuval tell in comments, the previous question algorithms not complete so this is a good question for a complete algorithm in given time complexity.

Update 2: this is local multiple choice interview questions that we should choose the best option as the time complexity that I mentioned in my question (options listed here).

enter image description here


Get this bounty!!!

#StackBounty: #algorithms #time-complexity #data-structures #sorting #arrays Find $k$'th smallest element in matrix with sorted rows

Bounty: 100

This is very hard question as mentioned on some site on google and firstly introduce on Interview Amazon Question.

We have an $mtimes n$ matrix in which all rows are sorted in ascending order and all elements are distinct. We want to find the $k$-th smallest element in this matrix.

There is an $O(m (log m + log n))$ algorithm for doing this!

I see lots of posts, especially here, but as Yuval Filmus mentioned in comments there are difference in large value of $k$.

We are familiar with median of medians method that throw half of elements with median, but here there is a very challenging question. How is this time complexity reached?

Update: this is exactly copy of one Ex. in Jeff Algorithms Book (Book Page 55 Ex: 21 Part C, Chapter Recursion :

enter image description here

As Yuval tell in comments, the previous question algorithms not complete so this is a good question for a complete algorithm in given time complexity.

Update 2: this is local multiple choice interview questions that we should choose the best option as the time complexity that I mentioned in my question (options listed here).

enter image description here


Get this bounty!!!

#StackBounty: #algorithms #time-complexity #data-structures #sorting #arrays Find $k$'th smallest element in matrix with sorted rows

Bounty: 100

This is very hard question as mentioned on some site on google and firstly introduce on Interview Amazon Question.

We have an $mtimes n$ matrix in which all rows are sorted in ascending order and all elements are distinct. We want to find the $k$-th smallest element in this matrix.

There is an $O(m (log m + log n))$ algorithm for doing this!

I see lots of posts, especially here, but as Yuval Filmus mentioned in comments there are difference in large value of $k$.

We are familiar with median of medians method that throw half of elements with median, but here there is a very challenging question. How is this time complexity reached?

Update: this is exactly copy of one Ex. in Jeff Algorithms Book (Book Page 55 Ex: 21 Part C, Chapter Recursion :

enter image description here

As Yuval tell in comments, the previous question algorithms not complete so this is a good question for a complete algorithm in given time complexity.

Update 2: this is local multiple choice interview questions that we should choose the best option as the time complexity that I mentioned in my question (options listed here).

enter image description here


Get this bounty!!!