![Mergesort Investigation 2 - 2021 program](/images/mergesort_thumb.png)
Mergesort Investigation 2 - 2021 program
My July 2021 mergesort program, as the subject of an investigation, deserves some explanation.
My July 2021 mergesort program, as the subject of an investigation, deserves some explanation.
One coding problem I encountered was to do a merge sort of a linked list. I wrote a merge sort in Go, but when I tried to verify it via timing sorting large linked lists, I got some strange behavior
Here’s the problem:
Read a file of text,
determine the n
most frequently used words,
and print out a sorted list of those words along with their frequencies.
A programming interview question from the Daily Coding Problem email list. Here’s a non-hand-wavy explanation of a way to solve this problem.
Daily Coding Problem: Problem #736 [Easy]
Given a complete binary tree, count the number of nodes in faster than O(n) time. Recall that a complete binary tree has every level filled except the last, and the nodes in the last level are filled starting from the left. “Complete” means: every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes at the last level h.
Another programming interview question from the Daily Coding Problem email list. I received it as #1608.
Daily Coding Problem: Problem #1608 [Medium]
This problem was asked by Microsoft.
Write a program to determine how many distinct ways
there are to create a max heap from a list of N
given integers.
For example,
if N = 3
,
and our integers are [1, 2, 3]
,
there are two ways, shown below.
3 3
/ \ / \
1 2 2 1
Repo for my code.
Programming interview question from the Daily Coding Problem email list. I have it as #1602, but other folks have it as #331 from 2020. I guess I missed it back then.
Daily Coding Problem: Problem #1602 [Medium]
This problem was asked by LinkedIn.
You are given a string consisting of the letters x
and y
,
such as xyxxxyxyy
.
In addition,
you have an operation called flip
,
which changes a single x
to y
or vice versa.
Determine how many times you would need to apply this operation to ensure
that all x
’s come before all y
’s.
In the preceding example,
it suffices to flip the second and sixth characters,
so you should return 2.
Repo for code.
Another puzzle courtesy the Daily Coding Problem email list.
Daily Coding Problem: Problem #1578 [Hard]
This problem was asked by Facebook.
Given an array of numbers of length N
,
find both the minimum and maximum using less than 2 * (N - 2)
comparisons.
Github repo for my solution.
This is from the Daily Coding Problem email list. The owners of that list haven’t sent out a problem that caught my imagination in quite a while.
Daily Coding Problem: Problem #1553 [Hard]
This problem was asked by Airbnb.
You come across a dictionary of sorted words in a language you’ve never seen before. Write a program that returns the correct order of letters in this language.
For example,
given ['xww', 'wxyz', 'wxyw', 'ywx', 'ywz']
,
you should return ['x', 'z', 'w', 'y']
.
Github repo for my solution. Feel free to look it over, try it and email me (bediger8@gmail.com) if you notice anything.
There’s at least two things that one might conflate under the “Daily Coding Problem” rubric:
They’re related, as the book is a byproduct of the success of the email list. Both are deficient, but for different reasons