CareerCup

@zapurza: I think in that case also it will fail for this list

0->1->2->0->1->2

Do a level order traversal and add the numbers from top to bottom (If a node occurs multiple times, then keep the maximum number there).

The max number of a leaf node in this process will be the maximum sum.

1st itr: 3 
2nd itr: 12 ->7 
3rd itr:13 -> 20 {20, 15} -> 9 
4th itr: 17 -> 25 {25, 20} -> 28 {28, 17}-> 11.

Maximum number is 28.

Very nice.

But how to resolve the dependency and deadlock situation? Suppose, machine m1 acquires lock for file1 and keeps the lock for very long file due to processing. So, all the requests to access file1 will be stalled. Now, if machine m2 wants to do something sequential (i.e. read file1, file2, file3 one by one), it will be blocked for that time (Asynchronous works will be done easily. But sequential tasks will be stalled).

You have to choose larger set in order to reproduce it. Take this example,
1,1,2,2,2,2,2,3,4,5,6,7,8,9,10,11

And, it returns false.

Why can't we just add length add the beginning of each string. Then all these we don't have to find the delimiter.

Suppose, first string is of 10 characters (fellowship), second is of 5 characters(sandy), third is of 7(brownie) characters. So, we will serialize the objects like this 10-fellowship5-sandy7-brownie. Here '-' character will serve as delimiter as the we need to distinguish between characters and length numbers.

While deserializing, we know that the length of the first string (characters before '-'), then read that many numbers of characters to retrieve the string. Repeat this process until we read the entire serialized string.

One basic idea while parsing is that "all the elements in the left of current position has been validated properly." We are using the stack to check the validity of the given string. So, all the elements at same level which are present in the stack are already been validated.

Basic trim functions:

char* trim(char *str) {
	while (*str == ' ')
		str++;
	return str;
}

char* trimRear(char *str) {
	int len = str ? strlen(str) : 0;
	for (int i = len-1; i >= 0; i--) {
		if(str[i] == ' ')
			str[i] = '\0';
		else break;
	}
	return str;
}

Helper functions:

// Check whether there is only one ":" mark in the string or not.
int onlyTwoTokens(string str) {
	size_t firstPos = str.find_first_of(":");
	if (firstPos == string::npos)
		return -1;

	size_t rearPos = str.find_last_of(":");
	if (firstPos == rearPos)
		return 2;
	return -1;
}

// Count total number of tokens in the given string
int countTokens(string str, char token) {
    size_t pos = str.find(token);
    int count = 0;
    
    while (pos != string::npos) {
        count ++;
        pos = str.find(token, pos+1);
    }
    
    return count;
}

One basic notion, we should develop while solving this is that "a:b" is an object or entity. Here we use '-' marker to denote such objects.

bool checkObjects(stack<char> &s) {
	if(s.empty())
		return false;
    
    bool result = false;
	string str;
	while (!s.empty() && !result) {
		char ch = s.top();
		s.pop();
        
		if (ch == ',') {	// we found a sibling in same level
			if (onlyTwoTokens(str) != 2)
				return false;
            result = true;  // All the elements are present in the same level and already been validated.
                            // We need not to push one ',' and a '-' here. Since the previous element will take care of it.
		}
		else if (ch == '{'){	// It is the first object in that level, we must have one ":"
			if (onlyTwoTokens(str) != 2)
				return false;
			s.push('{');
			s.push('-');	// This is our object marker, one object has been found at the very beginning
            result = true;
		}

		str += ch;
	}
	return result;
}

bool checkForSiblings(stack<char> &s) {
	if(s.empty())
		return false;

	string str;
    bool result = false;
	while (!s.empty() && !result) {
		char ch = s.top();
		s.pop();

        if (ch == '{') {
            // Total number of '-' should be once greater than ','
            int countSeparator = countTokens(str, ',');
            int countObjectMarkers = countTokens(str, '-');
            if (countObjectMarkers == countSeparator && countObjectMarkers == 0)
                result = true;  // Empty object
            else if (countObjectMarkers == countSeparator+1)
                result = true;  // All the object markers are separated by separators.
            break;
        }
        else if (ch == ',') {
            if (onlyTwoTokens(str) != 2)
				return false;
            
            str.clear();    // We need to flush it, as the separator and the object are matched. Rest be handled by previous object
            continue;
        }
		str += ch;
	}

	return result;
}

