CareerCup

Heapify takes O(1) space complexity. This should work.

Yes that was the requirement in the movie as well.

The interviewer got this from the movie Labyrinth.

abishek, maybe I'm missing something or misunderstanding the question.
In the second output how can there be 5 total steps when the broken step is at 1?
Shouldn't the output be the total steps you can take before you reach the broken step? My impression was that you cannot go at or beyond the broken step.

I actually think it should be a min/max heap. After building the heap of a million stars, each time you insert at the root you'll need to remove the max element.

Yikes!
Alright here's another way of handling this problem.
Let's pretend there are 20 actual physical items left in stock. I'd report in the amazon UI that there are only 10 items left in stock. Once this count drops to zero, we'd have a backup of 10 more items left on shelf just to handle the scenarios where two customers have the same item in the same cart. This would mitigate the problem but not totally eliminate it. But something along these lines should be sufficient for most scenarios I believe.

bharat, what happens when time T expires?

Yeah I figured that it wasn't the type of answer the interviewer was looking for.

Okay so let's try to solve this another way.

So based upon this info then the item becomes unavailable only after a customer has clicked on the "Pay" button. Until then it must remain in both customers shopping carts. Once one of the customers clicks on the pay button, the item should be silently removed from the other customer's shopping cart with a message "Sorry this item is no longer available... more on the way" or something of that nature.

This assumes the list/array is sorted.

In a brick and mortar store if someone has the last item placed in their shopping cart the shelf will appear empty. I would follow the same model. If they decide to not purchase the item then it becomes available again.

I see a lot of brute force like methods. Although my answer is probably not what the interviewer is looking for it can be solved much simpler.

string sumBinary(string s1,string s2)
{
	string sum;
	int result = (std::stoull(s1.c_str(),NULL,2) + std::stoull(s2.c_str(),NULL,2));	 
	while(result != 0)
	{
		if(result & 0x1)
		{
			sum = "1" + sum; 
		}else
		{
		    sum = "0" + sum; 
		}

		result >>= 1;
	}
	 
	return sum;
}

Nice solution but I think this can be optimized further. I don't think you need a HashMap.

Use Dijjkstra's algorithm or an A* variant.

also need to add a check for NULL.

void wordsearch(string sWord,vector<string> v,int x,int y,vector<string> vCoord)
{ 
	if(y < v.size() && x < v[y].length())
	{
		if(sWord[vCoord.size()] == v[y][x])
		{
			stringstream ss;
			ss << v[y][x];
			ss << " (" << x << "," << y << ")"; 
			vCoord.push_back(ss.str());
		
			if(vCoord.size() == sWord.length())
			{
				for(int i=0;i<vCoord.size();i++)
					printf("%s ",vCoord[i].c_str());

				vCoord.clear();
			}
		}else
		{
			vCoord.clear();
		}

		wordsearch(sWord,v,x+1,y,vCoord);
		wordsearch(sWord,v,x,y+1,vCoord);
		wordsearch(sWord,v,x+1,y+1,vCoord);
	}
}

void additive(int n)
{
	stringstream ss;
	ss << n;
	string s = ss.str();

	int substrLen = 1;
	int index=0;
	while((substrLen * 3) <= s.length())
	{
		while(index < s.length())
		{
			string op1 = s.substr(index,substrLen); 
			string op2 = s.substr(index+op1.length(),substrLen);
			string op3 = s.substr(index+op1.length() + op2.length(),substrLen);
			if(stoi(op1) + stoi(op2) == stoi(op3))
				printf("\n%s + %s = %s",op1.c_str(),op2.c_str(),op3.c_str());

			index += substrLen*3;
		}

		index = 0;
		substrLen++;
	}
	  
}

