Mo Lam
BAN USERI am looking for a job in CS/Math industry.
I was a 2 times USAMO qualifiers (ranked 80th in USA in 2010).
A former captain of NYC Math team's A team (2010).
A current volunteer count of NYC math team.
Mo Lam
5836 Penrod Street,
Corona, NY 11368
(646) 831-0919 (Cell)
moplam@gmail.com
Age: 20
--------------------------------
Education:
Stony Brook University (2010 – 2012)
B.S. in Mathematics, Applied Mathematics and Statistics
Graduation Honor: Summa Cum Laude
Major GPA: 4.0
Cumulative GPA: 3.94
HS for Math, Science, and Engineering (2006 – 2010)
High School Diploma (Engineering Track)
----------------------------------------
Skills:
Excellent Math skill, was once ranked 80th in USA/Canada amongst all HS students in USA Math Olympiad.
Fluent in Cantonese and Mandarin. Able to read, write and type in both traditional and simplify Chinese.
Leadership experience in a sport club in college and New York City Math Team.
Able to create dynamic (object oriented) webpage / database with the following languages:
PHP, HTML, CSS, XML, Perl, Google API, SQL (MySQL, SQLite, …), Javascript and AJAX
Able to program with:
C/C++, Java, Unix shell script, Maple, LaTex
--------------------------------------------
Extra-Curricular Activity, Leadership, and other Experience:
New York City Math Team (2007 – present)
Member since February 2007. Member of the A team since 2009.
Captain of NYC Queens team (2009, 2010 @ state level).
Captain of NYC A team (2010 @ national level).
USA Math Olympiad participant for 2009 (ranked 246th individually in USA/Canada), 2010.(ranked 80th)
Student Coach of New York City Math Team (2010 – present)
Stony Brook University Company of Archers (Archery Club) (2010 – 2012)
Executive board member (Secretary) for 2011 – 2012 academic year (committed ~20 hours per week). Expanded the club to a club with ~100 members and ~30 regular members.
Field Marshals of the club for Spring 2011 and Fall 2012
Undergraduate teaching assistance for ISE305 - Database Design class in Stony Brook University (Fall 2012)
Teaching assistance for Calculus BC in HS for Math, Science, and Engineering (2009 – 2010 academic year)
----------------------------------------
Major Awards and Honor:
December 2012: Summa Cum Laude honor
Spring 2011, 2012, Fall 2011: Academic Achievement Awards (4.0 semester GPA)
2011: Top 500 in William Lowell Putnam Competition 2011 (410th in USA/Canada)
2010 – 2012: Digication e-portfolio showcase star of Stony Brook University
2010 (80th in USA/Canada), 2009 (236th): USA Math Olympiad
June 2010: UFT Albert Schanker Scholarship recipient
2010: Captain of NYC A team
and much more
To analyze this question, I think you should not jump right into coding, you should imagine plotting a graph of X vs. rating. The people at the relative minimum will get the lowest hike, then go from there left and right and increment each one by the minimum hike until you hit the relative maximum, so instead of doing any crazy manipulation, I will just find all relative max and min.
Using your example: 1,4,6,2. 1 and 2 are the relative min, so they get the least.
The thing to look out for are when 2 adjacent people have the same rating.
I will leave the rating to you and only write a function to output the hikes (I will write it in Java, haven't wrote Java code in a while so it may be slightly off)
/*** Editing: did not realize that 2 people adjacent will not have same rating ***/
public void(int minhike, int[] ratingArr, int[] hikeArr)
{
int count = ratingArr.length;
int[] relativeMax = new int[count];
int[] relativeMin = new int[count];
// these 2 can be some list to reduce space, I am too lazy to do it now
int i=1,j=0,k=0,l=0,m=0;
bool increasing = (ratingArr[0] < ratingArr[1]);
bool first = increasing;
for(i=1;i<count;i++)
{
if (increasing)
{
if(ratingArr[i] < ratingArr[i-1]) {relativeMax[j++] = i-1; increasing = false;}
//change from increasing to decreasing
}
else if(ratingArr[i] > ratingArr[i-1]) {relativeMin[k++] = i-1; increasing = true;}
//the other way
// this way 1 is included in the relativeMax or Min, but we have to take care of the last one
}
if(increasing) relativeMax(j++)=i-1
else relativeMin(k++)=i-1 // log the last one too.
//Now relative Max and Min are logged. j and k will be differ by at most 1, they may be equal.
for(i=0; i < j;i++)
{
hikeArr[relativeMin[i]] = minhike;
if(first) // if it started by increasing
{
if(i < k) // in case if k > j
for(l = relativeMin[i] + 1; i < relativeMax[i];l++)
hikeArr[l] = hikeArr[l-1] + minhike;
if(i != 0)
for(l = relativeMin[i] - 1; i > relativeMax[i-1];l--)
hikeArr[l] = hikeArr[l+1] + minhike;
}
else //started decreasing we can be assure that j <= k
{
for(l = relativeMin[i] + 1; i < relativeMax[i+1];l++)
hikeArr[l] = hikeArr[l-1] + minhike;
for(l = relativeMin[i] - 1; i > relativeMax[i];l--)
hikeArr[l] = hikeArr[l+1] + minhike;
}
// At this point, all hike except the relative max's are stored. Also, if 2 consecutive value are both relatively min/max, I only store one.
for(i = 0 ; i < k; i++)
{
l = relativeMax[i];
if(l = 0) hikeArr[0] = hikeArr[1] + minhike;
else if (l = count - 1) hikeArr[l] = hikeArr[l-1] + minhike;
else hikeArr[l] = (hikeArr[l-1] > hikeArr[l+1] ? hikeArr[l-1] : hikeArr[l+1]) + minhike;
}
}
}
This is still HS math. You just don't know your linear algebra well enough.
Step 1) do a determination test (write a 3x3 det function, please don't tell me you can't even write an expression) If it is 0. It may have 0 or infinite solution
Step 2) Applied row reduction, but if det is not zero, you can divide the first row and make a[0][0] = 1. Then make a[0][1] = a[0][2] = 0, then make a[1][1] = 1 and a[0][1] = a[0][2] = 0, and do it for a[2] (maybe I indexed it backward from yours? whatever that is not the point). Then you finished row reduction and have the unique solution.
This is more of an opinion base question.
When I program in any language (especially on non-object-oriented languages), I program my code piece by piece and make sure each parts works individually.
So first thing first:
1) Find out where the error(s) are occurring. If you have good coding practice, more of the time you should be dealing with not so many errors.
1a) When you have a function (classes too for other languages), make sure it works for all cases. It is very important.
1b) If any of your function (including your main) is >100 lines, you should ask yourself if you should simplify (break it down further?) it (well for smaller stuff probably go for smaller numbers)
2) fix everyone of your functions (especially the ones used by the features that is having error). (+ if you do it well, you don't have to go double/triple checking them)
3) check your main process.
Also, fix the cases in my SQL.
If you do not use subquery, you will need a 3 table join (DVD a <--> Person <--> DVD b). both on OWNER_ID = PERSON_ID, where a.Title = 'superman' and select DISTINCT b.Title
SELECT DISTINCT b.Title
FROM (DVD a,Person p INNER JOIN Person p ON p.Person_id = a.Owner_ID) INNER JOIN DVD b ON p.PersonID = b.Owner_ID
WHERE a.Title = "Superman"
Write a query that returns the list of DVDs that belong to owners who own “Superman”
--> the list of DVDs should be distinct, and you only want the DVD Titles (At least when I was teaching assistance for a DB class, I make my student not to output useless stuff).
This line only give you SUPERMAN and nothing else. It is wrong. All, the where clause is wrong-.-
You should do subquery. first get the people with SUPERMAN, kindof like your query:
SELECT Owner_ID
FROM DVD d
WHERE Title = 'Superman' ;
Then join them back and get all DVD title
SELECT DISTINCT Title
FROM DVD d,Person p INNERJOIN Person p ON p.Person_id = d.Owner_ID
WHERE p.Person_ID IN
(SELECT Owner_ID
FROM DVD d
WHERE Title = 'Superman') ;
When the file is "large", they usually mean that you can't throw the whole thing into your memory. If you can fit it in your memory, then all you need is a hashmap for both day and compare them carefully.
So what if you can't fit it all into your memory. My solution would be a bucket sort (in a different sense).
You probably would use up some harddisk space to accomplish this. You should put all of the once with last name starting with A into a file, all of them starting with B into a file, etc. Then you have smaller files to deal with and you only need to compare the A files with each other, B files with each other, etc.
Now, if the files are not small enough, you can break them down using the second letter. You need to break it up until both file can fit into your memory with enough memory to do other things too.
Now for each pair of files (yesterday's A and today's A, etc).
You can sort them using your normal O(log(n)) methods, and then compare line by line. And log them into your desire log file (note that there's a chance that the log won't fit into your memory, print them to your hard disk too)
Now that I think more about it,
first position's output depends on last position's input,
--> We can't do it with simple AND/OR/NOT (XOR, and anything form by the 3 basic)
--> We need to some how have shifted 1st pos to last, 2nd to (2nd to last).
--> My ways work, but it's probably more efficient if we shift alternate bits >> 1 << 1, then alternate 2 bits >>2 <<2, etc. (issue with this is we don't know the size of the binary number, can't be sure that it's power of 2).
The only thing I can come up with is reversing bit by bit. I don't think there's any good binary operation for this.
unsigned int a = 100; //just treat a as your binary number,
unsigned int b = 0; // the final result
int s = sizeof(a) * CHAR_BIT; // # of bits in a;
for(int i = 0; i < s; i++)
{
b <<=1; // left shift b
b |= a & 0x1; //get unit bit
a >>= 1; // right shift a
}
//now b is your result
The logic behind this is:
Let's say
a=1010
Step 1:
a=0101
b=0001
Step 2:
a=0010
b=0010
etc.
Great idea, but if you are using C pointer (hence the language is C or C++), this requires you to implement a stack (well, it's very easy, but still) of Strings. + It takes up extra memory.
Using C pointer, reserving the whole string, then reverse individual words is better.
O(n)? Are you sure? I am not used to this language that you use so I am having a very hard time to read, but I don't think this gives O(n).
What is the time complexity for "11111111...11111" ? It looks like O(n^2) to me.
In fact, I can't understand what it does for "111111111111111".
The fact that we are only looking for even length palindrome makes it a lot easier.
For even length palindrome, the middle 2 characters are the same, so we can find all occasion and find the longest palindrome from there.
Record the max length and the start of of longest palindrome, and output using these data at the end.
char* leftmostOfPalindrome(char* r)
{
char* l = r++;
while(*(l-1) == *(r+1)){l--; r++;}
return l;
}
char* longestPalindrome( char* s)
{
char* cur = s, *cur_lt, *result, *palin;
int l = 0, max_l = 0;
while(*cur != '\0')
{
if(*cur == *(cur+1))
{
cur_lt = leftmostOfPalindrome(cur);
l = (cur - cur_lt + 1) * 2;
if(l > max_l){max_l = l; result = cur_lt;}
}
cur++;
}
palin = (char*) malloc (max_l+1);
for(l = 0; l < max_l; l++) palin[l] = result[l];
palin[l] = '\0'; //if max_l = 0, palin = "\0";
return palin;
}
Code Tested for C++ using "testtsettesttset12312313", "1331", "11111111111111"
Worst case scenrio, "11111111111111", etc. It will have O(n^2). Barely any extra memory is allocated (you can't not use the malloc since you need to return it while not destroying the original data,
Well, if only 1 person can pass each time, it will take 21 minutes, but 2 people can cross the bridge at the same time, so the minimum optimal time is 10.5 (assume that the bridge has 2 people crossing at any given time, which is impossible if t is not integer), and we can tell that the optimal solution is integer.
11 works, (7 & 10 go, 3 go when 7 reach the other side, at t = 10, 1 go across // one side 3 & 7 & 1, the other 10). Thus, 11 is the optimal solution.
public static int[] find(int[] A, int z /*,int k if k is given */)
{
int i,size;
int B[z]; // it best to do max of (k,z)
/* //if k is given
if (z > 2k) return null;
for(i =0; i < z; i++) B[i] = -1;
*/
for(i = 0; i < A.length /* note */; i++) // or use true and break when you reach the end of the array if you can't get size of A
{
if (A[i] >= z) continues; // useless number
if(B[z-A[i]] > 0) return {i, B[z-A[i]]};
B[A[i]] = i; //B[5] is index of last 5
}
return null;
}
This function returns i, j for A[i] + A[j] = z; and it accounts of 5 + 5 = 10; Also returns null if fails.
- Mo Lam April 24, 2013You should never assume an array is sorted (@ the other answers)
One way to do this is:
Pseduo-code:
public static int[]/*array? depending on your language*/ find(int [] A, int z/* , int k if exists*/)
{
int i, size;
/* //if k exists
if (z > 2k) return null; // because you can't add 2 number from 1 to k to get anything <2, >2k
size = k;
*/
size = z;
int B[size] = {}
for(i = 0; i < size; i++)
B[i] = -1; //initialize B
for(i = 0; i < A.length; i++) //you may not need A.length if you can't find it with your language, just exit when the array ends
{
if(A[i] >= z) continues; //if A[i] >=z, A[i] + a[j] > z
if(B[z - A[i]] > 0) return {i, B[z-A[i]]};
B[A[i]] = i; // this will make B[5] store the index for last 5, you can use an if too, but waste of comparison
}
return null; // if the function does not return in the for, there is no such pair.
}
I did not catch that no 2 adjacent employee has the same rating, but the's no way 2 people sitting next to each other with different rating to both be relative min (at least for a integer plot)
- Mo Lam August 25, 2013