Scala Coding Challenges

Problems

1. Time Delta [Medium]
2. Word Order [Medium]
3. Runner Up Score [Easy]
4. Words Score [Medium]
5. Birthday Cake Candles [Easy]
6. Mini Max Sum [Easy]
7. Time Conversion [Easy]
8. Fraudulent Activity Notifications [Medium]
9. Text Wrap [Easy]
10. Merge the Tools [Medium]
11. Capitalize [Easy]
12. Minimum Bribes [Medium]
13. Minimum Swaps 2 [Medium]
14. Compare the Triplets [Easy]
15. An Interesting Game [Medium]
16. Two Sub-arrays [Expert]
17. Sherlock and Anagrams [Medium]
18. Hackerland Radio Transmitters [Medium]
19. Minimum Loss [Medium]
20. Missing Numbers [Easy]
21. Pairs [Medium]
22. Sherlock and Arrays [Easy]
23. Maximum Sub-array Sum [Hard]
24. Compress the String [Medium]
25. Playing with Numbers [Hard]
26. Index of first occurrence [Medium]
27. Move Zeros [Easy]

DSA Designs

1. Array-Based Stack Implementation (Data Structures & Algorithms in Python, page 234)

• The implementations for top, is_empty, and len use constant time in the worst case. The O(1) time for push and pop are amortized bounds a typical call to either of these methods uses constant time, but there is occasionally an O(n)-time worst case, where n is the current number of elements in the stack, when an operation causes the list to resize its internal array.

2. Reversing Data Using a Stack (Data Structures & Algorithms in Python, page 235)

• One technical detail worth noting is that we intentionally strip trailing newlines from lines as they are read, and then re-insert newlines after each line when writing the resulting file. The reason for doing this is to handle a special case in which the original file does not have a trailing newline for the final line.
• If we exactly echoed the lines read from the file in reverse order, then the original last line would be followed (without newline) by the original second-to-last line. In our implementation, we ensure that there will be a separating newline in the result.

3. Array-Based Queue Implementation (Data Structures & Algorithms in Python, page 241 - 246)

Operation	Running Time
Q.enqueue(e)	O(1)*
Q.dequeue()	O(1)*
Q.first()	O(1)
Q.is_empty()	O(1)
len(Q)	O(1)

*amortized

4. Validating a Binary Sort Tree(BST)

• Even though there is no memory used the space complexity of this operation is O(d) where d is the depth of the tree

• The time complexity is O(n) where n is the number of nodes in the tree. This is because we are traversing through each of the tree's nodes

• For a valid BST, a node's value has to be greater than or equal to the minimum value and less than the maximum value.

  if tree.data < minValue or tree.data >= maxValue:
    return False

5. Linked Lists

• A linked list is a data structure that represents a sequence of nodes. In a singly linked list, each node points to the next node in the linked list. In a doubly linked list, each node points to both the next node and the previous node in the linked list.
• In a linked list, the least significant digit always comes first. So that 2 -> 4 -> 7 -> 1 represents the number 1742

5.1. Creating a linked list

class Node {
  Node next = null;
  int data;

  public Node(int d) {
    data = d;
  }

  void appendToTail(int d) {
    Node end = new Node(d);
    Node n = this;
    while (n.next != null) {
      n = n.next;
    }
    n.next = end;
  }
}

5.2. Deleting a node from a singly linked list

• Given a node n, we first find the previous node prev and set prev.next equal to n.next. If the list is doubly linked, we must also update n.next to set n.next.prev to n.prev.
• The important thing to remember is (1) To check for the null pointer and (2) To update the head or tail pointer as necessary
• If this is implemented in a language that requires the developer to do memory management, deallocating the removed node should be considered.

Node deleteNode(Node head, int d) {

    Node n = head;

    if (n.data == d) {
      return head.next; /*moved head*/
    }

    while (n.next != null) {
      if (n.next.data == d) {
        n.next = n.next.next;
        return head; /*head did not change*/
      }
      n = n.next;
    }
    return head;
  }