Now, for the final part of the interview, please implement decreaseKey on a binomial heap in Haskell.
The definition of the heap is as follows
data BinomialTree a = Node a [BinomialTree a]
data BinomialHeap a = BinomialHeap [BinomialTree a]
Now, for the final part of the interview, please implement decreaseKey on a binomial heap in Haskell
Do your own interview
are you google
maybe
I thank them for their time and leave.
>pull into parking lot for interview
>there's an ambulance
>guy in his early 20s is convulsing on a stretcher and being put in the back
>behind him two guys come out with a whiteboard
>it's a half-done fizzbuzz program
>towards the bottom it's nothing but red
>the top is blue marker
>realize the bottom half is blood
>they go to the side of the building, there's a powerwasher
>spray it down for a few seconds, dry if off, and wheel it back inside
>mfw
>data BinomialTree a = Node a [BinomialTree a]
infinite recursion user
Node a ( Node a ( Node a ( Node a ( Node a ( Node a ( Node a ( Node a (
Kek
this lol. I've actually done it and had a director of engineering call me a few hours later asking what went wrong
>Haskell
the list can be empty
>thank you for your time, I will see myself out
>get back here weeb, your personal information are at stake for this interview
>failure to comply will result in all of the data records we have on your browsing history, even through tor, will be appended to your online records
Don't apply for the NSA bruhs
>implying any company uses Haskell
It happened to me, but it was a delete all x procedure for linked list in C. It took me long to recover.
Thats not even hard m8
I know, but the stress and blackboard effect destroyed me. I lost my brain. Later, when I came home I wrote that shit.
Now for the final part of your art college interview, we need you to synthesize two-part enamel paint in seven colors using this Bic pen and your sperm.
Nerds need a labor union or something.
data BinomialTree a = Node a [BinomialTree a]
data BinomialHeap a = BinomialHeap [BinomialTree a]
mmap :: (a -> (Bool, a)) -> [a] -> (Bool, [a])
mmap f [] = (False, [])
mmap f (x:xs) =
let (b, x') = f x
(b', xs') = mmap f xs in
(b || b', x' : xs')
decr :: (Ord a) => a -> a -> BinomialTree a -> (Bool, BinomialTree a)
decr old new (Node n t)
| old == n = (True, Node new t)
| new < n =
let (b, t') = (mmap (decr old n) t) in
if b then (True, Node new t')
else (False, Node n t')
| otherwise =
let (b, t') = mmap (decr old new) t in
(b, Node n t')
decreaseKey :: (Ord a) => a -> a -> BinomialHeap a -> BinomialHeap a
decreaseKey old new (BinomialHeap t) = BinomialHeap $ fmap (snd . decr old new) t
What is this syntax highlighter. Nothing actually triggers me more than broken syntax highlighters.
not bad, the only problem is that it doesn't account for repeated elements in the heap.
Oops, perhaps I should have actually read the definition of a binomial tree. I just skimmed it and thought keys were unique.
I suppose I can just repeat the operation to fix it.
data BinomialTree a = Node a [BinomialTree a]
data BinomialHeap a = BinomialHeap [BinomialTree a]
mmap :: (a -> (Bool, a)) -> [a] -> (Bool, [a])
mmap f [] = (False, [])
mmap f (x:xs) =
let (b, x') = f x
(b', xs') = mmap f xs in
(b || b', x' : xs')
decr :: (Ord a) => a -> a -> BinomialTree a -> (Bool, BinomialTree a)
decr old new (Node n t)
| old == n = (True, Node new t)
| new < n =
let (b, t') = (mmap (decr old n) t) in
if b then (True, Node new t')
else (False, Node n t')
| otherwise =
let (b, t') = mmap (decr old new) t in
(b, Node n t')
decreaseKey :: (Ord a) => a -> a -> BinomialHeap a -> BinomialHeap a
decreaseKey old new (BinomialHeap t) =
let (b, t') = mmap (decr old new) t in
if b then decreaseKey old new (BinomialHeap t')
else (BinomialHeap t')