bool wildmatch(string s,string sPattern)
{
	if(s.length() == 1 && sPattern.length() == 1 && s[0] == sPattern[0])
		return true;
 
	if(s.length() == 1 || sPattern.length() == 1)
		return false;
	 
	if((s[0] == sPattern[0]) || sPattern[0] == '?')
	{
		return wildmatch(s.substr(1),sPattern.substr(1));
	}
	else if(sPattern[0] == '*' && s[0] != sPattern[1])
	{
	 	return wildmatch(s.substr(1),sPattern);	
	}else if(sPattern[0] == '*' && s[0] == sPattern[1])
	{
		return wildmatch(s.substr(1),sPattern.substr(2));
	}

	return false;
}

Sweet!

bool check_bits(char byte)
{
   int count=0;
   while(byte > 0)
   {
	   if(byte & 0x1)
	   {
			count++;
	   }

	   byte >>= 1;
   }

   return (count==3);
}

epic fail.... :)

We can solve this using recursion.
Call "printTotalReportCount" which will call getDirectReportCount and recursively find all the managers subordinate total.

int getDirectReportCount(map<string,string> mEmployees,string employee,int count)
{
	map<string,string>::iterator iter = mEmployees.begin();

	while(iter != mEmployees.end())
	{
		if(iter->second == employee && iter->first != iter->second)
		{
			count++;
			count += getDirectReportCount(mEmployees,iter->first,0);	
		}	

		++iter;
	}

	return count;
}

void printTotalReportCount(map<string,string> mEmployees)
{
	map<string,string>::iterator iter = mEmployees.begin();

	while(iter != mEmployees.end())
	{
	    printf("\n%s - %d",iter->first.c_str(),getDirectReportCount(mEmployees,iter->first,0));
		iter++;
	}
}

We can solve this using recursion.
First call is "printTotalReportCount" which will tally every employee's total subordinate count.

int getDirectReportCount(map<string,string> mEmployees,string employee,int count)
{
	map<string,string>::iterator iter = mEmployees.begin();

	while(iter != mEmployees.end())
	{
		if(iter->second == employee && iter->first != iter->second)
		{
			count++;
			count += getDirectReportCount(mEmployees,iter->first,0);	
		}	

		++iter;
	}

	return count;
}

void printTotalReportCount(map<string,string> mEmployees)
{
	map<string,string>::iterator iter = mEmployees.begin();

	while(iter != mEmployees.end())
	{
	    printf("\n%s - %d",iter->first.c_str(),getDirectReportCount(mEmployees,iter->first,0));
		iter++;
	}
}

Actually just realized this wouldn't work if we have negative numbers...

But maybe the function can be modified to find the two numbers closest to zero and add them together.

This would be O(N)

int smallestSum(int arr[N])
{
	int min1 = arr[0];
	int min2 = arr[1];

	for(int i=2;i<N;i++)
	{

		if(arr[i] < min1)
		{
			if(min1 < min2)
			{
				min2 = min1;    	    
			}

			min1 = arr[i];
		}
		else if(arr[i] < min2)
		{
			if(min2 < min1)
			{
				min1 = min2;    	    
			}

			min2 = arr[i]; 		
		}

	}

	return (min1+min2);
}

Could we do a search for the two smallest numbers in the array and add them together?
Would this work?

This seems like a nice solution. But couldn't this be optimized further in that we only need step 5? Why do we need the rest of the steps?

Nice!

I gotta see what's going wrong with my algorithm.

I disagree...
If my algorithm is correct then
if N = 10 there should be 1 way.
if N = 11 there should be 13 ways.
if N = 12 there should be 3 ways.

Run your code when N equals these values.

The solution is:
1. Pick a position on the grid
2. Fill the grid with all the ways a queen can move,
3. Pick the next empty position
4. Repeat steps 2 and 3.

Once the grid is filled we see if we used N queens and increment the number of ways N queens can be positioned on the grid. We then clear the grid and repeat steps 1 - 4 again with the next position on the grid.

Sample:
N = 10
Output = 1

