Problem of the Day: Duplicate Entries (update)

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.

Problem of the Day: Duplicate Numbers

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.

Duplicate Numbers

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).

linky linky

Problem of the Day: 2 Stacks 1 Queue (update)

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 pop() and push() functions, then made the separate MyQueue class using two stacks as planned.

Problem of the Day: 2 Stacks 1 Queue

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.

2 Stacks 1 Queue

Problem of the Day: Stacks & Queues (update)

Linked-lists always mess with me a bit so it’s good that I used one here. My solution is to use two classes: as the main program (calls the operations and prints the results) and as the data structure. includes two internal classes: Head and Node.

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 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.

Problem of the Day: Stacks & Queues

One data structure that can do both stack and queue functions. The underlying structure will be a double-linked-list because I haven’t used much of those lately.

Stacks && Queues

Glad you’re back for another great week!

Today’s problem is about combining two common data structures in to one. Your goal is to implement a data structure that can pop and push like a stack and also dequeue and enqueue like a queue. Here is an example of how your data structure should work.

> [5]

> [5,6]

> [7,5,6]

> 7

> 5

Note: pop and dequeue will essentially do the same thing since they always pull from the front of the line. As always, bonus points for efficiency!

Stacks & Queues

Problem of the Day: Pyramid Sort

Sorting is always tricky and heavily studied for speed and efficiency. My first through was using the idea of keeping the odd numbers on the left and the even on the right which works if the array is only sequential numbers; that assumption certainly makes an assumption out of you and me.

Scratch that idea right quick. Next plan, find the highest number in the array and put it in the middle (index n/2 of odd-numbered arrays or index n/2 + 1 of even numbers to keep the higher number on the right). Works, but then it has to work through both halves at that point. Easy with recursion but not as straight forward.

Last idea, and probably the one I’ll go with, is to focus on the lowest number instead of the high number. Don’t find the highest and put it where it might go instead find the lower number and put it where it will go. The lowest numbers always go on the ends, alternating from left to right where-as the highest number will go in the “middle” then split the array. Work from the outside to the inside instead of inside out. We’ll see where this takes me.

I really should start using something other than Java for variety and to work out the other languages I’m familiar with, C, JS, PHP, even AndroidOS using a nice GUI; but not today.

Anyway, here’s the problem description:

The pyramids of Egypt are some of the most fascinating structures in the world. To honor the great pyramids we’ll be introducing pyramid sort. Pyramid sort works so that the highest numbers are in the center of the array and the lowest are on the edges. When comparing 2 numbers the smaller number goes on the left. So if the array contains 1,2,3 then 1 goes on the left with 2 on the far right and 3 in the middle. Here are 2 more examples:

> psort([1,2,3,4,5])

> psort([1,3,5,7,9,11])

Problem of the Day: Smiley Face (update)

Straight forward implementation of my plan. Found two bugs that were my mistakes:

  1. Typo on when to decrement the counter, I used “)” instead of “(“
  2. When using the split() function I didn’t know I had to escape the “)” character because it is a reserved character. The more you know.

Otherwise it works well. I made sure to keep the functions that do the work, countPar() and print(), separate from main() which should make using a JUnit test to check it rather than calling it from main(). I should really learn how to use JUnit tests. Maybe tomorrow.

Problem of the Day: Smiley Face

Smiley Face

Goal is to verify whether there are matching parenthesisisisisis while crawling through text that can contain a smiley emoticon “:)” that doesn’t count.

Quick idea is to use Java’s built-in split() function to pull out the emoticon, put the string back together, and count the parenthesisisisisis with a simple +/- counter. If the end result is 0 then the parenthesisisisisisisisisisisisisis match!.

Otherwise it’d be parsing the string and not counting any “)” that has a “:” before it. More work than I want to do though.

Coding Practice

Still unemployed and based on my last two technical interviews I’m a little out of practice. To fix this I’m going to start doing the Problem of the Day. Should be an hour or so a day if not less and something to keep me coding.

*Since I’m starting late, expect to see some updates for the ones I’ve done so far that aren’t timed appropriately.