Monthly Archives: February 2007

Always Have Exact Change With Only 10 Coins!

I hate having spare change. Change sucks because it usually just sits in your house and it’s a waste of money. I found a way to use the change you have and never get change back when purchasing with cash. With a set of just 10 coins, you can make change for any amount from 1 cent to 99.

I’ve already read about the 10 coins somewhere else online. It’s not really interesting to have the answer given to you. Since I’m a nerdy computer scientist, I was trying to come up with an algorithm to produce this set of coins. I came up with an iterative solution that goes like this:

Start out with no coins.

From 1 to 99 cents:

If you can make exact change for the current amount, go to the next amount.

Otherwise, try adding the largest denomination coin to your set of coins (a quarter) that will allow you to pay the exact amount. If it’s too big, go to the next smallest until you hit a penny.

End Loop.

I came up with this in the shower. When I got out and tried it, it actually worked! Here’s a portion of the trace through the loop:

No coins, I need to make change for 1 cent. Add a penny. Yay, I can make change for one cent!

4 pennies, need to make change for 5 cents. Add a nickel.

4 pennies 1 nickel, need to make change for 10 cents. Add a dime.

And so on. I believe the algorithm works because it uses a greedy heuristic of choosing the largest denomination coin first before defaulting to the penny. Am I a nerd? Yes.

Oh, I just realized I didn’t actually say which 10 coins were the ones you need. They’re 4 pennies, one nickel, two dimes, and three quarters. You can also do it with two nickels and one dime but that’s not what my algorithm came up with, plus two dimes are lighter than two nickels!

Have fun getting rid of your change!

PS2 – Karaoke Revolution Party Review


I got Karaoke Revolution Party in December for around $10 at Toys R Us. It was a pretty sweet deal. I already had a microphone from Socom, so I figured I wouldn’t need an extra mic. Luckily it worked.

So the basic premise of Karaoke Revolution is that you sing songs, and you get more points if you sing in tune with the correct vocals. There are note “tubes” that show up indicating whether you’re singing too low or high. It’s not quite like reading music or anything, but I guess it’s pretty good for public use.

I really like the idea of playing a game with only your voice. It’s a pretty interesting idea and I’m kind of mad that I waited so long to finally buy a Karaoke Revolution game. I sort of secretly wanted to buy it ever since seeing these guys playing it.

The gameplay isn’t perfect, though. It seems like the game has an easier time recognizing pitch in higher octaves, so if you’re a guy, you already have a disadvantage to the girls. Also, the game is really strict in telling you exactly how to sing a song. So when I add some “soul” it ends up costing me points. Boo! It’d be pretty sweet if the game could detect freestyling and reward players for doing it well. I guess that would be pretty hard though.

The song selection is varied. There’s a lot of songs from the 80s up to current popular songs. They even have Neil Diamond, which my brother was happy about. I think most people will find at least one song they’d be interesting in singing, if they’re interested in singing a song to begin with.

Overall, Karaoke Revolution Party is a pretty cool party game. I wish I had bought two mics so I could test out the versus and duet modes. I think there’s some duets… Maybe I’ll buy the new American Idol version.

Google Update: Invitation to Google College Days

So I got an email back from Google the Monday after my interview, but I hadn’t posted anything about it. They invited me to their Google College Days, which I’ve actually never heard of before. It seems pretty cool. Here’s part of the email they sent:

Congratulations, your on-campus interviews went well and we would like to invite you to Google’s Headquarters in Mountain View, CA for a College Day!

Google College Days are fun! We’ll fly you out before the interviews, provide lodging and transport you to Google on Friday morning for a full day visit and then fly you back home. You’ll be on site from 8:45 AM – 3:15 PM on Friday. Below is the agenda for our College Days.

8:45 AM – Depart to Google (we’ll pick you up from your hotel)

9:15 AM – Arrive Google and Check-In

9:30 AM – Kick Off (executive sponsor to speak and kick off the day, coffee
and pastries)

10:15 AM – Interviews (3, 45 minute technical interviews). Please note: You will be asked questions to test your coding, algorithm and design skills. You might want to refer to to learn more about our products in beta.

12:05 PM – Tour of the Googleplex

12:50 РLunch at the Google Caf̩ with engineers

1:45 PM – Organized Free Time (have a chair massage, chat with other

2:15 PM – Q&A/Closing (Engineers and Recruiters show up to answer questions
about life at Google and the hiring process, etc.)

2:45 PM – Ice Cream Social (Build a sundae and chat with other students,
Google Engineers and Recruiters)

3:15 PM – Depart to hotel (we’ll transport you back to your hotel)

This is way too cool. I think it’s the dream of every nerd to visit the Googleplex, and to be flown out there (for free) for a tour, food, and interviews is just plain awesome. The fact that they’re interviewing me for a position is like icing on the cake for a nerd like myself. I wonder if I’ll be allowed to take pictures… It’d make an awesome blog post.

I’ll be attending their March 23rd one, since it’s the date with the least conflict for me. Hopefully everything will go well and I’ll be able to visit the Googleplex on a more regular basis. Like every weekday or so…

Dream: Door to Door Pig Salesman

So I had this totally weird dream last night. It involved my entire neighborhood! For some reason, there was someone going door to door leaving pigs at people’s houses. When the guy got to our house, we didn’t answer the door. He opened our outer shutter door and left a pig in between the two doors. I could see all of this happening through our peep hole, even though It’d be pretty impossible to see that low in real life. Weird. Okay, now that I think of it, I guess he was more of a pig mailman than a salesman, but I have a feeling we were billed for the pig. To be payed for at a later date.

Anyway, when I opened the door, the pig ran in and I guess we kept it as a pet. I went to my neighbor’s house and found that the pig guy had left a pig in her door as well. When I opened it though, it was like some kind of mutant weird pig and I ran away.

Later, I went to my across the street neighbor’s house. We had seen him with his pig earlier, so I guess we decided to check up on it. When we got there, he adamantly denied having any kind of pig. We knew he was lying because we saw him playing with the pig though his window from our house.

Then the dream ended. It totally made no sense to me, but that’s how a lot of my dreams go. It’s probably worth noting that today is Chinese New Year, and yes, it’s the year of the pig!!! Maybe that somehow subconsciously seeped into my brain while I was dreaming last night… Also, my Chinese zodiac sign is the pig!!! Dun dun dunnnn!!!