const int N = 10;
void fillQueenPositions(int row,int col,int (&grid)[N][N],int &count)
{
	if(count == N)
		return;

	if(row < 0 || col < 0)
		return;

	if(row >= N || col >= N)
		return;	
  
	//fill horizontal/vertical planes
	for(int i = row+1;i<N; i++)
	{
		grid[i][col] = 2;
	}

	for(int i = row-1;i>=0; i--)
	{
		grid[i][col] = 2;
	}

	for(int i = col+1;i<N; i++)
	{
		grid[row][i] = 2;
	}

	for(int i = col-1;i>=0; i--)
	{
		grid[row][i] = 2;
	}

	//fill diagonals
	int r=row+1,c=col+1;
	while(r<N && c<N)
	{	
		grid[r][c] = 2;
		r++;
		c++;
	}

	r=row-1,c=col-1;
	while(r>=0 && c>=0)
	{	
		grid[r][c] = 2;
		r--;
		c--;
	}

 
	r=row-1,c=col+1;
	while(r>=0 && c<N)
	{	
		grid[r][c] = 2;
		r--;
		c++;
	}

	r=row+1,c=col-1;
	while(r<N && c>=0)
	{	
		grid[r][c] = 2;
		r++;
		c--;
	}

	//fill knight move positions
	if(row+2 < N && col+1<N)
	{
		grid[row+2][col+1] = 2;
	}

	if(row+2 < N && col-1>=0)
	{
		grid[row+2][col-1] = 2;
	}

	if(row+1 < N && col+2 < N)
	{
		grid[row+1][col+2] = 2;
	} 

	if(row+1 < N && col-2 >=0)
	{
		grid[row+1][col-2] = 2;
	} 

	if(row-2 >=0 && col-1>=0)
	{
		grid[row-2][col-1] = 2;
	}

	if(row-2 >=0 && col+1<N)
	{
		grid[row-2][col+1] = 2;
	}

	if(row-1 >=0 && col-2>=0)
	{
		grid[row-1][col-2] = 2;
	}
	
    if(row-1 >=0 && col+2<N)
	{
		grid[row-1][col+2] = 2;
	}

	grid[row][col] = 1;
	count++;
	
	bool bEmptySpotFound = false;
 
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			if(grid[j][i] == 0)
			{
				row = j;
				col = i;	
				bEmptySpotFound = true;
				break;
			}
		}

		if(bEmptySpotFound)
			break;
	}

	if(bEmptySpotFound)
	{
		fillQueenPositions(row,col,grid,count);
	}
	 
}
 
int countQueenPositions()
{
	int count = 0;
	int grid[N][N];

	for(int r=0;r<N;r++)
	{
		for(int c=0;c<N;c++)
		{
			int nQueens = 0;
			fillQueenPositions(r,c,grid,nQueens);

			if(nQueens == N)
			{
				count++;
			}

			//reset the grid
			for(int i=0;i<N;i++)
			{
				for(int j=0;j<N;j++)
					grid[i][j] = 0;
			}
		}
	}
	
	return count;
}

This code fails the following three test cases:

s = "aa"
p ="a*"

s = "aa"
p = ".*"

s = "ab";
p = ".*";

This doesn't work. Most of the test cases fail.

bool isMatch(const char *s,const char *p)
{ 
	if(s == NULL || p == NULL)
		return false;
 
	int index=0;
	int patternIndex=0;
	char lastChar;
	for(patternIndex=0;patternIndex<strlen(p) && index<strlen(s);patternIndex++)
	{		
		if(p[patternIndex] == s[index])
		{
			lastChar = p[patternIndex];
			index++;
			continue;
		}

		if(p[patternIndex] == '*')
		{			
			while(index<strlen(s))
			{
				if(s[index] != lastChar)
				{
					break;
				}

				index++;
			}
		}
		else if(p[patternIndex] == '.')
		{
			lastChar = s[index];
			index++;
		}else
		{	 	
			lastChar = p[patternIndex];
		}
	}

	return (patternIndex == strlen(p) && index == strlen(s));
}

EXACTLY... this is what I was confused about. When I ran the test through hacker rank for sample case #1 it came back as failed until I hard coded "nothing".

