CSE Company Interview Questions

PROBLEM : Given an input stream of n characters consisting only of small case alphabets the task is to find the first non repeating character each time a character is inserted to the stream. Example Flow in stream : a, a, b, c a goes to stream : 1st non repeating element a (a) a goes to stream : no non repeating element -1 (5, 15) b goes to stream : 1st non repeating element is b (a, a, b) c goes to stream : 1st non repeating element is b (a, a, b, c) Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains an integer N denoting the size of the stream. Then in the next line are x characters which are inserted to the stream. Output: For each test case in a new line print the first non repeating elements separated by spaces present in the stream at every instinct when a character is added to the stream, if no such element is present print -1. Constraints: 1<=T<=200 1<=N<=500 Exa...

PROBLEM : Given a Linked list of size N, the list is in alternating ascending and descending orders, your task is to complete the function sort() that sorts the given linked list in non-decreasing order. Example: Input List: 10->40->53->30->67->12->89->NULL Output List: 10->12->30->43->53->67->89->NULL Input: The function takes a single argument as input the reference pointer to the head of the linked list. There are T test cases and for each test case the function will be called separately. Output: For each test case function should return reference pointer to the head of the new linked list. Constraints: 1<=T<=100 1<=N<=100 0<=A[]<=10^3 Example: Input: 2 6 1 9 2 8 3 7 5 13 99 21 80 50 Output: 1 2 3 7 8 9 13 21 50 80 99 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : ----------------------------------------------------------------...

PROBLEM : Given a singly linked list containing n nodes. Modify the value of first half nodes such that 1st node’s new value is equal to the last node’s value minus first node’s current value, 2nd node’s new value is equal to the second last node’s value minus 2nd node’s current value, likewise for first half nodes. If n is odd then the value of the middle node remains unchanged. Note: Input in the linked list is like new node will be entered at the head position (1st position). Input: First line consists of T test cases. First line of every test case consists of N, denoting the number of nodes. Second line of every test case consists of Node of linked list. Output: Single line output, return the head of modified linked list. Constraints: 1<=T<=100 1<=N<=100 Example: Input: 2 5 10 4 5 3 6 6 2 9 8 12 7 10 Output: -4 -1 5 4 10 8 -2 4 8 9 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION :...

PROBLEM : Given two linked lists, your task is to complete the function makeUnion, that returns the union of two linked lists. Input: The function takes 2 arguments, reference pointer to the head of the first linked list (head1) and reference pointer to the head of the second linked list (head2). There are multiple test cases and for each test case this function will be called separately. Output: The function should return reference pointer to the head of the new list that is formed by the union of the two the lists. Note: The new list formed should be in non-decreasing order. Constraints: 1<=T<=100 1<=N<=103 Example: Input: 1 6 9 6 4 2 3 8 5 1 2 8 6 2 Output: 1 2 3 4 6 8 9 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* structure of the node is as struct node { int data; struct node* next; }...

