CareerCup

public class LRUCache<K,V>{
	private MyLinkedHashMap<K,V> cache;
	private final int cache_size;
	public LRUCache(int size){
		cache_size = size;
		this.cache = new MyLinkedHashMap<K,V>(){
			protected boolean removeEldestEntry(MyLinkedHashMap.Entry<K,V> eldest){
				//System.out.println("remove Eldest entry: " + (cache_size >= size()));
				return cache_size < size();
			}
		};
	}

	public V get(K key){
		return cache.get(key);
	}
	public void put(K key, V value){
		cache.put(key,value);
	}
	public boolean  containsKey(K key){
		return cache.containsKey(key);
	}
	public void print(){
		cache.print();
	}
	public void printTable(){
		this.cache.printTable();
	}
}

Use AWS Cloud front.

caching static content
caching dynamic content for a small time ( 1sec, 1 minute, depend)
Route your data to the closest server ( CDN )
tcp optimizations: keep alive connections to reuse connections and avoid 3wayhanshake

there is a bug in carrercup.com.. why It did not encoded my code?

The classes for CD, Song, and User are all fairly straightforward. They consist mainly of
member variables and getters and setters.

public class CD { 
 /* data for id, artist, songs, etc */ 
 } 
 
 public class Song { 
 /* data for id, CD (could be null), title, length, etc */ 
 } 
 
 public class User { 
 private String name; 
 public String getName() { return name; } 
 public void setName(String name) { this.name } 
 public long getlD() { return ID; } 
 public void setID(long ID) { ID = iD; } 
 private long ID; 
 public User(String name, long iD) { … } 
 public User getUser() { return this; } 
 public static User addUser(String name, long iD) { ... } 
 }

The Playlist manages the current and next songs to play. It is essentially a wrapper
class for a queue and offers some additional methods for convenience.

public class Playlist { 
 private Song song; 
 private Queue<Song> queue; 
 public Playlist(Song song, Queue<Song> queue) { 
 … 
 } 
 public Song getNextSToPlayQ { 
 return queue. peek(); 
 } 
 public void queueUpSong(Song s) { 
 queue. add(s); 
 } 
 }

Like a real CD player, the CDPlayer class supports storing just one CD at a time. The
CDs that are not in play are stored in the jukebox.

class CDPlayer { 
 private Playlist p; 
 private CD c; 
 
 /* Constructors. */ 
 public CDPlayer(CD c, Playlist p) { ... } 
 public CDPlayer(Playlist p) { this.p = p; } 
 public CDPlayer(CD c) { this.c = c; } 
 
 /* Play song */ 
 public void playSong(Song s) { ... } 
 
 /* Getters and setters */ 
 public Playlist getPlaylist() { return p; } 
 public void setPlaylist(Playlist p) { this.p = p; } 
 
 public CD getCD() { return c; } 
 public void setCD(CD c) { this.c = c; } 
 }

public class Jukebox { 
 private CDPlayer cdPlayer; 3 private User user;
 private Set<CD> cdCollection;
 private SongSelector ts; 
 
 public Jukebox(CDPlayer cdPlayer, User user, 
 Set<CD> cdCollection, SongSelector ts) { 
 … 
 } 
 
 public Song getCurrentSong() { 
 return ts.getCurrentSong(); 
 } 
 
 public void setUser (User u) { 
 this. user = u; 
 } 
 }

In any object-oriented design question, you first want to start off with asking your
interviewer some questions to clarify design constraints. Is this jukebox playing CD?
Records? MP3s? Is it a simulation on a computer, or is it supposed to represent a
physical jukebox? Does it take money, or is it free? And if it takes money, which
currency? And does it deliver change?

Unfortunately, we don't have an interviewer here that we can have this dialogue with.
Instead, we'll make some assumptions. We'll assume that the jukebox is a computer
simulation that closely mirrors physical jukeboxes, and we'll assume that it's free.
Now that we have that out of the way, we'll outline the basic system components.
• Jukebox
• CD
• Song
• Artist
• Playlist
• Display (displays details on the screen)

