CareerCup

It is easy to think it is a largest number problem but it is not. For eg : List(9,6,3,0). largest number is 9630 which is divisible by 3. Like wise 3069 is divisible by 3. It is about taking a set of numbers and creating a subset which is divisible by 3. It is a subset sum problem and the subset sum should be divisible by 3.

Search for K Nearest Neighbors Algorithm for the best answer. However since this was asked in an interview looks like the below approach would work. You have N Cordinates of Taxis and you have a Point P(x,y) which is your location. Using the nearest point algorithm find the nearest point to P. This gives you a cab which is closest to You. Now you delete this cab and find another cab closest to you. Do this 3 more times and you get the closest 5 cabs to you.

I upvoted HJ but it wont appear as they run in isolation. One will throw a Segmentation fault :P

This is not really the question. I suspect the interviewee got confused. The question is more like a frog can jump 1stone or 2 stones at a time. can he get to the end, if yes print all possible paths.

It is a DP problem. Sum the entire array and divide by 2. If the sum is even than use the subset sum problem to search for sum/2. If the sum is odd no solution exists.

You need a windowing approach to solve this problem. Actually the use case has been picked straight from Apache Spark which does many such operations. For the sake of this question you need to create a Min Heap for each product id. The timestamp decides which element is the root. Whenever you do a read or insert operation you delete elements from the heap till the only elements that are left are less than a month old and then you do the insert or read operation.

23 .. it is prime ;)

I don't get the confusion ?? Total cost of joining is L1 + 2*(L2+L3+L4...) + Ln. So you actually need to find the maximum and 2nd max make them the end of the rope and just join others. In my example I assumed L1,Ln are max. This will be the minimum cost.

I am sure you are not looking for the answer. Simple answer would be to use a Regex or split based on . and compare each number.

By forcing you not to use High=N I think he is forcing you to count sort or bin sort.

It is a K-way merge.

1. Use Java Serialization on the tree & tree nodes and then deserialize this tree.
2. Write the pre/post traversal of the trees to the disk as text and recreate the tree.

You can use Reflection. You can also use instanceof.

Create a new bit vector with same length. Set bits from start to end point as opposites to the main vector and do an AND for these two. Use the results as the toggled vector

1. Write multi threaded code which simulates emails from multiple hosts.
2. Simulate other factors like new users joining/ adminstrative tasks/emails/spams.
3. Since he talks about distribution, test node failures.
4. Test replication of storage.
5. Test storage of attachments.
6. Test across data centres.
7. Test with timezones. Various timezones have various loads at different times.
8. Test dispatch of advertisements.

IPV6 doesn't have a Header which reduces packet size.
Reduces the number of NAT's required.

Sorry abt this. bad post.

Fails for a simple case {1,5,100},{1,45,75},{1,100,200}

Fails for a simple case {1,5,100},{1,45,75},{1,100,200}

1. Put them in a HashMap
2. Do a sort : remove adjacent.
3. Do a Bin sort

The answer is a LinkedHashMap which maintains the order in which elements are inserted. Regarding Random is easy : Generate a random number between 0 and Size and do a get(randomnumber)

Use Multimap. Use the sorted value of a string as Key.

So for tac. The key will be act.
Also for atc. The key will be act.

If it is a doubly link list it is trivial. Start one node from the front and the second node from the back. Time O(n) space O(1)

While almost all the answers are good the objective of such a question cannot be the solution. If I was the interviewer I would like to see how better corner cases are held. Almost all the answers above will fail in some cases.

Can you please elaborate

Generate Fibonacci numbers iteratively. Select the 5000th number.

You need to provide more information on this :-)

In place merge sort might be the answer. In reality In place merge sort is hard to get right the easier solution is Quicksort.

If you want to search on any of the categories like ItemNo or Authour or title etc you would need multiple maps.

1. You can create object which encapsulates everything.
2. Create multiple maps with Keys like(Title/Author/Product No) and value is a pointer to the Object.

You need not store the whole objects in the map.

Create a BST with words from the Files. Each Node in the tree will have below structure

Node{
String word;
String[] fileName;
int count
int[] line
}

For each word increment the count and insert the File name and line# in node structure

Once you are done creating the tree. Remove all Nodes that have count as 1.

Since the Files are already sorted. All you have to do is a external merge till you get 1 million elements. You don't need any more items from the Files.

Do you even need a Data structure for this ? The question says that you want to find the timestamp for which the traffic was maximum. Just keep a max variable and keep on updating it. Whenever max gets updated store the timestamp in a variable.

