Data Structure Interview Questions and Answers – Page 18

What is a complete binary tree?

You have to make a package library which will do the calculation of (a^b)mod(c), where a, b, c are very large size of 10000 digits. (^- power). Design a data structure for the numbers' storage and suggest what functions will you be providing to us...

Find the two nodes in Binary Tree which have longest distance between them.

There are two singly linked lists l1 and l2 representing polynomials in X. we have to find difference b/w lists l1-l2. Lists are in orders of descending powers. Constraints: no extra space i.e., O(1) space O(m+n) time complexity....

Given a binay tree, all nodes follow to make tree BST except one. Find out that node.

Design a layer in front of a system which cache the last n requests and the responses to them from the system. what data structure would you use to implement the cache in the later to support following operations. [a] When a request comes lo...

Find the number of occurrences of a given number in a sorted array.

Given a preorder traversal of a binary search tree, find the inorder traversal

Given a number of words.. how do you search in a dictionary in best optimized way........For searching a new word.. you might need to start from the first in the dictionary..

Given a string S of words and no of character per line m, with m being greater than the longest word in S, print S in a set of lines so that each line contains no more than m characters and no word split between 2 lines.

Write code to check whether given tree is BST or not. ( initially I gave O(n^2) he said optimize then I gave O(n) and O(n) space then he said we don't have this much space then I was able to do in O(n) and O(1) space). 3. Whether code is thr...

There is a linked list of numbers of length N. N is very large and you dont know N. You have to write a function that returns k random numbers from the list. Numbers should be completely random.

A Binary tree ( Need not be BST) node has three pointers. Left child, right child and parent pointer. Another pointer is added called ExtraID which points to either NULL or one of the inorder successor. Inorder successor means , if we list nodes i...

Delete the node from link list,You have the pointer of that node only?

Consider an array 'A' of n elements. Let A[0] to A[k-1] ( The first K members of the array A ) form the first window of the array where 0<k<n. Now you have to find the maximum number of the window and display it. After displaying it the wind...

Given that, there are 2 linked lists L1 and L2. The algorithm finds the intersection of the two linked lists. i.e' "L1 intersection L2 " ( similar to intersection of 2 sets ). Write all the possible test cases involved in the above given problem. ...

Write a C Program to reverse a string. Explain it.

Write a program to check whether a given binary tree is mirror of itself.

Find the median of two sorted arrays. Eg. a1[] = {1, 2, 7, 8} a2[] = {3, 9, 12, 23}, then find the median of the array created by merging them, ie {1 2 3 7 8 9 12 23}

Given an inorder traversal only for a binary tree (not necessarily a BST), give a pseudo code to generate all possible binary trees for this traversal sequence.

Write a function that returns a node in a tree given two parameters: pointer to the root node and the inorder traversal number of the node we want to return. The only information stored in the tree is the number of children for each node.

Write a function which finds a substring in a string and replaces all occurrences with another string. Prototype of the function : char* FindReplace(char* src, char* find, char* replace);

Remove Repeated Characters in a string in a language of 2^40 characters

You are given a string. Develop a function to remove duplicate characters from that string. String could be of any length. Your algorithm must be in space. If you wish you can use constant size extra space which is not dependent any how on string ...

Implement a Queue using a Stack ADT. He told me to write tight code for this as well. He wanted optimized methods for this, and asked me to enumerate different ways of optimizing this data structure, and to analyze each one. After I did that...

You have a BST containing integers. Now given any two numbers x and y, how do u find the common ancestor of nodes which have these values in them. You are given pointer to root of the BST

Design a data structure where push is similar to normal queue, but pop deletes one instance of the last inserted most-frequently occuring element.

Given a BST and 2 integers m and n, print all the elements greater than equal to m and less than or equal to n

Given a binary tree, in this binary tree every node has left, right and sibling pointers. For all the nodes sibling pointer is pointed to unknown. Write an algorithm to point every node sibling pointer to its actual sibling expecting to do t...

Given the numbers from 1 to n, write an algorithm to find how many distinct binary search trees can be formed.. eg n=4, no of distinct bst's are 14. ??