CareerCup

class Valet 
	// park car to a particular spot.  return a ticket if success
	Ticket parkAt (Car car, Spot spot)
	
	// park car, return a ticket if success
	Ticket park (Car car)

	// find a suitable spot for car.  return null if no spot can fit car
	Spot findSpot(Car car)

	// where is car in the parking lot?
	Spot findCar(Ticket ticket)
	
	// is the parking lot full
	boolean isFull()

	// redeem ticket. return spot if sucess
	Spot redeem(Ticket ticket)
}

Class Ticket {
	// to create a ticket, you need a car and a spot
	Ticket (Car car, Spot spot)
}

Car : size, ...
Spot: size, location...

I think what you mean by second last (n-1) node is where the * is

*                               n-1             n
_               _               _               _

{
p = ll.head; q == null; i = 0;
while (i < 3 && p != null) {
    p = p.next;
}

if (p != null) {
    q = ll.head;
}
while (p != null) {
  p = p.next;
  q = q.next;
}
//  q is your answer

}

The same principal applies to the second question. q advances half the distance of p in each loop. If p hits the end of the list before it could double its stride, then q advances half the different between end of list and p

Many specifications are missing from a very general question like this one. For example, should the list be thread-safe? If the question does not specify the requirement you think it is necessary (ie. multiple results of the same genre name), ask the interviewer to clarify, or make an assumption yourself.

Based on the simplicity of the question, I think the interviewer is looking for some unit tests. So my answer was steering to that direction.

If the interviewer wants you to consider a more complex environment (ie. the list is in memcached and can be updated on the fly), I am sure s/he will mention it (or followup questions).

You can perform more sophisticated tests (ie. multi-threaded, mock data objects)
with TestNG. I think TestNG is an excellent tool for integration tests (you can of course use it for unit tests). But the original question was so simple that there is no need to take out the heavy duty tool.

You can of course run with the question and assume a more complex environment to impress the interviewer ;)

my bad ruby. I should have explained it. I "imagine" this object calls SearchEngine which does the searches base on the information from musicList. The question is about writing test cases, so I created SearchEngine to support my test cases.

I edited the pseudocode to clarify the role of SearchEngine. Hope it helps

Why is 100% automation not possible?

If the reasons are resources constraints, technology limitations... things that you can achieve if you throw in extra money, people, time. List them out and discuss the options with your manager.

If the reasons are in the "defying gravity" category, still list them out and discuss the options with your manager.

In the end, the goal is to find the best alternative to 100% automation with the limited resources.

Economics 101: Human has unlimited wants but limited resources. Spend wisely.

Three test cases:
1. test search with only the required parameter (genre) and with optional parameters (index and num of requests)
2. test if music list can handle edge case of 1000 entries
3. test if music list would reject 1001th entry

Using java/junit, here is the init() for each test

{
	@Before
	public void initTest() {
		musicList = new LimitedSizeList<MusicRecord>();
		MusicRecord music1 = new MusicRecord ("Jazz", 1000 , 20605 );
		MusicRecord music2 = new MusicRecord ("Pop", 1005 , 126452 );
		MusicRecord music3 = new MusicRecord ("Country", 1035 , 31209 );
		
		musicList.add(music1);
		musicList.add(music1);
		musicList.add(music1);
	}

}

And here are the 3 tests I listed above

{

	@Test
	// can search() handle the following search options? 
	// search by genre only, search by genre and optional index, search by genre and optional index, num of request
	public void testSearch() {

// pseudocode obj se to perform the searches for the test case
		SearchEngine se = new SearchEngine(musicList);
		
		// test searching music1 with only genre
		MusicRecord music = se.search("Jazz");
		assertEquals (music.genre, "Jazz");
		assertEquals (music.index, 1000);
		assertEquals (music.nRequest, 20605);
		
		// negative test searching music2 with genre and optional index
		music = se.search("Pop", 2014);
		assertNull (music);

		// test searching music3 with genre, optional index and optional request number
		music = se.search("Country", 1035, 31209);
		assertEquals (music.genre, "Country");
		assertEquals (music.index, 1035);
		assertEquals (music.nRequest, 31209);
		
	}
	
	// can LimitSizeList handle edge case of 1000 records?
	@Test
	public void testSizeLimit() {
		for (int i=0; i < 997; i++) {
			// initTest() added 3 records into the test list
			MusicRecord music = new MusicRecord("Genre " + i, 2000+i, 30000+i);
			musicList.add(music);
		}
	}

	
	// will LimitedSizeList throws ExceedSizeLimitException if more than 1000 records added?
	@Test(expected = ExceedSizeLimitException.class)  
	public void testSizeLimitException() {
		for (int i=0; i < 998; i++) {
			// initTest() added 3 records into the test list
			MusicRecord music = new MusicRecord("Genre " + i, 2000+i, 30000+i);
			musicList.add(music);
		}
	}

}

Breath First Search marks a visited node so it will not be revisited. A performance tweak would be, sort the distance between an unvisited or unblocked child node and the destination, recursive down to the shortest distance node first.

For example, if the start is (1,1) and the end is (3,0) of a matrix of 10x10. The algorithm should try the path of child (1,0) before the path of child (1,2). The distance between (1,0) and (3,0) is 2. The distance between (1,2) and (3,0) is 4.

{
public class MinRecursiveAdd {
	
	   private static Scanner in;
	  
	   
	   public static void main(String[] args) {
	      
	      in = new Scanner(System.in);
	      int a = in.nextInt(); 
	      int b = in.nextInt();
	      
	      
	      int result;
	      if (a < b) {
	    	  result = recursiveAdd(b, a);
	    	  System.out.println( b + " is added " + a + " times.");
	      } else {
	    	  result  = recursiveAdd(a,b);
	    	  System.out.println( a+ " is added " + b + " times.");
	      }
	      
	      System.out.println("recursiveAdd result is " + result);
	      
	   }
	   
	   static int recursiveAdd(int num, int times) {
		  
		   if (times > 0) {
			   return num + recursiveAdd(num, times - 1);
		   } else {
			   return 0;
		   }
	   }

}

}

The question hinted that the user id is not a unique field. I will do it this way

select t.uid, max(t.countUid)
from
(select uid, count(uid) as countUid from yourtable group by uid order by countUid desc) t