mytestaccount2
BAN USERMaintain a bitset of size(7*24*60*60) i.e. num of seconds in a week.
Now, for each interval, mark these bits true.
In the end, if all bits are 1, then the entire week is covered, else not.
Assuming the input to be number of seconds since Sunday 00:00:00, there will be 2
Special cases:
1. an interval spans more than a week, we need to immediately return true.
2. an interval starts at let's say friday and ends on tuesday next week.
For this, we need to set bits for fridaysaturday night, and shift offsets of sundaytuesday by 7*24*60*60
void findPairThatSumsCloseToZero(vector<int> a)
{
int i, j, best, cur_best, n = a.size();
int best_start, best_end;
if (n < 2) return;
sort(a.begin(), a.end());
i=0, j=n1;
best = a[i] + a[j], best_start = i, best_end = j;
while (i < j) {
cur_best = a[i] + a[j];
if (abs(cur_best) < abs(best)) {
best = cur_best;
best_start = i, best_end = j;
}
if (cur_best < 0) {
i++;
} else if (cur_best > 0) {
j;
} else {
break;
}
}
printf("closest to zero=%d found at index %d and %d\n", best, best_start, best_end);
}

mytestaccount2
April 13, 2015 void findPairThatSumsCloseToZero(vector<int> a)
{
int i, j, best, cur_best, n = a.size();
int best_start, best_end;
if (n < 2) return;
sort(a.begin(), a.end());
i=0, j=n1;
best = a[i] + a[j], best_start = i, best_end = j;
while (i < j) {
cur_best = a[i] + a[j];
if (abs(cur_best) < abs(best)) {
best = cur_best;
best_start = i, best_end = j;
}
if (cur_best < 0) {
i++;
} else if (cur_best > 0) {
j;
} else {
break;
}
}
printf("closest to zero=%d found at index %d and %d\n", best, best_start, best_end);
}

mytestaccount2
April 13, 2015 DUP of 13467664
 mytestaccount2 April 13, 2015string addBinaryStrings(string a, string b)
{
string c;
int carry = 0;
int lena = a.length(), lenb = b.length();
int i=lena1, j=lenb1, k=max(lena, lenb)1;
c.resize(k+1, '0');
while (i>=0 && j>=0) {
c[k] = ((a[i]'0') ^ (b[j]'0') ^ carry) + '0';
carry = (carry + (a[i]'0') + (b[j]'0')) > 1 ? 1 : 0;
i,j,k;
}
while (i>=0) {
c[k] = (carry ^ (a[i]'0')) + '0';
carry = (carry+(a[i]'0')) > 1 ? 1 : 0;
i,k;
}
while (j>=0) {
c[k] = (carry ^ (b[j]'0')) + '0';
carry = (carry+(b[j]'0')) > 1 ? 1 : 0;
j,k;
}
if (carry) return "1" + c;
return c;
}

mytestaccount2
March 22, 2015 bool isReachable(int a[], int n)
{
int maxwecango = a[0];
int i = 1;
if (n == 1) return true;
if (n < 1) return false;
while (i <= maxwecango) {
if (i == n1) return true;
if (i+a[i] > maxwecango) {
maxwecango = i+a[i];
}
i++;
}
return false;
}

mytestaccount2
March 11, 2015 Very nice approach!
But it fails for the following boundary case:
A[] = {0}
@gevorgk: Awesome!!
 mytestaccount2 March 07, 2015@Kim: Because 2D array reserves O(r*c) space even if we will be using only few cells(as it is sparse)
 mytestaccount2 March 03, 2015void printLongestSubstringOfUniqueChars(const char *s)
{
int i, j, map[256] = {0};
int n = strlen(s), overall_best = 0, cur_best = 0, overall_offset=0, cur_offset = 0;
for (i=0; i<n; i++) {
if (map[s[i]] == 0) {
map[s[i]] = 1;
cur_best++;
if (overall_best < cur_best) {
overall_best = cur_best;
overall_offset = cur_offset;
}
} else {
for (j=cur_offset; j<i; j++) {
map[s[j]] = 0; cur_best;
if (s[j] == s[i]) {
j++; break;
}
}
cur_offset = j; map[s[i]] = 1; cur_best++;
printf("cur_offset became %d\n", cur_offset);
}
}
printf("ans: ");
for (i=overall_offset; i<overall_offset+overall_best; i++) {
printf("%c", s[i]);
}
printf("\n");
}

