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 : MinHeap + List ) Report Duplicate  Flag  PURGE
Microsoft Software Engineer / Developer Algorithm  0of 0 votes
AnswersR3  Q3. What the different issue in multithreading ? 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 32bit 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 coliner 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 ChipEncryption 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 ? ABCOffered 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 ADDBlocker 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 nth 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....yn1 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 Carparking 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 Datastructure 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/ bitmap]
 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 Ddays , 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 atleast 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 klength 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 DataStructure 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 2klength string constructable from the cache, where all substring of Resultant substring are also in cache ? What Datastructure 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. {hintsD&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 (YX) Number of Zero anywhere.. Cool: Ans is 2*X
If Y > X: Less Zero! Erase (XY) 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 = ncountOne;
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])));
}

dutta.dipankar08
June 10, 2015  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 (YX) Number of Zero anywhere.. Cool: Ans is 2*X
 If Y > X: Less Zero! Erase (XY) 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 = ncountOne;
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])));
}

dutta.dipankar08
June 10, 2015 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 zeroth 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

dutta.dipankar08
March 24, 2015 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);
}

dutta.dipankar08
June 09, 2014 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);
}

dutta.dipankar08
June 09, 2014 #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)

dutta.dipankar08
March 24, 2012 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, 10th element is 12. Find out nth 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)+']:'

dutta.dipankar08
February 16, 2012
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 inbetween two same char.