CareerCup

public static boolean isValidIp(String s){
		if(s==null || s.length()==0||s.length()>15) return false;
		for(int i = 0,num=0,numDots=0;i<s.length();i++){
			char c = s.charAt(i);
			if(c=='.'){
				if(++numDots>3 || num>255) return false;
				num = 0;
			}else{
				int digit = c-'0';
				if(digit<0||digit>9)return false;
				num*=10;
				num+=digit;
				if(num>255)return false;
			}
		}
		return true;
	}

public class AirportNode{
		private String name;
		private ArrayList<AirportNode> from = new ArrayList<AirportNode>();
		private ArrayList<AirportNode> to = new ArrayList<AirportNode>();
		private int longestPath = 0;
		public AirportNode(String name){ 
			this.name = name;
		}
		public String Name(){
			return name;
		}
		public int LongestPathDistance(){
			return longestPath;
		}
		public void addFrom(AirportNode n){
			from.add(n);
			n.updateLongestPath(this);
		}
		public void addTo(AirportNode n){
			to.add(n);
			n.addFrom(this);
		}
		public void updateLongestPath(AirportNode n){
			if(n.LongestPathDistance()>=longestPath){
				longestPath = n.LongestPathDistance()+1;
				to.remove(n);
				to.add(0, n);
				for(AirportNode f : from)
					f.updateLongestPath(this);
			}
		}
		
		public AirportNode getLongestPathNode(){
			return to.size() == 0 ? null : to.get(0);
		}
		
	}
	
	public String findPath (String [] airports){
    	HashMap<String,AirportNode> map = new HashMap<String,AirportNode> ();
    	    	for (int i = 0 ; airports.length - 2 >= i  ; i += 2){
    	    		AirportNode d = null;
    		    	if(!map.containsKey(airports[i])){
    			    	d = new AirportNode(airports[i]);
    	    			map.put(airports[i],d);
    	    		}else
    		    		d = map.get(airports[i]);
    	    		AirportNode a = null;
    	    		if(!map.containsKey(airports[i+1])){
    		    		a = new AirportNode(airports[i+1]);
    			    	map.put(airports[i+1],a);
    	    		}else
    	    			a = map.get(airports[i+1]);
    	    		d.addTo(a);
    	    	}
    	    	AirportNode n = null;
        	for(String d:map.keySet()){
    	    		if(n == null || 
    	    	    	    	n.LongestPathDistance()<map.get(d).LongestPathDistance()) 
    	    			n = map.get(d);
    	    	}
    	 
     	   	StringBuilder sb = new StringBuilder ();
      	  	sb.append(n.Name()) ;
     	   	while ((n = n.getLongestPathNode()) != null) {    	   
    	    	   	sb.append("->") ;
    	    	   	sb.append(n.Name()) ;
      	  	}    	
      	  	return sb.toString() ;
	}

What if there is a airport that has path to two airport? I think ,this solution does not work!!
for example,
let the array is {1,2,3,4,1,3,5,3,2,5,2,4}
so the paths are
1->2
3->4
1->3
5->3
2->5
2->4

So, the solution should be 1->2->5->3->4
But, your algorithm is return 1->3->4

My method is based on the mathematical formula that sum of numbers in between 1 and n which is "n*(n+1)/2"

Let say N is 20
the sum of numbers less than 20 and divisible by 3 are:
3 + 6 + 9 + 12 + 15 + 18 = (1+2+3+4+5+6)*3
In this case, I can calculate the sum of numbers in between 1 and 6 by using "n*(n+1)/2". So this is equals to (6*7/2) * 3

This is the same for the sum of numbers less than 20 and divisible by 5.
5 + 10 + 15 = (1+2+3)*5 => (3*4/2)*5

As seen, we add 15 in both of operations, so we have to eliminate duplicates.
In order to do that, I calculate the same for the sum of numbers less than 20 and divisible by 15.

At the end, I add the sum of divisible by 3 and the sum of divisible by 5 than subtract the sum of divisible by 15

That's it!

I gave the same answer!!!
I still don't know how to deal with the cases when initial X is 0 or negative!!!

Yeah!! you are right, I made a mistake, I corrected it.

Now, Let us take example of 10 (10 is not included)
div3 = 3*4/2 = 6*3 = 18
div 5 = 1*2/2 = 1*5 = 5
div15 =0

div3 + div5 - div15 = 18+5 - 0 = 23

Firstly, I solved it by designing O(N) algorithm but than, by the help of interviewer, I came up with a solution that solves the problem in O(1)

My final solution is as follows:

public int SumOfNumber(int N){
        N--;
	int divisibleBy3 = N/3;
	divisibleBy3 = (divisibleBy3 * (divisibleBy3 + 1) /2)*3;

	int divisibleBy5 = N/5;
	divisibleBy5 = (divisibleBy5 * (divisibleBy5 + 1) /2)*5;

	int divisibleBy15 = N/15;
	divisibleBy15 = (divisibleBy15 * (divisibleBy15 + 1) /2)*15;
	
	return divisibleBy3 + divisibleBy5 - divisibleBy15
}

public int NumberOfPossibleStrings(String str){
		if(str == null || str.length()==0) return 0;
		if(str.length()==1)return 1;
		if(str.length()==2)
			if(str.charAt(0)<'3'&&str.charAt(0)>'0')return 2;
			else return 1;
				
		if(str.charAt(0)=='0'||str.charAt(0)>'2')
			return NumberOfPossibleStrings(str.substring(1));
		return NumberOfPossibleStrings(str.substring(1))+
				NumberOfPossibleStrings(str.substring(2));
	}