Now, let’s break this down further and think about the possible actions.
• Playlist creation (includes add, delete, and shuffle)
• CD selector
• Song selector
• Queuing up a song
• Get next song from playlist

A user also can be introduced:
• Adding
• Deleting
• Credit information

Each of the main system components translates roughly to an object, and each action
translates to a method. Let's walk through one potential design.

The Jukebox class represents the body of the problem. Many of the interactions
between the components of the system, or between the system and the user, are
channeled through here.

What about this implementation in place.
We reverse the sencond half of the list and compare half of the list.
I think It more efficient.
IF WE have to leave the linked list as Its initial state, then we can just reverse the half again.

public static boolean  isPalindrome(LNode node){
		int size = size(node);
		int middle = size/2;
		
		if((size % 2) != 0) middle++; // special clase for odd linked list size
		
		LNode current = node;
		LNode runner = node;
		int counter = 0;
		while(counter < middle-1){
			runner = runner.next;
			counter++;
		}
		runner.next = reverse(runner.next);
		runner = runner.next;
		while(runner != null){
			if(runner.value != current.value){
				return false;
			}
			runner = runner.next;
			current = current.next;	
		}
		
		return true;
		
	}

	public static LNode reverse(LNode node){
		LNode current = node;
		LNode next = null;
		LNode prev = null;
		
		while(current != null){
			next = current.next;
			current.next = prev;
			prev = current;
			current = next;
		}
		return prev;
	}

C:\javatest>java Trees
Tree questions
1 ,2 ,
0 ,2 ,

Well.. Then I am just half wrong. look at the output

root = insert(root,1);
		insert(root,2);
		inorder(root);
		System.out.println();
		chSum(root);
		inorder(root);

output:

C:\javatest>java Trees
Tree questions
1 ,2 ,
2 ,2 ,

Root holds 2.

then I just need to change the case where the node is a leaf

public static int chSum(TNode node){
		if(node == null){
			return 0;
		}else if(node.left == null && node.right == null){
			return 0;  // return 0,since we dont have anything left
		}else{
			int  tmp = node.value;
			node.value = chSum(node.right);
			return tmp + node.value + chSum(node.left);
		}
	}

hey, tell me why I am wrong?

public static int chSum(TNode node){
		if(node == null){
			return 0;
		}else if(node.left == null && node.right == null){
			return node.value;
		}else{
			int  tmp = node.value;
			node.value = chSum(node.right);
			return tmp + node.value + chSum(node.left);
		}
	}

is It a heap? If so, there is not need to recreated:

Parent of node i = i/2
Left node for node i = i*2
Right node for node i = (i*2) + 1

I agree mostly about all.
But I think we should have a class call ElevatorSystem that has a Set of Elevators.
ElevatorSystem must be a singleton object where you control each Elevator.

Additional business rules could be:
-> There are a window of time where the elevator are very crowded, so If there are N Elevators and M floors. It could be good to N/2 elevators only server requests for floors from 0 to M/2 and the rest from M/2 + 1 to M
-> If 2 elevators at floor 10 are going down, and there is a request at floor 5th, then one of them will have to attend the request, but not both. which one? Well It may be one that is carries less people perhaps.
-> Each Elevator must contain a priority attribute that can be use to take decisions of requests.

We want to avoid any synchronization issue, so access to Queue<Request> reqs must be synchronized.

We can even make the system distributed and treat each elevator as a Peer, Host or Computer. So we can send messages back and forth.
For example:

Request at floor 5:
->Send broadcast to all Elevators
-> Each elevator that receives the messages, sent back with an reply message with Its state ( location, occupation, weight, etc etc ) And let the System decide which one to call.

We can discuss a lot about this type of questions. I think It is good to share ideas as much as possible.

C:\javatest>java Test axelaxel
aaeellxx
It is even: true
aelxxlea

C:\javatest>java Test aaa
aaa
It is even: false
aaa

C:\javatest>java Test aaaab
aaaab
It is even: false
aabaa

