// LinkList.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
struct list
{
int month;
struct list *next;
};
typedef struct list node;
void init(node* record)
{
record->next=NULL;
}
void addnode(node* record,int d)
{
node* fresh;
fresh=(node *)malloc(sizeof(node));
fresh->month=d;
fresh->next=record->next;
record->next=fresh;
}
void print(node *record)
{
node* temp;
temp=(node *)malloc(sizeof(node));
for(temp=record->next;temp;temp=temp->next)
printf(" %d",temp->month);
}
void reverse(node* record)
{
node* temp;
node* temp1;
node* temp2;
temp=(node *)malloc(sizeof(node));
temp1=(node *)malloc(sizeof(node));
temp2=(node *)malloc(sizeof(node));
temp=record;
temp1=temp->next;
temp2=temp1->next;
temp->next->next=NULL;
while(temp2!=NULL)
{
temp=temp1;
temp1=temp2;
temp2=temp1->next;
temp1->next=temp;
}
record->next=temp1;
}
int _tmain(int argc, _TCHAR* argv[])
{
node* start;
start=(node *) malloc(sizeof(node));
init(start);
int i=0;
for(i=5;i>=0;i--)
addnode(start,i);
print(start);
reverse(start);
printf("\n");
print(start);
printf("\n");
return 0;
}
2. Copy link list to another list
// Copy List
node* CopyList(node* head)
{
node* current = head; // used to iterate over the original list
node* newList = NULL; // head of the new list
node* tail = NULL; // kept pointing to the last node in the new list
while (current != NULL)
{
if (newList == NULL)
{
// special case for the first new node
newList = (node *)malloc(sizeof(node));
newList->month = current->month;
newList->next = NULL;
tail = newList;
}
else
{
tail->next = (node *)malloc(sizeof(node));
tail = tail->next;
tail->month = current->month;
tail->next = NULL;
}
current = current->next;
}
return(newList);
}
3. Length of the list
int Length(node* head)
{
node* current = head;
int count = 0;
while (current->next != NULL)
{
count++;
current = current->next;
}
return count;
}
4. Check if there a loop in the list
bool hasLoop(node* startNode)
{
node* slowNode = startNode;
node* fastNode = startNode;
node* fasterNode = startNode;
while (slowNode && fasterNode == fasterNode->next && fasterNode == fastNode->next)
{
if (slowNode == fastNode || slowNode == fasterNode)
return true;
slowNode = slowNode->next;
}
return false;
}
5. Delete a node in a doubly linked list
void deleteNode(node *n)
{
node *np = n->prev;
node *nn = n->next;
np->next = n->next;
nn->prev = n->prev;
delete n;
}
6. Print data from a binary tree
/*
Given a binary search tree, print out
its data elements in increasing
sorted order.
*/
void printTree(struct node* node) {
if (node == NULL) return;
printTree(node->left);
printf("%d ", node->data);
printTree(node->right);
}
7. What is Binary tree
struct node
{
int key_value;
struct node *left;
struct node *right;
};
struct node *search(int key, struct node *leaf)
{
if( leaf != 0 )
{
if(key==leaf->key_value)
{
return leaf;
}
else if(key
{
return search(key, leaf->left);
}
else
{
return search(key, leaf->right);
}
}
else return 0;
}
/*
Helper function that allocates a new node
with the given data and NULL left and right
pointers.
*/
struct node* NewNode(int data) {
struct node* node = new(struct node); // "new" is like "malloc"
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/*
Give a binary search tree and a number, inserts a new node
with the given number in the correct place in the tree.
Returns the new root pointer which the caller should
then use (the standard trick to avoid using reference
parameters).
*/
struct node* insert(struct node* node, int data) {
// 1. If the tree is empty, return a new, single node
if (node == NULL) {
return(newNode(data));
}
else {
// 2. Otherwise, recur down the tree
if (data <= node->data) node->left = insert(node->left, data);
else node->right = insert(node->right, data);
return(node); // return the (unchanged) node pointer
}
}
8. Factorial of number
//
// recursive version
//
int Factorial( int Num )
{
if ( num > 0 )
return Num * Factorial ( Num –1 );
else
return 1;
}
//
// iterative version
//
int Factorial( int Num )
{
int I
int result = 1;
for ( I= Num; I > 0; I-- )
{
result = result * I;
}
return result;
}
9. Fibonacci of a number
int fib( n ) // recursive version
{
if ( n < 2 )
return 1;
else
return fib ( n –1 ) + fib ( n –2 );
}
int fib( n ) //iterative version
{
int f1 =1, f2 = 1;
if ( n < 2 )
return 1;
for ( i = 1; i < N; i++)
{
f = f1 + f2;
f1= f2;
f = f1;
}
return f;
}
10. Find the last occurrence of a character in the string
char *lastchar(char *String, char ch)
{
char *pStr = NULL;
// traverse the entire string
while( * String ++ != NULL )
{
if( *String == ch )
pStr = String;
}
return pStr;
}
11. Return nth node from the end of the linked list in one pass
node* GetNthNode ( node* Head , int NthNode )
{
node * pNthNode = NULL;
node * pTempNode = NULL;
int nCurrentElement = 0;
for ( pTempNode = Head; pTempNode != NULL; pTempNode = pTempNode->next )
{
nCurrentElement++;
if ( nCurrentElement - NthNode == 0 )
{
pNthNode = Head;
}
else
if ( nCurrentElement - NthNode > 0)
{
pNthNode = pNthNode ->next;
}
}
if (pNthNode )
{
return pNthNode;
}
else
return NULL;
}
12. Delete a node n, if you don’t know the head of the list
Q: What is the difference between 'BOOL' and 'bool'?
A: 'bool' is a built-in C++ type while 'BOOL' is a Microsoft specific type that is defined as an 'int'. You can find it in 'windef.h':
Code:
typedef int BOOL;
#ifndef FALSE
#define FALSE 0
#endif
#ifndef TRUE
#define TRUE 1
#endif
The only possible values for a 'bool' are 'true' and 'false', whereas for 'BOOL' you can use any 'int' value, though 'TRUE' and 'FALSE' macros are defined in 'windef.h' header.
13. Search for a value in sorted array
C++
/*
* searches for a value in sorted array
* arr is an array to search in
* value is searched value
* left is an index of left boundary
* right is an index of right boundary
* returns position of searched value, if it presents in the array
* or -1, if it is absent
*/
int binarySearch(int arr[], int value, int left, int right)
{
while (left <= right)
{
int middle = (left + right) / 2;
if (arr[middle] == value)
return middle;
else if (arr[middle] > value)
right = middle - 1;
else
left = middle + 1;
}
return -1;
}
14.
Q: Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?
A: A(1), B(2), C(5), D(10)
1. A & B cross together. They take 2 minutes
2. A come back to start point. He takes 1 more min.
3. So far 3 minutes invested in total
4. C and D start together. Reach in 10 minutes. So total 13 minutes invested so far
5. B who is at the far end, take the torch and comes back to start point. He needs 2 min
6. So far far 15 min invested
7. A and B start together, reach the far end in 2 min
8. Total 17 min invested.
15.
Q: How would you find a cycle in a linked list? Try to do it in O(n) time. Try it using constant amount of memory.
A: p2 is guaranteed to reach the end of the list before p1 and every link will be tested by the while condition so no chance of access violation. Also, incrementing p2 by 2 and p1 by 1 is the fastest way of finding the cycle. In general if p1 is incremented by 'n' and p2 by 'm', ('n' not == 'm'), then if we number the nodes in the cycle from 0 to k-1 (k is the number of nodes in the cycle), then p1 will take values given by i*n (mod k) and p2 will take values i*m (mod k). These will collide every n*m iterations. Clearly, n*m is smallest for n==1 and m==2.
bool HasCycle(Node *pHeadNode)
{
Node *p1, *p2;
p1 = p2 = pHeadNode;
while (p2 && p2->Next) {
p1 = p1->Next;
p2 = p2->Next->Next;
if (p1 == p2)
return true;
}
return false;
}
16.
Q: Implement an algorithm to reverse a singly linked list. (with and without recursion)
Node *RevSList(Node *pCur, Node *pRev) {
if (!pCur) return pRev;
Node *pNext = pCur->Next;
pCur->Next = pRev;
pRev = pCur;
return (RevSList(pNext, pRev));
}
Node * RevSList(Node *pCur) {
Node *pRev = NULL;
while (pCur)
{
Node *pNext = pCur->Next;
pCur->Next = pRev;
pRev = pCur;
pCur = pNext;
}
return pRev;
}
17. Delete a node in Single Link List
node *DelSLLNode(node *pDelete, node *pHead)
{
if (pHead == pDelete)
return (pHead = pHead->next);
node *pPrev = pHead;
for ( ; pPrev->next; pPrev = pPrev->next)
{
if (pPrev->next == pDelete)
{
pPrev->next = pPrev->next->next;
break;
}
}
return pHead;
}
18.
One train leaves Los Angeles at 15 MPH heading for New York. Another train leaves from New York at 20mph heading for Los Angeles on the same track. If a bird, flying at 25mph, leaves from Los Angeles at the same time as the train and flies back and forth between the two trains until they collide, how far will the bird have traveled?
If distance is X miles between NY and LA, then it takes X/(15+20) hours for the trains to collide, and bird will have travelled 25X/(15+20) = 5X/7 miles in that time.
19.
You have 12 balls. All of them are identical except one, which is either heavier or lighter than the rest - it is either hollow while the rest are solid, or solid while the rest are hollow. You have a simple two-armed scale, and are permitted three weighings. Can you identify the odd ball, and determine whether it is hollow or solid.
Let the balls be numbered 1 to 12. Firstly, put 1-4 on one side and 5-8 on other side. If both are equal then one of 9-12 is odd. Then second try, weigh 9-10 vs 1-2, if equal, one of 11-12 is bad, else 9-10 is bad. Testing which one is bad can be done by (third try) weighing 11 or 9, respectively, with good ball 1. It also gives whether the odd ball is heavy or light.
20.
You have 5 jars of pills. Each pill weighs 10 gram, except for contaminated pills contained in one jar, where each pill weighs 9 gm. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?
Take one pill from first, two from second, three from third and so on. Total pills are n(n+1)/2 and should weigh 10n(n+1)/2. If it weighs x gm less than that then the x'th jar is contaminated, since we took x pills from that jar which weighed 1 gm less.
21. Write a function that finds repeating characters in a string
/* Returns an array of size 256 containg count
of characters in the passed char array
*/
int *getCharCountArray(char *str)
{
int *count = (int *)calloc(sizeof(int), NO_OF_CHARS);
int i;
for (i = 0; *(str+i); i++)
count[*(str+i)]++;
return count;
}
/* The function returns index of first non-repeating
character in a string. If all characters are repeating
then reurns -1
*/
int firstNonRepeating(char *str)
{
int *count = getCharCountArray(str);
int index = -1, i;
for (i = 0; *(str+i); i++)
{
if(count[*(str+i)] == 1)
{
index = i;
break;
}
}
return index;
}
int _tmain(int argc, _TCHAR* argv[])
{
char str[] = "geeksforgeeks";
int index = firstNonRepeating(str);
if(index == -1)
printf("Either all characters are repeating or string is empty");
else
printf("First non-repeating character is %c", str[index]);
return 0;
}
22. Format the paragraph having multiple statements (ended with a “.” Period). For instance “This is one completed statement.The other just started with no space,so I’ll pay you $10.0 to format it.”
23. Implement Undo, Redo of MS Word
No comments:
Post a Comment