PROBLEM : Given two linked lists, your task is to complete the function findIntersection, that returns the intersection of two linked lists. Input: The function takes 2 arguments, reference pointer to the head of the first linked list (head1) and reference pointer to the head of the second linked list (head2). There are multiple test cases and for each test case this function will be called separately. Output: The function should return reference pointer to the head of the new list that is formed by the intersection of the two the lists. Note: The new list formed should be in non-decreasing order. Constraints: 1<=T<=100 1<=N<=103 Example: Input: 1 6 9 6 4 2 3 8 5 1 2 8 6 2 Output: 2 6 8 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* structure of the node is as struct node { int data; struct n...

PROBLEM : Given Pointer/Reference to the head of a linked list, task is to Sort the given linked list using Merge Sort. You need to complete the function splitList() and mergeList(), which will be called by the function mergeSort(). void mergeSort(struct node** headRef) {     struct node* head = *headRef;     struct node* a, b;     if ((head == NULL) || (head->next == NULL))        return NULL;     splitList(head, &a, &b);     mergeSort(&a);     mergeSort(&b);     *headRef = mergeList(a, b); } The spliList() function takes three input, head of the linked list and references to two pointers that are initially null. The function changes these pointers so that will point to the two new splitted lists, left and right halves respectively. The function splits the linked list in to two halves just like in standard merge sort and store the two new head in pointer a and...

PROBLEM : Given a sorted singly linked list and a data, your task is to complete the function sortedInsert that inserts the data in the linked list in sorted way i.e. order of the list doesn't changes. Input: The function takes 2 arguments as input, reference pointer to the head of the sorted single linked list and an integer data value which is to be inserted in the list. There are multiple test cases and for each test case the function will be called separately. Output: For each test output will be space separated integers denoting the values of the linked list. Constraints: 1<=T<=100 0<=N<=100 -999<=A[]<=999 Example: Input: 2 6 25 36 47 58 69 80 19 2 50 100 75 Output: 19 25 36 47 58 69 80 50 75 100 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /* structure of the node of the list is a...

PROBLEM : Sort a linked list using insertion sort.     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     ListNode* insertionSortList(ListNode* head) {         if(head==NULL||head->next==NULL)             return head ;                     ListNode* list=NULL ;         ListNode* temp ;                 while(head){             temp=head->next ;     ...

PROBLEM : You are given a Double Link List with one pointer of each node pointing to the next node just like in a single link list. The second pointer which is arbitary pointer  which can point to any node in the list and not just the previous node. The task is to complete the function copyList which take one argument the head of the linked list to be copied and should return the head of the copied linked list. Input: You have to complete the method which takes one argument: the head of the linked list. You should not read any input from stdin/console. The struct Node has a data part which stores the data and a next pointer which points to the next element of the linked list and an arbitrary pointer (arb) which points to any arbitrary node . There are multiple test cases. For each test case, this method will be called individually. Output: Your function should return the head of the copied list. Constraints: 1 <=T<= 100 1 <=N<= 100 1 <=Q<= 100 ...

PROBLEM : Given two polynomial numbers represented by a linked list. The task is to complete the  function addPolynomial that adds these lists meaning adds the coefficients who have same variable powers. Example: Input:      1st number = 5x^2 + 4x^1 + 2x^0      2nd number = 5x^1 + 5x^0 Output:         5x^2 + 9x^1 + 7x^0 Input:      1st number = 5x^3 + 4x^2 + 2x^0      2nd number = 5x^1 + 5x^0 Output:         5x^3 + 4x^2 + 5x^1 + 7x^0 Input: The first line of input contains an integer T denoting the no of test cases. Then in the next line is an integer N denoting the no of terms of first polynomial. In the next line are N space separated pairs x and y where x denotes the coefficient and y denotes the power. Similarly In the next line is an integer M denoting the no of terms of the second polynomial and in the line following it are N space separated pairs for second ...

PROBLEM : Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     ListNode* partition(ListNode* head, int x) {         if(head==NULL||head->next==NULL)             return head ;       ...

PROBLEM : Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     ListNode* swapPairs(ListNode* head) {         if(head==NULL||head->next==NULL)             return head ;                   ...

PROBLEM : Sort a linked list in O(n log n) time using constant space complexity. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     ListNode* sortList(ListNode* head) {         if(head==NULL||head->next==NULL)             return head ;                     ListNode* a=NULL ;         ListNode* b=NULL ;         divide2half(head,&a,&b) ;         a=sortList(a) ;         b=sortList(b...

PROBLEM : Given a single linked list and an integer x your task is to complete the function deleteAllOccurances  which deletes all occurences of a key x present in the linked list. The function takes two arguments: the head of the linked list and an integer x. The function should return the head of the modified linked list. Input: The first line of input contains an element T, denoting the no of test cases. Then T test cases follow. Each test case contains three lines. The first line of each test case contains an integer N denoting the no of elements of the linked list. Then in the next line are N space separated values of the linked list. The third line of each test case contains an integer x. Output: The output for each test case will be the space separated value of the returned linked list. Constraints: 1<=T<=300 1<=N<=100 1<=x<=N Example(To be used only for expected output): Input: 2 5 2 2 1 4 4 4 6 1 2 2 3 2 3 2 Output: 2 2 1 1 3 3 ...

PROBLEM : Delete xth node from a single linked list. Your task is to complete the method deleteNode which takes two arguments:  the address of the head of the linked list and an integer x. The function returns the head of the  modified linked list. Input: The first line of input contains an element T, denoting the no of test cases. Then T test cases follow. Each test case contains three lines. The first line of each test case contains an integer N denoting the no of elements of the linked list. Then in the next line are N space separated values of the linked list. The third line of each test case contains an integer x. Output: The output for each test case will be the space separated value of the returned linked list. Constraints: 1<=T<=300 2<=N<=100 1<=x<=N Example(To be used only for expected output): Input: 2 3                       1 3 4             ...

PROBLEM : Given Linked List Representation of Complete Binary Tree, construct the Binary tree.Your task is to complete the function convert which takes two arguments the first being the head denoting the head of the linked list and the second argument is root denoting the root of the tree to be constructed. Note : The complete binary tree is represented as an linked list in a way where If root node is stored at position i, its left, and right children are stored at position 2*i+1, 2*i+2 respectively. Input: The first line of input is the no of test cases T. Then T test cases follow . Each test case contains 2 lines. The first line contains an integer N denoting the no of nodes of the linked list . Then in the next line are N space separated Ki values of the linked list . Output: Output of each test case will be the level order traversal of the the constructed binary tree. You do not have to  print it . Constraints: 1<=T<=100 1<=N<=100 1<=Ki <=10...

PROBLEM : Implement a Queue using Linked List. Input (To be used for Expected Output): The first line of the input contains an integer 'T' denoting the number of test cases. Then T test cases follow. First line of each test case contains an integer Q denoting the number of queries . A Query Q is of 2 Types (i) 1 x   (a query of this type means  pushing 'x' into the queue) (ii) 2     (a query of this type means to pop element from queue and print the poped element) The second line of each test case contains Q queries seperated by space. Output: The output for each test case will  be space separated integers having -1 if the queue is empty else the element poped out from the queue . You are required to complete the two methods push which take one argument an integer 'x' to be pushed into the quee  and pop which returns a integer poped out from othe queue. Constraints: 1<=T<=100 1<=Q<=100 1<=x<=100 Example: Input 1 5...

PROBLEM : Given a singly linked list of integers, Your task is to complete a function that returns true if the given list is palindrome, else returns false. Input: The first line of input contains an integer T denoting the no of test cases. Then T testcases follow. Each test case contains 2 line the first line contains an integer N denoting the size of the linked list. In the next line are N space separated values of the nodes of the linked list. Output: For each test case output will be 1 if the linked list is a pallindrome else 0. Constraints: 1<=T<=1000 1<=N<=50 Example(To be used only for expected output): Input 2 3 1 2 1 4 1 2 3 4 Output: 1 0 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /*The structure of the Node is struct Node {     int data;     struct Node* next; };*...

PROBLEM : Given two linked lists that represent two large positive numbers. Your task is to complete the function SubLinkedList which takes two arguments l1 and l2. The function subtracts the smaller number from larger one and return a pointer to the resultant linked list. Input The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains an integer n denoting the size of the first linked list (l1)  In the next  line are the space separated values of the first linked list. The third line of each test case contains an integer m denoting the size of the second linked list (l2). In the forth line are space separated values of the second linked list . Output: For each test case output will be space separated values of the resultant linked list. Constraints: 1<=T<=100 1<=n,m<=100 Example: Input: 1 3 1 0 0 1 1 Output: 0 9 9 --------------------------------------...

PROBLEM : The task is to complete the function  multiplyTwoLists which multiplies two linked lists l1 and l2 and returns their product . The function takes two linked list l1, l2 as its arguments. Note: The output could be large take modulo 10^9+7. Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains an integer n denoting the size of the first linked list (l1)  In the next  line are the space separated values of the first linked list. The third line of each test case contains an integer m denoting the size of the second linked list (l2). In the forth line are space separated values of the second linked list . Output: For each test case output will be an integer denoting the product of the two linked list. Constraints: 1<=T<=100 1<=n,m<=100 Example(To be used only for expected output): Input 2 2 3 2 1 2 3 1 0 0 2 1 0 Output 64 1000 ...