Sort the string and swap contiguous elements to the beginning and to the end.
Complexity

O ( N long N ) + O ( N )

Space complexity O ( 2N )

public static String getPalindrome(char str []){
	char [] result = new char[str.length];
	Arrays.sort(str);
	boolean isEven = (str.length % 2 == 0);
	int start  =0;
	int end = str.length -1;
	char reminder = ' ';
	for(int i = 1; i < str.length; i+=2){
		if(str[i-1] != str[i]){
			if(isEven){
				return "-1";
			}else{
				reminder = str[i-1];
				isEven = true;
			}
		}else{
			result[start++] = str[i];
			result[end--] = str[i-1];
		}
		if(i+1 == str.length-1) // special case when is not even and reminder is the last one
			reminder = str[i+1];
	}
	
	if(start == end){
		result[start] = reminder;
	}
	return new String(result);
}
public static void main(String [] args){
	System.out.println(getPalindrome(args[0].toCharArray()));
}

It still wrong.
It is missing a lot cases. Like 9 +1

2+2+2+2+2

and so on...

#trueStory good catch. Well... Let me think about a new solution. I will get back soon. thx

What about this one?

But I am still struggled with the complexity. It seems to be O ( n ^ 3 ) What do you guys think ?

public static void printAll(int t){
 		System.out.println(t + " = ");
 		for(int i=2; i <= t; i++){
 			for(int j=1; j <= i/2 ; j++){
 				System.out.print((i-j) + "+" + j);
 				for(int x=i; x < t; x++){
 					System.out.print("+1");
 				}
			System.out.println();	 			
 			}
 		}
 	}

A little improvement on my previous approach. But It still O (n^3)

Is there any better way to improve this ?

public static void printAll(int t){
 		System.out.println(t + " = ");
 		for(int i=2; i <= t; i++){
 			for(int j=1; j <= i/2 ; j++){
 				System.out.print((i-j) + "+" + j);
 				for(int x=i; x < t; x++){
 					System.out.print("+1");
 				}
			System.out.println();	 			
 			}
 		}
 	}

public static void all(int t){
	String R[][] = new String[t+1][];
	R[0] =new String[0];
	for(int i = 1; i <= t; i++){
		R[i] = new String[(i/2) + 1];
		for( int j = 1; j <= i/2; j++){
			R[i][j] = (i-j) + "+" + j + "";
		}
	}
	System.out.println(" -> ["+t+"] =  ");
	for(int i = t; i >= 0 ; i-- ){
		for(int j = 1; j < R[i].length; j++){
			System.out.print(R[i][j]);
			for(int x= i; x < t; x++){
				 System.out.print("+1");
			}
			System.out.print(", ");
			
		}
		System.out.println();
	}
	System.out.println();
}

test case:

all(10);

output:

-> [10] =
9+1, 8+2, 7+3, 6+4, 5+5,
8+1+1, 7+2+1, 6+3+1, 5+4+1,
7+1+1+1, 6+2+1+1, 5+3+1+1, 4+4+1+1,
6+1+1+1+1, 5+2+1+1+1, 4+3+1+1+1,
5+1+1+1+1+1, 4+2+1+1+1+1, 3+3+1+1+1+1,
4+1+1+1+1+1+1, 3+2+1+1+1+1+1,
3+1+1+1+1+1+1+1, 2+2+1+1+1+1+1+1,
2+1+1+1+1+1+1+1+1,
1+1+1+1+1+1+1+1+1+1,

Here in the complexity, I need help. It seems that It is n^3 worse case ( but not sure )
Complexity

O ( n* n/2) + O (n*(n/2)*t) = O (n^2) ??? please help.

Here is an example with Memorization:

public static void main(String [] args)
	{
		int V [] = {0,1,5,8,9,10,17,17,20,24,30};
		for(int i = 0; i < 10; i++){
			rod_cutting(V,i);
		}
		
	}