Also agreed with your analysis of the second example. The answer should be a not b.

I think the engineers at Fuze that setup this test made some mistakes.
In the end I got screwed.

I believe with a palidrome there can only be one (or zero) characters of an odd count in the string. The rest of the characters counted in the string have to be even.

bool canBePalidrome(string s)
{
	map<char,int> mCount;

	for(int i=0;i<s.length();i++)
	{
		mCount[s[i]]++;
	}
	
	map<char,int>::iterator iter = mCount.begin();
	bool bOddFound = false;

	while(iter != mCount.end())
	{
		if(iter->second % 2 != 0)
		{
			if(bOddFound)
				return false;

			bOddFound = true;
		}

		iter++;
	}

	return true;
}

void getCommon(char *s1,char *s2,char *sCommon)
{		
	for(int i=0;i<strlen(s1);i++)
	{
		for(int j=0;j<strlen(s2);j++)
		{
			if(s1[i] == s2[j])
			{
				bool bFound = false;
				for(int k=0; k<strlen(sCommon);k++)
				{
					if(s1[i] == sCommon[k])
					{
						bFound = true;
						break;
					}
				}

				if(!bFound)
				{
					sCommon = strcat(sCommon,&s1[i]);
				}

				break;
			}
		}
	}	 
}

This is wrong. You are adding 1+2+3+4+5. The answer is supposed to be
123 + 45

void printSum(string s)
{
	string sNum = "";
	int sum= 0;
	vector<int> v;

	for(int i=0;i<s.length();i++)
	{
		if(isdigit(s[i]))
		{
			sNum += s[i];
		}else if(sNum.length() > 0)
		{
			sum += atoi(sNum.c_str());
			sNum = "";
		}
	}

	if(sNum.length() > 0)
		sum += atoi(sNum.c_str());

	printf("\nsum = %d",sum);
}

Almost... but it fails on this array

{6,7,6,7,6,7,6,7,6,5}

There is nothing in the question that indicates the insertion complexity... only search complexity.

save the edges of the array and insert the entire array into a min-max heap.
findmin and findmax takes constant time. Check to make sure that the edges are not equal to what is returned by the search functions.

int findNextSparse(int n)
{
	bool bOne = false;
	int current = n;
	bool bFound = false;

	while(!bFound)
	{
		current = ++n;

		while(current != 0)
		{
			if(current & 0x1 == 1)
			{
				if(bOne)
				{
					bFound = false;
					break;
				}

				bOne = true;
			}else
			{
				bOne = false;
			}

			current = current >> 1;
		}

		if(current == 0)			
			bFound = true;	 
	}
	
	return n;
}

Perhaps you can use a binary search tree and as you are doing an in order tree traversal push all the numbers into a queue. The number contained in the queue is the largest number.

Was the merged array supposed to maintain all values in sorted order?

This is a horrible interview question.
evaluate what exactly? There is nothing to evaluate.
And if the example is what was given by the interviewer then the question itself has flaws.

The example implies that W = 6
ONE+TWO = THREE
How can ('O' = 2) + ('T' = 4) = 'T'? In this case 2+4 = 6 which would be 'W'

How can
FOUR +FOUR = EIGHT?

Again you have ('O' = 2) + ('O' = 2) = 4 which equals to 'T' and not 'I' or 'G'

Maybe each row in the hash table should point to the same list in memory (small, medium, large compartments) This will allow for all tokens to be unique.

Actually now that I'm thinking about it, this probably won't work because each token for each passenger is unique. a collision means two passengers have the same token.

This sounds like a hashtable problem with multiple buckets that handle collisions. However, the hashtable will need to be modified. The unique token is the value generated by the hash function.

With the exception that there will only be three buckets per hashtable row (representing small, medium, large compartments).

When the hash token is generated you can look cycle through the three buckets in the hash table to either insert into an empty space or do a swap.

This sounds like a graph traversal problem using BFS.

This looks like O(nlogn)