Join Regular Classroom : Visit ClassroomTech

Tally Solutions Interview Questions + Coding Solutions – codewindow.in

Hot Topics

Tally Solution

Technical Round

Design an algorithm to search an element in a singly linked list in O (1) complexity without using any other data-structure.

It is not possible to search an element in a singly linked list with O(1) complexity without using any other data structure. The reason is that in a singly linked list, to find an element, we need to traverse the list one-by-one starting from the head of the list to find the element. The the time complexity of traversing a singly linked list is O(n) where n is the number of elements in the list.
if you are allowed to use some other data structure, one possible approach to achieve O(1) search complexity would be to use a hash table to store the elements of the linked list as the keys, and their corresponding addresses in the memory as the values.
Here is an example of an algorithm to search an element in a singly linked list using a hash table:
  1. Create an empty hash table.
  2. Traverse the singly linked list and for each element of the list, insert the element as the key and its memory address as the value into the hash table.
  3. Now, to search for an element in the singly linked list, we can simply use the hash table's O(1) search complexity by providing the element as the key and retrieve its memory address.
  4. Once we have the memory address of the element, we can easily access the element from the singly linked list.

You need to develop a text-editor. What is the data structure that you'll use to store the data? It should consume minimum possible memory, and should be able to support most of the basic functions of a text editor

B-trees are a type of balanced tree data structure that stores large amounts of data on disk or in memory. Each node in a B-tree contains a set of keys, along with corresponding values or pointers to values, and also, it has pointers to its children. B-trees are optimized for efficient read and write operations, and are often used in databases and file systems to store large amounts of data.
One of the main advantages of using a B-tree is that it is highly memory efficient. Because B-trees are balanced tree data structure, the height of the tree is logarithmic with respect to the number of elements, which reduces the memory required to store large strings. Additionally, B-trees allows for efficient insertion, deletion, and search operations which are basic functionalities of a text editor.
B-trees can be used along with a Trie data structure to implement the auto-complete functionality of the text editor.

Find loop in Linked List.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

class Node{
    public:
    int data;
    Node* next;
    Node(int data){
        this->data=data;
        this->next=NULL;
    }
};

void push(Node* &head,int data){
    Node* temp=new Node(data);
    temp->next=head;
    head=temp;
}

Node* detectLoop(Node* &head){
    if(head==NULL || head->next==NULL){
        return head;
    }
    Node* slow=head;
    Node* fast=head;
    
    while(slow!=NULL && fast!=NULL){
        fast=fast->next;
        if(fast!=NULL){
            fast=fast->next;
        }
        slow=slow->next;
        if(fast==slow){
            return slow;
        }
    }
    return NULL;
}

int main() {
    
    Node* head=NULL;
    
    push(head, 20);
    push(head, 4);
    push(head, 15);
    push(head, 10);
    
    head->next->next->next->next = head;
 
    if (detectLoop(head))
        cout << "Loop Found";
    else
        cout << "No Loop Found";

    return 0;
}
/*
output:
Loop Found
*/

Sort 0’s, 1’s and 2’s in linked list.

#include <bits/stdc++.h>
using namespace std;

class Node{
    public:
    int data;
    Node* next;
    Node(int data){
        this->data=data;
        this->next=NULL;
    }
};

void push(Node* &head,int data){
    Node* temp=new Node(data);
    temp->next=head;
    head=temp;
}

void insertAtTail(Node* &tail,Node * curr){
    tail -> next = curr;
    tail = curr;
}

Node* sortList(Node* &head){
    Node* zeroHead=new Node(-1);
    Node* oneHead=new Node(-1);
    Node* twoHead=new Node(-1);
    
    Node* zeroTail=zeroHead;
    Node* oneTail=oneHead;
    Node* twoTail=twoHead;
    
    Node* curr=head;
    
    while(curr!=NULL){
        int value=curr->data;
        
        if(value==0){
            insertAtTail(zeroTail,curr);
        }
        else if(value==1){
            insertAtTail(oneTail,curr);
        }
        else if(value==2){
            insertAtTail(twoTail,curr);
        }
        curr=curr->next;
    }
    
    if(oneHead->next != NULL){
        zeroTail->next=oneHead->next;
    }
    else{
        zeroTail->next=twoHead->next;
    }
    oneTail->next=twoHead->next;
    twoTail->next=NULL;
    head=zeroHead->next;
    
    delete zeroHead;
    delete oneHead;
    delete twoHead;
    
    return head;
}