public static void rod_cutting(int V[], int N){
		int B[] = new int[N+1];
		String path []= new String[N+1];
		B[0] = 0;
		
		for(int i = 1; i <= N ; i++){
			int max =  V[i];
			path[i] = i + "ps ($" +V[i] +")";
			for(int j = 1; j < i; j++){
				int current = V[j] + B[i-j];
				if(current > max){
					max = current;
					path[i] = j + "ps ($"+V[j]+")  + " + (i-j) + "ps ($"+(B[i-j])+")";
				}
			}
			B[i] = max;
		}
		System.out.println(path[N] + " = $" + B[N]);		
	}

Output:

null = $0
1ps ($1) = $1
2ps ($5) = $5
3ps ($8) = $8
2ps ($5)  + 2ps ($5) = $10
2ps ($5)  + 3ps ($8) = $13
6ps ($17) = $17
1ps ($1)  + 6ps ($17) = $18
2ps ($5)  + 6ps ($17) = $22
3ps ($8)  + 6ps ($17) = $25

both works.

Complexity O ( N )

public static void findMaxSubArray(int[] A){
 		int start = 0;
 		int end = 0;
 		int start_so_far = 0;
 		int max = 0;
 		int max_so_far = 0;
 		
 		for( int i = 0; i < A.length; i++)
 		{
 			max_so_far += A[i];
 			
 			if( max_so_far >= max ){
 				max = max_so_far;
 				end = i; 
 				start = start_so_far;
 			}else if(max_so_far < 0){
 				max_so_far = 0;
 				start_so_far = i + 1;
 			}
 		}
 		
 		for(int i= start; i <= end; i++){
 			System.out.print(A[i] + " , ");
 		}
 		System.out.print(" = " + max);
 	}

space complexity = O ( N )
running complexity = O ( N^2 )

public static int rod_cutting(int V[], int N){
		int B[] = new int[N+1];
		B[0] = 0;
		
		for(int i = 1; i <= N ; i++){
			int max =  V[i];
			for(int j = 1; j < i; j++){
				int current = V[j] + B[i-j];
				max = Math.max(max,current);
			}
			B[i] = max;
		}
	return B[N];		
	}

I believe my answer is not acceptable... But I least I came up with something that works ok. I will spend more time to get a better answer ( without peeking! I really will do it on my own )

import java.util.*;
public class Test{

public static void main(String [] args){
	Random r = new Random();
	int N = 1000;
	int T = r.nextInt(Integer.MAX_VALUE);
	
	int A [] = new int[N];
	for(int i = 0; i < A.length; i++){
		A[i]=r.nextInt(Integer.MAX_VALUE);
	}
	
	Arrays.sort(A);
	reverse(A);
	print(A);
	sumSubset(A,T);
}
public static boolean sumSubset(int A[], int T){
	System.out.println("Target = " + T );
	int totalSum = 0;
	String nums = "";
	for(int i = 0; i < A.length; i ++){
		if(A[i] > T) continue;
		totalSum = A[i];
		int subtotal = 0;
		for(int j = i+1; j < A.length; j++)
		{
			int tmp= totalSum;
			nums = A[i] + "+ ";
			subtotal= totalSum;
			for(int z = j; z < A.length; z++){
				if( tmp + A[z] <= T ){
					tmp += A[z];
					nums += A[z] + " + ";
				}
				if(tmp == T){
					System.out.println(nums + "= " + T);
					return true;
				
				}
				
				subtotal += A[z];
			}
			/*if(subtotal < T ){
				System.out.println("You will never find an answer here");
				return false;  // There is no way to get to the T value
			}*/
		}
	}
	System.out.println("I could not find the answer, Sorry Sr Axeliux");
	return false;
}


public static void reverse(int A[]){
	int i = 0;
	int e = A.length -1 ;
	while(i < e){
		swap(A,i,e);
		i++;
		e--;
	}
}
public static void print(int A []){
	for(int i = 0 ; i < A.length; i ++){
		System.out.print(A[i] + ", ");
	}
	System.out.println();
}
public static void swap(int A[], int a, int b){
	int t = A[a];
	 A[a] = A[b];
	 A[b] = t;
}








}

