I know I’ve been saying it for a while, but I swear eventually I’m going to un-tie the database query from the UI thread to stop the app from hanging on large imports. Honestly it’s on my To-Do List. Check it for yourself. See? Right there at number 4. When that day comes, hoo boy you’ll all love it. Also on that list is a UI refresh, turns out white letters on black background ISN’T the best for battery life. Heh, the more you know. Oh and a UI design for larger screens, which soon even phones are hitting (thanks Samsung and your fascination with phablets).
More importantly, I really need to get on that app that connects to the qBittorent web-UI so I don’t have to keep awkwardly using the Chrome browser to manipulate a screen that works best with a mouse. I’m sure a lot of other people could use it but really I tend to make apps that I want. So someday once I’m tired of the website on the mobile Chrome browser.
But in more important news, back to a new hardcore Minecraft world! So far I’ve gone through 12 of them, finding more and more stupid ways to die in each one. The worst was the 10th, where I was so desperate for diamonds I was digging up the world and didn’t notice the three creepers that were right behind me.
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.