Data Structure interview questions – page 21

You are given a special kind of binary tree, in which there is another attribute, grandparent, which is a pointer to the grandparent of a node. The tree structure is thus,

Given two values k1 and k2 and a root pointer to a BST. Print all numbers b/w k1 and k2 in increasing order i.e. k1<=x<=k2 where x is an element of tree.

2. Given a binary tree , write a function to determine whether its a balanced binary tree. A tree is said to be balanced if for every node, difference in height of the sub trees are not more than 1.

Given a string of words, number of spaces between words can be any number more than 1. Write a program to squeeze all multiple spaces into one space.

Given an array of integers, we have to find out the [b]Minimum Non-negative sum[/b] in the array ([b]not necessarily continuous[/b]).

Insert a node into a circular linked list. This CLL is sorted. So, if the CLL is like 1->2->4->6->1 you will be asked to input a node 3 and it must come between 2 and 4. Write a program for this in C++ or JAVA

Given a linked list in sorted order,now it is broken at a point and rearranged.

Code to delete a node in a circular linked list

Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.

Details of hash table and heaps.

Print a singly linked list in reverse order

Given a word and a file containing words in the dictionary find anagrams of that word.

Write a code of Merge sort on Linked list.

WAP for inplace removal of vowels from a char string

Write code for image of binary tree

Find the number of strings of length n having u uppercase letters , l lowercase letters and d digits

Write a preorder traversal of a binary search tree w/o recursion / stack / extra memory storage. Hint - you can augment the node data structure. However, you can&#39;t add a visited field to the node.

Given a large linked list and a small linked list, efficiently find the common elements in two LLs.

Sort the Doubly Linked List..In Minim time complexity...is it possible to sort doubly linked list in O(n)..can some one provide..tutorial ,code or algo fro this

Given an array. The array is sorted and rotated around an unknown point. Suggest a O(logn) algo for finding the index of unknown point.

Given an n-ary tree. requirement it to convert the elements in such a manner that every parent is median of its children.

Input is a matrix of size n x m of 0s and 1s.

Given a preorder traversal build a valid binary search tree. Write code covering all possible cases.

Merge two BST into One. BST t2 is merged into BST t1.

Write an inplace strrev routine

String searching without the use of any inbuilt APIs. You are given a chunk of data and another random chunk that needs to be searched for. You cannot use any kind of String/Regex API

Minimum no of comparisons to find min and max in an array on n elements.

Discuss data structures for designing NOTEPAD. Discuss with reference to buffer write.

You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create another array ar_low[] such that ar_low[i] = number of elements lower than or equal to ar[i] in ar[i+1:n-1]. So the output of above should be {0,2,1,2,2,1,0}

How do you rotate a string of length n word by word with constant extra space in linear time (wrt n) ?