yes. but what about the blocks 3x3 ??

key*

this is the missing part.

if ( keey > 9)  return false;

Oups/ I forgot to validate values from 0 to 9. not big deal to fix that.
Sorry about that.

Additional to that, I could have fix the size of each hashtable to 10, to save some memory as well.

I got little stuck at the interview and I couldn't get the right answer. After I hang out the phone, my mind just relaxed and cleared out and the solution just came to my mind and I could code it in 10-15min .... Too late I think.

Recomendation: Take a deep breath, relax and DO NOT GET NERVOUS!!! Interviews are not that hard ( when you prepare )

public static boolean validateSudoku(int A[][]){
	        @SuppressWarnings("unchecked")
		Hashtable<Integer,Boolean> rows[] =(Hashtable<Integer,Boolean>[]) new Hashtable<?,?>[9];
                @SuppressWarnings("unchecked")
		Hashtable<Integer,Boolean> columns[] =(Hashtable<Integer,Boolean>[]) new Hashtable<?,?>[9];
                @SuppressWarnings("unchecked")
		Hashtable<Integer,Boolean> blocks[][] =(Hashtable<Integer,Boolean>[][]) new Hashtable<?,?>[3][3];
		for(int r = 0; r < A.length; r++ ){
			for(int c = 0; c < A[r].length; c++){
				int key = A[r][c];

				if(rows[r] != null && rows[r].containsKey(key)){
					return false;
				}else{
					rows[r] = new Hashtable<Integer,Boolean>();
					rows[r].put(key,true);
				}
				if(columns[c] != null && columns[c].containsKey(key)){
					return false;
				}else{
					columns[c] = new Hashtable<Integer,Boolean>();
					columns[c].put(key,true);
				}
				int rk = r / 3;
				int ck = c / 3;
				if(blocks[rk][ck] != null && blocks[rk][ck].containsKey(key)){
					return false;
				}else{
					blocks[rk][ck] = new Hashtable<Integer,Boolean>();
					blocks[rk][ck].put(key,true);
				}
			}
		}
		return true;
	}

cheers,
Axel

just a little optimization

public static TNode FCA(TNode root, int a, int b){
		if(root == null) return null;
		if(root.value == a || root.value == b) return root;
		if(!exist(root,a) || !exist(root,b)) return null;
		
		return FCA_helper(root,a,b); 
	}
	public static TNode FCA_helper(TNode root,int a , int b){
		if(root == null) return null;
	
		boolean is_a_on_left = exist(root.left,a);
		boolean is_b_on_left = exist(root.left,b);
		if(is_a_on_left != is_b_on_left){
			return root;
		}else{
			if(is_a_on_left) // or is_b_on_left
			{
				return FCA(root.left,a,b);
			}else{
				return FCA(root.right,a,b);
			}
		}
	}
	public static boolean exist(TNode root, int value){
		if(root == null){
			return false;
		}else{
			if(root.value == value){
				return true;
			}else{
				return exist(root.left,value) || exist(root.right,value);
			}
		}
	}

We don't want millions on a recursive traversal right ?

equalTree could or not be recursivly since we are taking about hundred of nodes, which is not that big. But we can for sure make this none recursive and make it better.

public static boolean equalTree(TNode t1, TNode t2){
		if(t2== null) return true;
		if(t1== null) return false;
		if(t1.value == t2.value){
			return equalTree(t1.left, t2.left) && equalTree(t1.right,t2.right);
		}else{
			return false;
		}
	}

Here is an optimization. Since T1 is too big, we don't want to do it recursively right? So what about a BFS like this:

public static boolean isSubtree2(TNode t1, TNode t2){
		Queue<TNode> queue = new java.util.LinkedList<TNode>();
		queue.add(t2);
		while(!queue.isEmpty())
		{
			TNode current = queue.poll();
			if(equalTree(current, t2)){
				return true;
			}else{
				if(t2.value < t1.value){
					queue.add(t1.left);
				}else{
					queue.add(t1.right);
				}
			}
		}
		return false;
	}

