Data Structure

Browsing category

Solar Doomsday

Yesterday I was bored at work and decided to see if I could get back into the Google Foo Bar challenge.  I once again tried all the known combinations that had gotten me in before, and surprise surprise… I got back in.  This time it was the solar doomsday challenge, which I have gotten before.  I intially solved this challenge in Java, and for this attempt I decided to try and solve it in Python.  Both answers are pretty similar, and I’m sure there is a more eloquent solution, but it’s what I came up with.  The Java version was done first, and then Python one follows the same algorithm, just with the Python syntax.  Both use recursion to solve the problem.  The main difference is in the data structure used to hold the final list.  In Java I used a deque, which is a faster version of a linked list when used a queue.  In Python I just went with a standard list and reversed the list before returning the final answer.  Both work, but Python’s seems easier and uses less space than the Java version.

Python Version




'''
Created on Feb 15, 2017



@author: Tony Harrell
'''
import math;



def answer(area):
    fList = [];



    solarPanelCalc(area, fList);
    fList.reverse();
    return fList;



def solarPanelCalc(area, fList):
    pArea = 0;



    if area >= 1 and area <= 1000000:
        tmp = int(math.sqrt(area));
        print tmp;
        if tmp <= 0:
            return pArea;
        else:
            pArea = int(math.pow(tmp, 2));
            nArea = area - pArea;
            solarPanelCalc(nArea, fList);
            fList.append(pArea);
        return pArea;



print answer(12);



Java Version


import java.util.ArrayDeque;
import java.util.Arrays;

public class SolarChallenge {

	public static int[] answer(int area){
		int[] finalList = {};
		ArrayDeque&amp;lt;Integer&amp;gt; areaQueue = new ArrayDeque&amp;lt;&amp;gt;();

		solarPanelCalc(area, areaQueue);

		finalList = new int[areaQueue.size()];
		for(int i=areaQueue.size()-1; i&amp;gt;=0; i--){
			finalList[i] = areaQueue.pop();
		}

		return finalList;
	}

	public static int solarPanelCalc(int area, ArrayDeque&amp;lt;Integer&amp;gt; aq){
		int panelArea = 0;

		if(area &amp;gt;= 1 &amp;amp;&amp;amp; area &amp;lt;= 1000000){
			int temp = (int) Math.sqrt(area);
			if(temp &amp;lt;= 0){
				return panelArea;
			}else{
				panelArea = (int) Math.pow(temp, 2);
				int nextArea = area - panelArea;
				solarPanelCalc(nextArea, aq);
				aq.add(panelArea);
			}
		}
		return panelArea;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] ans1 = answer(12);

		System.out.println(Arrays.toString(ans1));

	}

}

Read more

Google’s FooBar Challenge

What is this FooBar Challenge...

So for the last couple of months I have been addicted to these challenges.  Its a fun game to test your programing knowledge; I also hear it’s a Google recruiting tool, but I haven’t made it far enough to really know.  From all I have looked up online it seems the challenges I am doing are newer than the “Beta Rabbit” ones that people saw in an earlier challenge and have posted answers to.  Not sure if Google is making a new hiring push or just opening up the challenge again with new problems.  What I do know is that the challenges are fun, if you are in to coding challenges.  They definitely have tested my coding abilities, and have broadened my algorithm knowledge.  I know all the basic data structures and algorithms that were taught while getting my degree.  But, some of the questions lead me to new algorithms I hadn’t been taught in any of my schooling.  I enjoy learning and being challenged so these challenges are right up my ally.  I don’t ever think it will lead to anything with Google, and that’s not why I’m really attempting them; although I wouldn’t mind.  I just enjoy the process of learning and it is getting my coding skills back up to par as I prepare to look for software engineering and development jobs.

The Google Search

This whole chasing the rabbit down the hole started when I was preparing for a coding test.  I had read online that the company wanted you to design a database schema and UI, so I decided to implement the whole thing in java so I would know exactly what to do.  While doing my implementation I ran into an issue that required an array list.  Because it had been awhile since I had really coded in straight java, I was Googling “Java ArrayList“.  I thought I had been hacked or someone had cleverly figured out how to implement JavaScript ads that broke my browser; because all of a sudden the browser window split open at the top and and “Your speaking our language.  Up for a challenge?“.  I thought about it for a second, because I hadn’t researched what the FooBar challenge was yet, and finally said screw it, if I get a virus I’ll fix the computer or rebuild it…  So I accepted the challenge and was taken to a terminal like window inside the browser.  This was the start of my challenge, and the start to my obsession and addiction to these challenges.  I have read online that other key search phrases will iniate the browser to ask if you want to take the challenge.  The ones that have worked for me are “Java ArrayList“, “Angularjs Directives” and “Python List Comprehension“.  As I said I have been obsessed and found a way into the challenge a couple of times.  I’ll explain more about that later.

The Challenges

The challenge start out simple enough your type “request” in the terminal receive the challenge and have 48 hours to solve the initial challenge as a guest.  They can usually be solved in a couple hours at most, but its nice that they give you a couple days in case your at work or have other obligations that need your attention.  The one caveat is that the browser window can’t be closed, or lose internet connection, otherwise your challenge will be over.  You need to complete the first challenge to be able to login to again.  Once you have completed the first challenge you are prompted to sign-in to your Gmail account to continue.  Once you have done this you can request another challenge or request another challenge at a later date when you have more time.

So what do these challenges consist of?  Well the initial problems are pretty straight forward, testing your basic coding abilities.  I don’t want to give away the problems for people who might still be trying to get into the challenge, but I will slowly be adding my solutions to my GitHub repo.  To the left is an example of one of the initial challenges and the test cases they provide you to make sure your code works.  The solution to the problem is in my repo now, but don’t look if you want to figure out the challenge yourself.  I have been taking screen shots like these of all the challenges I have faced so that way I can post them somewhere down the line when this version of the challenge is over.  My reasoning for wanting to do this is when I was doing research on the web about the challenge a lot of people commented that they wanted to see what the questions were likes, so they could try to solve them just for fun.  Knowing this, I want to post them for those people, and my solutions to the questions.  I don’t have solutions for all of the challenges as there have been a few that I couldn’t pass.  Either it was a single test case that I was unable to pass due to bounds, or with later the challenges they get pretty difficult and I couldn’t figure out the correct answer.  As others have stated on other blogs or posts on these challenges, someone creating these challenges probably has advanced math degree of some sort.  From what I’ve seen so far a solid understanding of data structures and commonly used algorithms is needed, as well as a good grasp on linear algebra for some problems.  A lot of the challenges are variations on other coding problems that are out in the wild.

Just Some Final Thoughts

If you actually read this whole post you are probably wondering how I got into the challenge so many times.  You need some patience and those search phrases I mentioned earlier.  I removed all my history to the begging of time a couple times, and also uninstalled chrome a couple of times. That might work for a shot or two, but I also used the search phrases on multiple computers with different IP addresses.  I work in IT so I had an abundance of computers to try the searches on.  So try on any computer you can get your hands on, but remember you need to keep the browser window open to be able to move on.  Once it is closed there goes your shot.  Also, if you trick the system into giving you another shot make sure to create or use a different email than you used before.  Google won’t give you another shot with a previously used email.  As I stated before I enjoy these challenges and just wanted to see how many there were and which ones I could solve.  I’m sure if I even got past the round where they supposedly request your information I wouldn’t get a call back.  If your up for a challenge and can get the browser to talk Google’s language the best of luck coding, and enjoy the ride.  Its fun and sometimes frustrating, but will make you a better coder in the end.

Read more