abhimanipal
BAN USERI am currently doing my Masters in Computer Science at SUNY- Buffalo. I have gpa of 3.68. Most of my development experience is in C/C++.
Check out my resume for more details on my research/ projects
Abhishek Agrawal
77, Merrimac Street,
Buffalo, NY 14221
aa225@buffalo.edu
(716) 435-7122
OBJECTIVE
Seeking a position in an organization that would allow me to utilize my skills to the maximum.
EDUCATION
University at Buffalo, The State University of New York Masters of Science, Computer Science and Engineering • Current CGPA 3.68/4.0
RESEARCH EXPERIENCE
Modified Priority Scheduler for Improved Performance NSF Funded
• We attempt to improve upon the resource utilization for clusters by designing better scheduling algorithms. The parameter we wish to optimize is the slowdown experienced by each job. • Made my own job simulator to compare my scheduling algorithm with the competition. The workload was taken from the parallel workloads archive. Code was written in Java. .
• Presented a research poster on this topic in IEEE Cluster 2009 conference.
Efficient Traversal of an Area using Wireless Sensor Nodes Masters Project
• Area traversal/ coverage is a fundamental application for Wireless Sensor Nodes. We developed 2 new algorithms in this area. • The first algorithm ensured quick coverage of the area and at a reasonable energy cost. The second algorithm covered the area efficiently even if there were holes in it, which was impossible previously.
• Language used was C. Got full credit for this project
SKILLS Programming Languages: C/ C++, Java
Parallel Programming/ Multi threaded programming Hadoop File System, HBase, Hive, Hama
Network Simulators: Glomosim, NS2 Other Technologies: Perl, Tcl, SQl, Microsoft Office Products Internet Technologies: HTML,JSP,ASP Operating Systems: Windows XP, Vista, FreeBSD, Unix, Linux
PROJECTS
A Compiler for C++ Language
• Implemented a compiler, which could compile instructions like data declaration, if else, for/ while loops in C++
• Language used was C++. Operating System was Windows. Secured an A for this project.
Created Containers for exchange of data between processes • A scheme for the processes in the kernel to exchange data. 5 system calls added to the kernel to facilitate this.
• Extensive usage of data structure locking, dynamic memory usage, sleep/wake mechanism in the kernel.
• Language used in C. Operating system used is FreeBSD. Secured full credit for this project.
File System using Inet Domain Sockets
• Designed a distributed file system using Inet Domain Sockets. The file system was capable of performing basic operations like File Create, File Read, File Write, File Append, File List, etc. Storage of files was persistent. • Language used was C. Operating System was Linux. Secured full credit for this project.
RCP- A new Transport Layer Protocol for TCP/IP stack
• RCP is a clone of TCP- Tahoe but the congestion control is completely handled by the receiver. Implement this protocol and compared its performance with TCP- Tahoe.
• Implementation was in NS2. Languages used were C++, Tcl. Operating System was Solaris.
Implementation of Markowitz model using Hadoop
• Simulating the Markowitz model on Hadoop. The co variance matrix and expected returns matrix is computed in parallel. Currently trying to simulate SVD decomposition on Hadoop to calculate the inverse of a matrix. Will compare the performance with traditional databases.
• Hadoop/HBase is used for data storage. Used Hama for matrix multiplication. Code was written in Java.
Mac Layer Protocol for TCP/IP stack
• Developed a MAC layer protocol for an ad hoc network. There are 99 senders and each sends b copies of data in every time unit. Receiver cannot sense the medium. The value of b which maximizes data transfer is found.
• Implementation was in Glomosim. Language used was C. Operating System was Solaris.
Portable Indoor Air Quality Sensor for Asthma Patients • Designed a sensor for use by Asthma patients. The sensor warned the patient if the air in the room could trigger an asthma attack. The sensor could be calibrated according to the needs of the individual. • Wrote the system specification document, the SRS document, the project plan, designed test cases for this
project.
ACHIEVEMENTS
• NSF grant for conducting research on scheduling in Clusters.
• Active contributor on DaniWeb C and C++ communities. username- abhimanipal
• Annual Scholarship for 4 years from Bharat Petroleum for outstanding performance in school.
• Treasurer of Leo Club- Youth Wing of Lions International, India
NODE* mirror(NODE* aHeadNode){
NODE* myTempNode = NULL;
if(aHeadNode) {
myTempNode = aHeadNode->left;
aHeadNode->left = aHeadNode->right;
aHeadNode->right = myTempNode;
if(aHeadNode->left)
mirror(aHeadNode->left);
if(aHeadNode->right)
mirror(aHeadNode->right);
}
}
In a BST we follow a particular pattern while inserting data. Hence we print the BST "in order" sorted data gets printed in O(n).
But you are right its not constant time
You are traversing the tree thrice in your solution. Was the interviewer cool with that ?
- abhimanipal June 09, 2010Stop posting your nonsense next to every question.
I have many friends in MS- India and they could not be happier with the work that they do ?
If you are so unhappy about your work then why dont you quit and end your misery ?
Can you show the steps of your algorithm with the help of an example ?
- abhimanipal June 08, 2010I like this answer .....
- abhimanipal May 30, 2010I think you have calculated the complexities wrongly.
1. We assume max heap has size k. So the heapify operation will have complexity of O(log k). This has to be done n times. So total time complexity O(nlog k).
2. Then sum up all the elements in the heap - O(k)
So O(nlog k+ O(k))
My attempt for this problem
int func(char* str)
{
int count=0;
// The second condition ensures that ) cannot come before an open (
while(*str!='\0'&& count>=0)
{
if(*str=='(')
count++;
else
count--;
str++;
}
// Equal number of ( and )
if(count==0)
return 1;
else
return -1;
}
The solution is still O(n) + O(n)
Your solution is exactly the same as the one given by thefourth
What you call as an arr[256], he calls a hash map
Another factor that we have to take into consideration is how is the dictionary stored ?
If it is a 2-d array of strings then the question is trivial.We can index directly into the array and return the string
If the dictionary is stored as a linked list then also the question is pretty trivial, traverse the linked list
But if the dictionary is stored as a suffix tree of a B- tree then the question is more complicated
@binu
How can we identify the value of A[i] with just log(A[i]) operations ?For example if the input is 7 ie. 111 I need 3 read operations to identify that I have read 7. but 3 is greater than log7
The factors of that number should be only 2,3,5
Or is 2,2,3,5 also allowed ?
I did not understand the question. Can some one post the sample input and the sample output
I am assuming that all the elements of Array B will be present in array A, but I think this assumption makes the question very simple.
What am I missing here ?
This is a O(n) solution. If at input you have just 2 elements, say 0,1 and the given value is 1000. So you wait for the incoming values. Assume n-2 values come thru. So you have to compare the value 1000 with n-2 values --> O(n) algorithm
- abhimanipal May 25, 2010Above method is same as hashing .....
- abhimanipal May 23, 2010The solution given in that paper is O(n3)
- abhimanipal May 23, 2010What if the input contains duplicate entries ?
For example if the input is 1 1 1 1 1 1 1 2, and I rotate it such that it now becomes
1 2 1 1 1 1 1 1 , will the binary search method work here as well ? I dont think so
// Assumptions: Null terminated string
// Test cases. If value of d is way to big then the code will return
// value of d cannot be -ve
// a and b can be same or different
// a and b can contain any values including '\0'
void func(char a,char b,char* str,int dist)
{
char t1,t2;
int flag=-1,count=dist,i=0;
// Distance cannot be less than or 0
if(dist<=0)
return ;
while(i+dist<strlen(str))
{
t1= str[i];
t2= str[i+dist];
if(t1==a)
flag=1;
else if(t1==b)
flag=2;
if(flag==1 && t2== b)
{
printf("Match found\n");
return;
}
else if(flag==2 && t2==a)
{
printf("Match found\n");
return;
}
flag=-1;
i++;
}
}
Store the chars to be deleted in a Hash Map. Initialize the counter i,j=0;
i: Loop though the i/p string.
If the char exists in the Hash Map, increment i
If the char does not exist in the Hash Map copy arr[j]= arr[i]; increment i,j
Put a '\0'at the jth location of the i/p string
For reversing the normal recursive code
I do not get the question. This is what I have understood so far. We are given a heap and we have to find the second smallest element.
This is what I think the answer should be. Since this is a min heap.We can find the smallest element in O(1). Remove the smallest element and heapify. O(log n). Now remove the second smallest element O(1). So the total cost should be O(log )
What am I missing here ?
You probably want to say while(n>=1)
- abhimanipal May 20, 2010I think the question is to reverse the array using bit wise operators. SO I think the approach used by Tarun is correct.
@Tarun
You have used an if condition to determine if the number of elements in the array. Based on that you run the loop to differently. Another option would be
i=0;
len= size of array -1;
while(i<=len)
{
//swap
//i++;
//len --;
}
Now the code is more compact
The second case is interesting. What happens when the list is something of this sort
10-->20
and we want to delete 20. According to the question we cannot touch 20. So what happens in this case ?
Another approach to this problem. I have made a small assumption instead of red and blue balls we have odd and even numbers. Logic remains the same anyway. Total complexity is O(n)
int findNextEven(int** arr,int size, int even)
{
// Start from the right of the list and return the next even number
int i=0;
for(i=even;i>=0;i--)
{
if(*(*arr+i)%2==0)
return i;
}
return -1;
}
int findNextOdd(int** arr,int size, int odd)
{
// Starts from the left of the list and return the next odd number.
int i=0;
for(i=odd;i<=size;i++)
{
if(*(*arr+i)%2!=0)
return i;
}
return -1;
}
void partition(int* arr, int size)
{
int i=0,odd=0,even=size-1,temp=-1,odd_temp=-1,even_temp=-1;
while(true)
{
// Get the left most odd number and the right most even number
odd= findNextOdd(&arr,size,odd);
even= findNextEven(&arr,size,even);
// If either of the 2 are -1 that means the list is already partitioned
if(odd==-1|| even==-1)
{
return;
}
else
{
temp= arr[odd];
arr[odd]=arr[even];
arr[even]= temp;
odd++;
even--;
}
}
}
Once this list is partitioned scan the list for the first even number and return. this is where the list is partitioned .
Pretty much same logic as prolific coder. But in C++
//Assumptions 2 null terminated strings. Original string will be destroyed
//Program insert the ' ' instead of the delimiters
void func(char* str, char* str1)
{
map<char,int> map1;
int i=0;
//Insert all delimiters in the map
for(i=0;i<strlen(str1);i++)
map1[str1[i]]++;
// If this char is a delimiter, insert space instead of the char
for(i=0;i<strlen(str);i++)
{
if(map1[str[i]]>0)
str[i]=' ';
}
}
int main(void)
{
char str[]= "abhishekagrawal";
char str1[]="askw";
printf("Before %s %s\n",str,str1);
func(str,str1);
printf("After %s \n",str);
cin.get();
return 0;
}
Another idea is to find the height of the left tree, find the height of the right tree. If the difference is more than 1, we return an error. The pseudo code will be some thing of this sort.
// Function return -1 if the difference is more than 1 level
// Function returns height of the tree other wise
// Assumptions : a properly constructed binary tree
int height(struct node** head)
{
// If head is equal to 0 return 0
//else t1 holds the height of the left tree t2 holds the height of the right tree
// if either of them is -1 that means some where down below there exits a sub tree with difference of more than 1 level. return -1
// if the difference is 0 or 1. then return the max height between either of the sub trees + 1
// else if the difference is 2 , return -1
}
Very nice and effective solution
- abhimanipal May 09, 2010This wont work....
Array 1:5,5
Array 2:6,6
Why would map be sorted in the first place ? Its a key value association
- abhimanipal May 07, 2010The number of errors in a program are directly proportional to the number of pointers used in the program - Yahswant Kanitkar (Author of one of the best books -Pointers in C)
But on a more serious note, usage of un initialize pointers can cause an application to crash. I guess this is the single biggest disadvantage...
I dont think the question is pretty obvious.... When you see a hex in the statement it is pretty obvious that the input is being taken in hexadecimal format
- abhimanipal May 07, 2010If the 2 constructor was not declared to be explicit then the code will not compile. The reason for that is the call to the constructor will be ambiguous.
Now when the 2 constructor is declared explicit the ambiguity is removed when we declare objects of the type string s1= "abc".
Ambiguity still exists when object is created this way
string s1("abc")
google "c++ explicit" for the reason, I am unable to post link to the web page
The function call should be
sum<int>::foo(2,3);
When extern is put in front of a variable it means that the memory for the variable is some where else.When extern is put before a function, what exactly does this mean ?That the function body is some where else ??
- abhimanipal May 06, 2010Code works....
Run the code and see
I dont think STL have an array type ?
When you say STL array, do you mean vectors ?
The question is to differentiate between pass by reference and pass by value.....
The answer is the one which was given in the first post
If the memory for this object was not on the heap then the program will crash
If the client does not come to know the object has been deleted and use the object to call a function or some thing then the program will crash
If you do this how will you ever create object to this class..
The question is to avoid object creation on the stack, we should still be able to create objects on the heap
Another use thought I am not 100% sure is when you want to place your object at a specific location in the memory
- abhimanipal May 06, 2010Yes .... Both for template as well as normal classes if there is a syntax error is the source code of the class, the code will not compile
- abhimanipal May 06, 2010What is there to elaborate ?It is a factual question.... If you dont believe that it is possible write code and see
- abhimanipal May 06, 2010Is the size of the class and object always same ?Why is it so ?
If the class has static members, then these members are not stored in the object. Inspite of that will the class and object have the same size ?
How will you use dynamic programming here ?
- abhimanipal May 04, 2010The question states that we have to print all the cells which are switched on ... So in a 10*10 matrix, if the value of the entry 7*7 is 1 we have to print that 7*7 is on.
If we sort the entries then we loose the fact the row and column nos that these entries came from
If the problem description is changed, so that we also have to identify the lines which has an integer mid point... How would one proceed then ?
Also @anonymous who posted the constant time algorithm, can you give a short description (or link ) of why is it that if we have more than 4 points, the mid point of atleast one line will be an integer ?
this will lead to a memory leak...
- abhimanipal May 03, 2010Another approach to this problem could be :
count1= Count the number of red balls
count2= Number of blue balls= Total - number of red balls
From start of the array till count1
Over write the contents with red balls
From count1 till count1+count2
Over write the contents with blue balls
Complexity will be O(n)+ O(n)= O(n)
No extra memory used
The solution is very good.... But it is not so obvious...
My advise sit with a book and pencil for 10 minutes and try to work it out
There is a one time cost of O(nlogn) to sort the numbers. But if the search is to be carried out frequently then the cost of each search will be O(n) if the list is not sorted as opposed to O(log n) if the list is sorted
- abhimanipal January 22, 2012