lngbrc
BAN USER 2of 2 votes
AnswersWAP to sort prime numbers smaller than given N by digits. If N is 40, the output should be 11, 13, 17, 19, 2, 23, 29, 3, 31, 37, 39, 5, 7.
 lngbrc in United States
Followup question: limit memory usage. Report Duplicate  Flag  PURGE
Amazon Senior Software Development Engineer Math & Computation
Firstly, need to ask interviewer to clarify:
 # of log entries/day, # of pages and # of users? can the data fit into a traditional DB or requires distributed storage. I assume the analyzed results can be loaded into an RDBMS.
 is this realtime analysis or can we use a Hadoop job to ETL? I assume ETL is allowed.
 should we optimize for query performance or write performance? I assume query performance is more critical.
The solution is to write raw log data to HDFS, using Apache Flume to support multiple data centers. Use Hadoop job to analyze the raw data and load results into an RDBMS for query.
In RDBMS, to support the first two queries, we can use a table with columns "page, usercount, visitcount". For third query, we can create a table with "page, userid, count".
for (int i = 0; i < tgt.length; i++) {
if (tgt[i] == 0) continue;
int pos = findPos(src, tgt[i]);
if (i == pos) continue;
int posZero = findPos(src, tgt[i]);
if (posZero != i) {
swap(src[posZero], src[i]);
}
swap(src[pos], src[i]);
}
an improvement maybe to cache zero position in src to avoid an lookup.
 lngbrc August 29, 2013I would use recursion to solve this problem:
public static boolean IsKPalindrom(char[] arr, int k) {
int match = 0;
if (arr.length <= 1) return true;
// try to match front and back of the string
for (match = 0; match < (arr.length / 2); match ++) {
if (arr[match] != arr[arr.length  match  1]) {
break;
}
}
if (match >= (arr.length / 2) {
// Yeah!
return true;
} else if (k == 0) {
// not palindrom, and we cannot remove any more characters
return false;
} else {
// remove 1 char and call recursively
return isKPalindrom(arr.subarray(match + 1, arr.length  match  1), k  1) 
isKPalindrom(arr.subarray(match, arr.length  match  2), k  1);
}
}

lngbrc
August 29, 2013 correction...
public static void Arrange(int[] arr)
{
int pos = 0;
int neg = 0;
for (int i = 0; i < arr.length; i ++) {
if (i%2 == 0) {
for (pos = max(pos, i); pos < arr.length; pos ++) {
if (arr[pos] > 0) break;
}
if (pos >= arr.length) break; // all remaining numbers are negative, exit
if (pos != i) {
swap(arr, pos, i);
pos ++;
}
} else {
for (neg = max (neg, i); neg < arr.length; neg ++) {
if (arr[neg] < 0) break;
}
if (neg >= arr.length) break;
if (neg != i) {
swap (arr, neg, i);
neg ++;
}
}
}
}
public static void Arrange(int[] arr)
{
int pos = 0;
int neg = 0;
for (int i = 0; i < arr.length; i ++) {
if (i%2 == 0) {
for (pos = max(pos, i); i < arr.length; i ++) {
if (arr[pos] > 0) break;
}
if (pos >= arr.length) break; // all remaining numbers are negative, exit
if (pos != i) {
swap(arr, pos, i);
pos ++;
}
} else {
for (neg = max (neg, i); i < arr.length; i ++) {
if (arr[neg] < 0) break;
}
if (neg >= arr.length) break;
if (neg != i) {
swap (arr, neg, i);
neg ++;
}
}
}
}

lngbrc
August 29, 2013
Replisaramsey773, Blockchain Developer at Adjetter Media Network Pvt Ltd.
I'm a 27 yearold blogger, makeup junkie and follower of Christ.I love all things that bring happiness. My ...
Open Chat in New Window
similar to "sort using two stacks" problem from "cracking..." book. treat the linked list as stack, and add another stack (linked list) to keep sorted results.
 lngbrc May 22, 2015