Psycho
BAN USERSimple guy. Loves Programming.
 0of 0 votes
AnswersState the difference between this two statement.
 Psycho in India
char str[] = "/root//foo/bar" ;
char *str = "/root//foo/bar" ;
Now, you have given an assignment str[in1] = str[in2]
where in1 and in2 both initialize with 0.
In first type of declaration no problem. But in second type of declaration 'Segmentation fault' is there. Why this happens? Report Duplicate  Flag  PURGE
Adobe Software Engineer / Developer C  0of 0 votes
AnswersJust Example : "Given 8 cue balls , one is weighing lesser than other 7. Find that(light weight) ball using just 2 chances on balance weight."
 Psycho in India
How to find a general solution to these kind of question? How to divide this set of balls? Is there any finer method or general formula? Report Duplicate  Flag  PURGE
Software Engineer / Developer Brain Teasers  0of 0 votes
AnswersAn unsorted array is given, where there is no specific range in which the elements occur. There is only one duplicate element present in it. Let it is a[i]. It should be within the half of the size of the array from where it appears for first time. i.e. the duplicate element should be within (i+(arr_size/2)), at ith index it appears for 1st time. Find the duplicate element with minimum number comparisons.
 Psycho in United States Report Duplicate  Flag  PURGE
Microsoft
 0 Answers C++ Topic : Related to 'Multiset' functionality
Consider this sample piece of code!
multiset<int> iends; multiset<int>::iterator et1; while(et1!=iends.end()){ multiset<int>::iterator te=et1; et1++; iends.erase(te); } while(et1!=iends.end()){ multiset<int>::iterator te=et1; iends.erase(te); et1++; }
What is the difference between this two pieces of code?
 Psycho December 09, 2012 Flag  PURGE
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.
 Psycho February 19, 2016Very 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).
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 10fellowship5sandy7brownie. 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 = len1; 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() == '');
}

Psycho
January 22, 2016 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)12345678(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,
[24] or,
[35] or
[46] or
[57] or
Since the array must have the element, then it must be any element from [6  to  8] range.
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
// prebooking, 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
}

Psycho
January 10, 2016 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)

Psycho
January 08, 2016 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 autotriggered to notify the next user in the waiting queue. Now, waiting queue logic can be developed independently.
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.
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.
 Psycho September 01, 2014Earlier 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];
}

Psycho
August 07, 2014 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;
}

Psycho
August 07, 2014 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

Psycho
August 06, 2014 This can be problem can be treated in different way.
If the topleft 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");
}
}

Psycho
March 02, 2014 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

Psycho
February 02, 2014 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/mergeksortedarrays/

Psycho
February 01, 2014 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 01 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.
@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)
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.
@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=Ka[i];
Index = SearchHashTable(Complement);
if(Index!=1)
cout<<"Indices:\t"<<HashTable[Complement]<<"\t"<<i<<endl;
}

Psycho
October 17, 2013
RepOliviaJBlack, Consultant at Apkudo
I am Olivia from San Diego. I am working as a checker in the Thom McAn Store company. My strong ...
RepShirleyCWest, Software Engineer at Agilent Technologies
Hello, me Shirley and I from Savage. I am an artist and I love to doing art and I am ...
@zapurza: I think in that case also it will fail for this list
 Psycho April 14, 2016