gillerick / coding-challenges-python Goto Github PK

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]

• 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.

• 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.

*amortized

• 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

• 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

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;
  }
}

• 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;
  }

• A queue is a data structure in which all the additions are made at one end (head or front of queue) and all deletions are made at one end (rear or tail of the queue)
• It is a FIFO data structure

• CPU scheduling
• Data is transferred asynchronously between two processes
• Graph traversal algorithms
• Transport and operations management
• File servers
• IO buffers
• Printer queues
• Phone calls to customer service hotlines
• Resource is shared among multiple consumers

• Enqueue - to put an item into the queue
• Dequeue - to remove an item from the front of the queue
• Lists are not efficient for implementing queues. While appends and pops from the end of the list are fast, inserts or pops from the beginning of the list is slow because all the other elements have to be shifted by one.