mytestaccount2
February 23, 2015 #include <stdio.h>
#include <stdlib.h>
#define INF (~0)
/* This can be optimized by caching */
unsigned int stick_length(int sticks[], int s, int e)
{
unsigned int i, ans = 0;
for (i = s; i <= e; i++) {
ans += sticks[i];
}
return ans;
}
unsigned int join_sticks(int sticks[], int s, int e, unsigned int **cache)
{
int k, p1, p2, tmp;
if (s > e) return INF;
if (s == e) return sticks[s];
if (cache[s][e] != INF) {
return cache[s][e];
}
for (k = s; k < e; k++) {
p1 = join_sticks(sticks, s, k, cache);
p2 = join_sticks(sticks, k+1, e, cache);
/* adding stick lengths, not same as making cost */
tmp = stick_length(sticks, s, k) + stick_length(sticks, k+1, e);
/* adding making cost */
if (k > s) tmp += p1;
if (k+1 < e) tmp += p2;
if (tmp < cache[s][e]) {
cache[s][e] = tmp;
}
}
return cache[s][e];
}
int main()
{
int i, j;
int sticks[] = {24, 25, 28, 4, 6, 10, 9};
// int sticks[] = {2, 3, 4, 6};
// int sticks[] = {2, 3, 4, 6, 7};
// int sticks[] = {13, 4, 6};
int n = sizeof(sticks)/sizeof(sticks[0]);
unsigned int ans;
unsigned int **cache;
cache = (unsigned int **)calloc(n, sizeof(int *));
for (i = 0; i < n; i++) {
cache[i] = (unsigned int *)malloc(n*sizeof(int));
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
cache[i][j] = INF;
}
}
ans = join_sticks(sticks, 0, n1, cache);
printf("ans: %u\n", ans);
return 0;
}

mytestaccount2
April 06, 2014 /*
* Find if any anagram of a, is present as a substring in b.
* Returns offset of string b, where anagram can be found.
* Otherwise: Returns NULL
*/
char * find_anagram(char *a, char *b)
{
if (!a  !b) return NULL;
int i, j;
int offset = 0;
int alen = strlen(a);
int blen = strlen(b);
char hash[256] = {0};
for (i = 0; i < alen; i++) {
hash[a[i]]++;
}
for (i = 0; i < blen; i++) {
/* If char available, decrement count,
* return if this was the last character to match
*/
if (hash[b[i]] > 0) {
hash[b[i]];
if (ioffset+1 == alen) {
return b+offset;
}
} else { /* If character not present OR if character exhausted,
* then remove the prefix starting from offset, until we
* find first character with the same value as current character
* i.e. b[i], At that point, move answer(offset) further.
* Example: a = "pqrp"; b = "rqpqpptpqprz";
*/
for (j=offset; b[j]!=b[i]; j++) {
hash[b[j]]++;
}
offset = j+1;
}
}
return NULL;
}

mytestaccount2
April 03, 2014 Is it possible to do this with recursion and still get O(N^3) complexity?
 mytestaccount2 February 21, 2014@BIN: this case will be covered by existing conditions.
 mytestaccount2 December 30, 2013#include <stdio.h>
