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
The solution I gave was to apply regular merge interval code to 2 list
1. Sort both lists by their end time
2. Run merge overlapping interval function on each list geeksforgeeks.org/merging-intervals/
3. Now add the two lists and sort by end time
4. Again apply merge overlapping interval function on this list, result will be your ans
Optimized version of above algo is to merge two list, after the step 2 in the above algo, all we need to do is extract 1 interval from each merged list and merge them and then check this merged interval with last interval in the result list to see if it can be merged too
I think you code has few bugs for input "11111" count should be 5 but your code outputs 4. Also for if (i + i < c.length) it should be if (i + 1 < c.length).
Following is the corrected code
public static int numStrings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] c = s.toCharArray();
int charVal = -1;
int count = 0;
for (int i = 0; i < c.length; i++) {
if (i + 1 < c.length) {
String temp = Character.toString(s.charAt(i)) + s.charAt(i + 1);
charVal = Integer.parseInt(temp);
if (charVal >= 0 && charVal <= 26) {
System.out.println(temp);
count++;
}
}
}
return ++count;
}
No , its basically you have a pool of number from 0 to long long and every time you do a checkout you get the next min number now once you are done with the number you can check it back in by checkin() function . Think of these numbers like some kind of token system
- sachin323 June 03, 2013sweeeet !! U r hired !! :)
Actually this was what he was looking , i had written some what similar code like this but i had hard time figuring out the recursive calling part of it , In the end he said he was kind of glad that i reached there but u know actually i took more than 30mins to get that incomplete code .
Anyways above code works it has some typos so here it is without those typos and it works in VS 2008
void NumSum(int targetSum, vector<int> v, int startVal, int partialSum)
{
if (partialSum == targetSum)
{
printf( "{");
for (int i=0; i < v.size(); i++)
{
printf ("%d , ", v[i]);
}
printf( "}");
return;
}
for (int i = startVal; i < targetSum;i++)
{
if (i+partialSum <= targetSum)
{
v.push_back(i);
NumSum(targetSum, v , i, partialSum+i);
v.pop_back();
}
}
}
void NumberofSum(int n)
{
vector <int> v;
for (int i=1; i <= n;i++)
{
printf("{");
NumSum(i , v, 1, 0);
printf("}\n");
v.clear();
}
}
I took a while to reach to ans as this was binary tree , the solution i had given there was
1) get preoder and inorder
2) take first element in prorder and search it into inorder all the element to left of it is left subtree and on right are right subtree
3)find the index of node1 and node2 in inorder , if one appears on the left of root and other on the right then return root as ans
4) if both appear on left side , discard all the elements right to root , same with if they appear on the right of root
5) increament index in preorder
6) continue this recursively
int numBSTnodes(const node* pNode){
if(pNode == NULL) return 0;
return (numBSTnodes(pNode->left)+numBSTnodes(pNode->right)+1);
}
//This function will find Kth smallest element
node* findKthSmallestBSTelement(node* root, int k){
node* pTrav = root;
while(k > 0){
int numNodes = numBSTnodes(pTrav->left);
cout << "Nodes ::" << numNodes << endl;
if(numNodes >= k){
pTrav = pTrav->left;
}
else{
//subtract left tree nodes and root count from 'k'
k -= (numNodes + 1);//(numBSTnodes(pTrav->left) + 1);
if(k == 0) return pTrav;
pTrav = pTrav->right;
}
}
return NULL;
}
/*
To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:
Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).
Initially, let p equal 2, the first prime number.
Strike from the list all multiples of p less than or equal to n. (2p, 3p, 4p, etc.)
Find the first number remaining on the list after p (this number is the next prime); replace p with this number.
Repeat steps 3 and 4 until p2 is greater than n.
All the remaining numbers in the list are prime.
*/
void GeneratePrimes(int N){
bitset<1000> b;
for(int i = 2; i < N; i++){
if(!b[i]){
//Mark all multiples of i to 1 as there are not prime numbers
int k = 2;
while((i * k) < N){
b[i * k] = 1;
k++;
}
}
}
for(int i = 2; i < N; i++)
{
if(!b[i]) cout << i <<" ";
}
}
well naive solution is to check each row`s element with every column`s element . This will take o(n3) time. Can we do better than this ?
bool found = true;
for(int i = 0; i < n; i++)
{
for(int k = 0; k < n; k++)
{
for(int j =0; j < n; j++)
{
if(a[i][j] == a[j][k]) continue;
else
{
found = false;
break;
}
}
if(found)
return i;
}
}
Ok got it , as they can dynamically expand
//Considering we are implementing Open Addressing
template <class Key , class value>
class HashTable{
private:
class Data{
Value v;
bool deleted;
};
vector<data> _hashTable;
int getHashCode(Key k);//hash function
public:
void insert(key k, value v);//for implementation of this function refer to cormen page 238
}
Hi Guys how about this aproach
A = {0,0,0,1,1,0,1}
B = {0,1,0,1,0,0,0}
sum_a = {0,0,0,1,2,2,3} // i.e a[i] = a[i] + a[i - 1]
sum_b = {0,1,1,2,2,2,2}
now begin from the back of sum_a and sum_b
if(sum_a[a_size] == sum_b[b_size])
{
while(sum_a[a_size] == sum_b[b_size]){
a_size --;
b_size --;
}
return a_size; // from this index to 0 is the sequence we are looking for
}
if(sum_a[a_size] > sum_b[b_size])
{
b_size--;
}
if(sum_a[a_size] < sum_b[b_size])
{
a_size--;
}
if( a_size == 0 || b_size == 0 )
return -1 ; // no such sequence exists
//I hope i am able explain logic clearly here , if any doubts let me know
- sachin323 November 04, 2010Polymorphism allows a client to treat different objects in the same way even if they were created from different classes and exhibit different behaviors.
You can use implementation inheritance to achieve polymorphism in languages such as C++ and Java.
Base class object's pointer can invoke methods in derived class objects.
You can also achieve polymorphism in C++ by function overloading and operator overloading.
imagine it like this
----------------------|
B 2 3 B 4 5 |
3 4 B 3 B 4 |
1 2 1 3 B 4 |
B 2 1 B 2 B |
-------------------------
Now in the above example if u found first black node at [0][0] no nodes are reachable from it , then u find node at [0][3] from this node u can see there are other B nodes connected it to
The ans to above question will be to BFS
imagine it like this
----------------------|
B 2 3 B 4 5 |
3 4 B 3 B 4 |
1 2 1 3 B 4 |
B 2 1 B 2 B |
-------------------------
Now in the above example if u found first black node at [0][0] no nodes are reachable from it , then u find node at [0][3] from this node u can see there are other B nodes connected it to
The ans to above question will be to BFS
I think we use the same logic which is used in the problem to build a BST from a sorted array . in which we use element in the middle as root and all the element left of it well go to left sub tree and all element right of will go to right subtree .
in this case as we dont have random access to elements we will have to write a function getNodeAt(node *head, int position) which will give us location of that element.To illustrate the idea look at the following code
Tree* BuildBST(Node *head ,int start , int end)
{
Tree *root = NULL;
if(end >= start )
{
int mid = (start + end) /2 ;
Node* temp = getNodeAt(head,mid);
root = new Tree(temp->data);
root->left = BuildBST(head,start,mid-1);
root->right = BuildBST(temp,mid+1,end);
}
return root;
}
here u can use counting sort which run in O(n + k) where k = number of key which are 256 i.e. no. of ASCII values
string CountingSort(string str){
int a[256];
int size = 255;
for(int i = 0; i < 256; i++){
a[i] = 0;
}
//count number of characters in string
for(string::iterator it = str.begin() ; it != str.end(); it++)
a[*it] += 1;
int len = str.length() - 1;
//rebuild string from back to keep sort stable
while(size--){
if(a[size]){
while(a[size]--){
str[len--] = char(size);
}
}
}
return str;
}
int Kadane(int a[],int n)
{
int max_start=0;
int max_end=0;
int max_sum=1<<31;
int sum = 0;
int i=0,j =0;
for(j=0;j<n;j++)
{
sum = sum + a[j];
if(sum > max_sum)
{
max_start=i;
max_end=j;
max_sum = sum;
}
if(sum < 0 )
{
sum = 0;
i = j+1;
}
}
for( int i = max_start ; i <= max_end ; i++)
printf("%d\n", a[i]);
return max_sum;
}
class Stack {
private:
int arr[200];
int size;
int top1;
int top2;
Stack(int sz) : size(sz),top1(0),top2(size -1)
{
}
bool isfull(){
if(top1 ==0 && top1 == top2)
return true;
else if(top1 + 1 == top2)
return true;
return false;
}
public:
void push_back_1(int elem){
if(!isfull()){
arr[top1++] = elem;
}
}
void push_back_2(int elem){
if(!isfull()){
arr[top2--] = elem;
}
}
int pop_1(){
if(top1 == 0) return -1;
return arr[top1--];
}
int pop_2(){
if(top2 == size - 1) return -1;
return arr[top1++];
}
};
void Array_Swap(int a[],int size){
int diff = 0;
int swap_index = 0;
int j =0;
for (int i = 0 ;i < (size-1) ;i++){
j = i + 1;
//skip numbers until we get number smaller than a[i]
while((a[i] - a[j++]) < 0);
diff = a[i] - a[j-1];
swap_index = j -1 ;
//find the number which will have lowest postive difference with a[i]
// save that number`s index and swap it with a[i]
for (;j < size -1 ; j++){
if((a[i] - a[j]) > 0 && (a[i] - a[j]) < diff)
{
diff = (a[i] - a[j]);
swap_index = j;
}
}
swap(a[i] ,a[swap_index]);
}
}
int main( )
{
int a[] = {4,5,6,3,1};
Array_Swap(a,5);
for(int i = 0 ; i < 5; i++)
cout << a[i] << endl;
int a[] = {4,5,6,-3,-1};
Array_Swap(a,5);
for(int i = 0 ; i < 5; i++)
cout << a[i] << endl;
return 0;
}
in C++ i would suggest STL Map.
Map<String,String> Dictionary;
Dictionary[word] = meaning ;
Advantage :
Maps store data in sorted order , will be beneficial when u need to print all words
starting from particular character
insertion and search in log n
search can be improved if we save iterators for words starting from each character
then when search for particular word is requested , get the saved iterator for first character of that word and search word from there .
i think the question was meant to test how good u understand sorting algos . I would have said i will go for bubble sort with only one pass . As we know in every pass a element is placed at it right position here max element would go to last in one pass.
As with merge sort we would have to first divide the list which would any how will take O(lg(n)) and then we look for max .
Well after the interview i came to this solution . first i got the summation of all elements in array and then divide the sum by 2 . now look into array for elements who can sum upto this sum .
Yes its O(n+ n2) = O(n2) solution . I dont know better than this .
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 [] = { .... };
int sum = ArraySummation(a,size);
sum = sum / 2;
FindSumElem(a,size,sum);
}
int SearchCircularArray(vector<int>& v ,int m, int num){
if(num > v.at(v.size() - 1)){
return binary_search(v.begin(),(v.end() - m),num);
}else
{
return binary_search(v.end()- m,v.end() -1 ,num);
}
}
int main( )
{
int a [] = {3,4,5,6,1,2};
vector<int> v(a,a+6);
//Here m = 2 , meaning array is circularly shifted by 2 times
//Fist parm:vector
//Second: m
//Third : Elemnt to be searched
cout << SearchCircularArray(v,2,10);
return 0;
}
Please let me know any other better approach than this or if i am missing something
int Kadane(int a[],int n)
{
int max_start=0;
int max_end=0;
int max_sum=1<<31;
int sum = 0;
int i=0,j =0;
for(j=0;j<n;j++)
{
sum = sum + a[j];
if(sum > max_sum)
{
max_start=i;
max_end=j;
max_sum = sum;
}
if(sum < 0 )
{
sum = 0;
i = j+1;
}
}
for( int i = max_start ; i <= max_end ; i++)
printf("%d\n", a[i]);
return max_sum;
}
int FindSum(int num){
//If num is single digit
int sum = 0;
if(num / 10 == 0)
return num;
else
{
while(num > 1){
sum = sum + num % 10;
num = num / 10;
}
//If sum is not single digit
if( sum / 10 != 0)
sum = FindSum(sum);
}
return sum;
}
int main( )
{
cout << FindSum(9999) << endl;
return 0;
}
@ChrisK Hi Chris based on my description your interpretation is right but interviewer said that numbers in the matrix represent the 'Goodness' factor of how confident we are about this line. Thats where it got fuzzy for me. Anyways the problem we ended up solving was much more simpler.
- sachin323 December 03, 2017Basically from pixel m[c][r] you need to pick the max value of m[c+1][r-1], m[c+1][r], m[c+1][r+1] . This will repeat for every cell in 0th column. Once you reach the end then on this path you will pick the smallest pixel value. After doing this for all cells in 0th column you will have R total values and from these you pick the smallest one which will be your ans.
To achieve above I mentioned this can be done by greedy approach to which he said there is better way that if you can actually work your way backwards from nth column to 0th column (actually this doesn't make any sense to me as it makes no difference if you start from the 0th column or nth column)
Anyways I got reject, I think mostly because I fail to understand what exactly was the problem