CareerCup

How does this approach sound like?
Assumptions:
- Meetings start at 8:00 AM and end at 6:00 pm (this can be changed to a 24 hour as well, but just for brevity).
- Meeting minimum time is 15 minutes, so that means each hour will have 4 divisions.
- 8 to 6 = 10 hours = 10 * 4 = 40 divisions total.

Now,
Assign each time slot a digit, alphabet, code, whatever... for now lets say a digit.

So if a meeting is scheduled from 10-10.30 am, so we'd add 9 and 10 into the HashSet.
(Logic: 8-8.15 = 1, 8.15 - 8.30 = 2, 8.30 - 8.45 = 3, ....... 10-10.15 and 10.15-10.30 = 9 and 10... and so on)

Now let's say someone tries to find a meeting from 10.15-10.45, we'll look for codes 10 and 11. The HashSet already has the entry 10, so that's a collision right there!

Time complexity to 'look up' = O(1), time complexity to add all the meetings from the arraylist = O(n).

How does this approach sound like?
Assumptions:
- Meetings start at 8:00 AM and end at 6:00 pm (this can be changed to a 24 hour as well, but just for brevity).
- Meeting minimum time is 15 minutes, so that means each hour will have 4 divisions.
- 8 to 6 = 10 hours = 10 * 4 = 40 divisions total.

Now,
Assign each time slot a digit, alphabet, code, whatever... for now lets say a digit.

So if a meeting is scheduled from 10-10.30 am, so we'd add 9 and 10 into the HashSet.
(Logic: 8-8.15 = 1, 8.15 - 8.30 = 2, 8.30 - 8.45 = 3, ....... 10-10.15 and 10.15-10.30 = 9 and 10... and so on)

Now let's say someone tries to find a meeting from 10.15-10.45, we'll look for codes 10 and 11. The HashSet already has the entry 10, so that's a collision right there!

Time complexity to 'look up' = O(1), time complexity to add all the meetings from the arraylist = O(n).

@Vandita.Chhabaria, Your solution is n^2, that's not very good for a larger data sets. Here's what you can change to make the solution better wrt to time complexity. I believe this can be done in O(n)

//Employee Class:
public class Employee{
	public String fName;
	public String movingFrom; //Building number;
	public String movingTo; //Building number;
	...
}

