data structures

Question 1

what is a link list ?

Answer 1

A linked list is a sequence of data elements, which are connected together via links. Each data element contains a connection to another data element in form of a pointer. Python does not have linked lists in its standard library.

Question 2

What are hash tables

Answer 2

Sort of dictionary: you start from a key –> hash values –>index of an array that contains a linked list. Hash tables are a type of data structure in which the address or the index value of the data element is generated from a hash function. That makes accessing the data faster as the index value behaves as a key for the data value. In other words, Hash table stores key-value pairs but the key is generated through a hashing function.

Question 3

What is the lookup time of a hash table? how can you make it faster?

Answer 3

It is at worse O(N) with N number of keys. This happens if you have a lot of collisions! Generally, it is O(1) you can get faster implementing a balanced binary tree search.

Question 4

What are Array_list?

Answer 4

Array list is data type similar to a list that resizes themselves when you append them. The key is to say double the size when you reach the limit. Doubling take O(n) to copy in the new structure. But the cost is amortized.

Question 5

What is the insertion time of an ArrayList (resizable arrays)

Answer 5

Well, it is less than O(n) it is O(1) on average the reason is that while copy takes O(n) when you have to double it happens rarely so you amortized. For an array of length N: N/2+n/4+N/8….

Question 6

Why are resizeble array important? Think about an algorith where you concatenate n string of lenght s copying avery time

Answer 6

Well, copy takes O(n), the first time you copy s+2s+3s.. +ns This is a pretty bad O(n^2*s) algorithm

Question 7

Code to check character of a string are unique?

Answer 7

• ask for Unicode or ASCII in general what is the size of characters. - return true for len <2 and false for len> tot characters (128) -loop trough by filling a boolean table and stop when a character is already there. This is O(n) or actually, this is bounded by the number of total character. runtime<128 O(min(N,128)) Space complexity is O(1) but you do need to have an external structure. To do it in place you need O(n^2) or nlogn if you sort it with an in place algorithm (but ask: am I allowed to modify the string?)

Question 8

what is a linked list

Answer 8

A linked list is an ordered collection of values. Linked lists are similar to arrays in the sense that they contain objects in a linear order. However, they differ from arrays in their memory layout.Linked lists, however, are made up of data records linked together by pointers. Note you can have double link and single link linked list kind of list.

Question 9

What is the gain in performance of a linked list comparet to a normal list?

Answer 9

Element Insertion & Removal: Inserting and removing elements from a (doubly) linked list has time complexity O(1), whereas doing the same on an array requires an O(n) copy operation in the worst case. You loose in lookup time: Element Lookup: Similarly, looking up an element given its index is a slow O(n) time operation on a linked list—but a fast O(1) lookup on an array. Memory Efficiency: Because the data stored in arrays is tightly packed they’re generally more space-efficient than linked lists. This mostly applies to static arrays, however. Dynamic arrays typically over-allocate their backing store slightly to speed up element insertions in the average case, thus increasing the memory footprint.

Question 10

Program for n’th node from the end of a Linked List

Answer 10

Use two pointers Maintain two pointers – reference pointer and main pointer. Initialize both reference and main pointers to head. First, move reference pointer to n nodes from the head. Now move both pointers one by one until reference pointer reaches the end. Now the main pointer will point to the nth node from the end. Return the main pointer.

Question 11

Whate are application of a binary search tree?

Answer 11

Binary search trees are collections that can efficiently maintain a dynamically changing dataset in sorted order, for some “sortable” type.* Having a sorted array is useful for many tasks because it enables a binary search to be used to efficiently locate elements. The problem with a sorted array is that elements can’t be inserted and removed efficiently.

Question 12

What is the algorithmic complexity of a binary search tree?

Answer 12

If balanced you can do all the most common operation in logarithmic time. Those operations are: efficient search, in-order forward/ backward traversal from any given element, predecessor /successor element search, and max /min queries, with the added benefit of efficient inserts and deletes. With a self-balancing binary search tree (BST), all of the above run in logarithmic time.

Question 13

What are tipycal application of the “heap” data structure?

Answer 13

Heap Data Structure

is generally taught with Heapsort. Heapsort algorithm has limited uses because Quicksort is better in practice.

Uses:

Priority Queues: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time. Binomoial Heap and Fibonacci Heap are variations of Binary Heap. These variations perform union also in O(logn) time which is a O(n) operation in Binary Heap. Heap Implemented priority queues are used in Graph algorithms like Prim’s Algorithm and Dijkstra’s algorithm.

Order statistics: can be used to efficiently find the kth smallest (or largest) element in an array. See method 4 and 6 of this post for details.

Question 14

List some sorting algorithm?

Question 15

Quickly how does quicksort work?

Answer 15

Quicksort is a divide and conquer algorithm.

it has a nlogn average time complexity

_Quicksort first divides a large array into two smaller sub-array_s: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

The steps are:

• Pick an element, called a pivot, from the array.
• Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
• Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
• The base case of the recursion is arrays of size zero or one, which are in order by definition, so they never need to be sorted.

Question 16

What is selection sort (not very important)?

Answer 16

selection sort is the simplest specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort.

You just go through the list finding the minimum and swapping

It is in place so it has O(1) space complexity

Question 17

How would you reverse a double linked list?

Answer 17

Here is a simple method for reversing a Doubly Linked List. All we need to do is swap prev and next pointers for all nodes, change prev of the head (or start) and change the head pointer in the end.

class Node:

Constructor to create a new node

def __init__(self, data):

self. data = data
self. next = None
self. prev = None

class DoublyLinkedList:

Constructor for empty Doubly Linked List

def __init__(self):

self.head = None

Function reverse a Doubly Linked List

def reverse(self):

temp = None

current = self.head

Swap next and prev for all nodes of

doubly linked list

while current is not None:

temp = current.prev

current. prev = current.next
current. next = temp

current = current.prev

Question 18

What algorithm would you use to sort a linked list?

Answer 18

Merge sort is the best.

Random access is really problematic so using quick sort is pain. You can use insertion sort but that is O(n^2) while merge sort is O(nlogn)