Double-linked-list worked but the link to move backwards,
.prev, wasn’t necessary. I created a package of datatypes I’ve made then imported a
Node object to create the list; since I had the option of including a link to the previous node I figured I’d use it. My 64-bit Java 1.8 install and Eclipse install can handle a total of about 3,500 servants; anything higher and it runs out of memory and starts losing nodes which causes null pointer issues.
The comments and I agree that given 1,500 servants the winner is the 953rd servant who kills the 1,456th servant. Most used some sort of data structure like I did, but a few pointed out that there’s a mathematical function, a circular left-shift, that does the same result. Probably can handle much larger groups of servants as well since it doesn’t actually have to create an object or instance of each one. LEARNDING!
So far doing the Problem of the Day has been entertaining and dare I say something I look forward to each day. I don’t try to finish first as I’m sure they’re put up while I’m still asleep and solved about an hour later. As far as giving something programming to do everyday I’m the real winner. /cue sappy “lesson learned” music from 80’s high school movie
This is a bit morbid and could easily be more of a math problem but computers are just so good at maths it’s an easy fit. Recursive or repetitive function that continues to eliminate the even numbered entries until only one is left. It seems like the 1st servant would always be the one to start everything but the comments and I agree that it continues in a loop; not necessarily stopping then starting with the 1st servant again.
This moves to a circular pattern throughout the servants. I thought an array at first, I always go to arrays it seems, but a linked-list (or conveniently a double-linked-list that I already made a couple POTDs ago) would be best since the size is constantly being dropped by one. The modification will require the last entry to point to the first entry once the entire thing is set up, then it just keeps removing the next-next entry until there is only one entry left.
But how to track only one entry being left…
The Lone Survivor
There are 1,500 loyal servants sitting around the king’s table when they decide to play a little game. The 1st servant gets a sword and kills the 2nd servant. He then gives the sword to the 3rd servant, who then kills the 4th servant and then gives the sword to the 5th. This continues so that the 1,499th servant kills the 1,500th servant and gives the sword back to the 1st servant.
Now the 1st servant kills the 3rd and gives the sword to the 5th. This process continues until only one servant remains. Which number servant is the lone survivor?
I found a hash-table I made while in a college course that fit the bill so I didn’t actually remake my own. It has more than the desired functions including type declarations and three different hashing methods: linear, double, and chain. I used the linear method since duplicate entries were just going to be reported and ignored; to achieve this I had to modify the class a bit but I made note of it when reusing the class file.
Class reuse at its finest.
Today’s problem is actually one I’ve seen before in a technical interview. I tried it then using nested loops that was O(n^2) complex and took longer than I expected trying to keep track of when an item was found and how to handle more than one duplicate entry. My interviewer suggested using a hash which I had never considered; that’s experience for you.
Since the loops are O(n^2) and I got lost in the truth tables the first time, I’m going to take my interviewers advice and use hashes instead. The plan is that as each value is added to the hash-table a collision will occur when a second number is added and throwing a duplicate entry. To do this I’m going to make my own simple hash object that will support:
- adding values to the table
- automatically increasing the table size if it gets >80% allocated
- reporting a duplicate value
- reporting the current hash allocation percent
Should be fun.
Hopefully while filling out your taxes you didn’t run in to any issues with duplicate numbers. However, if you did now is your chance to make up for it. For today’s problem you’ll be passed in an array of integers and asked to identify all the duplicate numbers.
For a bonus solve it in under O(n^2) without making use of a set/hash (unless you want to implement your own).
Sometimes the smallest thing messes up everything. I had a
static marker on the
head node so of course both stacks were the same! Oops. This caused the moving the items from one stack to the other problematic as they were the same stack. The other problem I ran into was I hadn’t considered the case of removing the last node from the head which caused some null pointer exceptions. All fixed now!
I re-used the head/node internal classes from POTD: Stacks & Queueus and remade the
push() functions, then made the separate
MyQueue class using two stacks as planned.
Messing with stacks and queues again, this time using two stacks to mimic a queue. The plan is to create a stack structure, then initialize two of them; one to hold the queue as it fills up (using the
push() method, using the
pop() method to get to the the front of the queue (bottom of the stack), remove the first entry, and put all the removed items back.
|3 4 5 6 --> dequeue() --> |4 5 6
2 Stacks 1 Queue
Let’s try and take a different spin on yesterday’s problem. Today’s goal will be to implement a stack. Then using two instances of the stack you’ll want to mimic the functionality of a queue. Thus your queue will have an enqueue and dequeue method but those methods will only use the push and pop functionality of your stacks.
Linked-lists always mess with me a bit so it’s good that I used one here. My solution is to use two classes:
StacksQueues.java as the main program (calls the operations and prints the results) and
Store.java as the data structure.
Store.java includes two internal classes:
Head is just the placeholder that links to the first item in the list and is created upon calling
new Store() from
StacksQueues. It also handles the
print() function that formats the double-linked-list as a string surrounding the comma-separated values with square-brackets. It was important to note that the head only links forward to the first node in the list, there is no previous call to get to the head since it’s not useful. Creating an iterator to move through the list calls
head.next so the head isn’t considered part of the list.
Nodes are each node in the DLL; they contain a
next link to the following node, a
prev link to the preceding node, and a
value of the node. The node constructor requires the internal value to store and each link has to be set based on where it is being added to the DLL.