CareerCup

if modifying is not an option, use stack

rather than keeping a new array, use the same array and use appropriate swapping...so Time = O(N) and space = O(1)

did u ask how the words in a dictionary are stored ?

not using pointer voodoo, cant we just swap the element values ?

u cant / shouldnt calculate distances between all places and the centre. have to be smart in selecting points to calculate the distances.
Precompute all points to a red black tree and then use that

Each node could probably maintain number of children in left and right. Choosing right/left can be a function of these values.
Also proceeding to the next level can also be a function of the depth of the tree.

prolly implementation of a hashmap is wat the interviewer was getting at acc to the operations insert and get...

public class sortInPlace {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[] = {1,3,5,6,2,4,7};
		sortArray(arr);
	}
	
	public static void sortArray(int []a)
	{
		int endOfFirstArray = 0,prevNum = -1;
		if(a.length < 2)
		{
			return ;
		}
		
		if(a.length == 2)
		{
			if ( a[0] > a[1]) {
				int temp = a[1];
				a[1] = a[0];
				a[0] = temp;
			}
		}
		prevNum = 0;
		for (int i = 1; i < a.length ; i++ )
		{
			if ( a[prevNum] > a[i])
			{
				break;
			}
			prevNum++;
		}
		
		int ptr2 = a.length -1 ,ptr1 = prevNum;
		for (; ptr2 > ptr1 ; )
		{
			if (a[ptr2] > a[ptr1])
			{
				ptr2--;
			}
			else
			{
				int temp = a[ptr2];
				a[ptr2] = a[ptr1];
				a[ptr1] = temp;
				int tempPtr2 = ptr2;
				for (int j = tempPtr2 -1 ; j >=0 ; j--)
				{
					if (a[tempPtr2] < a[j] )
					{
						temp = a[tempPtr2];
						a[tempPtr2] = a[j];
						a[j] = temp;
					}
					tempPtr2--;
				}
			}
		}
		
		for (int i = 0 ; i < a.length ; i++)
		{
			System.out.println (a[i]);
		}				
	}

}

divide by 8 ..store in bytes_copied
mod by 8 ...store in leftover_bits

perform normal memcpy using bytes at dest_address

new_dest_address = dest_address + bytes_copied ;
new_src_Address = src_address + bytes_copied ;
uint8 mask = (1 << (leftover_bits + 1) - 1;
uint8 maskComplement = ~(mask);

new_dest_address = (*new_src_address & mask ) | (*new_dest_address & maskComplement);

from point of view of generalising it wudnt work well...i am sure the next q would be to generalize it for more steps ;)

can go the binary way....start with the number 7, = 2^3 - 1


go on subtracting 1, and count the position of 1's in the binary number ...map to digits and u haev the set.

nope...thats not the way to do it...........for more ppl this doesnt scale well.
we have to do event based programming here.

Have a priority Q.
There are 3 types of events, person coming ,person leaving and the moment we need to examine.
push all these into a priority Q sorted according to time
remove each element until you get to the moment you want a count of.

could you give some explanation for "upper half of B is larger than lower half of B and lower half of A, thus upper half of B
should be larger than (m+n)/2 elements, "

probably with an example..thanks a lot

we can map each alphabet to a coordinate.....create a list of coordinates and then apply djikstra to get to the next alphabet.

why cant we just reuse normal sorting and overload the comparator to compare according to the new dictionary ??

yup...dont think it needs recursion or dive and conquer at all !!

i think what the interviewer was looking for is an implementation of hashmap and not just use the hashmap builtin solution.

the hashmap Collection comes with a lot of other algorithms and thus a lot of other code. we just need the basic implementation here

hashmap is the way to go here.... the underlying implementation of hashmap could be an array.

for add:
We hash the value to a number between [0..N], and add it at that position in the array. We need to describe collision management techniques.
if ur size increases than N, you will be reshashing the entire DS into

for delete:
same as above, rehash if size drops to quarter the capacity.

get :
is almost naturally constant for hash

getRandom :
choose a key randomly between 0 and currentcapacity. if the key has some value then return it, else hash again. you could choose to perform some optimization here w.r.t the currentSize on the number of retries.

drdobbs.com/database/topological-sorting/184410262

taking care of cycles

create a directed graph and then do topological sort

if it cant start/end at the root, does the path need to go through root ?

use suffix trees and then do dfs till u get third unique character ?

sort on empid key and compare

1st error is compile time and the other is runtime ?

how do u convert to a string ..prolly using "/" and "%"...so not sure if this is the way

I think here if u use bit operations , it will be faster than hash. if you know the max number in the list, we can use set and test methods. The operation will be way faster than hash and be O(n + m).

What say?

List <List<Integer> getCombinations (int num)
{
List <List<Integer>> allCombinations = new ArrayList<Integer>();
int val = num;
int i = 1;
while (val > 0)
{
List<Integers> temp1 = new ArrayList<Integer>();
temp1.add (i++);
List<List<Integers> tempList = getCombinations (val --);
int j = 0;
for (List<Integer> subList : tempList)
{
temp1.addAll(subList);
}
allCombinations.add(temp1);
}

return allCombinations;

}
}

store all words in hashmap with keys as their convertonumber values and multiple values for each key.
use ur number to index the values

use djikstra with path weight 1

A normal counter saved as a linked list when it hits max?

start backwards, shift all characters by newword - oldword, replace word when found

the time complexity is ok.
however keep it generalized for n...cant keep on adding for loops everytime n increases

cud u post the call to this method

if its:
test= "abcbba";
longestpalindrome(test, 0, test.length() - 1), it fails