void display(Node* head){
    Node* curr=head;
    while(curr!=NULL){
        cout<<curr->data<<" ";
        curr=curr->next;
    }
    cout<<endl;
}

int main() {
    
    Node* head=NULL;
    
    push(head, 0);
    push(head, 2);
    push(head, 0);
    push(head, -1);
    push(head, 2);
    push(head, 0);
    push(head, 1);
    
    display(head);
    sortList(head);
    display(head);
    
    return 0;
}
/*
output:
1 0 2 -1 0 2 0 
0 0 0 1 2 2 
*/

What is polymorphism?

Polymorphism is briefly described as “one interface, many implementation”. Polymorphism is a characteristic of being able to assign a different meaning or usage to something in different contexts specifically, to allow an entity such as a variable, a function, or an object to have more than one form. There are two types of polymorphism:
  1. Compile time polymorphism
  2. Run time polymorphism

What is static variable and puzzle?

A static variable creates a single copy of the variable and is shared among all the objects at a class level.
A puzzle is a problem or game that tests a person's ingenuity or knowledge.  Puzzles can be used for entertainment, education, and to develop problem-solving skills.

In a circular ground you have a stop watch how you would reach the centre.

  1. Start the stopwatch and begin walking in any direction along the circumference of the ground.
  2. As you walk, periodically check the stopwatch to measure the time it takes to complete one full lap around the circumference of the ground.
  3. Once you have accurately measured the time it takes to complete one full lap, use this information to calculate the distance to the center of the ground.
  4. Once you have calculated the distance, you can use this information to estimate the location of the center of the ground.
  5. Continue walking in the same direction, while periodically checking the stopwatch and using the distance to the center to guide you towards the center of the ground.
  6. Once you reach the center of the ground, stop the stopwatch.

Find number of elements in longest palindromic substring puzzle.

The length of the longest palindromic substring in a string can be found using various algorithms, such as the Manacher algorithm, the Dynamic Programming approach, or the Brute Force method. The specific algorithm you choose will determine the time and space complexity of finding the longest palindromic substring. The length of the longest palindromic substring will represent the number of elements in the longest palindromic substring

What is malloc() function in C?

malloc () or “memory allocation” method in C is used to dynamically allocate a single large block of memory with the specified size. It returns a pointer of void type which can be cast into a pointer of any form. It initializes each block with default garbage value.
Syntax: ptr = (cast_type*) malloc (byte_size)

What is a ledger?

A ledger is a book or a set of books used for recording financial transactions. It is the primary record-keeping tool for a business or organization's financial activities.

Reverse linked list in groups.

#include <bits/stdc++.h>
using namespace std;

class Node{
    public:
    int data;
    Node* next;
    Node(int d){
        this->data=d;
        this->next=NULL;
    }
};

void insertAtHead(Node* &head, int d) {

    // new node create
    Node* temp = new Node(d);
    temp -> next = head;
    head = temp;
}

void print(Node* head){
    Node* curr=head;
    while(curr!=NULL){
        cout<<curr->data<<" ";
        curr=curr->next;
    }
    cout<<endl;
}

Node* reverse(Node* &head,int k){
    Node* temp=head;

    for(int i=0;i<k;i++){
        if(temp==NULL){
            return head;
        }
        temp=temp->next;
    }

    int count=0;
    Node* curr=head;
    Node* prev=NULL;
    Node* forward=NULL;
    
    while(curr!=NULL && count<k){
        forward=curr->next;
        curr->next=prev;
        prev=curr;
        curr=forward;
        count++;
    }

    if(forward!=NULL){
        head->next=reverse(forward,k);
    }
    return prev;
}

int main() {
    
    Node* node = new Node(5);
    Node* head = node;
    Node* curr = head;
    Node* prev = NULL;
    
    insertAtHead(head,4);
    insertAtHead(head,3);
    insertAtHead(head,2);
    insertAtHead(head,1);
    
    print(head);
    cout<<head->data<<endl;
    reverse(head,2);
    print(head);

    return 0;
}
/*
output:
1 2 3 4 5 
1
1 4 3 5 
*/

What do you mean by tally?

A tally is a method of counting and recording numbers or quantities. It is often used to keep track of a certain item or items, typically by making a mark or marks for each item counted. The marks are usually made on a piece of paper or a board, but can also be made electronically. Tallying is used for many things such as counting votes, counting attendance, counting inventory and many more. The marks made on a tally sheet are called tallies.

Nagarro Solved

Automata Fixing

      

We Love to Support you

Go through our study material. Your Job is awaiting.

Recent Posts
Categories