tsiege / tech-interview-cheat-sheet Goto Github PK

Regarding:

Queues [...] Made with a doubly linked list that only removes from head and adds to tail.

Unless I'm mistaken, a doubly link list is not necessary for a queue (simply an additional pointer to the current head and tail)

For instance the first hit for implementation of a queue with a linked list shows a standard (not doubly linked) list.

under big-O notation, it is (incorrectly) called "worst case". Ditto for big-Ω. This is corrected in the next section, but it might be worth correcting.

The Time Complexity for Binary Search Tree (BST) basic operations (Insert, Remove and Search) is not O(log n) if the BST is unbalanced (is O(logn) only when we are talking about Balanced BST such as AVL and Red-Black). The correct time complexity would be O(h) where h is the height of the BST. It is h because the BST may become skewed as the following image.

see warning from #6

Might be a noob issue, but i'm trying to run the Typscript test and after installing all modules, i npm run test and get back this err, so i tried googling it and found this stackoverflow question but no answer.

Has anyone figured this out?

(node:2100) DeprecationWarning: Configuration via mocha.opts is DEPRECATED and will be removed from a future version of Mocha. Use RC files or package.json instead.

Right After it's as Follows in my Terminal

`Challenges
Selection Sort
swap
1) swaps position of two items in an array given their indices

0 passing (19ms)
1 failing

1. Challenges
   Selection Sort
   swap
   swaps position of two items in an array given their indices:

   AssertionError: expected [ 4, 3, 2, 1 ] to deeply equal [ 1, 3, 2, 4 ]

   • expected - actual

   [

   • 4
   • 1
     3
     2
   • 1
   • 4
     ]

   at Context. (challenges/challenges.test.ts:13:16)
   at processImmediate (internal/timers.js:439:21)

npm ERR! Test failed. See above for more details.`

Need to update merge sort space complexity to O(n)

It was odd to me that merge sort stats here are "better" than quick sort in every way - whereas Quicksort is used everywhere in practice, not Mergesort.

Why is QuickSort favourable over MergeSort in practice?
https://www.reddit.com/r/computerscience/comments/6krpz7/why_is_quicksort_favourable_over_mergesort_in/

Quicksort is used bc is has better space complexity than merge. Merge should be O(n)