Consider what your operations are. If you need a multi threaded application go for two CPU's. If you are more into single threaded computations go for single processor.

Overrride the HashMap class. Instead of one HashMap have two HashMaps to store the data. Override the get Method in your classs and check the type of Key passed to it by typecasting and then decide on which HashMap you want to run the GET Operation.

You can design the system in 2 ways :

1. Implement the virtual memory yourself and use File IO operations if and when you need more memory than existing memory. You need to swap some of your data to a File to create space for new Objects.

2. You try to clean memory just like a garbage collector does and remove unwanted objects from time to time. This is inferior to 1 and you run the risk of your program crashing because of lack of memory.

You can use a combination of 1 & 2.

If you are in the middle of the line this is probably going to be the worst solution.

No, issues :-)

@JZ : this is incorrect.. search CAT in this matrix with your Algo.

B,C,D,Z
E,A,F,G
J,K,L,T

CAT doesn't exist in this matrix but your Algo will return true.

This is Brute Force, how can you optimize ?

Interesting.. but is it correct ? consider searching CAT in the below matrix

ACA
AAA
ATD

How will you Hash A ?

@Abak : Good observation. The answer should be 1.

Sure, let me post the code for you today sometime.

@Anon : You could use DFS dear friend, point I am making is don't optimize in DP but get rid of the 1's that will also solve the problem.

I have a variation of the program already written.
Run it.
Here F = 1, means dead end path.
This is recursive convert to DP.

public class printPossiblePathsInMatrix {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		char[][] arr = new char[][]{
				{'A','B','F'},
				{'C','D','F'},
				{'E','G','H'}
		};
		possiblePath("", arr, 0, 0);
	}
	
	private static void possiblePath(String str, char[][] a, int r, int c)
	{

		if(r > 2 || c > 2)
			return;
		
		if(r==2 && c==2){
			str+= a[r][c];
			System.out.println("---" + str);
			return;
		}
		
		if(c+1 < 3)
		if(a[r][c+1] != 'F'){
			String s1 = str + a[r][c];
			possiblePath(s1, a, r, c+1);
		}
		
		if(r+1 < 3)
		if(a[r+1][c] != 'F'){
			String s2 = str + a[r][c];
			possiblePath(s2, a, r+1, c);
		}
		
		if( r+1 < 3 && c+1 < 3)
		if(a[r+1][c+1] != 'F'){
			String s3 = str + a[r][c];
			possiblePath(s3, a, r+1, c+1);
		}
		
	}
}

This is a DP problem. At each node you can think of path covered so far and the optimal solution to reach the end from here. Without recursion also gives a hint that DFS is not the answer. Look for min cost path problem in DP section at geeksforgeeks for a variation to this problem.

This is an implementation of the Push/Pull Model. The first time you go online you pull the data of your online friends, there after you push your name into the Active Maps of all the Users. When thier status changes they push their status to all the people in the Map. Read Observer/Observable design pattern for this.

Use two heaps a MAX Heap and a MIN Heap. This lets us decide in O(1) time to decide in which heap to enter the new number. If the heaps fall out of order, rebalance them by moving one item in LogN.

public class PermutationTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) 
	{
		// TODO Auto-generated method stub
		String permString = "ABCDE";
		Set<String> se = permutations(permString);
		Iterator<String> itr = se.iterator();
		System.out.println("Total size of Permutations = " + se.size());
		while(itr.hasNext()){
			System.out.println("--" + itr.next());
		}
	}
	
	public static Set<String> permutations(String str)
	{
		Set<String> se = new HashSet<String>();
		permute(str.toCharArray(),"",se);
		return se;
	}
	
	public static void permute(char[] rem, String str, Set<String> se)
	{
		if(rem.length == 1){
			String str2 = str + rem[0];
			se.add(str2);
			return;
		}
		for(int i = 0 ; i < rem.length ; i++)
		{
			char[] rem2 = getRemainingArray(rem,i);
			String s = "" + str + rem[i];
			permute(rem2, s, se);
		}
	}

	private static char[] getRemainingArray(char[] rem, int i)
	{
		char[] rem2 = new char[rem.length - 1];
		int k = 0;
		for(int j = 0 ; j < rem.length ; j++)
		{
			if(i!=j){
				rem2[k] = rem[j];k++;
			}
		}
		return rem2;
	}
	
	
}

Very strange question. What's the big deal. There has to be atleast one word and the sentence should start from it. Start a linear traversal from beginning and keep on adding characters, for every character added see if the word formed so far is a well formed word. If NO add more characters. If Yes, print this valid word and repeat the process for the remaining sentence.

@Vandy : this is a good answer.