Basic JSON validator code with basic error handling.

bool jsonValidator(char *str)
{
	// Trim all the white spaces.
	str = trim(str);
	str = trimRear(str);

	int len = 0;
	// we need at most 2 characters to start with
	if (str == NULL || (len = strlen(str)) < 2)
		return false;

	stack<char> s;
	for (int i = 0; i < len; i++) {
		switch(str[i]) {
			case ' ': // skip whitespaces
				if(s.empty())
					return false;
				break;
                
			case ',': // handle ','
				if (!checkObjects(s))
					return false;
				s.push(',');
				break;
                
			case '{':
                if (!s.empty() && s.top() == '{')   // Handle strings like this "{{"
                    return false;
				s.push('{'); 
				break;	// handle open braces
                
			case '}':
                // It's a candiate for whole object at the same level
				if(!checkForSiblings(s))
					return false;
                s.push('-');    // Denote as whole object
				break;	// handle close braces
                
			default: 
				s.push(str[i]); 
				break;
		}
	}

	// at the end all the elements of stack should be popped
	return (s.size() == 1 && s.top() == '-');
}

Complex solution, but your code returns false for {}

1. Your solution does not handle the case of empty JSON.
{} is a valid json string.

2. You should check whether stack become empty while popping or not in validateComma & validateBraces functions.

Suppose you have an array like this,
1,1,2,2,2,2,2,3,4,5,6,7,8,9,10,11


Then your element is [2]. Break the array in 8 ranges.
range 1 : index 0 to index 3
range 2 : index 2 to index 5
range 3 : index 4 to index 7
range 4 : index 6 to index 9
range 5 : index 8 to index 11
range 6 : index 10 to index 13
range 7 : index 12 to index 15 (last element)

So, if you compare the elements in the in those index, then the element [2] lies in range 2.

For first, it's the middle element.

For second, it's a bit trickier. Suppose we have splitted the array into 8 portion, the the array will looks like this,

(start element)1----2----3----4----5----6----7----8(end element)

If any of the alternate position's element matches with each other then it definitely has that element. We need atmost six comparison to determine the exact element.
[1---- to ----3] or,
[2------4] or,
[3------5] or
[4------6] or
[5------7] or
Since the array must have the element, then it must be any element from [6 --- to --- 8] range.

Suppose your input array contains repetitive elements from [3n/8] to [5n/8+1] then your solution will return false.

This Person class can be extended to waiters, managers, guests etc.

Class Person {
	String firstName;
	String lastName;
	String contactNo;
}

Class Guest extends Person {
	String email;
	String address;

	// All the setter and getter methods
}

This class Table is required as there are various types of tables and with different seats. Also, the occupancy time of each table differs accordingly.

