AlexeiDarmin

{"lastUpload":"2021-05-16T15:10:15.000Z","extensionVersion":"v3.4.3"}

AlexeiDarmin

/*
You have two numbers represented by a linked list, where each node contains a single
digit. The digits are stored in reverse order, such that the 1s digit is at the head of the list. Write a 
function that adds the two numbers and returns the sum as a linked list.

input: (7 -> 1 -> 6) + (5 -> 9 -> 2). That is 617 + 295
output: 2 -> 9 -> 1. That is 912

Also write a solution for the forward order of digits

AlexeiDarmin

function isPalindrome(head: Node): boolean {
  if (!head) return true

  let str = [head.data]
  let node = head
  while(node.next) {
    node = node.next
    str.push(node.data)
  }

AlexeiDarmin

/*
  Given two (singly) linked lists, determine if the two lists intersect. Return the intersecting node. 
  Note that the intersection is defined based on reference not value. That is, if the kth node of the first 
  linked list is the exact same node (by reference) as the jth node of the second linked list, then they are 
  intersecting.
*/
function getIntersection(h1: Node, h2: Node) {
  const nodes1 = getNodesMap(h1)
  const nodes2 = getNodesMap(h2)

AlexeiDarmin

/*
How would you design a stack which in addition to push and pop has a function min which returns
the minimum element. Push pop and min should all operate in O(1) time.
*/


class Node<T> {
  data: T
  next: Node<T>

AlexeiDarmin

/*
  Stack of plates: Imagine a literal stack of plates. If the stack gets too high, it might topple.
  Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold.
  Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks and 
  should create a new stack once the previous one exceeds capacity.
  
  SetOfStacks.push() and SetfStacks.pop() should behave identically to a single stack
  That is pop should return the same valeues as it would if there were just a single stack.
*/

AlexeiDarmin

class MyNewQueue<T> {
  mainStack: MyStack<T>
  tempStack: MyStack<T>

  constructor(value: T) {
    this.mainStack = new MyStack()
    this.tempStack = new MyStack()

    this.mainStack.push(value)

AlexeiDarmin

/*
Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack 
but you may not copy the elements into any other data structure such as an array. The stack supports the following
operations: push, pop, peek, and isEmpty.
*/

function sortStack<T>(mainStack: MyStack<T>): MyStack<T> {
  const tempStack = new MyStack<T>()
  while (!mainStack.isEmpty()) {

AlexeiDarmin

function hasPath<T>(n1: GraphNode<T>, n2: GraphNode<T>): boolean {
  const visitedByN1 = new Map()
  const visitedByN2 = new Map()

  let children1: GraphNode<T>[] = n1.children
  let children2: GraphNode<T>[] = n2.children

  while (children1.length > 0 || children2.length > 0) {
    let output = searchChildren(children1, visitedByN1, n2)

AlexeiDarmin

// given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minial height.
class BinaryNode<T> {
  data: T
  leftChild: BinaryNode<T>
  rightChild: BinaryNode<T>

  constructor(data: T) {
    this.data = data
  }