Data Structure interview questions – page 3

Database queries and normal forms

3. Some Basics on Data Base.

TO WRITE SOME ALGORITHM AND BASIC ABOUT DS

In binary search we have two comparisons one for greater than and other for less than the mid value. Optimize so that we need to check only once.

You are given two sorted lists of size m and n. Give an O(logm + logn) time algorithm for computing the kth smallest element in the union of the two lists

Given unsorted array and a no. X ,find 2 no. whose sum is X....a[i]+a[j]=X ...........do it in O(n)

Design the data structure & algorithm for elevator. Step by step, walk through the logic/algorithm of elevator moving up & when elevator is going down

You are given 2 arrays of size 'n' each. You need to stable-merge these arrays such that in the new array sum of product of consecutive elements is maximized. eg A= { 2, 1, 3} B= { 3, 7, 9} Stable merging A and B will give ...

Find a number from the array, which on sutracting with the given number gives minimum value ex: array= 2,5,6,8,9 gn number = 1 it should print 2 coz 1 - 2 = -1

What kind of data structure would you use to index annagrams of words? e.g. if there exists the word "top" in the database, the query for "pot" should list that.

An ASCII character is one byte long and the most significant bit in the byte is always '0'. b) A Kanji character is two bytes long. The only characteristic of a Kanji character is that in its first byte the most significant bit is '1'.

Suggest data structure for dictionary with features like * autocorrect * autocomplete * spellcheck

Rotate an array using reverse function.

Given array of integers, return an index such that it divides the array in 2 parts ,i.e.sum of all elements which are left side of the index = sum of all elements which are right side of the index. Do in linear time.

Design a hash table to store phone #s. Your job is to write a hash function that has a parameter username, and generate a key. Username is unique, length 5 and can be A-Z, 0-9, space. Write a hash function that generate keys without collisions and...

You are given an array of integers, say array1 of size n. You have to create another array (say array2) and fill its contents by following this rule: array2[i] will hold the value of the left-most integer from the range array1[i+1] to array1[n-1] ...

You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2**an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.

Design the data structures and algorithms for a LRU (Least Recently Used) Cache

Sort an array of size n containing integers between 1 and K, given a temporary scratch integer array of size K.

In a 2D matrix, a[i][j]= 1 if there is flight from city i to city j else a[i][j]=0 Code to find out all the pairs of towns connected by 1 hop flights.

Implement a superqueue DATA STRUCTURE ...like a queue with normal queue operations AND finding the maximum value in a constant amount of timeO(1)

Find out missing no. from a stack if two given stacks have same numbers

Suggest DS for polynomials. Write C program to add two polynomials.

There is an integer array. The array represent a graph which increases till one point and then start decreasing. WAP to find the maximum number in that array. Write production quality code which handles all the scenarios. He also checked various c...

Given an N arrays of size K each.. each of these K elements in the N arrays are sorted, each of these N*K elements are unique. Choose a single element from each of the N arrays, from the chosen subset of N elements. Subtract the minimum and maximu...

An array contains both positive and negative numbers in a random order. for example [-1,2,-3,4,5,6,-7,8,9]

Binary Search program has been given and asked us to write some test cases. I have not full gone through the code, so they must have given some defect in the code

Diff between typedef and define getbis function gives n bits from the position p of an binary no A.

Given a stream of incoming numbers. How will you output the fist n smallest numbers. how will you store them?

In a given array of elements like [a1, a2, a3, a4, ..... an, b1, b2, b3, b4, ....... bn, c1, c2, c3, c4, ........ cn]