/* Here's how you'd add data to a HasMap:
	Map<String, String> map = new HashMap<>();
	//Concat strings for from and to, it'd look like this: '1,2', which means
	// the employee is moving from building 1 to building 2
	map.add(emp.fromBuilding +","+ emp.ToBuilding, emp.fName);
	.... //Repeat for all employees.

//Here's how you'd do the matchup
pubic ArrayList<String> matchUp(HashMap map)
{
	List<String> list = new ArrayList<>();

	Iterator it = mp.entrySet().iterator();
	while( it.hasNext() )
	{
		Map.Entry pair = (Map.Entry) it.next();
		String temp = getReversed(pair.getKey());
		if(map.containsKey(temp))
			list.add(pair.value() + ", " + map.get(temp));
	}
	return list;
}

private String getReversed(String s)
{
	String[] temp = s.split(",");
	return temp[1] + "," + temp[0];
}

Number 1 : 25, represented as [2] -> [5] -> null
Number 2: 5, represented as [5] -> null

Bogus solution could be to convert the linkedlist into strings, then parse it back into integers. I'm sure this isn't what they're looking for.

public int multiplyLLNumbers(LinkedList one, LinkedList 2)
{
	Node node = one.Head();
	String temp = "";
	while(onenode.next() != null)
	{
		temp += node.data.toString();
	}
	
	String temp2 = "";
	node = two.Head();
	while(two.next() != null)
	{
		temp2 += two.data.toString();
	}
	
	return (Integer.parseInt(temp1) * Integer.parseInt(temp2));
}

Go through all the nodes, check if left and right exist, further check if their values are either lesser or greater than the node. Call the function recursively. Here's a java solution:

public boolean isValidBT(Node node)
{
	if(node == null)
		return true;

	if(node.hasLeft() && !(node.left.data < node.data))
		return false;

	if(node.hasRight() && !(node.right.data > node.data))
		return false;

	if( !isValidBST(node.left) || !isValidBST(node.right) )
		return false;

	return true;

}

I believe a value to the 'supervisor' or 'senior' in the employee would solve this problem. An interface that would have a few methods to 'forwardCall(Employee.Supervisor emp)' would make things look better.

public class Employee implements Call{
Employee supervisor;
String fName;
String lName;
...
public Employee(String fName, String lName, Employee supervisor)
{ this.fName = fName; this.lName = lName;  this.supervisor = supervisor;}

public transferToSupervisor(Employee sup)
{
	//Code to transfer call
}

public interface Call{

public void answerCall();
...
public void transferToSupervisor(Employee supervisor);
}

Not sure about this answer, feedback appreciated.

I guess this question needs more clarification, some example would be good as to what is expected.

A HashMap of MaxHeaps.

Map<String, MaxHeap> map;

where, key = artist name, MaxHeap.getRoot() will give you the song name.

The nodes will be made up of a simple datastructure with a key-value pair:

class SongNode{
	int count;
	String songName;
	
	public String getRootName(){
		return songName()
	}
	...
	...

Somewhat on these lines it could be answered. Feedback appreciated. Thank you.

Description:
1. Find the indexes of all the 'letters' in the given string and only iterate over that, than the entire string, because u may have a string "557747373447abc4757838383", that'll save you added complexity.
2. Use 2 data structures, a Queue and a HashSet.
3. Queue will help you find more combinations, HashSet will help in finding if the combination has been reached before.
4. For each added element in Queue, remove it and make more combinations.
5. This solution also works for already uppercase string like "4AbD2f" as well as duplicates like "3bb"

public static void combinations()
	{
		String s = "000000abde0000";
		
		//Boundary check 1, checks for string length
		if(s.length() == 0)
		{
			System.out.println("String length too small");
			return;
		}
		
		//Boundary check 2, checks if there are more than 0 'characters'
		int count=0;
		//Maintain an arraylist of indexes for characters, so we do not iterate over digits
		//in cases like huge string with many digits and less characters
		List<Integer> indexes = new ArrayList<Integer>();
		for(int i = 0 ; i < s.length() ; i++)
		{
			if(Character.isLetter(s.charAt(i)))
			{
				count++;
				indexes.add(i);
			}
				
		}
		System.out.println(indexes);
		
		if(count == 0)
		{
			System.out.println("No Combinations can be made");
			return;
		}
			
		//Queue to scan elements over again
		Queue<String> q = new LinkedList<>();
		
		//Add the given string to hashset
		Set<String> comb = new HashSet<String>();
		comb.add(s);
		q.add(s);
		
		
		//Boundary check 3, checks if given string had any uppercases
		s = s.toLowerCase();
		if(!comb.contains(s))
		{
			comb.add(s);
			q.add(s);	//Any new combination must be added to the queue to check for more
		}
			
		String temp,lastGood;
		Character c;
		int iterCount = 0;
		
		while(!q.isEmpty())
		{
			//Start with the first combination in the queue
			temp = q.remove();
			for(int i : indexes)//iterate over indexes we found than the entire string
			{
				iterCount++;
				lastGood = temp;	//copy of the original string
				c = temp.charAt(i);
				if(Character.isLowerCase(c))
				{
					temp = temp.substring(0, i) + Character.toUpperCase(c)+ temp.substring(i+1);
				}
				else
				{
					temp = temp.substring(0, i) + Character.toLowerCase(c)+ temp.substring(i+1);
				}
				//If the change just made is unique, add to the Set and Queue
				if(!comb.contains(temp))
				{
					//System.out.println("Adding: " + temp + " to comb!"); //for debugging
					comb.add(temp);
					q.add(temp);
				}
				//restore lastGood and start over
				temp = lastGood;	
			}
		}
		
		if(comb.size() == (Math.pow(2, count)))
		{
			System.out.println("All("+Math.pow(2, count)+") combinations have been found, over "+ iterCount + " loops!");
			System.out.println(comb);
		}
		else
		{
			System.out.println("Something went wrong!");
			System.out.println(comb);
		}
			
	}

I'm not yet sure how it works complexity wise, but looks like it's somewhere between n^(n-1), please help out here if you have an answer. Thank you!

If I've understood the problem correctly, we must release Q prisoners in Q days, that means 1 prisoner a day (at a time) could be a constraint.

Given this, I believe this is a divide and conquer technique.

So if we have 100 prisoners and wish to release 4, then we release the 4th prisoner first, followed be half of 4, 2nd prisoner, followed by half of 2, 1st prisoner, then similar approach on the right sub array.

This maximizes the profit or should I say minimizes the loss.

They've asked for an algorithm, so I'm assuming coding isn't required. I'll mention the logic.

Assumptions:
1. Meeting times start from 9 AM through 5 PM = 8 hours.
2. Minimum meeting time = 30 minutes.
3. From above 2, every conference room will have 16 time slots. (You can lower the intervals to 15 or 10 as you like, figure out the total slots accordingly).
4. So if every conference room were to be an array of 16 elements, then each element represents 30 minutes.

Let us say we have 100 conference rooms, then if we would like to book a meeting for time slot 10.00 AM to 10.30 AM, then we only look for the 2nd element of the array (array starts from 0-15) for all conference rooms or until we find an empty slot.

This solution is O(n) in time.

Detailed understanding of how the arrays are structured as per time slots:

[	0	, 	1	,	2	,	3	,	....	]
[   9-9.30	,  9.30-10 ,10-10.30 , 10.30-11,	....	]

Here's my approach, I think we need some kind of a backtracking. Which is why I'm using recursion. I'm not very good at recursion, so please excuse me if the code isn't written optimally.

What we do is, we pass in the first index to the function Hop(), then we check if its zero, return false. If the number itself is the length of the array, return true. After the assertions, we simply grab the number at the index of the input array and make those many hops. If we get a false reply, we lower the index and continue. Its working for most samples provided in the above thread. Comments are welcome. Thanks!

private static boolean Hop(int value){
		if(value >= input.length)
			return true;
		int hopValue = input[value];
		
		if(hopValue == 0)
			return false;
		
		boolean waddup = Hop(hopValue + value);
		if(waddup == false && hopValue>1)
			waddup = Hop(--hopValue + value);
		return waddup;

I am not sure if this is right, but, can we convert the 2d matrix into a 1d array? Then it could be worked as follows:

for (i=1; 1dArray.Length(); i++)
if (a[i] < ( a[i-1] && a[i+1] && a[i-4] && a[i+4])  then we found our element.

We can also use the above logic to skip a few lines of code. I just think it would again be n^2 because converting an NxN (say 4x4) matrix into a 1d would make new N=NxN i.e. N^2 (4^2 = 16 elements in 1d Array).... lol I don't know what I'm doing here. Please help me out a bit.

Isn't the solution kinda simple?
Just go through the array and find where a[ i ]<a[ i+1 ]
Wherever the condition is satisfied, index = ( a.length - i ) + 1
Or am I missing the basic concept of rotating a sorted array? -_-

I like the first answer to simply swap the value. Alternately, if we aren't even allowed to use a second variable, and assuming the singly linked list contains only numbers as data, we can use the typical math operations to swap the values.
a=21, b=5
1. a=a+b (a becomes 26)
2. b=a-b (b becomes 21)
3. a=a-b (a becomes 5)