Software Engineer interview questions – page 7

Implement LRU cache.

What is difference between ADBMS and DBMS?

Why u want do job?(why ur not doing post graduation?)

What will u do if ur from java background and company requires .NET peoples,not java peoples

Why this Company ?and some information about company( like achivements)

Object oriented software engg definition(definition contains word"framwork") ?and definitionof framwork

4)Given a set of integers, Display the non-empty subsets whose sum is zero. For example, given the set { -7, -3, -2, 5, 8}, the answer is the subset { -3, -2, 5} which sums to zero. This is the special case of knapsack problem and hence it is NP- Complete so i said we cannot find the solution in polynomial time.We consider all the subsets with k elements. Then check how many of these sets have a sum of 0. This is an exponential time algorithm

5)Create a data structure where inserting, deleting and finding the minimum element all have O(1) time. i said we can use augmented stack where with each element we can augment the minimum element along with its actual value.Then he said?what if you cannot create any new data structure but have to use only the previously available data structures? I replied that then we can use two stacks one to store the actual data and other to store the minimum values

3)In the same matrix mentioned above find the kth maximum element. I said that we just need to compare the last K x K sub matrix and to find the Kth element

You are needed to sort a given String. Trick is, you can send letter from any position only to the first of the string. Interviewer didnÂ't clear me as to if the letters are interchanged or the Ith position letter becomes the first letter of string

You start with A. In every step, A gets transformed to AB and B get transformed to BA. You are supposed to tell how many 'BB' will occur at Nth iteration. E.G. A AB ABBA ABBABAAB … So on

1)There are three types of balls arranged linearly in a random order Red, Green and Blue. Now your job is to sort them so that the Red balls are in front follwed by the Green balls and the Blue balls are pushed to the bask.This problem was the same as sorting the array of 0, 1 and 2. we can do this in o(n) using two pointers

2)Given an n x n matrix, where every row and column is sorted in increasing order. Given a number x, how to decide whether this x is in the matrix. The designed algorithm should have linear time complexity. a) Start with top right element b) Loop: compare this element e with x i) if they are equal then return its position ii) e x then move it to left (if out of bound of matrix then break return false) c) repeat the i), ii) and iii) till you find element or returned false

Beer overflow problem. Glasses are stacked like a pyramid onto a table. If you are given X liters of water to pour on the topmost glass, How much water will be held by each glass. Given, Xth glass an hold x liter and rest is over flown equally both sides. E.g. 10 glasses with 15 liter of water. Ans: 1 2 3 2.5 4.5 2

Sub Divide a Rectangle. Given a Rectangle of M X N. U have many smaller rectangles of M1 X N1 and so on. You have to divide the greater rectangle in such a way to minimize the wastage. Rules of division are, every cut is made horizontal or vertical to the whole block. In other words, if you start cutting a block from any side, you cut the whole block in that direction and you canÂ't stop in between and turn your knife by 90 degree or any angle for that matter

Javascript(Closures,Prototypes,Function/variable hoisting,Function expression vs function declaration,prototypal inheritance,modular pattern,JSONP,this)

Given two sides of a river having the same cities labeled in characters. Bridges are to be drawn from one side to another that can connect the same labels but the bridges shudnt cross each other. Find the max no of bridges that can be connected. Eg Side 1: A B C D Side 2: D C A B So bridges connecting A to A etc need to be made. But when A to A is connected above D to D is not possible. Dynamic programming solution exists

Implement a ctlr+f (find) functionality in a file. Make a data structure for this implementation

Given two sorted arrays find of size n and m. The n sized array has m spaces empty at the end. Code to merge these to arrays in single pass O(n+m).

Given a binary tree. Code to have each node point to the next node in the same level. Last element in the level must point to NULL

Make a set of all nodes that can occur in any path from a source to a destination in both directed as well as undirected graph. Note that a node can be visited any number of times not necessarily only once.

Easy one. How to make a linked list with for a number like 12345 must be stored in linked list as 1->2->3->4->5.

Given a string (say alpha) and a dictionary database from where I can find if a word is present in the dictionary by a O(1) time look up. Find if there exists a path from the root word(aplha) to leaf node having a single letter such that a child is formed by removing one letter at a time such that each word intermediately formed is also in the dictionery. Eg. If there is a path aplha->plha->pha->pa->a. And all the nodes are in dictionery. Dynamic programming solution exists

Implement an auto suggest in search engine. Like for google when u type max say maximum must be suggested in drop down. This is a problem on Information Retrieval.

Given a BST and two positions in a bst exchanged to give a violation in bst rule. Find the two elements and exchange them. Corner case to be considered is that root can also be a node which id exchanged

Given a set of n steps. A person can climb one or two steps at a time. Find the number of ways in which one can reach the nth step. (Easy stuff.. I probably wasn't doing good by this time)

Given many pairs intervals with their start and end. Find the maximum interval which intersects the maximum number of intervals. Look for corner cases again!

Design a Peer-to Peer sharing network like torrent. What all parameters would you like to consider?

You want to retrieve data about cricket players. Search string will be name. Also, we want first players having first 10/10000 hits. What data structures will you use to store data?

My CPI was 8.69, even then was asked why is it so low , why not 9 or above