public static char[] eliminate(char[] arr){
		if(arr == null) return arr;
		int p = -1;
		for(int i = 0; i<arr.length;i++){
			p++;
			if(p!=i) 
				arr[p] = arr[i];
			if( arr[p] =='b') 
				p--;
			if(arr[p] == 'c' && p>0 && arr[p-1] =='a') 
				p-=2;
		}
		p++;
		if(p<=arr.length -1) 
			arr[p] = '\0';
		return arr;
	}

Java implementation

public static void fill(HashMap<String, Double> map,int L,int N,double capacity){
		String key = "L"+L+"N"+N;
		if(!map.containsKey(key)){
			map.put(key, 0.0);
		}
		if(map.get(key)<0.25){
			double c = 0.25-map.get(key);
			if(capacity>=c){
				capacity = capacity - c;
				map.put(key, 0.25);
			}else{
				map.put(key, map.get(key)+capacity);
				capacity = 0.0;
			}
		}
		if(capacity>0.0){
			fill(map,L+1,N,capacity/3.0);
			int p = (int)(Math.log(N)/Math.log(2)) + 1;
			fill(map,L+1,N+p,capacity/3.0);
			fill(map,L+1,N+p+1,capacity/3.0);
		}
	}
	public static double capacity(int B,int L,int N){
		HashMap<String, Double> tower = new HashMap<String, Double>();
		fill(tower,1,1,B*0.75);
		return tower.containsKey("L"+L+"N"+N) ? tower.get("L"+L+"N"+N) : 0.0;
	}

Why no body uses HashMap ??
I think it can solve this O(n).
here is my Code

class Tuple3 { 
		String v1;
		int v2,v3;
		public Tuple3(String v1,int v2, int v3){
			this.v1 = v1;
			this.v2 = v2;
			this.v3 = v3;
		}
	}
	
	class Tuple2 { 
		String v1;
		int v2;
		public Tuple2(String v1,int v2){
			this.v1 = v1;
			this.v2 = v2;
		}
	}
	
	public Tuple2[] convert(Tuple3[] arr){
		HashMap<Integer, ArrayList<Tuple2>> map = 
								new HashMap<Integer, ArrayList<Tuple2>>();
		for(Tuple3 t3 : arr){
			if(!map.containsKey(t3.v2))
				map.put(t3.v2, new ArrayList<Tuple2>());
			map.get(t3.v2).add(new Tuple2(t3.v1, t3.v2));

			if(!map.containsKey(t3.v3))
				map.put(t3.v3, new ArrayList<Tuple2>());
			map.get(t3.v3).add(new Tuple2(t3.v1, t3.v3));
		}
		Tuple2[] narr = new Tuple2[arr.length*2];
		int pos = 0;
		for(int k : map.keySet())
			for(Tuple2 t:map.get(k))
				narr[pos++] = t;
		return narr;
	}
	
	public void testConvert(){
		Tuple3[] arr = new Tuple3[]{new Tuple3("a", 1, 5),
							    new Tuple3("b", 2, 4),
							    new Tuple3("c", 7, 8)};
		Tuple2[] narr = convert(arr);
	}

Why no body uses HashMap ??
I think it can solve this O(n).
here is my Code

class Tuple3 { 
		String v1;
		int v2,v3;
		public Tuple3(String v1,int v2, int v3){
			this.v1 = v1;
			this.v2 = v2;
			this.v3 = v3;
		}
	}
	
	class Tuple2 { 
		String v1;
		int v2;
		public Tuple2(String v1,int v2){
			this.v1 = v1;
			this.v2 = v2;
		}
	}
	
	public Tuple2[] convert(Tuple3[] arr){
		HashMap<Integer, ArrayList<Tuple2>> map = 
								new HashMap<Integer, ArrayList<Tuple2>>();
		for(Tuple3 t3 : arr){
			if(!map.containsKey(t3.v2))
				map.put(t3.v2, new ArrayList<Tuple2>());
			map.get(t3.v2).add(new Tuple2(t3.v1, t3.v2));

			if(!map.containsKey(t3.v3))
				map.put(t3.v3, new ArrayList<Tuple2>());
			map.get(t3.v3).add(new Tuple2(t3.v1, t3.v3));
		}
		Tuple2[] narr = new Tuple2[arr.length*2];
		int pos = 0;
		for(int k : map.keySet())
			for(Tuple2 t:map.get(k))
				narr[pos++] = t;
		return narr;
	}
	
	public void testConvert(){
		Tuple3[] arr = new Tuple3[]{new Tuple3("a", 1, 5),
							    new Tuple3("b", 2, 4),
							    new Tuple3("c", 7, 8)};
		Tuple2[] narr = convert(arr);
	}

public static Byte[] hexToByteBuf(String hex){
		Byte[] buf = new Byte[hex.length()%2 == 0 ? hex.length()/2:(hex.length()/2)+1];
		for(int i = 0; i<hex.length(); i++){
			buf[i/2] = (i%2 == 0) ? 0 : (byte) (buf[i/2]<<4);
			char c = hex.charAt(i);
			if(c<=57)
				buf[i/2] = (byte) (buf[i/2] | c-48);// "0" : 48
			else
				buf[i/2] = (byte) (buf[i/2] | c-55);// "A" : 65
		}
		return buf;
	}