Data Structure interview questions – page 5

Given an array of size 100. The elements of the array are not sorted. What is the average number of comparisons needed in a sequential search to determine that the element being searched is not there?

Given an array with some repeating numbers. Like 12,6,5,12,6

Given a 2D array which has all columns sorted and all rows sorted. Find the kth largest element in such array.

Assume that index i is within the stack size. Stack is implemented using an array A[1, ... N] and index variable is i push and pop operations are defined as below push: start A=x, i=i+1 pop: start i=i-1, x=A to implement stack co...

In order to make N size queue how many N size stacks are needed ? Answers: a) 1 b) 2 c) 3 d) 4

A sorted array is rotated any number of times now write a code to search a number in this array (without disrupting the original elements in the array)

Given an array (length n), we need to find the subarray (length k) such that the sum of the first j elements of the subarray equals the sum of the remaining (k-j) elements of the subarray. For e.g. Array: 2,2,13,4,7,3,8,12,9,1,5 ...

Given an unsorted array of positive integers and an integer N, return N if N exist in the array or the first number that is smaller than N.

Given an array containing numbers from 1 to N. Numbers are in also in range from 1 to N. Some numbers are missing and some numbers are repeated more than once. Find the missing numbers in O(n)

Given a linked list with a set of elements , group the elements into even and odd numbers. Example. Input: 1->4->6->7->10->13 Output: 1->7->13-> or 4->6->10->1->7->13 The output can be any o...

In a 2D-Matrix, there is one row which is equal to a particular column. Find that particular row and Column in the most efficient way possible. eg. 1 2 4 6 4 7 7 8 3 9 7 2 1 4 8 5

What kind a data structure will you use to implement an Instant Search feature.

You are given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of time. We have to find these duplicating numbers in O(n) and using only constant memory space. for eg suppose ...

In a boolean array, find the maximum size submatrix with all 1s (Note that its not the maximum square submatrix).

Design a datastructure to implement a stack such that ALL of push(), pop() and getMax() functions work in O(1) time. You have infinite memory at your disposal. Also note that function getMax() just returns the element with maximum value in t...

Given a sorted array arr[] and a number a, count the no. of occurences of x in arr[]. Logn solution expected.

Find the element from unsorted array whose sum is equal to given number S.

More on Hash tables, Chaining, Modulus, and Linked Hashing.

Find the two numbers whose difference is minimum among the set of numbers.

Given an m-ary tree, need to implement two functions lock and unlock on a node n. You can lock a node if none of the nodes in its subtree is locked and none of its ancestors are locked. Unlocking a node should release the lock. Suggest a good data...

An array contains the set of positive integer. Find the largest number c such that c=a+b where a,b,c are distinct number of the set? [Consider , reducing complexity]

Insert an element into a sorted linked list

Write a program to print the below shown array in spiral form. int a[][]={2,3,4, 6,7,8, 1,2,3} The output should be 234832167

In a array of size n, there is one number missing and one number repeated twice. Find them.

An external system has an array. You are given 3 inbuilt functions which perform their operation in O(1) time.

You have 1000 names in random order and i ask you to pick any name of my choice randomly and then give me complete info of that person so what data structure yuo will use to store person info?

Initially next_larger of every node is point to NULL. now write a c code which set all node's next_larger pointer. where next_largest point ...

An array of integers. The sum of the array is known not to overflow an integer. Compute the sum. What if we know that integers are in 2's complement form?

Given a sorted array and a number n , find the number of occurrences of that number in the array .

Find the longest repeated substring given an input string. eg. given "banana" you should find "anana"