#include <string.h>
#define FALSE 0
#define TRUE 1
typedef unsigned char BOOL;
typedef struct {
char *input;
char *pattern;
} test_case;
BOOL regex_match(char *s, char *p)
{
if ((!s[0] && !p[0]) 
(!s[0] && p[0] == '*' && !p[1])) {
return TRUE;
}
if (p[0] == '?'  p[0] == s[0]) {
return regex_match(s+1, p+1);
}
if (p[0] == '*') {
return regex_match(s, p+1)  // ignore the '*' completely
regex_match(s+1, p); // '*' in pattern consumes s[0]
}
return FALSE;
}
int main()
{
int i;
test_case tc[] = {
{"abcd","abdd"},
{"abcd","abcd"},
{"abcd","ab?d"},
{"","?"},
{"ab","?*"},
{"a",""},
{"","a*b"},
{"","****"},
{"","*c"},
{"",""},
{"","*"},
{"acfdfcdcdcd","a*cd*cd"},
{"abdfpdcdcd","ab*cd"},
{"abdfpdcdcd","ab*"},
};
for (i=0; i<sizeof(tc)/sizeof(tc[0]); i++) {
if (TRUE == regex_match(tc[i].input, tc[i].pattern)) {
printf("\"%s\" matches \"%s\"\n", tc[i].input, tc[i].pattern);
} else {
printf("\"%s\" doesn't match \"%s\"\n", tc[i].input, tc[i].pattern);
}
}
return 0;
}

mytestaccount2
December 29, 2013 Maintain a hashmap, where key is the sorted line.
e.g if a line is "3 2 6 1 4", it will be treated as "1 2 3 4 6" in hashtable.
Now, for each line:
1. sort it
2. lookup in hashmap
3. if it is not present, then enter it in hashmap and output it
4. if it is present, then don't do anything and continue to next line.
This code doesn't even compile, and after fixing it, it doesn't solve the following inputs:
1100101
12344680
1299111210
Awesome solution @JancoderSS
 mytestaccount2 October 10, 2013It can be due to many reasons e.g.:
1. Memory pressure, vmsize limit reached, connection limits or open file handle limits
2. Network is unreliable
3. Hardware Failure
4. Using Debug v/s regular binary
5. Race conditions (no locks in multithreaded program)
6. Dynamic Backend(e.g. no. of nodes in a social graph can increase/decrease)
7. Memory leaks.
8. Bugs in shared memory code/data
9. Time Difference b/w your node and another server.
10. Timeouts/ Max Time to Live expired e.g. Session Expiration
What is 'k' here?
 mytestaccount2 October 08, 2013Different solutions:
a) Sort the array of strings
b) Put each string in a Set
c) Put each string in a HashMap
d) Construct a Trie from array of strings.
@siva.sai.2020, your solution works only if n is an integer.
It doesn't work if n needs to be 1.5 years e.g.
1) How to find intersection across 'N' sorted arrays:
We can make use of a minheap.
Insert all A1[0],A2[0],...,An[0] in minheap.
while minheap is not empty, keep removing a document id from it.
Then increment the Ai from which this element came.
Whenever we find the same document id popping out 'N' times successively,
that implies that it is present in all the documents.
The idea is similar to merging 'N' sorted arrays.
2) Improvements when one array is small and other is relatively bigger.
Search each element of smaller Array in the bigger one.
complexity: O(m logN) where m<<N
3) Distribute computation across set of machines:
Assuming there are 'M' machines available:
assign N/M (provided M < N) arrays for finding intersections to each of them.
Now wait for each machine's intersection list.
Repeat the same distribution steps, until you get one final list i.e. list of document ids.
Each doument id in this list will contain all the search terms.
@Nova2358 : Can this be done using recursion instead of using explicit stacks,
like the regular BST traversal works.
@gavinashg:
I think it's because we want to minimize cube of empty spaces throughout the paragraph of lines.
Greedy doesn't guarantee that.
@Saimok : Nice!
 mytestaccount2 September 09, 2013@lucas.eustaquio:
