Algoritmer och mjukvarudesign

Instuderingsfrågor

• What is a hash table?
  A hash table is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets, from which the desired value can be found quickly.
• What is a bucket in a hash table?
  A bucket in a hash table is a container within the hash tables array where key-value pairs with the same hash value are stored.
• What is the purpose of a hash function in a hash table?
  The purpose of a hash function in a hash table is to map keys to indices of an array, enabling efficient storage and retrieval of key-value pairs.
• How is a hash function chosen for a hash table?
  The choice of a hash function depends on several factors such as distribution of keys, speed, and collision resolution strategy. A good hash function aims to distribute keys evenly across the array of buckets to minimize collisions.
• What is a hash collision?
  A hash collision occurs when two different keys produce the same hash value.
• How does a hash table handle collisions?
  Hash tables handle collisions by employing collision resolution techniques, such as chaining or open addressing.
• What is a hash collision chain?
  A hash collision chain refers to a linked list or another data structure used to store multiple key-value pairs that hash to the same index in a hash table.
• What is a hash table collision resolution algorithm?
  A collision resolution algorithm is a method used to resolve collisions that occur when multiple keys hash to the same index in a hash table.
• What is the difference between open addressing and chaining collision resolution techniques?
  In open addressing, collisions are resolved by finding an empty slot in the hash table, typically by linear probing or other methods. In chaining, collisions are resolved by storing multiple entries at the same index using linked lists or other data structures.
• How does linear probing work in open addressing?
  Linear probing is a method of resolving collisions in open addressing by searching for the next available slot in the hash table when a collision occurs. It involves linearly probing successive slots until an empty slot is found.
• What is the time complexity of searching for an element in a hash table?
  The time complexity of searching for an element in a hash table is O(1) on average, assuming a good hash function and a low load factor.
• What is the worst-case time complexity for searching for an element in a hash table?
  The worst-case time complexity for searching in a hash table is O(n), where n is the number of elements in the hash table. This occurs when there are many collisions and the hash table degenerates into a linked list at each index.
• What is the load factor of a hash table?
  The load factor of a hash table is the ratio of the number of elements stored in the hash table to the number of buckets.
• What is the ideal load factor for a hash table?
  The ideal load factor for a hash table depends on the chosen collision resolution strategy but is typically kept below 1.0 to minimize collisions and maintain performance.
• What is the purpose of a hash tables resize operation?
  The purpose of a hash tables resize operation is to maintain a low load factor and ensure efficient performance by increasing the number of buckets and redistributing the key-value pairs when necessary.
• What is the difference between a hash table and an array?
  A hash table is a data structure that stores key-value pairs and uses a hash function to compute an index for efficient retrieval. An array is a collection of elements stored in contiguous memory locations accessed using indices.
• What is the difference between a hash table and a map?
  A hash table is a specific implementation of a map data structure, which associates keys with values. While a hash table typically uses a hash function for indexing, a map may use other methods such as trees or arrays for storage and retrieval.

Instuderingsfrågor

Instuderingsfrågor

• What is a Binary Search Tree?
  A Binary Search Tree (BST) is a binary tree in which each node has a value greater than all the values in its left subtree and less than all the values in its right subtree.
• What is the time complexity of searching for an element in a balanced BST?
  The time complexity is O(log n) in a balanced BST.
• What is the worst-case time complexity for searching an element in a BST?
  The worst-case time complexity is O(n), which occurs when the BST becomes a skewed tree (like a linked list).
• How does an in-order traversal of a BST output the elements?
  An in-order traversal of a BST outputs the elements in ascending sorted order.
• What property must the left and right subtrees of a BST node satisfy?
  All nodes in the left subtree must have values less than the node's value, and all nodes in the right subtree must have values greater than the node's value.
• What is a balanced BST, and why is it important?
  A balanced BST is a tree where the height of the left and right subtrees of any node differ by at most one. It is important because it ensures O(log n) time complexity for operations.
• Describe the process of inserting a new value into a BST.
  To insert a new value, start at the root and compare the value with the current node. If the value is less, move to the left child; if greater, move to the right child. Repeat until finding an appropriate null position to insert the new value.
• Give an example of a situation where a BST is preferable over a hash table.
  A BST is preferable when you need to maintain sorted order of elements or perform range queries, such as finding all elements between two values.
• How would you check if a binary tree is a BST?
  Perform an in-order traversal of the tree and check if the output is sorted in ascending order. If it is, the tree is a BST.

Instuderingsfrågor