hankm2004
BAN USERAssumption I made in this problem is that machine tells how many characters matched given query string. For example, if the word to guess is "daddy", the machine will returns 3 when the query string is "b".
Based on that assumption, the following would solve the problem
Step 1: for all alphabet letters, find out how many each alphabet exists in the target word and add the alphabet letter to the seed as many as it exists.
Step 2: previous steps will produce unordered string with the same size with the target words with correct number of alphabet letters.
Recursively, create the possible permutation with same length as the target word and find the matching string.
string tryPermutation(string seed, string left)
{
string found = "";
string tryPermutation(string seed, string left)
{
string found = "";
if (left.length() == 0 && IsCorrectWord(seed) == true)
return seed;
for (int i = 0; i < left.length(); i++)
{
string newSeed(seed);
newSeed.push_back(left.at(i));
string newLeft = left.substr(0, i);
newLeft.append(left.substr(i+1, left.length()-(i+1)));
found = tryPermutation(newSeed, newLeft);
if (!found.empty())
break;
}
return found;
}
return seed;
for (int i = 0; i < left.length(); i++)
{
string newSeed(seed);
newSeed.push_back(left.at(i));
string newLeft = left.substr(0, i);
newLeft.append(left.substr(i+1, left.length()-(i+1)));
found = tryPermutation(newSeed, newLeft);
if (!found.empty())
break;
}
return found;
}
//assumption: countMatched returns number of characters matching from given string. e.g. for "bobby", countMatched("b") will return 3.
string GuessWord()
{
string seed = "";
for(int i = 'a'; i<= 'z'; i++)
{
int nMatched = 0;
if (nMatched = countMatched((char)i))
{
for (int j = 0; j < nMatched; j++)
seed.push_back((char)i);
}
}
//we now have correct number of characters for the target word.
string found = tryPermutation("", seed);
}
int search_hindex(int *input, int start, int end, int hindex)
{
int half =0, found = 0;
if (start > end)
return hindex;
half = start + (end - start)/2;
if (half + 1 > input[half])
{
hindex = half + 1;
found= search_hindex(input, start, half -1, hindex);
} else {
found = search_hindex(input, half+1, end, hindex);
}
return found;
}
int compute_hindex(int* input, int length)
{
int hindex = 0; //not found
hindex = search_hindex(input, 0, length-1, hindex);
if (hindex ==0)
hindex = length;
else
hindex--;
return hindex;
}
Node* swap_pairs(Node *start)
{
Node* cur, *prev, *next, *result;
cur = start;
next = 0;
prev = 0;
result = 0;
while(cur && cur->next)
{
next = cur->next->next;
if (!result) result = cur->next;
if (prev) prev->next = cur->next;
cur->next->next = cur;
cur->next = next;
prev = cur;
cur = next;
}
if (!result) result = start;
return result;
}
Here is C++ version:
bool IsAlphabet(char c)
{
return ((c >='a' && c<='z')||(c>='A' &&c<='Z'));
}
bool IsSame(char s , char d)
{
int lowbase_a = s-'a';
int upperbase_a = s-'A';
int lowbase_d = d-'a';
int upperbase_d = d - 'A';
return ((lowbase_a == lowbase_d) ||(upperbase_a == upperbase_d) || (lowbase_a == upperbase_d) || (upperbase_a) == (lowbase_d));
}
bool IsPanlindrome(const char * str, int length)
{
int s = 0;
int e = length;
while (s < e)
{
if (!IsAlphabet(str[s]))
{
s++;
continue;
}
if (!IsAlphabet(str[e]))
{
e--;
continue;
}
if (IsSame(str[s], str[e]))
{
s++;
e--;
} else
return false;
}
return true;
}
struct Node {
Node * next;
int value;
};
Node* mergeSList(Node* lists[], int count)
{
Node *end;
Node *start;
if (count > 0)
start = lists[0];
for(int i = 1; i < count; i++)
{
start = merge(start, lists[i]);
}
return start;
}
Node * merge (Node * list1, Node * list2)
{
Node *start = 0;
Node *end = 0;
Node *cur1 = list1;
Node *cur2 = list2;
while (cur1 || cur2)
{
Node *next = 0;
//if list1 reached the end
if (!cur1 && cur2)
{
next = cur2;
cur2 = cur2->next;
} else if (cur1 && !cur2)
{
next = cur1;
cur1 = cur1->next;
} else if (cur1->value > cur2->value)
{
next = cur2;
cur2 = cur2->next;
} else {
next = cur1;
cur1 = cur1->next;
}
if (!start)
start = end = next;
else{
end->next = next;
end = next;
}
}
return start;
}
This algorithm is equivalent to the merge operation of merge sort since each list is already sorted.
Running time will O(N), where N is total number of elements in K sorted linked lists.
#include <cstdlib>
#include <stdio.h>
//if start pos is unknown
int binary_search(int * array, int length, int target)
{
//could not find the value until the found spos, do binary search for array from spos to end of the array
int left = 0;
int right = length -1;
int half = -1;
while (left <= right)
{
half = left + (right- left)/2;
if (array[half] == target)
return half;
if (array[left] < array[half])
{
if (array[half] > target && array[left] <= target)
right = half - 1;
else
left = half + 1;
} else {
if (array[half] < target && target <= array[right])
left = half + 1;
else
right = half -1;
}
}
return -1;
}
int main(int argc, char *argv[])
{
int array[7] = {5,6,7,9,1,2,3};
int target = atoi(argv[1]);
printf("target = %d\n", target);
int result = binary_search(array,7, target);
printf("found = %d\n", result);
return 1;
}
Here is a working code in C++
#include <stdio.h>
int max_ps(char* str, int n, int max);
bool is_palindrome(char *str, int n);
int LPS(char *str, int n)
{
return max_ps(str, n, 0);
}
int max_ps(char* str, int n, int max)
{
int lmax = 0;
int rmax = 0;
if (n == 0)
{
return max;
}
if (is_palindrome(str, n) && n > max)
{
max = n;
}
lmax = max_ps( str+1, n-1, max);
rmax = max_ps(str, n-1, max);
if (lmax > max)
max = lmax;
if (rmax > max)
max = rmax;
return max;
}
bool is_palindrome(char *str, int n)
{
int s = 0;
int e = n-1;
while(s < e)
{
if (*(str+ s++) != *(str + e--))
{
return false;
}
}
return true;
}
int main()
{
char * a = "aaacyoomimooyiabb";
int max = 0;
max = LPS(a, 17);
printf ("max lps = %d\n", max);
return 0;
}
Here is a working version in Python.
def find_duplicate(expr):
stack=[]
char_in_between = 0
for i in range(0, len(expr)):
if expr[i] == '}' or expr[i] == ')':
pair = '{' if expr[i] == '}' else '('
pop=''
while(len(stack) > 0 and pop != pair):
pop = stack.pop()
if (pop != '{' and pop != '('): char_in_between +=1
if char_in_between == 0:
print "duplicate parenthesis!!"
break
char_in_between = 0
else:
stack.append(expr[i])
I thought the same as ninhnnsoc except for the case that returns the whole matrix itself.
Assumption is that you need to return the sub matrix (that is smaller than whole matrix) that has most 1s.
1. Scan each row in the matrix and store the rows that has no 1 in the array.
2. Check the array to see if there are any row having no 1.
3. If array is empty, compare the number of 1s in the four cases:
case 1. count number of 1s for Matrix M-1 X N staring from 0,0
case 2. count number of 1s for Matrix M-1 X N starting from 1,0
case 3. count number of 1s for Matrix M X N-1 starting from 0,0
case 4. count number of 1s for Matrix M X N-1 starting from 0,1
4. returns the matrix with most 1s
5. if array is not empty, divide MxN into sub matrices and count number of the 1s
6. Returns the matrix with most 1s
First of all, what is the purpose of the data structure ?
If getting "no of student" and "no of subject" is the goal, we can use two maps, one with <stduent id, no_of_subject> pair as an element and the other one with <subject id, no_of_students> pair as an element.
However, if the goal is to retrieve students taking a specific subject or retrieve subjects that a specific student is taking, I would use two maps (or hashtable):
- stduent hash map: key => stduent id , value => list of subject ids(either linked list or std::vector)
- subject hash map: key=> subject id, value=> list of student ids(either linked list or std::vector)
Enhanced previous one to avoid unnecessary search.
Here is a solution in python.
I was not sure what should be return type, so I printed out the result.
def find_long_seq(matrix, vlen, hlen):
is_vertial = False
max_seq = 0
for i in range(0, vlen):
cur_seq=0
for j in range(0, hlen):
if matrix[i][j] == 1:
cur_seq+=1
elif matrix[i][j] == 0:
if max_seq < cur_seq:
max_seq = cur_seq
is_vertical = False
cur_seq = 0
if max_seq > hlen - j:
continue
if j == hlen-1 and max_seq < cur_seq:
max_seq = cur_seq
is_vertical = False
for h in range(0, hlen):
cur_seq = 0
for l in range(0, vlen):
if matrix[l][h] == 1:
cur_seq+=1
elif matrix[l][h] == 0:
if max_seq < cur_seq:
max_seq = cur_seq
is_vertical = True
cur_seq = 0
if max_seq > vlen - l:
continue
if l == vlen-1 and max_seq < cur_seq:
max_seq = cur_seq
is_vertical = True
print "max sequence = " + str(max_seq) + " is_vertial : " + str(is_vertical)
I was trying to find what I did wrong in my code since my code returned 4 times instead of 3 times. I now see I am not the only one.
The following is the working code in Python
def find_word2(matrix, word, hsize, vsize):
result = 0
s = datetime.datetime.now()
for i in range(0, len(matrix)):
result += search_matrix2(word, matrix, hsize, vsize, i, 0, 0)
e = datetime.datetime.now()
lapsed = e - s
print word + " showed up " + str(result) + " times : took " + str(lapsed.microseconds) + " ms"
def search_matrix2(word, matrix, hsize, vsize, hpos, vpos, index):
if (vpos >= vsize or hpos >= hsize or matrix[vpos][hpos] != word[index]):
return 0
if (index == len(word)-1):
return 1
return search_matrix2(word, matrix, hsize, vsize, hpos+1, vpos, index+1) + search_matrix2(word, matrix, hsize, vsize, hpos, vpos+1, index+1) + search_matrix2(word, matrix, hsize, vsize, hpos+1, vpos+1, index+1)
Let say there are N sites and M ads.
Assume that parsing the text file is trivial.
For build initialization take two steps:
- build hash table going through sites: O(N)
- Adding one ad to hash table:
1) Finding site: O(1)
2) Adding to Site: worst case O(M) (if one site has all M Ads)
- I could optimize that by searching up to second node since what we need for the actual operation is the highest and second highest node. In that case,
I will be O(1)
Therefore, adding ads to site hash table would take O(M*M) worst case, O(M) best case.
Storage complexity will be O(NXM) for the first case, O(N) for the optimized case.
For the actual searching for adds given site id, it would be O(1)
Is it enough ?
This is another one using BFS.
def bfs_count(root):
result = {}
current_depth =0
current_node_count = 0
current_negative_count = 0
next_node_count = 0
queue = deque()
queue.append(root)
current_node_count =1
max_count = 0
max_depth = 0
while (len(queue)):
node = queue.popleft()
current_node_count-=1
if (node.value < 0):
current_negative_count+=1
if (node.left != None):
queue.append(node.left)
next_node_count += 1
if (node.right != None):
queue.append(node.right)
next_node_count +=1
if (current_node_count == 0):
if (current_negative_count > max_count):
max_count = current_negative_count;
max_depth = current_depth
current_depth+=1
current_node_count = next_node_count
next_node_count = 0
current_negative_count = 0;
result[max_depth] = max_count
return result
Here is working version in python
//tree node structure
class Node:
left = None
right = None
value = -1
def __init__(self, value =-1):
self.value = value
def find_negatives(tree):
count = []
count_negatives(tree, count, 0)
max = 0;
depth = 0;
for i in range(0, len(count)):
print "depth " + str(i) + " count: " + str(count[i])
if (count[i] > max):
max = count[i]
depth = i
print "result depth : " + str(depth) + " count : " + str(max)
return max
def count_negatives(tree, count, depth):
if tree is None:
return
if tree.value < 0:
print "found : " + str(tree.value) + " depth : " + str(depth)
if (len(count) -1 < depth):
count.append(1)
else:
count[depth] = count[depth] +1
count_negatives(tree.left, count, depth+1)
count_negatives(tree.right, count, depth+1)
return
Here is working code in C++.
#include <string>
#include <map>
#include <iostream>
#include <fstream>
typedef struct Node AdNode;
struct Node{
int id;
int bid;
AdNode * next;
};
typedef struct siteNode {
int id;
int reserve;
std::string name;
AdNode *bestBid;
AdNode *ads;
} site;
site* parse_site(std::string& line);
void add_ads(std::map<int, site*>& site_map, std::string& line);
void do_auction(std::map<int, site*>& map, int ad_id);
bool add_to_site(std::map<int, site*>site_map, int site_id, int id, int bid);
void print_sites (std::map<int, site*> site_map);
int main (int argc, char* argv[])
{
if (argc < 3)
{
std::cout << "Usage: adserver [path_to_site_csv] [path_to_ads_csv]" <<std::endl;
return 1;
}
std::map <int, site*> site_map;
std::cout << "site = "<< argv[1] <<std::endl;
std::ifstream s_file;
s_file.open(argv[1]);
std::string line;
while(!s_file.eof())
{
std::getline(s_file, line);
std::cout << "line = " << line << std::endl;
site* new_site = parse_site(line);
if (new_site)
{
std::cout << "site id = " <<new_site->id << std::endl;
site_map.insert(std::pair<int, site*>(new_site->id, new_site));
}
}
s_file.close();
std::cout << "ads = " <<argv[2] << std::endl;
std::ifstream a_file;
a_file.open(argv[2]);
while (!a_file.eof())
{
std::getline(a_file, line);
add_ads(site_map, line);
}
a_file.close();
print_sites(site_map);
int ad_id;
do {
std::cout << "Input an add id:" <<std::endl;
std::cin >> ad_id;
do_auction(site_map, ad_id);
}while(ad_id != 1);
return 0;
}
site* parse_site(std::string& line)
{
site* new_site = nullptr;
int count = 0;
size_t spos = 0;
size_t pos = line.find(',', spos);
while (pos != std::string::npos)
{
if (!new_site)
{
new_site = new site();
new_site->bestBid = nullptr;
new_site->ads = nullptr;
}
if (count == 0)
{
new_site->id = atoi(line.substr(spos, pos-spos).c_str());
} else if (count == 1)
{
new_site->reserve = atoi(line.substr(spos, pos-spos).c_str());
}
spos = pos + 1;
pos = line.find(',', spos);
if (pos == std::string::npos && spos < line.size())
{
new_site->name = line.substr(spos, line.size() - spos);
std::cout << "name = " << new_site->name <<std::endl;
}
}
return new_site;
}
void add_ads(std::map<int, site*>& site_map, std::string& line)
{
AdNode* new_ad = nullptr;
int count = 0;
size_t spos = 0;
size_t pos = line.find(',', spos);
int num_sites = 0;
int id;
int bid;
std::cout << "ad : " << line <<std::endl;
while (pos != std::string::npos)
{
if (count == 0)
{
id = atoi(line.substr(spos, pos-spos).c_str());
} else if (count == 1)
{
bid = atoi(line.substr(spos, pos-spos).c_str());
} else if(count == 2)
{
num_sites = atoi(line.substr(spos, pos-spos).c_str());
} else {
int site_id = atoi(line.substr(spos, pos-spos).c_str());
if(!add_to_site(site_map, site_id, id, bid))
{
continue;
}
}
spos = pos + 1;
count++;
pos = line.find(',', spos);
if (pos == std::string::npos && spos < line.size())
{
int site_id = atoi(line.substr(spos, line.size() -spos).c_str());
if(!add_to_site(site_map, site_id, id, bid))
{
continue;
}
std::cout << "id = " <<site_id <<std::endl;
}
}
}
void do_auction(std::map<int, site*>& map, int ad_id)
{
std::map<int, site*>::iterator found = map.find(ad_id);
if (found == map.end())
return;
site* s = found->second;
if(s->ads && s->ads->bid >= s->reserve)
{
AdNode * winner = s->ads;
int price;
if (s->ads->next)
{ //more than one ads
price = (s->ads->next->bid >= s->reserve)?s->ads->next->bid: s->reserve;
} else {
price = s->reserve;
}
std::cout<< winner->id << " " << price << std::endl;
} else {
std::cout << "0 0" <<std::endl;
}
}
void print_sites (std::map<int, site*> site_map)
{
std::map<int, site*>::iterator it = site_map.begin();
for (; it != site_map.end(); it++)
{
site* s = it->second;
std::cout<<"site : "<< s->id << " reserve : " << s->reserve <<std::endl;
AdNode * c = s->ads;
while (c)
{
std::cout << "ad id : " << c->id << " bid : " << c->bid <<std::endl;
c = c->next;
}
}
}
bool add_to_site(std::map<int, site*>site_map, int site_id, int id, int bid)
{
std::map<int, site*>::iterator found = site_map.find(site_id);
if (found == site_map.end())
{
return false;
}
AdNode * new_ad = new AdNode();
new_ad->id = id;
new_ad->bid = bid;
new_ad->next = nullptr;
site * site = found->second;
std::cout << "adding a ad ( "<<new_ad->id<<") to a site : " << site->id <<std::endl;
std::cout<< "add price: " << new_ad->bid <<std::endl;
if (!site->ads)
site->ads = new_ad;
else
{
AdNode* current = site->ads;
AdNode* prev = nullptr;
while (current)
{
if (new_ad->bid > current->bid)
{
new_ad->next = current;
if (prev)
prev->next = new_ad;
else
site->ads = new_ad;
break;
} else if (new_ad->bid == current->bid)
{
if (new_ad->id < current->id)
{
new_ad->next = current;
if (prev)
prev->next = new_ad;
else
site->ads = new_ad;
break;
}
}
prev = current;
current = current->next;
}
if (!current)
prev->next = new_ad;
}
return true;
}
Say, Rest api is like /user/recent_items?userid=[id]
I would keep the hash table of items that were checked out by all users.
Due to the memory constraint, this hash table only keeps certain number of items. To make sure the hash table would keep most recently check items by users, I would like the LRU list to keep the item ids.
This will make sure only most recently view items would stay in the cache.
I was trying to find solution faster than O(N*N), but I could not.
Here is a solution in python
def find_max_span(data):
output = []
for i in range(0, len(data)):
current = data[i]
count = -1
for j in range(0, i):
if (data[j] < current):
if (count==-1):
count =1
else:
count+=1
output.append(count)
return output
As other people pointed out earlier, it is very vague question. Assumptions I made for this question was:
Print out subsets that sum of numbers in the set is zero
No duplicate is allowed (e.g. "1,0,-1" and "-1,1,0" are the same)
def find_zerosum(inputs):
next_pos = 0
used=[]
current = []
found = {}
for i in range(0, len(inputs)):
used.append(0)
zero_sum(found, inputs, current, used, 0)
def zero_sum(found, ordered, current, used, pos):
if len(current) > 0 and is_zerosum(current) == True:
key = ",".join(str(x) for x in sorted(current))
if found.has_key(key) != True:
found[key] = 1
print key
return
for i in range(pos, len(ordered)):
if (used[i] == 1): continue
new_current = list(current)
new_current.append(ordered[i])
new_used = list(used)
new_used[i] = 1
zero_sum(found, ordered, new_current, new_used, i)
def is_zerosum(numbers):
s = 0
for i in range(0,len(numbers)) :
s+= numbers[i]
return s == 0
Here is one written in C++
void excel_column_converter(std::string& source)
{
bool is_alpha = false;
if (source[0] >= 'A' && source[0] <= 'Z' )
{
is_alpha = true;
} else if (source[0] >= '0' && source[0] <= '9')
{
is_alpha = false;
} else {
std::cout<<"invalid input" <<std::endl;
}
if (!is_alpha)
{
std::string result = "";
char *pEnd;
long number = atoi(source.c_str());
int residual = 0;
do {
residual = number%26;
char next = 'A'+residual;
result = std::string(&next, 1) + result;
if (number >= 26 && ((number/26) <26))
{
char last = number/26;
next = 'A' + (last-1);
result = std::string(&next, 1) + result;
}
number /= 26;
} while(number >= 26);
std::cout<< "result for "<<source<< "=" <<result <<std::endl;
} else {
int i = 0, sum = 0;
while(i < source.length() && source[i]>= 'A' && source[i] <= 'Z')
{
sum = sum*25 + ((source[i] - 'A')+1);
i++;
}
std::cout<<"result for "<< source<<"="<< sum<<std::endl;
}
}
Here is a working solution in python.
def eval_mathexpr(expr):
digit_stack = []
op_stack = []
number = ''
for i in range(len(expr) -1, -1, -1):
if expr[i].isdigit() == True :
number = expr[i] + number
if (i > 0):
continue
else :
if len(number) > 0:
digit_stack.append(float(number))
elif is_op(expr[i]) and i > 0 and i < len(expr)-1:
if len(number) > 0:
digit_stack.append(float(number))
number=''
while is_normal_op(expr[i]) == True and (len(op_stack) > 0 and is_compound_op(op_stack[-1])==True):
if (len(digit_stack) >= 2) :
left = digit_stack.pop()
right = digit_stack.pop()
op = op_stack.pop()
result = compute(left, op, right)
digit_stack.append(result)
op_stack.append(expr[i])
else:
raise AttributeError
while len(op_stack) and len(digit_stack) >= 2 :
op = op_stack.pop()
lvalue = digit_stack.pop()
rvalue = digit_stack.pop()
result = compute(lvalue, op, rvalue)
digit_stack.append(result)
return digit_stack.pop()
def compute (lvalue, op, rvalue):
if (op == '+') :
return lvalue + rvalue
elif op == '-' :
return lvalue - rvalue
elif op == '*' :
return lvalue * rvalue
elif op == '/' :
return lvalue / rvalue
else:
raise AttributeError
def is_op(str):
return (is_normal_op(str) or is_compound_op(str))
def is_normal_op(str):
return (str == '+' or str=='-')
def is_compound_op(str):
return (str == '*'or str == '/')
I used python to code.
def print_word_permute(word):
n = len(word)
permute_word("", word)
def permute_word(prefix, left):
n = len(left)
if (n == 0):
print prefix
return
for i in range(0, n):
if left[i].isalpha() == True:
permute_word(prefix + left[:i]+left[i].upper() , left[i+1:])
permute_word(prefix + left[:i]+left[i], left[i+1:])
break
Repcharlespladd, Android Engineer at Abs india pvt. ltd.
I am Charles from Pascoag USA. I have strong knowledge of pain management systems. And I have experience in providing ...
Here is the working code in C++.
- hankm2004 June 23, 2015