anonymous
BAN USER Mishu Garg
Flat No. 102, House No. 2-59
Monica Residency, Megha Hills,
Madhapur, Hyderabad 500081 E-mail: charmnenjoy@gmail.com
Contact Number: 9000507099
OBJECTIVE To work in a challenging environment to utilize my skills and knowledge and achieve a position of senior software engineer in an organization.
RELEVANT EXPERIENCE Possesses over 3 years of experience in various software’s development. Experience includes development of projects based on Java, J2EE technologies, along with Perl, and Cognos.
EDUCATION
Jul 2004 - June 2008
June 2004
June 2002
Thapar University , Bachelor of Technology (B.Tech), Computer Science (CGPA: 9.11)
Gobindgarh Public School, 12th CBSE (Aggregate: 85%)
St. Farid Public School, 10th CBSE (Aggregate: 86.8%)
TECHNICAL
EXPERTISE Core Java (Inheritance, Collections, Synchronization)
J2EE (Struts, Servlets, JSP, JDBC)
JavaScript
Perl
C, C++
Cognos (Reporting Studio)
HTML
Sybase Database Server
SQL Server
Eclipse, My Eclipse
Apache Tomcat Server
Design Patterns
CVS Repository
SVN Repository
WORK
EXPERIENCE
Jan 2008 - Jun 2008
Jun 2008 - Present D. E. Shaw & Co. Pvt Ltd (DESIS)
Intern
D. E. Shaw & Co. Pvt Ltd (DESIS)
Senior Member Technical
Member of a team that is responsible for developing software regarding file transfer operations.
Member of a team that is responsible for developing an Inline C Application that reads the third party Intex API’s and extracts information using them.
Member of team responsible for developing and maintaining daemon framework.
Member of team that developed reports using Cognos and Microsoft SQL Server.
PROJECTS File Transfer Gateway
It encompasses the automating the process of file archival received via various means like ftp, email, http. We receive daily, fortnightly, monthly reports through various sources and by various parties. The whole process used to happen manually, which takes a lot of time on a daily basis and was prone to errors. I needed to communicate with third party frequently, understand their set of requirements, evaluate the alternatives and limitations, and then develop a solution for same.
Technologies: Core Java, J2EE, Design Patterns, Web Services, Perl, SQL Server, Sybase, XML, XSD, XSLT.
DesIntex
Intex is a third party application that provides binary files containing the information and API’s to read the data. Developed an Inline C application to make use of those API’s and extract the required data and update the database with same. Challenge was to identify the correct API calls for each desired fields and validate the output generated. Next task was to generate reports on the top of database.
Technologies: C, Perl, SQL Server, Sybase, Cognos.
Daemon Framework
Running various processes as daemons via a parent process Daemon Monitor. Job was to make the processes as real daemons, rather than running them manually and have a monitor on the top of all these processes. Daemon Monitor takes cares of starting the processes, kill/restart them if required, identify if a process is failing due to some reasons, and take the appropriate action. It involves automatic switching to DR in case of failures.
Technologies: Core Java, Perl, SQL Server, Sybase.
Quality Management System – Project Planning (QMS-PP)
It aims to automate the workflow followed by QA team. Initially, the project planning was exercised with the aid of Microsoft Project Planner and communicated as plain text. QMS is proposed in assisting QA to create and maintain project plan of versatile projects in a more sophisticated fashion. The goal was to make the process easy for the end user and provide a GUI so as to make even most complex tasks very simple and also aids at easier access of the project plan, generating reports out the available data, etc.
Technologies: Java, J2EE, JSP, JavaScript, Struts, SQL Server, XML.
Reconciler
Worked on an infrastructure whose aim to compare the two sets of data, find out the inconsistencies between them, and then resolve them. Process involves going through various normalization rules, performing various computations etc before actually comparing the firm side data with third party data, identifying the inconsistencies and reasons for same and finally, resolving the differences.
Technologies: Core Java, Struts, SQL Server, Sybase, Perl, XML.
Developed various Cognos reports
Developed various reports as per different requirements, varying from the simple to complex ones.
PERSONAL DETAILS Date of Birth: 20th September 1987
Home Town: Mandi Gobindgarh
Father’s Name: Mr. Dharam Pal Garg
Permanent Address: House No. 208, Subhash Nagar, Gali No. 1, Sector 20D,
Mandi Gobindgarh, Punjab - 147301
- 0of 0 votes
AnswersEmployees in my company are complaining about elevator, saying its too slow... Lift operates for 50 floors
- anonymous in United States
I hire you and you have to tell me what is the problem and solutions to it.
Input:
Motor can't be changed
You can't get a new elevator as its too costly.
Get 5 matrices you would collect and how would you use them.| Report Duplicate | Flag | PURGE
Google Applications Developer - 0of 0 votes
AnswersHow would you design a movie search engine.
- anonymous in India
Think about both abstract and specific questions. How would you answer each of them.
ex: get me romantic movies, latest movies, movies with fight of no more than 10 mins.| Report Duplicate | Flag | PURGE
Google Applications Developer - 5of 5 votes
AnswersGiven a set of numbers, find the longest subset with consecutive numbers be it any order.
- anonymous in India
Input:
S = { 5, 1, 9, 3, 8, 20, 4, 10, 2, 11, 3}
we have 2 consecutive sets
s1 = {1, 2, 3, 4, 5}
s2 = { 8, 9, 10, 11}
Ans.
s1 = {1, 2, 3, 4, 5}| Report Duplicate | Flag | PURGE
Google Applications Developer Algorithm
@Dumbo..
I see that you call 2 functions - readInput() which is O(n) and then findEquivalenceClasses().
In second function, you call DFS for each node. DFS is O(n) and so findEquivalenceClasses() becomes O(n^2) and thus overall complexity as O(n^2).
Not sure, I am missing out something in ur algo...
at least..he seemed ok..
problem is not about finding this necessarily at run time...it could be you have millions of data..you need to identify false clicks.
Probably, you can use this info to prevent this in future and calculate the correct amount of payment that can be done...last point is solely my judgement
here is my answer to this question
1. Create a new hashmap. Its key will contain starting index of contiguous set and value be ending index of contiguous set.
2. Iterator through array.
3. Let each value be x. look for x-1 and x+1 in hashmap.
case1. there exists an entry for x-1, so update its value to x if x is greater than existing value
case2. there exists an entry for x+1, get its value, say vx and insert an entry with key as x and value as vx.
case 3. there exists an entry for x; simply ignore
case 4: insert into hashmap, key x and value x
Ex: S = { 5, 1, 9, 3, 8, 20, 4, 10, 2, 11}
5 => { (5,5) }
1 => { (5,5), (1,1) }
9 => { (5,5), (1,1), (9,9) }
3 => { (5,5), (1,1), (9,9), (3,3) }
8 => { (5,5), (1,1), (8,9), (3,3) }
20 => { (5,5), (1,1), (8,9), (3,3), (20,20) }
4 => { (5,5), (1,1), (8,9), (3,4), (20,20) }
10 => { (5,5), (1,1), (8,9), (3,4), (20,20), (10,10) }
2 => { (5,5), (1,2), (8,9), (3,4), (20,20), (10,10) }
11 => { (5,5), (1,1), (8,9), (2,4), (20,20), (10,11) }
3 => { (5,5), (1,2), (8,9), (3,4), (20,20), (10,11) } -> (ignored)
after array iteration is done, repeat step 3 with minor modifications by iterating over map again and longest set will be with max diff b/w key and value.
Let key be k and value be x
case1. there exists an entry for x-1, so update its value to x if x is greater than existing value. delete entry with key = k
case2. there exists an entry for x+1, get its value, say vx and update k's value to vx.
delete entry for with key = x+1. repeat this step with x = vx
Now iterate over { (5,5), (1,2), (8,9), (3,4), (20,20), (10,11) }
5 => no action,
1 => update 1's value to 4 and delete (2,4) resulting in
{ (5,5), (1,4), (8,9), (20,20), (10,11) }
repeat with x = 4
update 1's key to 5 and delete (4,5) resulting in
{ (1,5), (8,9), (20,20), (10,11) }
8 -> update 8's value to 11 and delete (10, 11) resulting in
{ (1,5), (8,11), (20,20) }
repeat with x = 11 -> no action
20 => no action
{ (1,5), (8,11), (20,20) }
Haven't mentioned above, at each step we will maintain key-value pair with max diff. So at the end of map iteration, we have result.
Complexit = O(n)...though I'm finding this complex..Is there a simplified way of doing this.
1. Insert zeroes at A's end and sort it in increasing order.
2. Make a copy of B and sort the copy in descending order keeping a track of original positions at same time.
Ex: after steps 1 & 2
A = ( -1, 0, 0, 1)
B (original) = (3, 1, 2, 4)
B copy after sorting = ( (4,3), (3,0), (2, 2), (1,1))
now arrange A's elements in order provided by B's copy i.e. 0th value will go to 3rd pos, 1st -> 0th, 2nd -> 2nd, 3rd -> 1st
a = (0, 1, 0, -1)
start with print ("", n, n); // 1st n is num of remaining opening braces and 2nd n is num of remaining closing braces.
void print (String s, int open, int closed) {
if (open = 0) {
for (i = 0; i < closed; i++) {
s.append(")");
}
system.out.println(s);
return;
}
print(s+"(", open -1, end);
print (s+"()", open -1, end -1);
here is what we can do
low1 = 0; // even indexes
low2 = 1; // odd indexes
len = arr.length;
if (len%2 ==) {
high1 = len-2;
high2 = len-1;
}
else {
high1 = len-1;
high2 = len-2;
}
// search in even indexes
int idx = search (low1, high1, value, true); // true to say it is for even indexes
if (idx == -1) {
idx = search (low2, high2, value, false)
}
return idx;
}
int search (int low, int high, int value, boolean even) {
while (low < high) {
int mid = (low+high)/2;
if (even && mid %2 != 0) { // if index is even and mid is not even, make mid as even
mid = mid-1;
}
else if (!even & mid%2 == 0) { // if index is odd and mid is even, make mid as odd.
mid = mid -1;
}
if (a[mid] == value) {
return mid;
}
else if (a[mid] < value) {
low = mid+2;
}
else {
high = mid-2;
}
return search (low, high, value);
}
return -1;
create a new array of size arr1, lets say output array. insert all elements of arr2 into hash
len = arr1.length;
for (i = 0; i < len; i++) {
if (exists arr1[i] in hashmap) {
output[i] = output[i-1] + 1;
}
else {
output[i] = 0;
}
if (output[i] == arr2.length) {
return j; //j is last index of arr1, which contains all elements of arr1 starting from j - arr2.length
}
}
ex: arr1 = {4, 1, 6, 3, 5, 4, 3, 6, 8, 4, 1, 9, 5}
arr2 = { 4, 1, 6, 8, 9 }
ouput = {1, 2, 3, 0, 0, 1, 0, 1, 2, 3, 4, 5, 0 }
Sort the skill points in decreasing order.
1. initialize both team points to zero.
2 start from team1 and keep adding the players to it from the players list (always add the player with max points) till its score becomes more or equal to opposite team
3. now do the same - step2 with team2 and keep doing that with both team alternatively till all the players are exhausted.
4. Now at the end, if diff of players in 2 teams is 0 or 1 - you are done.
otherwise, add the players with min. pts to team having insufficient players.
ex: 100, 40, 25, 20, 10, 5
team1 : 100 -> total score = 100
team2: 40, 25, 20, 10 , 5 -> score = 100
but team1 has 1 player and team2 has 5 players. we need to move 2 players to team1.
so move players with min score i.e. 5 & 10
hope i have nt missed anything..waiting for comments...
assign player with max skill points to the team.
2. start with another
1. Sort the array treating {0} as one group and {1, 2} as one group.
2. Now again sort the array of 1 & 2.
i = 0;
j = len-1;
// first loop sorts the array with 0 at front and {1, 2} at end
while (i <=j) {
while (a[i] ==0) {
i++;
}
while (a[j] == 1 || a[j] == 2) {
j--;
}
}
// This loop sorts array of 1 & 2
i = j;
j = len-1;
while (i <=j) {
while (a[i] ==1) {
i++;
}
while (a[j] == 2) {
j--;
}
}
So you sort the array in two passes. Time complexity = O(n)
- anonymous July 24, 2012convert the number to string and then apply below steps
1. make the last digit same as first.
2. increase the middle number by 1.
repeat the steps on middle number till its length is 0 (even length) or 1 (odd length).
fun(32648)
1. make last digit as 3 - number becomes 32643
2. increase middle by 1 - no. is 32653
3. now fun(265)
3.1 no. is 262
3.2 no. is 272
3.3 fun (7) - returns 7
combining all final no. is 32723
for even length, ex: 420973
fun(420973 ) -> 420974 -> 4+fun(2097 + 1) + 4
fun(2098) -> 2 + fun(09 + 1) + 2
fun (10) -> 1 + fun("") + 1 -> 1
combining now, o/p is 421124
We can do in O(n) time and O(n) space using dynamic programming. We will construct an auxiliary array, that will tell us max loot, if we start from a particular position.
// Initialize sol[] with -1
int loot (int[] a, int i) {
int len = a.length;
if (sol[i] != -1) { // value has been set already.
return sol[i];
}
else if ( (i == len -1) || (i == len-2) ) { // We are at one of last two elements of array.
return a[i];
}
else if (i >= len) { // We have passed the length of array.
return 0;
}
sol[i] = max (a[i] + loot(a, i+2), loot(a, i+1), a[i] + loot(a, i+3));
return sol[i];
main function will call
loot(a, 0)
It could be similar to 8 queens problem.
HashMap map = new Map(); // Map to keep track of all numbers already used.
void placeNumber(int pos) {
if (pos = 8)
return;
for (int i = 1; i < 9; i++) {
int existingPos = map.get(i);
if (existingPos == pos) {
// You need to remove old entry from map, if you reach back there again by backtracking
map.remove(i);
}
if (!map.exists(i) && isPossible(pos, i) {
map.put(i, pos);
placeNumber(pos+1)
}
}
main() {
reverse(head, null, newHead);
}
public void reverse(Node head, Node prev, Node newHead) {
Node next;
if (head.getNext() != nulll) {
next = head.getNext();
}
head.setNext(prev);
prev = head;
if (next != null) {
reverse (next, prev)
}
else {
newHead = head;
}
}
Do a BFS to find the last element of tree with a small modification. Every time you remove an element from queue, store it in a variable and keep it updating. At end of BFS, this element will hold the parent of last element in tree.
So now you have root -> say r,
last element -> say e,
and parent of last element -> say p
now do as follows
left = r.left
right = r.right
r.left = null
r.right = null
e.left = left;
e.right = right;
if (p.right != null) {
p.right = r;
}
else {
p.left = r;
}
Build a hashmap with key as customer id and value as pages being visited by customer.
1. Initialize the map with pages visited by customer as on day1.
2. looping thru next days, for each customer, check if page visited is not already there in list and old list is not empty, print that customer id.
1. Loop through the array.
2. For each word, sort the characters and add it to hash map with key as sorted word and value as original word.
At end of loop, you will all anagrams as value to a key (which is sorted by its constituent chars).
3. Iterate over the hashmap, print all values of a key together and then move to next key.
Space complexity: O(n), time complexity: O(n)
// formatting it now
if (head == null) {
return;
}
reverseByRecursion(head, null);
public void reverseByRecursion(ListNode node, ListNode prev) {
ListNode temp = node.getNext();
node.setNext(prev);
if (temp == null) {
head = node;
return;
}
reverseByRecursion(temp, node);
}
// formatting it properly
if (head == null) {
return;
}
reverseByRecursion(head, null);
public void reverseByRecursion(ListNode node, ListNode prev) {
ListNode temp = node.getNext();
node.setNext(prev);
if (temp == null) {
head = node;
return;
}
reverseByRecursion(temp, node);
}
Just a little modification to above algo.
after we have (3,0)(4,1)(5,8)(6,2)(7,3)(8,4)(9,6)(10,5)
start splitting at each position one by one and see if maxIndex -minIndex + 1 == length of partition
1. partition is (3,0) and (4,1)(5,8)(6,2)(7,3)(8,4)(9,6)(10,5)
for left it is 0-0+1 == 1, so possible with len = 1
for right it is 8-1+1 !=7
2. partition is (3,0)(4,1) and (5,8)(6,2)(7,3)(8,4)(9,6)(10,5)
for left, 1-0+1 ==2, len = 2, maxlen becomes 2
for right, 8-2+1 != 6
3. partition is (3,0)(4,1)(5,8) and (6,2)(7,3)(8,4)(9,6)(10,5)
for left, 8-0 + 1 != 3
for right, 6-2 +1 == 5, len = 5, maxlen becomes 5
and so on
at the end you have the ans.
taking help from luke's post
public class ShuffleArray {
public static int nextIndex(int index, int len) {
int nxt = index*2;
if (nxt >= len) {
nxt = (index - len/2)*2 + 1;
}
return nxt;
}
public static void main(String args[]) {
char[] arr = { 'a', 'b', 'c', 'd', 'e', 'A', 'B', 'C', 'D', 'E'};
int len = arr.length;
boolean[] b= new boolean[len];
for (int i = 0; i < len; i++)
b[i] = false;
/* Idea is to start from index 1, find what should be its position
* using method nextIndex. then replace the element and find the desired
* position for that element. Keep on doing that, until you have
* touched all positions.
*/
int count = 0;
for (int i = 1; i < len/2; i++) {
// Finding reqd position for i.
int n = nextIndex(i, len);
int j = i;
char temp1 = arr[i];
// you may reach back to original position or the one that has been touched already.
while ( (n != j) && b[n] != true ) {
System.out.print("j=" + j + ", n=" + n);
char temp2 = arr[n];
arr[n] = temp1;
temp1 = temp2;
j = n;
// indicate the position is touched.
b[n] = true;
n = nextIndex(j, len);
for (int k = 0; k < len; k++) System.out.print(arr[k] + ", ");
System.out.println();
count++;
}
}
System.out.println(count);
}
}
I think nC3 is the scenario for triangles for n points in plane and not lines. ex: i don't know how to create 4C3 triangles from 4 lines.
1. let p1, p2, ...pk be the set of parallel lines. for each set, we have to consider one line.
2. actual count of lines to be considered is:
c = c-k (1 for each pi where i = 1...k)
3. with c lines, traingles are c-2
4. now each set of parallel line, let pi be involved in formation for qi number of traingles,
final count = (c-2)+ q1(p1-1) + q2(p2-1) + qn(pn-1)
NOTE: this doesn't consider small traingles being part of bigger triangles
a=[600, 500, 400, 300, 260, 220] and b = [200, 97, 50, 11, 10 , 3].
1. take diff of each element from first element and create new dummy arrays
For this A' = [0,100,200,300,340,380] and B' = [0,103,150,189,190,197]
2. now based on diffs, create pairs
first pair = 600, 200
A'[1] < B'[1] => choose A'[1] and go to first (i.e zeroth) element of B.
2nd pair = 500, 200
A'[2] > B'[1] => choose A[0] & B[1]
3rd pair = 600, 97
A'[2] > B'[2] => choose A[0] & B[2]
4th = 600, 50
A'[2] > B'[3] => choose A[0] & B[3]
5th = 600, 11
lly, 6th = 600, 10;
A'[2] > B'[5] => choose A[0] & B[5] 7th = 600, 3
now choose A[1], B[1]
in case, all words are of equal length - solution is simple. We can simply keep inserting the words in a hashset and while inserting a word - we check if reverse of word already exists in set. If it exists, answer is yes and we break, else answer is no when we reach the end of list.
- anonymous May 23, 2015Complexity is when words are of different length. Here is the proposal, ran over several cases and seem to work fine
1. We shall maintain 2 tries - one for original words (trie1) and one for reversed words (trie2).
2. For each word, check if exists in the trie1. If not, insert it in trie1. Also, look for the word in trie2 following it char by char.
a. No match - move on
b. There is a match and you reach the sentinel node by the end - this means 2 words form a palindrome and you can put them in any order.
c. There is a match and either it is non-sentinel node and word is still left. Check if remaining portion is palindrome. If yes, word in trie2 forms the prefix of final palindrome and current word forms the suffix.
3. Reverse each word, check if exists in the trie2. If not, insert it in trie2. Also, look for the word in trie1 following it char by char.
a. No match - move on
b. There is a match and you reach the sentinel node by the end - this means 2 words form a palindrome and you can put them in any order.
c. There is a match and either it is non-sentinel node and word is still left. Check if remaining portion is palindrome. If yes, word in trie1 forms the suffix of final palindrome and current word forms the prefix.
Complexity is O (2kn) since each workd is traversed twice