crystal.rishi2
BAN USER- 0of 2 votes
AnswersDivide a triangle into 5 triangles of equal area
- crystal.rishi2 in India| Report Duplicate | Flag | PURGE
Kalido Software Engineer / Developer Brain Teasers
Hi Nikhil,
On a second thought, this question seems to asking for ZigZag Traversal of the tree. I hope I am correct. Following is the code for Zig Zag Traversal.
void ZigZagTraversal(struct Node *root) {
struct Node *temp;
int leftToRight = 1;
stack<Node*> current;
stack<Node*> next;
current.push(root);
while (!current.empty()) {
temp = current.top();
current.pop();
if (temp) {
cout<<temp->data<<" ";
if (leftToRight) {
if (temp->left)
next.push(temp->left);
if (temp->right)
next.push(temp->right);
}
else {
if (temp->right)
next.push(temp->right);
if (temp->left)
next.push(temp->left);
}
}
if (current.empty()) {
leftToRight ^=1;
std::swap(current, next);
}
}
}
1. Invalid Token ID
2. NULL Token ID
3. Maximum limit exceeded for token ID (Buffer Overflow)
4. What happens to token ID when corresponding product is deleted
5. Token is valid but product is not in stock
There is no need of additional data structures, it can be done in place. In your approach u need to create words from the sentence and then place it into stack. So much effort may not be required. We can reverse the complete sentence and then reverse every word in the output of the sentence reversal step.
- crystal.rishi2 October 24, 2012Reverse the whole sentence and then reverse the output word by word
CODE :
void reverseWordByWord (char *str) {
char *start = str;
int len = strlen(str);
char *end = str+len-1;
reverse(start, end);
int i;
for (i=0; i<len; i++) {
if (str[i]== ' ') {
end = &str[i-1];
reverse(start,end);
start = &str[i+1];
}
}
//Reverse the last word !
end = &str[i-1];
reverse(start,end);
}
strcat can be used. Write the char in some buffer using sprintf and then use strcat
- crystal.rishi2 October 23, 2012Can you please explain the solution further, I still don't get it
- crystal.rishi2 October 23, 2012We can actually split the list into two lists of M and N size as required. Mark MthNode->next = NULL and Delete all the elements in the N size linked list.
- crystal.rishi2 October 23, 2012Following function can be used
void reverseWordByWord(char string[]) {
int len = strlen(string);
char *start = &string[0];
char *end = NULL;
for (int i=0;i<len;++i) {
if (string[i] == ' ') {
end = &string[i-1];
reverse(start, end);
start = i+1<len?&string[i+1]:NULL;
}
}
//reverse the last word
end = &string[len-1];
reverse(start, end);
}
Use majority number algorithm and check whether majority number count is actually n/2 or more
- crystal.rishi2 October 23, 2012Whether you will consider the heavier pan or lighter pan in case both pans are unequal ??
- crystal.rishi2 October 23, 2012DNF Algo for the question asked
void DutchNationalFlag012s(int *a, int n) {
int low=0, mid=0, high = n-1;
while (mid<=high) {
switch(a[mid]) {
case 0:
swap(&a[low++], &a[mid++]);
break;
case 1:
mid++;
break;
case 2:
swap(&a[mid], &a[high--]);
break;
}
}
}
Code for Reverse Level Order for each Level procedure
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
void ReverseLevelOrderForEachLevel(struct Node *root) {
struct Node *temp;
if(!root)
return;
queue<Node*> Q;
stack<Node*> S;
Q.push(root);
Q.push(NULL);
while (!Q.empty()) {
temp = Q.front();
Q.pop();
if (temp == NULL) {
while(!S.empty()) {
cout<<S.top()->data<<" ";
S.pop();
}
cout<<endl;
if(!Q.empty()) {
Q.push(NULL);
}
}
else {
S.push(temp);
if(temp->left)
Q.push(temp->left);
if(temp->right)
Q.push(temp->right);
}
}
}
Ans to Ques 1 :
Do a level order traversal using a queue.
Pseudocode
Enqueue(Q, root)
Enqueue(Q, NULL) //marker for level end
while (!isEmptyQueue(Q)) {
temp = Dequeue(Q);
if (temp == NULL) {
//marks end of level
//Pop all the elements and print
if (!isEmptyQueue(Q))
Enqueue(Q, NULL) //marker
}
Push(stack, temp);
if (temp->left)
Enqueue(Q, temp->left);
if (temp->right)
Enqueue(Q, temp->right);
}
The other question can be solved as well by making minor modifications
- crystal.rishi2 October 22, 2012Similarly a++++ is not allowed as well
Check this : http ://ideone.com/ 4S3S4Z
@nj, Can you please explain what exactly is happening inside getLCA ??
Especially here
while(apos!=bpos)
{
if(apos>bpos)
apos/=2;
else bpos/=2;
}
The question does not clearly mention whether all the negatives are the same or whether all the positives are the same. If they are diff say we have -2, -5, -1,etc. and 4,8,7,etc then we cannot use the DNF algo as it is.
- crystal.rishi2 October 21, 2012Reverse the list and compare with the original list
Reversing is very easy
void reverseList (struct Node **head) {
struct Node *current = *head, *prev = NULL, *next;
while (current) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head = prev;
}
Now we can compare with original list
- crystal.rishi2 October 21, 2012Please explain the logic of how lookup table is being filled ?
- crystal.rishi2 October 20, 2012Excuse me if I am doing it wrong but I am getting the following compilation error while trying to compile the xor swap pointer function
error: invalid conversion from 'int' to 'Node*' [-fpermissive]
error: invalid conversion from 'int' to 'Node*' [-fpermissive]
error: invalid conversion from 'int' to 'Node*' [-fpermissive]
Thanks, I got this modified code
struct Node* rec_nth(struct Node* node, int n) //n being the 'nth' element index from the end
{
static int count;
static Node* soln = NULL;
if(node->next == NULL)
{
count = 0;
return node;
}
rec_nth(node->next,n);
if (++count == n)
{
soln = node;
}
return soln;
}
Following C++ solution can be used : (Ref: stack overflow)
int main (int argc, char * const argv[]) {
string s = "sarp";
bool used [4];
permute(0, "", used, s);
}
void permute(int level, string permuted, bool used [], string &original) {
int length = original.length();
if(level == length) { // permutation complete, display
cout << permuted << endl;
} else {
for(int i=0; i<length; i++) { // try to add an unused character
if(!used[i]) {
used[i] = true;
permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string
used[i] = false;
}
}
}
Kindly let me know what is the problem with the approach below, it is causing runtime error.
struct Node* NthFromLast(struct Node *head, int N) {
static int count =0;
if (!head)
return NULL;
NthFromLast(head->next, N);
if (++count == N)
return head;
else
return NULL;
return NULL;
}
Couting sort and bucket sort can be used.
void CountingSort(int *a, int n, int range) {
using namespace std;
int *b = new int(n);
for (int j =0; j<n; ++j)
b[j] =0;
int *count = new int (range+1);
int i;
for (i =0; i<=range; ++i)
count[i] = 0;
for (i =0; i<n; ++i)
count[a[i]] = count[a[i]] +1;
for (i =1; i<=range; i++)
count[i] = count[i] + count[i-1];
for (i =n-1; i>=0; i--) {
b[count[a[i]]-1] = a[i];
count[a[i]] = count[a[i]]- 1;
}
for (i =0; i<n; ++i)
cout<<b[i]<<" ";
cout<<endl;
}
int main () {
int a[] = {3,2,1,4,2,3,2,2,2,1,4,3,2};
int size = sizeof (a)/ sizeof(*a);
CountingSort(a,size,4);
return 0;
}
G++ compiler gives output as 10. However I am not sure why people are calling the behavior as undefined
- crystal.rishi2 October 18, 2012Padding is required to keep the size of structs in multiples of 2. That way, it is easier to allocate memory and store in memory.
- crystal.rishi2 October 17, 2012dynamic_cast has been designed only for inheritance hierarchy downcasting. Use static_cast or reinterpret_cast. However, reinterpret_cast is not portable across platforms.
- crystal.rishi2 October 17, 2012
If you use normal new then if the allocation fails, NULL WILL NOT be assigned to the pointer because internally it uses temp pointer to allocate memory and only if it is successful, then its address is copied to your poiniter, else exception is thrown.
- crystal.rishi2 August 12, 2013