zeroByzero
BAN USER
6 Answers this is my general doubt not a...
this is my general doubt not a particular question .
- zeroByzero January 06, 2013
1. how should we respond if we have no clue about the problem asked ..?
2. and are we asked to code all problems they ask.., like if problem involve complex data structure if you know the approach to the problem ,do they also ask for their code ,.?| Flag | PURGE
@ 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 .
- zeroByzero January 13, 2013please explain your logic little more.
- zeroByzero January 13, 2013duplicates from whole string.
- zeroByzero January 13, 2013for 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 .
- zeroByzero January 11, 2013please elaborate how to go with tries, here we are given stream of characters not array of characters.
- zeroByzero January 11, 2013perfect
- zeroByzero January 10, 2013you have to shift only till n/2, since maximum length of repeated substring can be n/2.
- zeroByzero January 10, 2013i 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.
- zeroByzero January 03, 2013i am sorry , i dont have full question . i have got it from some senior ..this was something similar
- zeroByzero January 02, 2013yeah 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
- zeroByzero December 29, 2012looking at the node structure , question is not clear..please check once again .
- zeroByzero December 27, 2012this is greedy approach wouldnt it fails for some of the cases ....wouldn't it fails for some of the cases ?
- zeroByzero December 18, 2012why are we using doubly linked list..?
- zeroByzero December 17, 2012hey annonymous couldnt understand clearly..please elaborate your logic..why doubly linked list and how delete operation in O(1) ?
- zeroByzero December 16, 2012we 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 .
- zeroByzero October 22, 20127k is right answer
- zeroByzero September 02, 2012store 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
- zeroByzero August 20, 2012i could not understand the logic, please explain little bit..
- zeroByzero August 18, 2012nice logic..
- zeroByzero August 17, 2012hey 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
- zeroByzero August 17, 2012gives starting point , but of lot of improvement posible as suggested by ranechabria..
- zeroByzero August 16, 2012u 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.
- zeroByzero August 16, 2012this 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.
- zeroByzero July 24, 2012that looks to be only correct answer out of all given above.
- zeroByzero July 24, 2012for ny doubt learn short circuit property of AND ,OR operator.
- zeroByzero July 21, 20122,3,4 and other too.
- zeroByzero July 21, 2012since 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.
- zeroByzero July 09, 2012Open Chat in New Window
perfect.
- zeroByzero January 13, 2013