My Hindi Forum - View Single Post

sunita · 13-12-2009, 09:48 PM

Create a fast cached storage mechanism that, given a limitation on the amount of cache memory, will ensure that only the least recently used items are discarded when the cache memory is reached when inserting a new item. It supports 2 functions: String get(T t) and void put(String k, T t).

Create a cost model that allows Google to make purchasing decisions on to compare the cost of purchasing more RAM memory for their servers vs. buying more disk space.

Design an algorithm to play a game of Frogger and then code the solution. The object of the game is to direct a frog to avoid cars while crossing a busy road. You may represent a road lane via an array. Generalize the solution for an N-lane road.

What sort would you use if you had a large data set on disk and a small amount of ram to work with?

What sort would you use if you required tight max time bounds and wanted highly regular performance.

How would you store 1 million phone numbers?

Design a 2D dungeon crawling game. It must allow for various items in the maze - walls, objects, and computer-controlled characters. (The focus was on the class structures, and how to optimize the experience for the user as s/he travels through the dungeon.)

What is the size of the C structure below on a 32-bit system? On a 64-bit?
struct foo {

char a;
char* b;
};

Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.
Implement put/get methods of a fixed size cache with LRU replacement algorithm.

You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.
Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))" Please give a solution in O(n) time complexity

How does C++ deal with constructors and deconstructors of a class and its child class?

Write a function that flips the bits inside a byte (either in C++ or Java). Write an algorithm that take a list of n words, and an integer m, and retrieves the mth most frequent word in that list.

What's 2 to the power of 64?

Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?

How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.

Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?

There is linked list of millions of node and you do not know the length of it.
Write a function which will return a random number from the list.

You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?
How long it would take to sort 1 trillion numbers? Come up with a good estimate.

Order the functions in order of their asymptotic performance: 1) 2^n 2) n^100 3) n! 4) n^n

There are some data represented by(x,y,z). Now we want to find the Kth least data. We say (x1, y1, z1) > (x2, y2, z2) when value(x1, y1, z1) > value(x2, y2, z2) where value(x,y,z) = (2^x)*(3^y)*(5^z). Now we can not get it by calculating value(x,y,z) or through other indirect calculations as lg(value(x,y,z)). How to solve it?

How many degrees are there in the angle between the hour and minute hands of a clock when the time is a quarter past three?

Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element.

Given two linked lists, return the intersection of the two lists: i.e. return a list containing only the elements that occur in both of the input lists.

What's the difference between a hashtable and a hashmap?

If a person dials a sequence of numbers on the telephone, what possible words/strings can be formed from the letters associated with those numbers?

How would you reverse the image on an n by n matrix where each pixel is represented by a bit?

13-12-2009, 09:48 PM	#3
sunita Member Join Date: Dec 2009 Posts: 64 Rep Power: 15	More Questions for Software Engineers Create a fast cached storage mechanism that, given a limitation on the amount of cache memory, will ensure that only the least recently used items are discarded when the cache memory is reached when inserting a new item. It supports 2 functions: String get(T t) and void put(String k, T t). Create a cost model that allows Google to make purchasing decisions on to compare the cost of purchasing more RAM memory for their servers vs. buying more disk space. Design an algorithm to play a game of Frogger and then code the solution. The object of the game is to direct a frog to avoid cars while crossing a busy road. You may represent a road lane via an array. Generalize the solution for an N-lane road. What sort would you use if you had a large data set on disk and a small amount of ram to work with? What sort would you use if you required tight max time bounds and wanted highly regular performance. How would you store 1 million phone numbers? Design a 2D dungeon crawling game. It must allow for various items in the maze - walls, objects, and computer-controlled characters. (The focus was on the class structures, and how to optimize the experience for the user as s/he travels through the dungeon.) What is the size of the C structure below on a 32-bit system? On a 64-bit? struct foo { char a; char* b; }; Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure. Implement put/get methods of a fixed size cache with LRU replacement algorithm. You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum. Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))" Please give a solution in O(n) time complexity How does C++ deal with constructors and deconstructors of a class and its child class? Write a function that flips the bits inside a byte (either in C++ or Java). Write an algorithm that take a list of n words, and an integer m, and retrieves the mth most frequent word in that list. What's 2 to the power of 64? Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one? How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge? There is linked list of millions of node and you do not know the length of it. Write a function which will return a random number from the list. You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number? How long it would take to sort 1 trillion numbers? Come up with a good estimate. Order the functions in order of their asymptotic performance: 1) 2^n 2) n^100 3) n! 4) n^n There are some data represented by(x,y,z). Now we want to find the Kth least data. We say (x1, y1, z1) > (x2, y2, z2) when value(x1, y1, z1) > value(x2, y2, z2) where value(x,y,z) = (2^x)(3^y)(5^z). Now we can not get it by calculating value(x,y,z) or through other indirect calculations as lg(value(x,y,z)). How to solve it? How many degrees are there in the angle between the hour and minute hands of a clock when the time is a quarter past three? Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element. Given two linked lists, return the intersection of the two lists: i.e. return a list containing only the elements that occur in both of the input lists. What's the difference between a hashtable and a hashmap? If a person dials a sequence of numbers on the telephone, what possible words/strings can be formed from the letters associated with those numbers? How would you reverse the image on an n by n matrix where each pixel is represented by a bit?