BlackMath
BAN USERMy Key Values :
• Be a well known software developer and a good freelance programmer.
• Code various algorithms and solve algorithmic problems optimally.
• Learn new programming and web scripting languages.
• Write freelance software apps in my free time.
RESUME
SOMDIP SEN
M, Indian, 24 years
House No. 42, Karthika, Manjunatha Layout,
Munnekolal, Marathahalli, Bangalore -560037
email: somdip.nitdgp@gmail.com
Phone: +91 7760268396
KEY VALUES
• Be a well known software developer and a good freelance programmer.
• Code various algorithms and solve algorithmic problems optimally.
• Learn new programming and web scripting languages.
• Write freelance software apps in my free time.
EMPLOYER DETAILS
• Subex Limited ( Telecom-domain product-development company )
April 2011 - present
Wrote code for processing CDRs (Call Detail Records) and allow network operators to settle charges
with their network partners, which was used within a software application product “Partner Settlement”.
Technologies used: C# and Java with Oracle back-end database.
• Tata Consultancy Services (Jan 2010 – March 2011)
Wrote code for a banking and finance project “Global Wealth Management Platform”, which targets the
high net-worth individuals and helps them manage their money in a better way.
Technologies used: J2EE, Struts Framework, JSP with PL/SQL for back-end coding.
• Prepared algorithmic problem-solving questions and thus, worked as a Content Developer with a start-up company since last 3 months, just as freelance work.
FREELANCE WORK
Known as « BlackMath » across various freelancing sites, here are some of my works as a freelance developer in a period of 1 year.
Catalog Scraper Wrote a PHP script to scrape http://www.proactivecomponents.com/partscatalog/catalog/
containing 55,000 web-pages and 5.5 million products and dump the data in excel files.
URL Finder Wrote a Java desktop application which takes a list of company names (10,000 + names)
from a file and searches them on various search sites - google/yellowpages/dexknows/
whitepages to get the website and other info of those companies.
Quiz Website Integrated the time management quiz application on an existing website "www.28hoursaday.com" in PHP/Ajax/HTML/CSS.
JSnake Game Coded the famous Snake game in Java with added features and hardness levels.
YellowPages
DATA scraper Wrote Java desktop app for website scraping of http://www.yellowpages.com/ and store information of all hospitals/medical centers in any city.
MOBILE SHOPPE RECORD MANAGER Coded a software which gives you easy access to all customers’ records, print invoice bills directly and maintain records for various branches of the shop, being used by a friend.
EDUCATION
PERCENTAGE OF MARKS OBTAINED IN CLASS X: 89.4%
(C.B.S.E. 2003) from Mount Carmel, Ghugus, Chandrapur.
PERCENTAGE OF MARKS OBTAINED IN CLASS XII: 77.6%
(C.B.S.E 2005) from Modern School, Nagpur.
Passed my B.Tech (Final Year) in Electronics & Communication Engineering from
National Institute of Technology, Durgapur.
C.G.P.A.: 7.84 (on an absolute scale of 10)
Semester I II III IV V VI VII VIII
GPA 7.47 8.43 7.87 8.29 7.64 8.20 7.29 7.52
TECHNICAL SKILLS
Programming Languages
***********************************************************
- C / C++
- C#
- Java
Web Technologies
*************************************************************
- HTML / DHTML / XHTML
- CSS
- PHP
Databases
*************************************************************
- Microsoft SQL Server
- Oracle
ACCOLADES AND ACCOMPLISHMENTS
• A Sun Certified Java Associate (SCJA) on Java 1.4 Platform, securing 100% in Sun Certification Exam.
• Been Top worker of the month twice on www.vworker.com, for freelance work.
• A regular programmer of various online judges with a current world rank #742 in Sphere Online
Judge (SPOJ).
• Qualified for the Google CodeJam, 2008.
• An active programmer of weekly online programming contest Topcoder with a current country rank in
top 350, also qualified for Topcoder Open 2008 in the first qualification round.
• Selected for the finals of Brainmesh, National-level web development contest in MUKTI 2007, NIT Durgapur.
• Some of my team achievements in various national institutes' online programming contents worth notable are:
1. 14th in BYTECODE'07, IIT Guwahati online programming contest.
2. 15th in Trinity of Neo'08, IIT Guwahati online programming contest.
3. 50th in CODECRAFT'08, IIIT Hyderabad online programming contest.
• Was one of the problem setters of Codecracker, Intra-college programming contest of NIT, Durgapur.
• Secured first position in state at "Holy Faith International Talent Search Examination (HFI) 1998-99"
held at school.
HOBBIES
• Freelancing
• Participating in various online programming contests.
• Coding standalone apps.
• Playing Computer Games and Coding.
PERSONAL DETAILS
• Date of Birth: 08th January, 1988
• Languages Known: English, Hindi and Bengali.
- 0of 0 votes
AnswersImplement LRU cache.
- BlackMath in India for KDK - Kindle Development Kit
I think this question is already there on careercup.
I answered with hashmap + minheap.
Access takes O(1) and inserting new element takes O(lg n).| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven a stack.
- BlackMath in India for KDK - Kindle Development Kit
Can we find range of numbers in the stack ?
Range is Max value in stack - Min value in stack.
Q > How will we design the stack to get Range in O(1) ?
Ans > I answered this one saying we have max variable and min variable defined in the stack. Whenever we push any number into stack, we compare with the current max and update, if necessary. Same with min.
Q > Then, he asked me what happens when we pop ?
If the element to be popped is the max element, how do we find the second max to be the new max element.
Ans > This, i answered we maintain two different stacks inside a stack called maxStack and minStack for max and min elements. He asked me to code everything. I did.
Then, he asked me if there are duplicates in the stack, can we optimise our solution so that the max element doesn't get inserted into the maxStack more than once and still we get all the above functionalities in optimised way ?
Ans > I answered we maintain a map of integer and it count. When we push into the stack, if the element is already there in the stack, we increase its count and update the maxStack or minStack, if necessary. When we pop, we decrease the count. If count becomes 0, then we update the maxStack and minStack, if necessary.
I coded everything then.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
ok, i would like to answer this.
inserting : 7, 8, 1, 6, 9, 2
insert element : 7
stack : 7
maxstack : 7
minstack : 7
insert element : 8
stack : 7, 8 (top of stack is the last element in this list)
maxstack : 7, 8
minstack : 7
insert element : 1
stack : 7, 8, 1
maxstack : 7, 8
minstack : 7, 1
insert element : 6
stack : 7, 8, 1, 6
maxstack : 7, 8
minstack : 7, 1
insert element : 9
stack : 7, 8, 1, 6, 9
maxstack : 7, 8, 9
minstack : 7, 1
insert element : 2
stack : 7, 8, 1, 6, 9, 2
maxstack : 7, 8, 9
minstack : 7, 1
Now if we pop 2, no effect on maxstack and minstack.
we can find the range correctly. Range is 9 - 1 = 8
Now we pop 9, maxstack : 7, 8
minstack : no change
we can still find the range correctly. Range is 8 - 1 = 7
Now we pop 6, maxstack and minstack no effect
we can still find the range correctly. Range is 8 - 1 = 7.
so, inserting or popping out 6 does not change anything,
since it is in between maxstack top value and minstack top value.
we can't pop out 7 or 8 before 6 is popped out.
so, we dont need to save 6 in the maxstack and minstack.
The algorithm works correctly for range.
Please evaluate the test case in this way, before posting comments.
I think this answers your second question too.
Please revert back your comments.
This is not the complete code and i have not tested it.
The last part for duplicates is not coded here.
But this will give an idea what i wrote there.
public class MyStack
{
int maxSize;
int arr[maxSize];
int size;
int top;
Stack<Integer> maxStack;
Stack<Integer> minStack;
MyStack (int size)
{
arr = new int[size];
maxSize = size;
this.size = 0;
top = -1;
maxStack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public int getTop ()
{
if (size <= 0)
return -1;
return arr[size-1];
}
public int getRange ()
{
if (size <= 0)
return -1;
return (maxStack.top() - minStack.top());
}
public void push (Integer s)
{
if (size >= maxSize - 1)
return;
arr[size] = s;
size++;
if ( ! maxStack.isEmpty())
{
if (maxStack.top() < s)
maxStack.push(s);
}
else
maxStack.push(s);
if ( ! minStack.isEmpty())
{
if (minStack.top() > s)
minStack.push(s);
}
else
minStack.push(s);
}
public void pop ()
{
if (size <= 0)
return;
int elementToPop = arr[size-1];
size--;
if ( ! maxStack.isEmpty())
{
if (maxStack.top() == elementToPop)
maxStack.pop();
}
if ( ! minStack.isEmpty())
{
if (minStack.top() == elementToPop)
minStack.pop();
}
}
}
Nice solution. I implemented it.
But its not showing all the triplets of integers with the criterion mentioned. I know that the problem statement just needs one. But what do we do if we want all the triplets ?
Its not printing out triplets like :
{4,5,8}, {4,5,6}, {1,3,8}, {1,3,6}, etc.
Here is my java code :
public class Find3OrderedIntegersInArray
{
// Given an array find 3 elements such that a[i] < a[j] < a[k] and i < j < k in 0(n) time.
public static void main (String args[])
{
int[] arr = new int[]{4,7,5,1,3,8,9,6,2};
int size = 9;
int[] mini = new int[size];
int[] maxi = new int[size];
mini[0] = 0;
maxi[size-1] = size-1;
int min = arr[0];
int max = arr[size-1];
for (int i = 1; i < size; i++)
{
if (arr[i] < min)
{
min = arr[i];
mini[i] = i;
}
else
mini[i] = mini[i-1];
// System.out.print (mini[i] + " ");
}
System.out.println();
for (int i = size-2; i >= 0; i--)
{
if (arr[i] > max)
{
max = arr[i];
maxi[i] = i;
}
else
maxi[i] = maxi[i+1];
// System.out.print (maxi[i] + " ");
}
System.out.println();
System.out.println("The output : ");
for (int i = 0; i < size; i++)
if (arr[mini[i]] < arr[i] && arr[i] < arr[maxi[i]])
System.out.println(arr[mini[i]] + " < " + arr[i] + " < " + arr[maxi[i]]);
}
}
Code for the same logic. Only, hashmap is a class variable, no need to pass it as parameter.
nodesByLevel is the hashmap being used, initialized outside the method.
Pass printElementsInEachLevel (rootNode, 0) ;
public static void printElementsInEachLevel (Node node, int level)
{
if (node == null)
return;
List<Node> lst = nodesByLevel.get(level);
if (lst == null)
lst = new ArrayList<Node>();
lst.add(node);
nodesByLevel.put(level, lst);
printElementsInEachLevel (node.left, level + 1);
printElementsInEachLevel (node.right, level + 1);
}
I completely agree with the above comment.
The idea of using some hash function to use as the key for values is great. Obviously, the sum of ascii values does not prove to be a good key value. I got some idea from the RK algorithm.
We can use double-hash or triple-hash if required to get a unique key value. Adding the ascii values can be one technique. If it matches, then we can apply another hash technique on top of that. The other hash technique has to be thought of and can be anything like:
"Anna" -> ascii(A) - ascii(n) + ascii(n) - Ascii(A).
This is just an example and maintain another hashmap for these entries.
If our string to be checked matches all these criterions, then we assume it is an anagram and print the value for that key and our word under consideration.
This provides a full proof method for avoiding wrong analysis of anagrams, though the storage is a little bit higher but good time complexity.
A java program is here.
System time used.
works fine...
import java.lang.Math.*;
public class getRandomNumber
{
public static double random(int min, int max)
{
double l = 0.0;
Long time = System.currentTimeMillis();
time = time%1000;
double t = time*1.0/1000;
l = min*1.0 + t;
return l;
}
public static void main(String args[])
{
System.out.println(random(1,2));
}
}
Passing the sum and count variables as parameters seem to be wrong since we don't have a track when the recursion has traversed all the nodes.
Keep sum and count as global variables or class variables in java.
No need to pass any parameters.
Time : O(n)
// sum and count are class variables.
// sum = 0; count = 0; before calling avg.
// call this function as avg(rootNode).
// after the function call, avg = sum / count;
public static void avg(Node node)
{
if(node == null)
{
// System.out.println(sum + " " + count);
return;
}
else
{
sum += node.value;
count++;
avg(node.left);
avg(node.right);
}
}
Thank you guys for your support.
- BlackMath July 05, 2012I finally got the hiring call from amazon.