Nice work! But, it only works on the assumption that arrays A, B, C are sorted.
If that is not the case, then we will have to do a stable sort on these arrays
and store them in aux array taking O(A + B + C) space.
I thought on the same lines.
But I think we can do it in O(A + B + C) time.
This is because the values are already sorted.
We just have to think in terms of a window which contains atleast 1 element
from A,B,C
I think the example states incorrectly that circles whose center is at (0,0) and (0,1)
intersect. Since second circle's radius is 5, and first one's is 1, they don't intersect.
You would also need to have a Hash Table, otherwise how would you know
which BST facebook.com currently belongs to.
i.e. if facebook.com has been visited 4 times(therefore present in BST with key=4), and now we get another visit, how would we know that we have to move it from BST with key=4 to BST with key=5.
That can be achieved with Hash Table, storing a count for each webpage for that particular day.
 Arrays provide contiguous memory, while LL doesn't
 Element at a particular index in an array can be accessed in O(1), for LL it is O(N)
 Adding/Deleting element from the middle in an array is O(N), however for LL it is O(1)
due to rearranging of pointers.
 Arrays are limited due to memory constraints of contiguous allocation.
Linked Lists have no such constraint.
what is the time granularity of one index of the circular array?
Is it no. of connections in one sec or one minute?
Return HTTP 302 Redirect Response, and specify the other data center as the
new target address.
When the client gets the HTTP reply, it will send the request to the second data center
and it will know how to resolve it.
 Show road delays due to accident/fire etc.
 Speed
 Offline Access
 Live Street View
 Traffic updates for commonly traveled paths saved by a user e.g. commute to office/school etc.
 Should highlight recent places visited by Friends
 Support for checking out shops, parks, etc. online via Street View
 Highlight alternate routes in different colors based on travel time, toll, miles etc, no. of red lights etc.
 Show recently searched directions for a particular user
 Show commonly taken paths in a specific area(zipcode, city, state)
Idea is similar to finding majority element in an array.
Let 'x' be the element present 'n' times in the array.
We'll compare 2 consecutive array indices at a time e.g 0,1 2,3 4,5 and so on.
If any of these comparisons finds two matching numbers, then that is our answer.
However there is a corner case where 'x' is present alternately
e.g. x1x2x3x4x5x6x7x8x9xA....
In this case, at the end of 'n' comparisons(see above step), we won't be finding any match. Now, if we compare the last four elements, we are guaranteed to find two x's.
We don't need to scan the whole array as wenlei.zhouwl mentioned.
Few ideas:
 Find people who are common friends to your friends.
Let's say you have 50 friends, a person who is friends with most of these,
is highly likely to be known to you as well.
 Friend suggestion could also be determined from the communities/groups/interests/places
you are part of.
 Photographs tagged with many people including you, can offer very good
friend suggestions.
We can have a number of systems serving a range of keyval pairs.
Periodically, each system will broadcast its range of keys served to other systems.
A client can connect to any system to get the value for a key.
If that particular server doesn't have the answer, it can redirect the client to the
appropriate system.
LinkedHashMap
 mytestaccount2 August 19, 2013typedef struct
{
Mutex m;
int reader_cnt; // initialize to 0, 0 means available for reader or writer
// 1 means taken by a writer
// >0 means taken by readers
} RWLock;
int read_lock(RWLock *lock)
{
int res = 0;
MutexLock(lock>m);
if (reader_cnt == 1 ) // taken by writer
{
MutexUnlock(lock>m);
return 1;
}
reader_cnt++;
MutexUnlock(lock>m);
return res;
}
int read_unlock(RWLock *lock)
{
int res = 0;
MutexLock(lock>m);
if (reader_cnt < 1) {
MutexUnlock(lock>m);
return 1;
}
reader_cnt;
MutexUnlock(lock>m);
return res;
}
int write_lock(RWLock *lock)
{
MutexLock(lock>m);
if (reader_cnt != 0) // taken by other readers or writer
{
MutexUnlock(lock>m);
return 1;
}
reader_cnt;
MutexUnlock(lock>m);
return 0;
}
int write_unlock(RWLock *lock)
{
MutexLock(lock>m);
if (reader_cnt != 1)
{
MutexUnlock(lock>m);
return 1;
}
reader_cnt = 0;
MutexUnlock(lock>m);
return 0;
}

