on 24-Oct-2018 (Wed)

Question

In python/algorithms, what is the time complexity of insert(i,item) for lists (e.g. you have l = [1,2,3,4,5], what is big-O of doing: l.insert(1,7)?

Answer

O(n)

Question

In python/algorithms, what is the time complexity of the in operation for lists (e.g. you have l = [1,2,3,4,5], what is big-O of doing: if 3 in l: ?

Answer

O(n)

Question

In python/algorithms, what is the time complexity of the copy operation for dictionaries (e.g. you have d = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5}, what is big-O of doing: d2 = d1.copy()?

Answer

O(n)

Question

In python/algorithms, what is the time complexity of the get operation for dictionaries (e.g. you have d = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5}, what is big-O of doing: d['b']?

Answer

O(1)

Question

In python/algorithms, what is the time complexity of the set operation for dictionaries (e.g. you have d = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5}, what is big-O of doing: d['b'] = 0?

set item

Answer

O(1)

Question

In python/algorithms, what is the time complexity of the in operation for dictionaries (e.g. you have d = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5}, what is big-O of doing: if 'e' in d: ?

contains (in)

Answer

O(1)

Question

In python/algorithms, what is the time complexity of iterating over a dictionary (e.g. you have d = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5}, what is big-O of doing: for key in d: ?

Answer

O(n)

Question

In python, and in all languages, an array is a special type of list that is different from a normal list, how (think of Array in Java terms)?

Answer

With an array, all its elements are stored in one continuous block of memory!

Question

In python/algorithms, pointer structures are lists of items that can be [...] in memory (<--1 or 2 words in answer)

Answer

spread out / distributed / non-continuous

Question

In algorithms, very generally, a node contains two components: 1) a pointer to some data and; 2) [...]

Answer

pointer(s) to one or more other nodes.

Question

In algorithms, very generally, a node contains two components: 1) [...] and; 2) pointer(s) to one or more other nodes.

Answer

a pointer to some data

Question

In algorithms/data structures, specificallly in python, the last node(s) in a linked structure (e.g. link list, tree, etc) has its next pointer pointing to [...]

Answer

None

Question

For algorithms, in python, define a simple Node class to represent a simple node, which can hold some data and end up as part of a linked stucture (e.g. linked list)

Answer

class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None

^^ note that we are initially setting the next pointer to None (self.next = None) as easy way to properly terminate the linked list that will be made using these Node objects

Question

For algorithms, in python, if you have a Node class, such as:

class Node(object):
   def __init__(self, data):
      self.data = data
      self.next = None

Why is it still better to create a seperate SinglyLinkedList class, as below, rather than just constructing the link list directly from the objects of the Node class?

class SinglyLinkedList:
   def __init__(self):
      self.first = None
   def append(self, data):                       
      node = Node(data)             
      if self.first == None:
          self.first = node             
      else:                 
          current = self.first                 
          while current.next:                     
              current = current.next
          current.next = node

Answer

To abstract away the internals of the Node class from the programmer/user (e.g. the programmer using the SinglyLinkedList class's append method, just adds items to the linked list without having to know about the details of the Node class and all the pointer, etc or even knowing that this is a linked list used to append/hold the items, aside from the name of the class)

Question

In algorithms, for linked list traversel, you keep advancing the node.next pointer until you [...]

Answer

hit None (which signifies the end of the linked list)

Question

In algorithms, in python, if we have a Node class and a LinkedList class that uses it (and abstracts Node's inner wroking/pointers), how do we iterate over the data of all the Nodes in the LinkedList class without taking away the abstraction of the inner working of Node?

Answer

via a generator function defined in LinkedList class.
here is example (this is not needed to pass this test :) :

class LinkedList(object):
...
    def iter(self):        
        current = self.tail        
        while current:            
            val = current.data            
            current = current.next            
            yield val