Agree with you. but in your code you forgot to remove the next node.

public static LNode reverse(LNode head){
		if(head == null || head.next == null) return head;
		if (head.next.next == null){
			LNode tmp = head.next;
			tmp.next = head;
			head.next = null;
			head = tmp;
			
		}else{
			LNode previus = head;
			LNode current = previus.next;
			LNode next = current.next;
			previus.next = null;
			while(next != null){
				current.next = previus;
				previus = current;
				current = next;
				next = next.next;
	                }

	                current.next = previus;
	                head = current;
		}
		return head;
	}

public static LNode add1(LNode l1, LNode l2){
		LNode result = null;
		int size1 = size(l1);
		int size2 = size(l2);
		int currentDigit = Math.max(size1,size2);
		boolean carrier = false;
		while(l1 != null && l2 != null)
		{	
			int sum = 0;
			if(currentDigit <= size1){
				sum += l1.value;
				l1 = l1.next;
			}
			if(currentDigit <= size2){
				sum += l2.value;
				l2 = l2.next;
			}
			
			currentDigit--;
			
			if(carrier){
				sum += 1;
			}
			if(sum >= 10){
				carrier =true;
			}else{
				carrier = false;
			}
			result = append(result,sum%10);
		}
		if(carrier)
		{
			result = append(result,1);
		}
		return result;
			
	}
	public static int size(LNode head){
		if( head == null) return 0;
		
		LNode tmp = head;
		int counter = 0;
		while(tmp != null){
			counter++;
			tmp = tmp.next;
		}
		return counter;
	}

//Implement an algorithm to find the nth to last element of a singly linked list.
	// complexity  O (2n) since size(head) requires O ( n )
	public static LNode kth(LNode head, int k){
		if(size(head) < k)
		{
			return null;
		}else{
			LNode runner = head;
			LNode target = head;
			while(k > 0 ){
				runner = runner.next;
				k--;
			}
			while(runner != null){
				runner = runner.next;
				target = target.next;
			}
			return target;
			
		}
	}

public static void deleteMe(LNode me){
        	if(me.next == null) return; // If it is the last element of the list, this cannot be deleted
        	if(me.next.next == null){
        		me.value = me.next.value;
        		me.next = null;
        	}else{
			 while(me.next.next != null){
			 	me.value = me.next.value;
			 	me = me.next;
			 }
			 me.next = null;
		}
        }

// remove duplicates
	// complexity O ( n )
	public static void removeDuplicates(LNode head){
		Hashtable<Integer,LNode> table = new Hashtable<Integer,LNode>();
		if(head == null) return;
		if(head.next == null) return;
		LNode current = head;
		LNode next = current.next;
		table.put(current.value, current); 
		while(next != null){
			if(table.containsKey(next.value)){
				next = next.next;
				current.next = next;
							
			}else{
				table.put(next.value,next);
				current = next;
				next = next.next;
			}
			
		}
	}

// remove duplicates with out an extra buffer.  
// complexity O (n^2) 
	public static void removeDuplicates2(LNode head){
		if(head == null) return;
		if(head.next == null) return;
		
		LNode current = head;
		
		
		while(current != null){
			int currentValue = current.value;
			LNode previus = current;
			LNode next = current.next;
			while(next != null){
				if(next.value == currentValue){
					
					next = next.next;
					previus.next = next;
				}else{
					previus = next;
					next = next.next;
				}
				    
			}
			current = current.next;
		}
	}

I would be worse if you try to save each letter and iterate one by one. the complexity will be >= O (n square )

I dont see a better solution. do you ?

again ganesh?? your code does not work!!!!!!!!!!!!!!!!!!!!!!

ganesh read the problem well before posting. Unique characters meas each one never is repeated in the string. No the other way around.

well. you can compare every character of the string to every other character of the string. This will give you O ( n square )

another option is, you can soft the array on O ( n long n ) and then, iterate to look for duplicates.
What about that?

sorry, I meant the following:

min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;

I agree with you. My mistake I meant

min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;

sorry about that.