dutta.dipankar08
BAN USERHi,
I am Dipankar Dutta from IIT Roorkee.
For more info please visit my </p><a href="http://dipankar.me.pn/">Home</a> <p>Page.
Note that, My Home page is moved from iitr domain to <b>me.pn</b> domain. To Visite my home page <a href ="http://dipankar.me.pn/"> CLICK HERE </a>
you can also mail me. My mail ID
dutta.dipankar08[at]gmail.com
AVAILABLE ON DEMAND...Still you can view my old resume in my IITR Home Page,
Thank you,
Dipankar
- 0of 0 votes
AnswersR4 | Q2. Given a BST, find out the minimum length form root to leaf with sum S. Note that:
- dutta.dipankar08 in India for MS Office Platform
a) Path from root to leaf node.
b) Sum of node of the path is S.
c) if multiple such path exist, print minimum length path.
d) What is advantage of BST rather than BT used for this algorithm, how it improve the performance. in BST, is it required to explore both side ?
e) Write working codes for it.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersRound 4( 2h 30 min)
- dutta.dipankar08 in India for MS Office Platform
===================
Q1. You are given a Text, where all space, full stop and all punctuation mark is removed. You want to reconstruct the text by putting spaces between words.
A dict is given and following API < bool isInDect(word) > is also given.
a) Decide if the text can be converted a sentence with valid words or NOT.
b) Find how many way you can do the reconstruction of the text
c) Find what is the minimum number of space can be used for this reconstruction.
d) For case (c) find out the indexes where you suppose to put a space.
e) Now recover the text to sentence in place .
Subsequent Question:
1. Why Greedy technique will not work for this
2. yes ! Backtracking will work, what is the problem of using backtracking
3. Illustrate and explain how the solution is contracted from the Dynamic table.
4. Write the correct working code for (c),(d),(e).| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersR3 | Q4. You have a file with million words in it. Find most frequent 10 word in that file. Node that you can store all word in memory.
- dutta.dipankar08 in India for MS Office Platform
(Note : Min-Heap + List )| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersR3 | Q3. What the different issue in multi-threading ? What is the difference between mutex and semaphore.
- dutta.dipankar08 in India for MS Office Platform| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersR3 | Q2. Reverse a 32-bit integers. write code for it.
- dutta.dipankar08 in India for MS Office Platform| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersRound 3:(1.h 15min)
- dutta.dipankar08 in India for MS Office Platform
===================
Q1. In a plane n points (X and Y) is given. How will you find out maximum co-liner points. Extend this algorithms. it for point(x,y,z) in 3D plane.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswerR2 | Q3. Design a Chip-Encryption system. Which will do following operation:
- dutta.dipankar08 in India for MS Office Platform
1. Take a word from user
2. Encrypt the word by some Private or public key cryptography or any other algo.
3. Transmit the encrypted word by TCP or UDp or SSL.
Design the class diagram using OOD. Which design pattern you are using to achieve this.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersR2 | Q2. You have a dictionary of words. Given a word, print all anagram are in dictionary . State the data structure to be used to solve this problem.
- dutta.dipankar08 in India for MS Office Platform| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersRound 2:(1.h 15min)
- dutta.dipankar08 in India for MS Office Platform
===================
Q1. Given a sorted array having duplicate elements,how would you find first index of a given element in O(nlogn).
Write code for it. Change the condition to find out last index of that elements.
[ Hint Binary search]| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - -2of 2 votes
AnswersR1 | Q2. Find an element in a sorted rotated array in O(nlogn ) complexity.
- dutta.dipankar08 in India for MS Office Platform| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersRound 1: (1 h)
- dutta.dipankar08 in India for MS Office Platform
==============
Q1. Design a Garbage collector like java. How would you detect depended reference loop ?
Hist : Class design, Cycle detection algorithms for disjoint graph( List of connected graph)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersRound 4: [HR rounds]
- dutta.dipankar08 in India for InMobi
Ans 1: Explaied about InMobi and why should i Join It?
Ans 2. Benefit details.
Q1. As already you have been Offered from ABC , would u accept our offer and why?
Q2. Current CTC ? ABC-Offered CTC ? Expected CTC ?| Report Duplicate | Flag | PURGE
InMobi Software Engineer / Developer - 0of 0 votes
AnswersRound 3 | [With manager]... Discussion regarding Product , Issues etc etc...
- dutta.dipankar08 in India for InMobi
Q1. As you know there are a lot of s/w which block adds. How to crack these ADD-Blocker S/w ?
[hints-: Url mapping]
Q2. How will you efficiently Look up Adds for a Particular mobile user. Do it very space and Time bounded manner. Find DS and Design algo for that.
[ Hints -Some concept of Learning technique, Expert System, and Data mining ]| Report Duplicate | Flag | PURGE
InMobi Software Engineer / Developer - 0of 0 votes
AnswersRound 2 | Q2. Explain your Internnship Project. He Asked for the System Model and Mathematical Proof .{ as my project does this } Some Cross Question about the Architecture of the System.
- dutta.dipankar08 in India for InMobi| Report Duplicate | Flag | PURGE
InMobi Software Engineer / Developer - 0of 0 votes
AnswersRound 1| Q3: Find out n-th ugly number ? an ugly number is define as 2^i * 3^j * 5^k.
- dutta.dipankar08 in India for InMobi
[Hints -DP]| Report Duplicate | Flag | PURGE
InMobi Software Engineer / Developer - 0of 0 votes
AnswersRound 1 | Question 2: Suppose you are givean an expression E= x1 y1 x2 y2....yn-1 xn.
- dutta.dipankar08 in India for InMobi
Where Xi belong to natural number and Yi belongs to { +,*}
you need to parenthesize such that it maximize the value of E ?
Let's change Yi to { +,-,*,/}, then how to maximize E?
Now add % operator in that set..then how to maximize E?
[Hints --Use DP]| Report Duplicate | Flag | PURGE
InMobi Software Engineer / Developer - 0of 0 votes
AnswersRound 1 | Q1. Suppose We want to design a Car-parking system. where car can be parked in FCFS basis, But there are some Spacial person ,say P1,P2,p3..having a priority of x1<x2<x3. can be access car according to their Priority.
- dutta.dipankar08 in India for InMobi
Give the Data-structure to implement this. Derive Algo and Find Complexity.
[Hints- Heap +Queue OR Multilevel Feedback Priority Queue OR Multiple Heap Structure ]
How to ensure that starvation will not occurs ? How will you integrate with previous Data Structure ?
[Hints -Ageing Technique OR use Time Stamp ]| Report Duplicate | Flag | PURGE
InMobi Software Engineer / Developer - 0of 0 votes
AnswersWritten Test | Q2. A cache contains a list of String of length atmost L.suppose cache contain n String Given a String X (of length g) as input, Find out whether any anagram of X is in cache efficiently? Find out Time Complexity. [Hints - Tries /hash/ bit-map]
- dutta.dipankar08 in India for InMobi| Report Duplicate | Flag | PURGE
InMobi Software Engineer / Developer - 0of 0 votes
AnswersWritten test | Q1. Find out Inorder traversal of a Binary Tree without Recursion [hints -use Stack]
- dutta.dipankar08 in India for InMobi| Report Duplicate | Flag | PURGE
InMobi Software Engineer / Developer - 0of 0 votes
AnswersRound5 | Q2 : Suppose, Amazon have a Logging system Like This:
- dutta.dipankar08 in India for SDE
They Track all logs daily basis, stored in separate log file.Log contains a collection of tuples of Customer ID and Page ID. The length of Customer ID and Page ID is L1 and L2. Suppose We have a log of D-days , and size of each log fine can be Order of n , where n be the number of customer.
In a most generalized situation, you can assume that a customer can visit the same page multiple times in a day or any number of days.
We are interested to find out the number of Distinct customer visited at-least p distinct pages within exactly T days.
Propose a Data Structure to be use to solve this problem efficiently . Design an Algorithm to solve this problem and Find out the complexity of the algorithm.
{Hints:- Double Hashing/ {Hashing +Tries/BST }}| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswerRound4 | Q4 : Explain the Run Time Polymorphism in OOPs. Why it is important ?
- dutta.dipankar08 in India for SDE| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersRound4 | Q2 : Design a Architecture of Online Movie Booking System . Find the possible issues and Idea to Resolve them. How do you optimize the Performance against all these issues.
- dutta.dipankar08 in India for SDE| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswerRound4 | Q1 : Expain all Concept of OOPs.
- dutta.dipankar08 in India for SDE| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersRound3 | Q2 : Given a Cache of k-length Strings of size n,. Given a String X, We can to convert to another String Y using the following two Rules:
- dutta.dipankar08 in India for SDE
R1:you can change only one character at a Time in stepwise Transformation
R2: All intermediate String in the transformation must be also in cache.
Cache has also an API : Called Is_Transformable(X,Y) return Ture if it is possible to transform X to Y, without violating the Above rule.
Assume that Cache is fixed size and there is a sequence of Query of Checking the possibility of Transformation is coming to The API of Cache.
the Question is : What Data-Structure U can use to implement Cache ? It might need some Initial Complexity to Organize the data , for efficient lookup, and provide service to APIs.
How can u implement the API in O(1).
Suppose we add one more API which calculate minimum number of Steps required to transform X to Y, How do u solve this problem in O(1).
[Hints: Graph Algorithms and Transitive closure ]| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersRound3 | Q1 : Given a Cache of n String Having length of k each, on Alphabet ALPHA where |ALPHA|=t, Find out number of 2k-length string constructable from the cache, where all sub-string of Resultant sub-string are also in cache ? What Data-structure should you use to Lookup cache? Design an Algorithm to find the count Efficiently? Calculate the Time/Space complexity of the technique. [Hints -Tries ]
- dutta.dipankar08 in India for SDE| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersRound2 | Q3 : What is Heap Tree? How you implemnt a Priority Queue using Heap.
- dutta.dipankar08 in India for SDE| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersRound2 | Q1 : Given a matrix pxq, You start from top left and have to reach the bottom right. Can only traverse right or bottom. How many ways are there to reach at the bottom right?. So If I allow all 4 way move is possible what will be the ans ? . What happened if i make some Restricted Move ? [Hints DP , Backtracking ]
- dutta.dipankar08 in India for SDE| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersRound1 | Q2: Is it possible to build a heap only from inoder traversal ? Why or Why Not ? Write Code/Algo of the Same. Proof the correctness of your Algorithm. {hints-D&C]
- dutta.dipankar08 in India for SDE| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersRound1 | Q1: What is Heap Tree? Explain With Example.
- dutta.dipankar08 in India for SDE| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersWritten Test * Q4: Given a function getInorderSuccessor which takes a BST (Binary Search Tree) as it's parameter. Every node has an extra pointer "next" , which is intialized to null, fill next with node pointers which represent Inorder Successor. [Hints -Recursion/Stack/DP]
- dutta.dipankar08 in India for SDE| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersWritten Test Q3: You are given a linked list which has the following structure
Code:linkedList { data *nextLink *randomLink }
*nextLink will always point to next node in the linked list
- dutta.dipankar08 in India for SDE
*randomLink will point to any random node node it the list (or NULL)
Now given a list L write an algorithm to create replica of the list( say L') in O(n) time and O(n) space. [Hints- Need Double Pass/Hashing]| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWritten Test Q2: In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn]. We have to do it in O(1) extra space. [Hints- D&C or swapping]
- dutta.dipankar08 in India for SDE| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWritten Test Q1: Given a root and a node of a BST tree, write a function which print all the nodes which are a 'k' distance from the given nodes in sorted order. (distance can be upwards and downwards) [Hints -Recursion]
- dutta.dipankar08 in India for SDE| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
Write the 0/1 String in your board.
Now your target is to erase some 0 and one such that we have equal number of zero and one left in the board
The remaining number in the board is the "Sequence". Note we are not altering the order and We are not suppose to return a substring
Now question is what to erase and what not ?
Let we have X number of ONE and Y number of Zero.?
If X == Y , Cool ! Equal number of Zero one Found! Ans is Full number
IF X < Y : Less One ! erase (Y-X) Number of Zero anywhere.. Cool: Ans is 2*X
If Y > X: Less Zero! Erase (X-Y) Number of One from the board! Ans is 2*Y
Complexity : O(N)
The code is as below:
#define MIN(a,b) ((a < b)?a:b)
int MaximalSubSequenceOfEqualNumberOFZeroOne(int *a, int n){
int countOne=0,countZero=0;
for(int i=0;i if(a[i]==1) countOne++;
}
countZero = n-countOne;
return 2 * MIN(countZero,countOne);
}
int main(){
int a[]={1,0,1,0,1,0,1,0,0,1,0,0,0};
printf("Ans:%d",MaximalSubSequenceOfEqualNumberOFZeroOne(a,sizeof(a)/sizeof(a[0])));
}
- Write the 0/1 String in your board.
- Now your target is to erase some 0 and one such that we have equal number of zero and one left in the board
- The remaining number in the board is the "Sequence". Note we are not altering the order and We are not suppose to return a substring
- Now question is what to erase and what not ?
- Let we have X number of ONE and Y number of Zero.?
- If X == Y , Cool ! Equal number of Zero one Found! Ans is Full number
- IF X < Y : Less One ! erase (Y-X) Number of Zero anywhere.. Cool: Ans is 2*X
- If Y > X: Less Zero! Erase (X-Y) Number of One from the board! Ans is 2*Y
Complexity : O(N)
The code is as below:
#define MIN(a,b) ((a < b)?a:b)
int MaximalSubSequenceOfEqualNumberOFZeroOne(int *a, int n){
int countOne=0,countZero=0;
for(int i=0;i if(a[i]==1) countOne++;
}
countZero = n-countOne;
return 2 * MIN(countZero,countOne);
}
int main(){
int a[]={1,0,1,0,1,0,1,0,0,1,0,0,0};
printf("Ans:%d",MaximalSubSequenceOfEqualNumberOFZeroOne(a,sizeof(a)/sizeof(a[0])));
}
void swap(int *a,int i,int j){
printf("Do Swap %d with %d\n",a[i],a[j]);
if(a[i]==0){a[i]=a[j];a[j]=0;}
else if(a[j]==0){a[j]=a[i];a[i]=0;}
else{
printf("Invlid swap(%d,%d)",a[i],a[j]);
}
}
void SwapAtoBWhenOneZero(int *a,int *b,int n){
// build reverse index of Array A
int RevIndex[n];
for(int i=0;i<n;i++) {RevIndex[a[i]] = i;}
for(int k=0;k<n;k++){ //let's place a[k] in proper place
//a[k] shoud be b[k] and it is, so continue..
if(a[k]== b[k]){continue;}
//yes.. Now we have a mismatch and b[k] shoud be in place of a[k]
// where is b[k] in array A ?we can found it from RevIndex[b[k]] ..
int target_idx = RevIndex[b[k]];// it return the index.
if( a[target_idx] == 0 || a[k] == 0){ // is that element is Zero.. Ok.. yes.. so swap is possible..
swap(a,k,target_idx);
}
else{ // direct swap is not possible bcz atleast one elemnt shoud be zero..
// swap using zero-th index...
int zero_idx = RevIndex[0];
swap(a,zero_idx,target_idx);
swap(a,k,target_idx);
swap(a,zero_idx,k);
}
// reConstract revese Index
for(int i=0;i<n;i++) {RevIndex[a[i]] = i;}
}
}
int main(){
int a[] = {1, 3, 2, 4, 0};
int b[] = { 4, 0, 3, 2, 1};
SwapAtoBWhenOneZero(a,b,5);
}
>>> Compiling...
Compiled succesully with warning
>>> Running...
Do Swap 0 with 4
Do Swap 1 with 0
Do Swap 4 with 0
Do Swap 3 with 0
Do Swap 0 with 3
Do Swap 2 with 0
Do Swap 3 with 0
Do Swap 0 with 2
Do Swap 1 with 0
Do Swap 2 with 0
int EightDMove[8][2] = { { 0,1},{1,0},{1,1},{0,-1},{-1,0},{-1,-1},{1,-1},{-1,1} };
#define IS_VALID_MOVE(i,j) ( i>=0 && i<4 && j>=0 && j<5 )
int countOccZigZag(char maze[4][5], int i, int j, char *in)
{
/* Yes Match found and ends here */
if(*in == '\0')
return 1;
/* yet to match something */
int sum =0;
for (int k =0 ;k<8;k++)
{ int a = i+EightDMove[k][0];
int b =i+EightDMove[k][1];
if(IS_VALID_MOVE(a,b) && maze[a][b] == *in)
{
sum += countOccZigZag(maze,a,b,in+1);
}
}
return sum;
}
void test()
{
/* Initilaize the board and text */
char p[4][5] = {
{'S', 'N', 'B', 'S', 'N'},
{'B', 'A', 'K', 'E', 'A'},
{'B', 'K', 'B', 'B', 'K'},
{'S', 'E', 'B', 'S', 'E'}
};
char target[] = {'S','N','A','K','E','\0'};
/* Call the util when there is a match */
int sum =0;
for (int i=0 ;i<4;i++)
for (int j=0;j<5;j++)
if (p[i][j] == *target )
sum += countOccZigZag(p,i,j,target+1);
printf ("Count : %d",sum);
}
void replaceQnMarkByZeroOne(char *a,int i)
{
if (a[i] == '\0')
{
puts(a);
return ;
}
while(a[i] != '?' )
{
i++;
if(a[i] == '\0')
{
puts(a); return;
}
}
/* We get a Question Mark */
a[i] = '0';
replaceQnMarkByZeroOne(a, i+1);
a[i] = '1';
replaceQnMarkByZeroOne(a, i+1);
// This is for back trace
a[i] = '?';
}
void test()
{
char str[]="a?b?c?";
replaceQnMarkByZeroOne(str,0);
}
#---Print all word to generate -----
# Mobile NUmver genarator====
# Author : Dipankar
#-----------------------------------
key={0:[''],
1:[''],
2:list('abc'),
3:list('def'),
4:list('ghi'),
5:list('jkl'),
6:list('mno'),
7:list('pqrs'),
8:list('tuv'),
9:list('wxyz')
}
def getAllWord(num):
if(len(num)==0):
return [''];
else:
return [ i + j for i in key[int(num[0])] for j in getAllWord(num[1:])]
res=getAllWord('9920')
print res, len(res)
a sequence of ugly numbers are :
<1,2,3,4,5,6,8,9,10,12,15,16,18,20........>
Note that all number are in the form of 2^i * 3^j * 5 ^k , i.e has only the factor : 2 or 3 or 5. For example 13 is not an Ugly number. 21 is also not an Ugly number as it can't be expressed as 2^i * 3^j * 5 ^k [ 7 is a factor ] . The ugly number are in increasing order, whre 1st elemnt is 1, second element is 2, 10-th element is 12. Find out n-th Ugly number ?
Yes..you should use Dynamic programming..It is just similar with Chain matrix Multiplication...
- dutta.dipankar08 February 19, 2012Yes..
- dutta.dipankar08 February 19, 2012First ugly no is 1 when i=j=k=0; i,j,k belongs to Z+,i.e {0,1,2,3....}
- dutta.dipankar08 February 19, 2012First ugly no is 1 when i=j=k=0; i,j,k belongs to Z+,i.e {0,1,2,3....}
- dutta.dipankar08 February 19, 2012Working Python Code As below....
def dp_per(x,y):
#print x,y
if len(y)==1:
print x+y
global count
count=count+1
else:
cache=[]
dp_per(x+y[0],y[1:])
cache.append(y[0])
for i in range(1,len(y)):
if y[i] not in cache:
cache.append(y[i])
dp_per(x+y[i],y[1:i]+y[0]+y[i+1:])
print 'enter your String !!!!'
x=raw_input()
count=0
print 'Ans as below:'
dp_per('',x)
print 'Total Ans['+str(count)+']:'
Repmariacbrister, Graphics Programmer at Graphic Systems
Hey, I am Maria and I am from Bluefield. Currently, I work as a freelancer graphic artist. From an early ...
Repmonicahbess, SDET at Adap.tv
Hi Everyone, I'm Monica H. Bess. I love to build props...everything from a casket to pneumatic monsters.My ...
Repcoragkemmer, Data Scientist at Bankbazaar
Have years of experience to treating variety of outpatients with modalities such as massage, exercise, paraffin, joint mobilization, mechanical traction ...
Statement: We can shuffle the string if and only if the frequency of maximum occurring charterer is less than or equals len(string) + 1.
- dutta.dipankar08 September 07, 2016Proof. Let's consider we have a string of length 9. In worst case the valid shuffle should be looks like:
X_X_X_X_X_X where X is the max occurring char.
so for string having length of 9, we can almost 5 most occurring char. If we add one then it will break the above structure having a distinct char in-between two same char.