Class Table {
	long tableID;		// table identifier
	int seatingCapacity;	// Max number of guests it can accomodate
	int category;		// It's not really important but various categories like family, dinner, couple is required
	bool inOccupied;	// whether this table is currently occupied or not.
	bool occupiedHalfHours[48];	
	// this variable is trickier. We divided our 24 hours into 48 halves. Whenever we book 
	// this table set true is occupied for that specified half hour. This variable is mainly used 
	// to checking availability of this table during any specific time.

	public Table() { // initialize all the variables }
	public bool isReserved (long start, long end) { // checks whether this table is reserved for this time window or not}
	public bool isFitToRequest(int totalNum, long start, long end) {}
}

This is the booking or reservation class and will be assigned to the requester.

class Reservation {
	long bookingID;		// reservation ID
	long startTime;			// when starts
	long endTime;			// when ends
	Guest askedPerson;	// who asks for this reservation
	int totalPersonCount;	// total member count

	// This details below will be filled by the Restaurant system
	bool isCancelled;
	bool isWaiting;
	ArrayList<Table> allocatedTables;	// which tables has been allocated to this reservation
	// Main reason for this is that, totalPersonCount may be greater than the seats available for
	// a particular table, in that case we need to allocate another table for same booking.
	
	private bool canFitIntoTable(Table t) {}
	public void notifyUserWithDetails()	// User will be informed
	// This function will be triggered if booking is successful, can not be made or in waiting.
}

Class ReservationSystem {
	int numberOfTables;	// Total numbers of table can be accomodate in this restaurant
	long openingTime;		// Restaurant opening time
	long closeTime;		// Closing time, all the requests should be performed in between these two times
	ArrayList<Table> tables;	// Holds all the table information, used to query the table inforamtion
	ArrayList<Reservation> waitingList;	// All the reservations currently in waiting state
	HashMap<Integer, Reservation> reservationMap;	// searches any reservation query with booking/reservation ID.

	// This variable is used to reduce the time for the query like this : "Give all the free tables"
	// at any specific time. We can extract the same information using 'tables' variable
	// as it holds the free slot times also. But in some heavy traffic restaurant, which accepts
	// pre-booking, looping all the tables and extracting the availability will be a tedious one. 
	// So, again 
	HashSet<Tables> freeSlots[48];

	public ReservationSystem() {}
	public boolean cancelReservation(long ID);
	public void contactCustomer(Reservation rID);
	public boolean closeReservation(long ID);
	public Reservation searchReservation(long ID);
	public int checkAvailablity(int noOfperson, long start, long end, ArrayList<Table> tables, ArrayList<long> alternateTimes);
}

Class Restaurant {
int restaurantID;        // restaurant ID
long timeOfStarting;  // opening time
long timeOfClosing;  // closing time
int totalSeats;    // total seats that this reservation has
ReservationSystem system;
void iniitalizeReservationSystem(long openTime, long closingTime, int seats);

// All the basic query interface to the reservation system
}

I think, we can boil down this question to a simpler one.

Basic concept is that we need to find two extreme nodes (one furthest left, one furthest right) in between all the 'k' given nodes. So, any nodes which lie in between these nodes will be under those two's LCA i.e. divergent point of the paths connecting root and these two nodes will be the LCA of all 'k' nodes.

So, the algo is:

1. Do the inorder traversal of the tree.
2. Find two nodes, one extreme left of the tree and one extreme right.
3. Run normal LCA on that findLCA(node *root, node *left, node *right)

Its not about finding LCA of two elements but LCA of k elements!

Great. One reservation system which accepts several reservations initiated by respective person.

In addition to this, one basic thing that ReservationSystem class should have is 'TotalSeatCount'. If a requestor asks for a reservation for few people, the system will tell the requestor to wait accordingly. Also, there should be one method 'completeReservation()' which will be called once the user leaves the restaurant and 'notifyUser()' method will be auto-triggered to notify the next user in the waiting queue. Now, waiting queue logic can be developed independently.

What is the question! Should we design hash table like data structure?

Inorder to serialize these kind of strings we need to place the string length along with delimiter. let's take our delimiter as ";<num>;" So, String "Hello" will be serialized as ";5;Hello"

Since, we know our delimiter string format, we can always deserialize it with ease.

@tdot M is not basically K*N. Because min-heap height will never be more than K. So its basically NLog(K), where N is the maximum length of K arrays.

Question should be "large element should appear after lower"

This solution is not feasible (a bit slow) if we need to find multiple words from the dictionary. This will iterate the dictionary again and again.

One question : If all the characters in the pattern are distinct, then whats the result it should return 1, I guess..

You can simple use module operator and division to find out the remainder.

They counts the number of vowels in a word.

leap year calculation is not correct.

if ((year%400 == 0) || (year%4 == 0 && year%100 != 0))
  months[1] = 29;

We can also optimize the time complexity to O(n) if we introduce a new field 'depth' to the node struct.

struct node {
  node *left, *right;
  int data, depth;
}node ;

We use the queue to traverse the tree in level order. Then update the maximum level of depth & child's depth on each node discover.

It can be done inplace. In this case you have to traverse each word twice.
1) Find a word, reverse it.
2) skip all the spaces or keep it as those are.

Recursion may be avoided in order to make it memory efficient.

Earlier one is O(n) time & space solution.
We can further optimize the space, if we use the existing array for holding the index of the max elements. Then return random index from them!

We can reduce the space complexity in O(1)..

int getIndexOfMaxRandomly(int arr[], int size)
{
  if (size <= 0)
    return -1;

  srand(time(NULL));

  int curMax = arr[0], maxCnt = 1;
  arr[0] = 0; // For the momemt treat this first elememt as max

  for (int i = 1; i < size; i++)
  {
    if (curMax < arr[i])
    {
      curMax = arr[i];
      maxCnt = 0;
      arr[maxCnt++] = i;
    }
    else if (curMax == arr[i])
      arr[maxCnt++] = i;
  }

  return arr[rand()%maxCnt];
}

