Basic Data structure questions

Comments

Post a Comment

Popular posts from this blog

[16 Feb 2020] Given an array where every element occurs three times, except one element which occurs only once.

Find the element that appears once Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space. Examples : Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3} Output: 2 In the given array all element appear three times except 2 which appears once. Input: arr[] = {10, 20, 10, 30, 10, 30, 30} Output: 20 In the given array all element appear three times except 20 which appears once. Following is another O(n) time complexity and O(1) extra space method suggested by aj. We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence. Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000 Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0; Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of
Read more

Which data structure is used in redo-undo feature?

Explanation:  Stack data structure is most suitable to implement redo-undo feature. This is because the stack is implemented with LIFO(last in first out) order which is equivalent to redo-undo feature i.e. the last re-do is undo first. Consider a situation where a client receives packets from a server. There may be differences in speed of the client and the server. Which data structure is best suited for synchronization? (A)  Circular Linked List (B)  Queue (C)  Stack (D)  Priority Queue Answer:   (B) Explanation:  Since packets need to be processed in First In First Out order, a queue can be used for synchronization. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. o Delection of the smallest element o Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose? (
Read more

Important Program Collection

C/C++ Greedy Algorithm Programs C/C++ Program Activity Selection Problem C/C++ Program Kruskal’s Minimum Spanning Tree Algorithm C/C++ Program for Huffman Coding C/C++ Program for Efficient Huffman Coding for Sorted Input C/C++ Program for Prim’s Minimum Spanning Tree (MST) C/C++ Program for Prim’s MST for Adjacency List Representation C/C++ Program for Dijkstra’s shortest path algorithm C/C++ Program for Dijkstra’s Algorithm for Adjacency List Representation C/C++ Program for Graph Coloring C/C++ Program for Rearrange a string so that all same characters become d distance away C/C++ Backtracking Programs C/C++ Program to print all permutations of a given string C/C++ Program The Knight’s tour problem C/C++ Program for Rat in a Maze C/C++ Program for N Queen Problem C/C++ Program for Subset Sum C/C++ Program for m Coloring Problem C/C++ Program for Hamiltonian Cycle C/C++ Program for Sudoku C/C++ Program for Tug of War C/C++ Program for (S
Read more