Problem:How far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j. The sequence 2, 4,
Continue Reading “Inverse Count Of An Array[Microsoft,Flipkart,Amazon]”
Problem:Given an array of integers, sort the array according to frequency of elements. For example, if the input array is {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}, then modify the array to {3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}. If frequencies of two elements are same, print
Problem: Complete the method which takes oneargument: the head ofthe linked list. The programshould not read any input fromstdin/console. The struct Node has a data part which stores the data and a nextpointer which points to the next element of the linked list. There are multiple test cases. For each test case, this method will
Continue Reading “Sort a linked list of 0s, 1s and 2s[Microsoft,Amazon]”
Problem:Given a sorted circular linked list, insert a new node so that it remains a sorted circular linked list. Problem Link /* struct node { int data; struct node *next; }; */ void sortedInsert(struct node** head_ref, int x) { node *tmp=(*head_ref); node *prev,*nxt; int val; int start_val=tmp->data; bool first=1; node *p=new node; p->data=x; if(x<tmp->data) {
Continue Reading “Insert an element in a sorted circular linkedList.[Microsoft & Amazon]”
Problem:Given two linked lists sorted in increasing order. Merge them both in such a way that the result list is in decreasing order. Both the Linked list can be of different sizes. /* The structure of linked list is the following struct Node { int data; Node* next; }; */ struct Node * mergeResult(Node *node1,Node
Continue Reading “Merge 2 sorted linked list in reverse order[Microsoft Interview Question]”
Problem:Given a directed graph you need to complete the function topoSort which returns an array having the topologically sorted elements of the array and takes two arguments. //http://www.practice.geeksforgeeks.org/problem-page.php?pid=700255 /* You need to complete this function */ int * topoSort(vector<int> graph[], int N) { // Your code here vector<int> indeg(N,0); int *arr=(int*)malloc(sizeof(int)*N); queue<int> cue; int u,v;
Continue Reading “Topological Sorting Problem[Microsoft,Flipkart,Amazon]”
Problem:FindReverse of a tree. /* Linked List Node structure struct Node { int data; struct Node *next; } */ // Should reverse list and return new head. struct Node* reverse(struct Node *head) { // Your code here Node *curr=head; Node *prev=NULL; Node *nxt; while(curr!=NULL) { nxt=curr->next; curr->next=prev; prev=curr; curr=nxt; } head=prev; return head; } Problem:Balance
Continue Reading “Some Microsoft Interview Problem Solution-2”
Problem description: Implement a stack using two queues. Problem link /* The structure of the class is class QueueStack{ private: queue<int> q1; queue<int> q2; public: void push(int); int pop(); }; */ /* The method push to push element into the stack */ void QueueStack :: push(int x) { // Your Code int t; if(q1.size()==0 &&
Problem Link /* The structure of a BST node is as follows: struct node { int data; struct node * right, * left; }; */ void printNearNodes(node *root, int l, int h) { // your code goes here node *p=root; if(p->data>=l && p->data<=h) { if(p->left) printNearNodes(p->left,l,h); printf("%d ",p->data); if(p->right) printNearNodes(p->right,l,h); } else { if(p->left) printNearNodes(p->left,l,h);
Continue Reading “Some Microsoft Interview Problem Solution”
Problem Description: Given a singly linked list: A0→A1→→An-1→An,reorder it to: A0→An→A1→An-1→A2→An-2→ Given 1->2->3->4->5 its reorder is 1->5->2->4->3. It is recommended do this in-place without altering the nodes’ values. Input: In this problem, methodtakes one argument: Address of the head of the linked list. The function should not read any input from stdin/console. The node structure