mytestaccount2
August 17, 2013 No need to have 2 mutex.
 mytestaccount2 August 17, 2013Another approach as opposed to swapping is to make
index A[i]1 ve for each 1<=A[i]<=N
Then we can scan the +ve portion of the array to find out the first index which is nonnegative. Now we can declare the answer as index+1.
If all indexes are ve, then N+1 is the answer.
Can you please explain how and why this algorithm works.
Thanks
typedef struct ternary_node {
node *left, *middle, *right;
char data;
} node;
static int cursor = 0;
node* preorder_to_tree(char *preorder)
{
node *r = new_node(preorder[cursor]);
if (!r  !preorder) return NULL;
/* return directly from Leaf Node */
if (preorder[cursor] == 'l') {
return r;
}
r>left = preorder_to_tree(++cursor + preorder);
r>middle = preorder_to_tree(++cursor + preorder);
r>right = preorder_to_tree(++cursor + preorder);
return r;
}
node* new_ternary_node(char c) {
node *tmp = malloc(sizeof(node));
if (tmp) {
tmp>data = c;
}
return tmp;
}

mytestaccount2
August 04, 2013 /* complexity O(m+n) */
/* k is the key to search */
bool_t search_element_in_sorted_2d_array(int *arr, int m, int n, int k)
{
int row=0, col=n1;
int current;
do {
current = arr[n*row+col];
if (current > k) { /* discard column, decrease column */
col;
} else if (current < k) { /* discard row, increase row */
row++;
}
} while ((row < m && col >= 0) && (k != current));
if (k == current) {
printf("Found element %d at arr[%d][%d]\n", k, row, col);
return TRUE;
} else {
printf("Could not find element %d\n", k);
return FALSE;
}
}

mytestaccount2
August 01, 2013 Each robot will have a starting position.
One starting position would be on left and the other is on right.
Therefore, we can let both robots move right until it reaches other's starting
position. As soon as a robot reaches other's starting position, it would double
its speed. Thus, eventually they will meet.
while (robot_current_posn != other_robot_starting_posn
&& two_robots_meet() == FALSE) {
move(right, 1);
}
while ( two_robots_meet() == FALSE ) {
move(right, 2);
}

mytestaccount2
August 01, 2013 1. Sort both arrays in descending order
/* Insert A[0] + B[0] into max heap */
max_heap.put(0, 0, A[0]+B[0]);
while (k) {
p = max_heap.get();
if (p.a_index < p.b_index) {
sum = A[p.a_index] + B[p.b_index+1];
max_heap.put(make_pair(p.a_index, p.b_index+1, sum));
} else if (p.a_index > p.b_index) {
sum = A[p.a_index+1] + B[p.b_index];
max_heap.put(make_pair(p.a_index+1, p.b_index, sum));
} else { /* add both adjacent elements */
sum = A[p.a_index] + B[p.b_index+1];
max_heap.put(make_pair(p.a_index, p.b_index+1, sum));
sum = A[p.a_index+1] + B[p.b_index];
max_heap.put(make_pair(p.a_index+1, p.b_index, sum));
}
}
p = max_hep.get();
sum = A[p.a_index] + B[p.b_index];
printf("kth max sum is formed by A[%d] + B[%d] = %d\n", p.a_index, p.b_index, sum);

mytestaccount2
July 29, 2013 Exactly what I thought :)
 mytestaccount2 July 28, 2013The complexity is O(N log N) which is same as BST based solution.
 mytestaccount2 July 28, 2013@czpete: awesome solution!
 mytestaccount2 July 25, 2013
@sumit: the question says that only 1 number is repeated n times.
 mytestaccount2 April 24, 2015In your test case, 3 and 2 are repeated.