Implement a queue using two stack. MyStack has push(int), int pop(), boolean isEmpty() functions.
When the stack is empty and pop is called return 0.
When the queue is empty, deQueue should return 0
Input:
ENQUEUE 4 ENQUEUE 6 DEQUEUE ENQUEUE 8 DEQUEUE
For Programming in C:
//Here is the Definition of stack for C Language
struct stack{
struct SintNode * head;
};
//Here is the Definition of SintNode for C Language
struct SintNode {
int num;
struct SintNode * nextNode;
};
void pushstack(struct stack *,int) can be used to push an integer into the specified stack.
int popstack(struct stack *) can be used to pop an integer from the stack.
int isEmpty(struct stack *) can be used to check whether a stack is empty.(1 = empty. 0 = not empty)
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "common.h"
#include "answer.h"
#include "stack.h"
#include
struct stack s1;
struct stack s2;
struct stack * s1p = &s1;
struct stack * s2p = &s2;
struct SintNode * head = NULL,*rear=NULL;
struct SintNode * getHeadOfLinkedList() {
return head;
}
void initialise(){
initstack(s1p);
initstack(s2p);
}
int getMax(){
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
void enQueue(int num)
{
// struct SintNode *head=NULL,*rear=NULL;
struct SintNode *n=(struct SintNode *)malloc(sizeof(struct SintNode));
n->num=num;
n->nextNode=NULL;
if(head==NULL)
{
head=n;
}
else
{
n->nextNode=head;
head=n;
}
// WRITE YOUR CODE HERE
}
int deQueue()
{ int num=0;
if(head==NULL)
return num;
if(head->nextNode==NULL)
{
num=head->num;
head=NULL;
return num;
}
struct SintNode *temp=head;
struct SintNode*temp1=head->nextNode;
struct SintNode*prev=NULL;
while(temp1!=NULL)
{
prev=temp;
temp=temp1;
temp1=temp1->nextNode;
}
num=temp->num;
prev->nextNode=NULL;
return num;
// WRITE YOUR CODE HERE
}
void push(int num) {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
}
int pop() {
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
return 0;
}
int getMin(){
return 0;
// YOU CAN IGNORE THIS FUNCTION FOR THIS PROBLEM
}
struct SintNode * getHead1(){
return getHeadOfLinkedList(s1p);
}
struct SintNode * getHead2(){
return getHeadOfLinkedList(s2p);
}
int getNumofOps(){
return getNumOfOperations(s1p) + getNumOfOperations(s2p);
}
In a given LinkedList (where each node has a character),
there is one character which appears twice.
Find a function to find the character and return it.
Please use the hashmap passed to this function to solve this problem
If there are no such character return '0' (zero)
Input: h->e->l->l->o->NULL
Output : 'l'
Input: a->s->d->f->g->h->j->a->NULL
Output: 'a'
//here is the class definition of SchNode
public class SchNode {
public char ch;
public SchNode nextNode;
public SchNode(char ch){
this.ch = ch;
}
}
//Here is the Definition of SchNode for C Language
struct SchNode {
char ch;
struct SchNode * nextNode;
};
//Here is the Definition of HashMapChInt for C Language
struct HashMapChInt {
int arr[256];
};
//This function returns an int value mapped to the key c
int HMChIntGet(struct HashMapChInt * map,char c);
//This function is used to insert an int value into the map with a key c
void HMChIntPut(struct HashMapChInt * map,char c,int val);
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "ExpHashMap.h"
#include "common.h"
#include
char func(struct SchNode * head,struct HashMapChInt * map){
char ch = '\0';
if(head==NULL)
{
return ch;
}
else
{
struct SchNode * temp=head;
while(temp != NULL){
if(HMChIntGet(map,temp->ch) != -1){
return temp->ch;
}
HMChIntPut(map,temp->ch,1);
temp= temp->nextNode;
}
return ch;
}
}
#include "ExpHashMap.h"
#include "common.h"
#include
struct SchNode * GetNode(char ch){
struct SchNode * newnode = (struct SchNode *)malloc(sizeof(struct SchNode));
newnode -> ch = ch;
newnode -> nextNode = NULL;
return newnode;
}
struct SchNode * func(struct SchNode * head1,struct SchNode * head2,struct HashMapChInt * map) {
struct SchNode * output = NULL;
if(head1 == NULL || head2 == NULL) return NULL;
struct SchNode * n = head1;
struct SchNode * p = head2;
struct SchNode * r = output;
while(p != NULL) {
int i = HMChIntGet(map,p->ch);
if(i == -1) {
HMChIntPut(map,p->ch,1);
}
else {
HMChIntPut(map,p->ch,i + 1);
}
p = p->nextNode;
}
while(n != NULL) {
int i = HMChIntGet(map,n->ch);
if(i == -1) {
//HMChIntPut(map,n->ch,1);
}
else {
if(i > 0) {
if(output == NULL){
output = GetNode(n->ch);
r = output;
}
else{
struct SchNode * newnode = GetNode(n->ch);
r -> nextNode = newnode;
r = r -> nextNode;
}
HMChIntPut(map,n->ch,i - 1);
}
}
n = n->nextNode;
}
return output;
}
Find the intersection of two given LinkedList (where each node has a character).
Return the LinkedList which has character which appears in both LinkedList (same sequence order as LinkedList1).
Please use hashmap to solve this problem.
Input: LinkedList1: H->e->l->l->o->NULL
LinkedList2: w->o->r->l->d->NULL
Output: l->o->NULL
Input: LinkedList1: h->i->NULL
LinkedList2: b->y->e->NULL
Output: null
// here is the definition of SchNode
public class SchNode {
public char ch;
public SchNode nextNode;
public SchNode(char ch){
this.ch = ch;
}
}
//Here is the Definition of SchNode for C Language
struct SchNode {
char ch;
struct SchNode * nextNode;
};
//Here is the Definition of HashMapChInt for C Language
struct HashMapChInt {
int arr[256];
};
//This function returns an int value mapped to the key c
int HMChIntGet(struct HashMapChInt * map,char c);
//This function is used to insert an int value into the map with a key c
void HMChIntPut(struct HashMapChInt * map,char c,int val);
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
Given a linkedlist, where each node has a character,
find the character which appeared the maximum time.
If you have multiple character as result, return the first character in that list.
Please use the hashmap to figure out the element
Input: h->e->l->l->o-> ->w->o->r->l->d->NULL
Output : 'l'
Input: y->e->l->h->a->h->a->NULL
Output: 'h'
// here is the definition of SchNode
public class SchNode {
public char ch;
public SchNode nextNode;
public SchNode(char ch){
this.ch = ch;
}
}
//Here is the Definition of SchNode for C Language
struct SchNode {
char ch;
struct SchNode * nextNode;
};
//Here is the Definition of HashMapChInt for C Language
struct HashMapChInt {
int arr[256];
};
//This function returns an int value mapped to the key c
int HMChIntGet(struct HashMapChInt * map,char c);
//This function is used to insert an int value into the map with a key c
void HMChIntPut(struct HashMapChInt * map,char c,int val);
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "ExpHashMap.h"
#include "common.h"
#include
char func(struct SchNode * head,struct HashMapChInt * map) {
char ch = '0';
if(head==NULL)
{
return ch;
}
else
{
int max=0;
struct SchNode *temp=head;
while(temp!=NULL)
{
int m=HMChIntGet(map,temp->ch);
if(m==-1)
{
HMChIntPut(map,temp->ch,1);
}
else
{
HMChIntPut(map,temp->ch,m+1);
}
temp=temp->nextNode;
}
temp=head;
while(temp!=NULL)
{
int m=HMChIntGet(map,temp->ch);
if(m>max)
{
max=m;
ch=temp->ch;
}
temp=temp->nextNode;
}
return ch;
}
}
Count the number of pairs in LinkedList (where each node has a integer)
whose sum equals given sum (all elements are unique).
Use hashmap to solve this problem; do not perform delete operation on hashmap
Input: 0->2->5->7->4->6->10->20->-10->NULL
Sum: 10
Output : 3 [(0, 10), (4, 6), (20, -10)]
// here is the definition of SintNode
public class SintNode {
public int num;
public SintNode nextNode;
public SintNode(int num){
this.num = num;
}
}
//Here is the Definition of SintNode for C Language
struct SintNode {
int num;
struct SintNode * nextNode;
};
//Here is the Definition of HashMapIntInt for C Language
struct HashMapIntInt {
int arr[65536];
};
//This function returns an int value mapped to the key k
int HMIntIntGet(struct HashMapIntInt * map,int k);
//This function is used to insert an int value into the map with a key k
void HMIntIntPut(struct HashMapIntInt * map,int k,int val);
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "ExpHashMap.h"
#include "common.h"
#include
int func(struct SintNode * head,int sum,struct HashMapIntInt * map) {
struct SintNode *temp=head;
int c=0,r;
while(temp!=NULL)
{
HMIntIntPut(map,temp->num,1);
temp=temp->nextNode;
}
temp=head;
while(temp!=NULL)
{
r=sum-temp->num;
if(HMIntIntGet(map,r) != -1 && r != temp->num) {
c++;
}
temp=temp->nextNode;
}
return c/2;
}
Given a LinkedList (where each node has a character)
remove duplicates characters and maintain the same order
Please use hashmap to solve this problem. Do not delete items from hashmap
Input: H->e->l->l->o->w->o->r->l->d->h->i->NULL
Output: H->e->l->o->w->r->d->h->i->NULL
//here is the class definition of SchNode
public class SchNode {
public char ch;
public SchNode nextNode;
public SchNode(char ch){
this.ch = ch;
}
}
//Here is the Definition of SchNode for C Language
struct SchNode {
char ch;
struct SchNode * nextNode;
};
//Here is the Definition of HashMapChInt for C Language
struct HashMapChInt {
int arr[256];
};
//This function returns an int value mapped to the key c
int HMChIntGet(struct HashMapChInt * map,char c);
//This function is used to insert an int value into the map with a key c
void HMChIntPut(struct HashMapChInt * map,char c,int val);
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "ExpHashMap.h"
#include "common.h"
#include
struct SchNode * GetNode(char ch){
struct SchNode * newnode = (struct SchNode *)malloc(sizeof(struct SchNode));
newnode -> ch = ch;
newnode -> nextNode = NULL;
return newnode;
}
struct SchNode * func(struct SchNode * head,struct HashMapChInt * map) {
if(head == NULL)
return NULL;
struct SchNode * n = head;
struct SchNode * output = NULL;
struct SchNode * r = output;
while(n != NULL) {
int i = HMChIntGet(map,n->ch);
if(i == -1) {
HMChIntPut(map,n->ch,1);
if(output == NULL){
output = GetNode(n->ch);
r = output;
}
else{
struct SchNode * newnode = GetNode(n->ch);
r -> nextNode = newnode;
r = r -> nextNode;
}
}
n = n->nextNode;
}
return output;
}
Given a input string (inputStr1) and reference string (inputStr2) as a LinkedLink, where
each Node has a character, remove all the occurrence of character of reference string
in the input string
Please use hashmap to solve this problem.
Input LinkedList: H->e->l->l->o->w->o->r->l->d->h->i->NULL
Deletion String: l->h->e->NULL
Output String: H->o->w->o->r->d->i->NULL
//here is the class definition of SchNode
public class SchNode {
public char ch;
public SchNode nextNode;
public SchNode(char ch){
this.ch = ch;
}
}
//Here is the Definition of SchNode for C Language
struct SchNode {
char ch;
struct SchNode * nextNode;
};
//Here is the Definition of HashMapChInt for C Language
struct HashMapChInt {
int arr[256];
};
//This function returns an int value mapped to the key c
int HMChIntGet(struct HashMapChInt * map,char c);
//This function is used to insert an int value into the map with a key c
void HMChIntPut(struct HashMapChInt * map,char c,int val);
NOTE: Do not use any printf or scanf statements while writing answers in C Language.
#include "ExpHashMap.h"
#include "common.h"
#include
struct SchNode *GetNode(char ch)
{
struct SchNode *newnode=(struct SchNode *)malloc(sizeof(struct SchNode));
newnode->ch=ch;
newnode->nextNode=NULL;
return newnode;
}
struct SchNode * func(struct SchNode * head1,struct SchNode * head2,struct HashMapChInt * map) {
struct SchNode *inp1=head1,*inp2=head2;
struct SchNode * output = NULL;
struct SchNode * r = output;
while(inp2!=NULL)
{
int i=HMChIntGet( map,inp2->ch);
if(i==-1)
{
HMChIntPut(map,inp2->ch,1);
}
inp2=inp2->nextNode;
}
while(inp1!=NULL)
{
int i=HMChIntGet( map,inp1->ch);
if(i==-1)
{
if(output==NULL)
{
output=GetNode(inp1->ch);
r=output;
}
else
{
struct SchNode *newnode=GetNode(inp1->ch);
r->nextNode=newnode;
r=r->nextNode;
}
}
inp1=inp1->nextNode;
}
return output;
}