We can have separate array to hold all the indices of max elements. Give any random number among them!

int getIndexOfMaxRandomly(int arr[], int size)
{
  int i = 0;

  if (size <= 0)
    return -1;

  int* idxArr = (int *) malloc (sizeof(int) * size);
  memset (idxArr, 0, size*sizeof(int));

  if (!idxArr)
    return -1;

  srand(time(NULL));

  int curMax = arr[0], maxCnt = 1;
  for (int i = 1; i < size; i++)
  {
    if (curMax < arr[i])
    {
      curMax = arr[i];
      maxCnt = 0;
      idxArr[maxCnt++] = i;
    }
    else if (curMax == arr[i])
      idxArr[maxCnt++] = i;
  }
/*
  for (int i = 0; i < maxCnt; i++)
    printf ("%d  ", idxArr[i]);
*/
  int randIdx = idxArr[rand()%maxCnt];
  free (idxArr);
  return randIdx;
}

There are 3 basic structures that are required for these operations.
1. Hashmap : to support add, delete, contains
2. Double linked list : to support most recent entry. That is most recent added. Since we are using hashmap, to maintain last added value (most recent) we required double linked list.. (double linked list helps in the case of deletion - we can delete any element).. getMostRecent() will be in o(1)
3. One array : to keep the number of elements present upto date. This will help in randomization... getRandom() will be o(1)

structure of one node in hash will be
hash[value] = {array index, double linked list ptr}

So, the operations will be..

1. add(e) : when we add one value, hash[e] = {arr index, double linked list ptr}
2. delete(e) : when we delete one value, We are going to replace the cell that contains value in array with the last element in array. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H. Since we are keeping a double linked list ptr.. deletion will be an easier operation to keep the most recent accordingly...
3. contains(e) : returns hash.contains(e)
4. getRandom() : return array[rand() % (array length)]
5. getMostRecent() : return last element of the double linked list

How do you get some random index ensuring that it has value present in that index?

Nice one!
But your solution assumes that no three vertices will be on same line. And also there is no notion of length ( the question does not have this notion also )

Is this question correct Min rectangle?
If you go for min rectangle then it should be of 1x1.

This can be problem can be treated in different way.
If the top-left element is considered as root of the tree , then this problem boils down to level order traversal of the tree.

Only one special handling is required
1. If it's the right most element in the considered tree or the top row in the current diagonal, just push its right and then bottom element.
2. For other elements in the current diagonal, just push the bottom element.

Do this until any element left in the queue.

typedef std::pair <int, int> position; //<x,y>

bool isVisible (int x, int y, int r, int c)
{
	return (x >= 0 && x < r && y >= 0 && y < c);
}

void printMatrixDiagonally (int matrix[][MAX], int r, int c)
{
	queue<position> q;
	int diagCount = 1; // counts how may elements are present in that diagonal level
	position start;
	start = make_pair (0,0);
	q.push(start);
	
	while (!q.empty())
	{
		for (int i = 0 ; i < diagCount; i++)
		{
			position xy = q.front();
			printf ("%d ", matrix[xy.first][xy.second]);
			//special handling if the diagonal level contains only one entry
			if (i == 0)
			{
				if (isVisible(xy.first, xy.second + 1, r, c))
				{
					start = make_pair (xy.first, xy.second + 1); // right
					//printf ("Pushing (%d,%d)\n", start.first, start.second);
					q.push (start);
				}
				
				if (isVisible(xy.first + 1, xy.second, r, c))
				{
					start = make_pair(xy.first + 1, xy.second); // bottom
					//printf ("Pushing (%d,%d)\n", start.first, start.second);
					q.push (start);
				}
			}
			else	// for all other 
			{
				if (isVisible(xy.first + 1, xy.second, r, c)) // just play with bottom
				{
					start = make_pair(xy.first + 1, xy.second); // bottom					
					//printf ("Pushing (%d,%d)\n", start.first, start.second);
					q.push (start);
				}				
			}
			q.pop();
		}
		diagCount = q.size();
		printf ("\n");
	}
}

You can check my code below.
Anyway here is the logic.
1. Use two pointers : one at the last index of 1st array and another in the first index of second array.
2. Since the arrays are sorted we can apply this logic.
a. if the one(index1) >= two(index2) then swpa this values. It is guaranteed that after merging those elements are in correct arrays.
b. stop swapping if one(index1) < two(index2).
3. Sort the final arrays in order to get merged arrays.
Overall complexity O(n log n) in place.

