sachin323
BAN USER- 1of 1 vote
AnswersA city represented by a rectangular matrix is divided into plot of lands, and the cost of each plot is known. Find the largest rectangular area of land we can buy, within a budget B.
- sachin323 in United States
4 6 7
3 5 2
2 4 5
B = 16| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 0of 0 votes
AnswersLets say we have to find a tallest line of the horizon from a given 2D array of the preprocessed image. The line starts at left most column of the Martrix and end at right most column of the matrix. To calculate the line you can only move left to right to 3 position, diagonally up , horizontally right and diagonally right i.e from a[i][j] you can move to a[i-1][j+1], a[i][j+1] and a[i+1][j+1].
- sachin323 in United States
When moving to the right we need to pick the highest value in the cell . We will do this for very row in column 0 i.e a[0][j] then we will pick the smallest value of the path we have got. The ans will the smallest of the all values we got from traversing all the path
I know this bit vague and I had hard time understanding the question but this what I understood
Lets say we have 3*3 array {{5,4,8}, {1,5,9}, {2,6,10}} . Now if we start from a[1][0] the possible path we can have
1 -> 6 -> 10 as we have to pick the highest value . Once we have this path we pick the smallest value on this path which is 1 . We repeat this for all rows in a[i][0] then among all those values pick the smallest one
Find the best line from the matrix.
I said we can do BFS to find best path but interviewer said time complexity of that is too high, need to do better than that.
Time complexity for BFS I think is Rows * 3^Colms as from any given cell we have 3 options to go to right (please confirm this as I not sure about it)| Report Duplicate | Flag | PURGE
Dropbox Software Engineer Algorithm - 1of 1 vote
AnswersGiven two list of unsorted intervals V1 and V2 write 2 functions 'OR ' and 'And' to return a new list
- sachin323 in United States
OR Function (union of list ): Input V1 = (2,4) (6,8) (1,3) V2 = (7,9) (2,5)
output = (1,5) (6,9)
And function : This will be intersection function and will return intersection of the lists| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 1of 1 vote
AnswersYou are given a string "abc" which is encoded like "123" where alphabets are mapped like a => 1 to z => 26. Now find out how many string can be formed by reverse engineering encode string "123".
- sachin323 in United States
For ex. given string "123" we can form 3 string "abc"(1,2,3), "lc" (i.e 12,3), "aw"(1,23).
for string "1234" we have following possible combinations, I might be missing some of them but you get the idea
{12, 3, 4}
{1, 23, 4}
{1, 2, 3, 4}| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersWrite code to Print the power set of given string
- sachin323 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersBar raiser round
- sachin323 in United States
Write code to return Kth smallest node from BST| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersWrite a Program for Dictionary which has functionality of lookup and insert . This program should be able to add words on the fly
- sachin323 in United States
I wrote simple code using HashTable
follow up
1) Now we are getting too many words what happens
me: Hashtable will dynamically resize resulting into performance hit . Also they might get hashed to same location as well as we might run out of main memory
2) Okay you are out of main memory , How will you scale this program
me: I will create buckets of HashTable lets say 26 buckets for one for each alphabet and would put them on different machines
3) Lets say you are out of memory on those machines too
me: Okay I need to put them on secondary storage . Here we can have fileSystem or Database . I chose database . I will create simple DB schema of BucketNumber and word .
I will use buckets on main memory as cache , if we are not able to find a word in the bucket then query databse with bucket number and words then remove the least number times looked up word (every time we lookup a word we increament the count i.e value in key,value pair on hashtable) from that bucket and add this word .
I mentioned that bottleneck in this case will be every time a word is not present we need to query DB which usually has high latency which will result into performance hit
4) Lets say we are okay with latency but what if we are getting inserting words between that are only between only in two buckets ex. words starting from a and b only| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersGiven following interface
Class NumberPool { int CheckOut() void Checkin(long long number) }
Write functionality for Number pool which has numbers from 0 to long long
- sachin323 in United States
Where checkout returns the next smallest available number from the pool and Checking accepts the number returned by user and adds back to pool .| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answerswrite a class Tool which will have a function void type() that every derived class should implement . A function Action() that every derived class can override . function init() which is available to only Tool and variable Name which will tell which class`s instance is this object
- sachin323| Report Duplicate | Flag | PURGE
FactSet Research Systems, Inc Software Engineer / Developer C++ - 0of 0 votes
AnswersWrite a poker function which will take an array of 5 ints and will return true if 2 elements and 3 elements are equal
- sachin323for ex . 10 5 10 5 5 returns true 5 10 10 10 5 returns true 1 5 10 10 10 returns false 1 2 3 4 5 returns false
| Report Duplicate | Flag | PURGE
FactSet Research Systems, Inc Software Engineer / Developer Algorithm - 0of 0 votes
AnswersRound 4:
- sachin323
write a insert function to insert into binary search tree node *insert(node *root);
Follow up :
Whats the problem with this ?
Ans: skewed tree for sorted inputs
Discuss algo that will avoid this ?| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersRound 1 :
suppose you are given a function void NumberofSum(int n) , write a code such that will print all the numbers that will sum up to n
- sachin323For Ex. n output 1 {1} 2 {(1,1) , (2)} 3 {(1,1,1), (1,2) , (3)} 4 {(1,1,1,1),(1,1,2),(1,3),(2,2) , (4)}
| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersThis was only technical question my interviewer was asking to every candidate he interviewed
- sachin323
What kind of questions u will ask to me if u have to design a Queue for me ?
i answered as
1) for data type u want it
he said int
2) It is going to contain very large numbers of objects
he said no
3)do u want to dynamically expanding
he said no , lets keep it simple
4)do want functionality of accessing any element in queue like At() function
interviewer : yes
5)Do u want min and max element functions
interviewer : yes
After this he kept saying what else what else and i was blank
he mentioned asking about environment would have been a good question like do want this queue for kernel for application or for Database
then he asked me to write a class which will implement this but he was rushing a lot kept saying we have very less time left so i end up writing queue full , queue empty , insert and pop conditions only
i must say i was bit disappointed by this interview as from CareerCup i have prepared for alot of coding question and from these kind of questions will everybody answer easily , how will they screen candidates| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Data Structures - -1of 1 vote
AnswersHi i interviewed today for MS on campus. Most of the questions were behaviral and only one technical question . It was half hr interview and my interviewer was rushing through interview quite a lot . I really have no idea how they are going to screen candidates just based on this
- sachin323
Tell me what you are doing now a days
i explained my work done at intern .| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Behavioral - 0of 0 votes
AnswersYou are given an array which consist of number between 0 to 5 digit range. Write a function which will return true or false, if array can be divided into 2 half such a that sum of the two half would be equal
- sachin323| Report Duplicate | Flag | PURGE
FlexTrade Software Engineer / Developer Arrays - 0of 0 votes
Answersa class contains 2 float and 1 double , what will be size of object ?
- sachin323
Now that class contains 2 floats and static double what will be size ? Reasons ?
Now it contains all static vars what will be size ? Why not Zero ?| Report Duplicate | Flag | PURGE
FlexTrade Software Engineer / Developer Object Oriented Design
void FindSumElem(int a[] , int size , int num){
vector<int> v;
for(int i = 0 ; i < size ; i++){
int index = i;
int sum = 0;
int j = i;
for(; j < size ; j++){
sum =sum + a[j];
v.push_back(a[j]);
if(sum == num){
cout << "Num found "<<num<< " " << sum << endl;
for(vector<int>::iterator it = v.begin() ; it != v.end() ; it++)
cout <<*it<<endl;
return;
}
if(sum > num ){
//make j point to next element
//EX. if a [] = {-1 , 0 ,3 } if previous j was at index 0 i.e. a[j] == -1
//now make it point to index 1 i.e a[j] == 0
//Basically i am skipping the element pointed by J as it is not part of solution
j = ++index;
//Flush the vector and start again
v.clear();
v.push_back(a[i]);
sum = a[i];
}
}
}
cout << "No such elements"<<endl;
}
int main( )
{
int a[] = {-1,0,3,4,5,6};
FindSumElem(a,6,9
);
return 0;
}
Guys your comments are welcome also try it with diff i/p and let me know of any bugs
P.S. please use Reply to Comment so i will come to know if anybody has replied
using namespace std;
typedef map<string,double> strmap;
void map_diff(strmap& map1,strmap& map2,strmap& result){
strmap::const_iterator it1 , it2;
it1 = map1.begin();
while(it1 != map1.end()){
result[(*it1).first] = (map2[(*it1).first] - (*it1).second);
it1++;
}
}
int main( )
{
strmap map1 , map2 , result;
map1["sac"] = 10.00;
map1["in"] = 50.00;
map1["an"] = 100.00;
map1["anu"] = 600.00;
map1["sj"] = 90.00;
map1["rbv"] = 10.89;
map2 = map1;
map_diff(map1,map2,result);
for(strmap::const_iterator it = result.begin(); it != result.end(); it++){
cout << (*it).first << " " << (*it).second << endl;
}
}
another possible solution is as below
//NOTE i have not compiled this code.
multimap<int,int> multimap;
for(i = 1 to 9 )
for(j = 1 to 9)
for(k = 1 to 9)
{
multimap[i + j + k] = (i*100+j*10+k);
}
//internally multimaps store the data in sorted order based on key
//so all the digit additions values will be stored in sorted order
//now get the iterators to traverse the multimaps and check for same digit addition values
multimap::iterator it;
multimap::iterator it2 = multimap.begin();
it2++; //make it point to 2nd map entry
for(it = multimap.begin();it2 != multimap.end();it2++)
{
if(it.first() == it2.first())
{
cout<<it.second()<<it2.second();
}
}
Given a matrix of characters M and an input string S, find if S occurs in M in horizontal or vertical direction.
- sachin323 March 27, 2010Any thoughts on this questions .
I think i should search the first char of string S in matrix which will take O(M*M) time then i think we can proceed in horizontal or vertical direction. I know this is very basic solution and interviewer is probably expecting better than this .