Small Coding Problems

Linked List: Dedup

• prev = None: Keeps track of the node immediately before the current node.

• curr = self.head: Starts traversing the linked list from the head.

• repeat = set(): Creates an empty set to store values that have already been encountered.

• while curr:: Traverses the linked list until the end is reached.

• if curr.data in repeat:: Checks whether the current node's value has already appeared.

  • If yes, prev.next = curr.next skips over the current node, removing the duplicate.

• else:: If the value has not appeared before:

  • repeat.add(curr.data) adds the value to the set.

  • prev = curr updates the previous pointer to the current node.

• curr = curr.next: Advances to the next node, whether the current node was a duplicate or not.

• Result: The linked list contains only the first occurrence of each value, preserving the original order.

Stacks / Recursion: Language

• stack = Stack(): Creates an empty stack to store strings that need to be processed.

• stack.push(""): Pushes the empty string onto the stack as the starting point.

• results = []: Creates an empty list to store all generated strings.

• while not stack.is_empty():: Continues processing until the stack is empty.

• current = stack.pop(): Removes and returns the top string from the stack.

• results.append(current): Adds the current string to the results list.

• if len(current) < k:: Checks whether the current string is shorter than the maximum allowed length.

  • If yes, the function can generate longer strings from it.

• for character in s:: Iterates through every character in the original string s.

• new_string = current + character: Creates a new string by adding the character to the end of the current string.

• stack.push(new_string): Pushes the newly generated string onto the stack so it can be processed later.

• return results: Returns the list of all generated strings.

BST: Width

• if self.root is None:: Checks whether the tree is empty. If it is, returns 0 because there are no nodes.

• queue = [self.root]: Creates a queue containing the root node. The queue is used to traverse the tree level by level.

• max_width = 0: Initializes a variable to keep track of the largest number of nodes found at any level.

• while queue:: Continues traversing the tree until the queue is empty.

• level_size = len(queue): Counts how many nodes are currently in the queue. This represents the number of nodes at the current level.

• if level_size > max_width:: Checks whether the current level has more nodes than the previous maximum.

  • If yes, updates max_width = level_size.

• for i in range(level_size):: Processes exactly the nodes belonging to the current level.

• curr = queue.pop(0): Removes the first node from the queue (FIFO: First In, First Out).

• if curr.left is not None:: Checks whether the current node has a left child.

  • If yes, adds the left child to the end of the queue.

• if curr.right is not None:: Checks whether the current node has a right child.

  • If yes, adds the right child to the end of the queue.

• return max_width: Returns the largest number of nodes found at any level.

n-queens

HW 1: N-Queens

• Checks whether queen placements are valid (no same row or diagonal).

• Uses a dictionary to store queen positions.

• Uses a stack to track which rows to try.

• If a placement works, moves to the next column.

• If no placement works, backtracks by removing the previous queen and trying another row.

• Returns the completed solution or None if no solution exists.

shakespeare

• Uses linked lists to store words grouped by word length.

• Each node stores a word, its frequency, and a pointer to the next node.

• find_frequency() increments a word's frequency or adds it if it is new.

• sort() uses insertion sort to order words by highest frequency, then alphabetically.

• Reads each query's word length and rank, then returns the word at that position or "-" if none exists.

triangles

• The Triangle class stores the three side lengths.

• getTriangleClass() checks that there are exactly three sides, all sides are positive, and the triangle inequality is satisfied.

• Uses a set to count distinct side lengths:

  • 1 distinct length = equilateral

  • 2 distinct lengths = isosceles

  • 3 distinct lengths = scalene

• Returns "invalid" if the sides cannot form a valid triangle.

• The main program reads side lengths from an input file, classifies each triangle, and writes the results to an output file.

• If a line has too few sides, the IndexError handler writes "-".