CareerCup

perfect.

@ amit nice solution , can you suggest how to go for all 256 characters . i am thinking to use array of 8 nos, but couldnt think of algo, please explain if you know .

please explain your logic little more.

duplicates from whole string.

for this kind of problems first identify the problem entities:
---- Problem State
1. in a restaurent there are different tables (say x in no) of different capacities .
2 .we can book a table of capacity n for m people (m<=n);
3. a table can be booked only if there is suitable time difference between two bookings
4. booking can be done only for particular no of hours for which restaurent opens .

--- what will be input from external interface

int CheckTableAvailability(int NumPeople, time_t TimeOfBooking, int *tableNumber, time_t *alternativeTime) 
{
if(isTable_Available(NumPeople,TimeOfBooking))
{
*tableNUmber=isTable_Available(NumPeople,TimeOfBooking);
return 1;
}
if(alternate_time(NumPeople,TimeOfBooking))
{
alternatetime=alternate_time(NumPeople,TimeOfBooking)
return 2;
}
else
{
cout<<"no Booking possible";
return 0;
}

}

- This function will tell whether the booking is possible or not. If possible on the input time it will
return 1 and file the tableNumber. If not on the input time, but at some time near to that, it will
return 2 with the alternativeTime and TableNumber that can be booked. If not at all possible then it will return 0.
bookTable(contactDetails, tableNumber, time_t TimeOfBooking)
Extra functionality
for CheckTableAvailability , it can also return an array of tableNumber possible for booking. Like some restaurants have different sections (smoking zone, pool side, garden side etc) which will give the customer a choice to make.

Class: Table
{
int TableId;
int SeatingCapacity;
string speciality;
}

Class Booking
{
int bookingId;
int TableId;
time_t startTime;
customerDetails;
}

Class: BookedTables
{
HashTable bookings ( key: timeslot, value: int booked[NumTables] );
// int array will contain whether the table is booked or not for this time slot. A value of 0 means not booked. A value other than 0 represents a booking id
}

in overloading functions with same name are used but they have different parameters type or no. for better understanding u may follow this link geeksforgeeks.org/function-overloading-in-c/
while overriding is concept in inheritence ,function with same name and parameters are present both in base and child class .

couldnt get you, looks like you are using suffix tree..please elaborate .

please elaborate how to go with tries, here we are given stream of characters not array of characters.

perfect

you have to shift only till n/2, since maximum length of repeated substring can be n/2.

i have got one possible solution . using linked list and hash-map.
1. for 1st string insert 1st and last character into the string and also in hash map.
2. for subsequent strings check hash values for its 1st character in hash table ,
IF hash for this character exist then insert last character of this string to next of the hash address we have got from hash map.
ELSE create new linked list for first and last character of this string and insert it into hash map also .
3. keep on processing all the string , when we are done , we can traverse all the linked list and apply cycle detection algorithm , this way we can find all the strings forming cycle.

please suggest modifications

we can use n-way merge using minimum heap of size(min of no of row and coloumn ) ,
it is example of standard n-way merge , here we are given n-sorted rows in 2-D matrx .

algorithm would work like :

1. pick up 1st elements from all the rows and insert them into Min-heap.
2. top of element contain minimum element , pop it and insert element from the array
whose element was poped .
3. while making insertion check the last popped value , if it is same then do not push this into heap, simply increment its pointer in the repected row, this will take care of duplicates too.
3.keep doing this operation till no element is left in any of the row and heap .

Complexity: if matrix is of size m*n
O(log m)*m*n

@ grace you have made a valid point .
for keeping check of duplicate, i.e, item is already there we should also keep hash map of 10 items and before insertion we should check if the item is already there, if it is already there then it should be moved in front of queue by deleting it fom its position (USE DLL)

thanx man..
i still have doubt, if for any problems we do not know their code, like if i am using suffix tree as a part of the algorithm , i am assuming SUFFIX tree can we constructed in O(n) but i do not know how to code that, in that case what should we do..?

we can keep a queue of last 10 item visited for every user . whenever a new item will be added last items should be deleted such that only 10 items are kept in FIFO fashion.

i am sorry , i dont have full question . i have got it from some senior ..this was something similar

yeah correct, but a little improvement using memozation will improve this code..


int no_of_BST(int n)
{
int arr[n];
arr[0]=arr[1]=1;
for(int i=2;i<=n;i++)
arr[i]=0;

for(int i=2;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
arr[i]+=arr[j-1]*arr[i-j];
}
}

return arr[n];
}

@ xiaolong ,i doubts its validity please explain your logic in details

looking at the node structure , question is not clear..please check once again .

this is greedy approach wouldnt it fails for some of the cases ....wouldn't it fails for some of the cases ?

why are we using doubly linked list..?

hey annonymous couldnt understand clearly..please elaborate your logic..why doubly linked list and how delete operation in O(1) ?

we can use minimum heap of size n with 1st element from every array.
1. pop the minimum element from the heap and push the element from the arrya which contains minimum element and heapify again....this process continues till no element remain in any array .

another approach can be to sort the nos nd check...(o(nlogn) not efficient .

7k is right answer

store inorder traversal of tree in an array and sort it ,and again do inorder traversal and insert value from sorted array to tree .
the method posted by PKS may not work.

this can be done by trversing the linked list and check if child is not null then modify the pointers in list.

[nod1]<>[node2]<>[--]..............[--]
| | | |
list1 l ist 2 list 3.............list4

for each node just do following
node1->next=list1(head);
list1(head)->previous=node1;
list1(tails)->next=node2;
node2->previous=list1(tails);

this is code
cur=start;

while(cur=>next!=NULL)
{
temp=cur->next;
temp2=cur->child;
if(temp2)   //if child exist
{
temp3=temp2;
while(temp3->next!=NULL)
   temp3=temp->next;
//node u have found end of child list just change pointers
cur->next=temp2;
temp2->previous=cur;
temp3->next=temp1;
temp1->previous;

//
now increment current pointer for next node
cur=temp1;
}
else
cur=cur->next;  //if child was NULL just go ahead
}
}

for any clarification or bug please comment

i could not understand the logic, please explain little bit..

nice logic..

hey thanx for pointing out about bug to delete last element, but its not dead loop as in both if and else current=current is there, have a look again

gives starting point , but of lot of improvement posible as suggested by ranechabria..

u should post suggestion in comment box instead of new reply.
ur comment doesnt make sense when it floats above original post.

hey man review your question nd post again lot of typos.

this is simple algo ,traverse the list ,delete the node whenever value matches.
start node is special case which is handled saperatly .

void delete(int x,node *start)
{
node *current=start;
while(current)
{
if(current->value==x)  //if we have to delete start node
{
if(current==start)
{
node *temp=start;
current=current->next;
start=current;
delete(node);
}
else
{
node *temp=current->next;
current->value=current->next->value;
current->next=current->next->next;
current=current->next;
delete(temp);
}
}
}

that looks to be only correct answer out of all given above.

that looks to be only correct answer out of all given above.

for ny doubt learn short circuit property of AND ,OR operator.

2,3,4 and other too.

since we have to enclose all N points, so we can always choose any 5 points in 3-D space (forming prims ) which will enclose all points.
correct me if i am wrong.

to me this is ambiguos.
is it o(5*n) or 5*O(n) ?

@ ali baba i think you want to do inorder traversal for getting sorted sequences , preorder traversal is not going to give sorted sequence.