Here is the logic.
1. Use two pointers : one at the last index of 1st array and another in the first index of second array.
2. Since the arrays are sorted we can apply this logic.
a. if the one(index1) >= two(index2) then swpa this values. It is guaranteed that after merging those elements are in correct arrays.
b. stop swapping if one(index1) < two(index2).
3. Sort the final arrays in order to get merged arrays.
Overall complexity O(n log n) in place.

void MergeTwoSorted(vector<int> &one, vector<int> &two)
{
	if (one.size() == 0 || two.size() == 0)
		return;
	int I = one.size() - 1, // Last index of 1st array
		II = 0;				// first index of 2nd array
	
	/* O(n) */
	// swap the values until we bring smaller value to one array
	// and all the bigger values to second array. Since it was sorted
	// we can manipulate the array in this way.
	while ((I >= 0) && (II < two.size()-1) && (one[I] >= two[II]))
	{
		swap(one[I], two[II]);
		I --;
		II ++;
	}
	
	// At this point all the smaller values in one array and larger in another 
	/* O(Nlog N) */
	sort (one.begin(), one.end());
	sort (two.begin(), two.end());
}

Begin :
One
15 21 35 49 77 83 86 86 92 93 
Two
11 26 26 27 36 40 59 62 63 68 72 90 
End :
One
11 15 21 26 26 27 35 36 40 49 
Two
59 62 63 68 72 77 83 86 86 90 92 93

Here _ is used as a special character. Special character handling should be there..
let if we encounter one _ then the final output of this will be __ (two _). It will help us to handle special character.

This is looks like merging k sorted array into a single array!

We can merge arrays in O(nk*Logk) time using Mean Heap. Following is detailed algorithm.

1. Create an output array of size n*k.
2. Create a min heap of size k and insert 1st element in all the arrays into a the heap
3. Repeat following steps n*k times.
a) Get minimum element from heap (minimum is always at root) and store it in output array.
b) Replace heap root with next element from the array from which the element is extracted. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.

geeksforgeeks.org/merge-k-sorted-arrays/

It sounds good. If a file is too large break it into a smaller chunks. but retain only one hash table during whole operation. Smaller chunks will lead us to creation of smaller file, merge the files to get the output.

Its almost impossible to solve this in O(n) and O(1) time.
There is a paper which describes citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.5554&rep=rep1&type=pdf : In the stable 0-1 sorting problem the task is to sort an array of n elements with two distinct values such that equal elements retain their relative input order.

But in order to do that we have to destroy the initial input array. But its just not done for just interviews of 1 hour.

Can you please explain this a bit in this perspective!!

Main problem with hash is that this will limit many functionality of a player. Although it plays the selected file in o(1) look up time. Searching with few letters cannot be performed here.

@Second Attempt If you use only BST then there is a possibility that you might end up with a list. Then inserting an appointment in a calender will cost o(n) time! Also collision detection will also cost o(n) time.

@ T on December 24, 2012:
You can only go either right or down. So, we cannot achieve (3,2,2) as a sequence.

@Nithish on April 17, 2010 :
Since we are putting all the smaller elements in one array and the larger elements in another array, we need to place the smaller elements from 2nd array to the proper places of 1st array. Finding a proper place needs moving all the bigger elements in right (if we are assuming ascending order). Here the complexity becomes o(n^2)

Its n-ary. Not binary tree not even binary search tree.

Question says : "Given a sorted array of size N and a sorted array of size M+N"
I think the first array contains m and second one contains n element or either way. We have to make second array as of (m+n) elements such that the order is preserve.

Please update the question properly.

Your solution is good. But I think you don't have to build this entire lookup table.
"oct" function in std will anyway do this for you.

This is the question if there are some problems to understand it.
hackerrank.com/challenges/stockmax

@atuljangra66 your code will fail for this {1, 5, 5, 8}

Initialize whole hash table with all -1s.
for(i=0;i<n;i++)
{
  hashTable[a[i]]++;
}

for(i=0;i<n;i++)
{
   Complement=K-a[i];
   Index = SearchHashTable(Complement);
   if(Index!=-1)
     cout<<"Indices:\t"<<HashTable[Complement]<<"\t"<<i<<endl;
}