jigs
BAN USERclass Encode:
def __init__(self):
self.ecoding = {}
self.__init_dict()
def __init_dict(self):
for i in range(1,27):
self.ecoding[str(i)] = chr(ord('a') + i -1)
print self.ecoding
def generate_all_encoding(self, input):
result = []
partial = ""
self.__generate_all_encoding(input.lower() , result, partial)
return result
def __generate_all_encoding(self, input, result, partial):
if input == "":
result.append(partial)
return
for i in range(1,3):
if len(input) >= i:
prefix = input[:i]
if self.ecoding.has_key(prefix):
self.__generate_all_encoding(input[i:], result, partial+self.ecoding[prefix])
Solution is incorrect. It will not return 1 and 0 with equal probablity.
Your logic is like this, when both generated bits are different (01 or 10) then return first bit (0 or 1 respectively). But think like this what if P(1) = 0.9 and P(0)=0.1 in this case probability of first bit is 1 will higher than probability of first bit is 0. it means you will return 1 bit with higher probability than 0.
Perform birary search for the given number X in the given BST. There are 2 possbile cases
1) Number X is present in the given BST.
2) Number X is not in the given BST.
In case of 1st scenario, return X as answer.
In case of 2nd scenario, Binary search process will reach to leaf node without finding x, in this case maintain Closest node (which has minumum value(node)-x ) in the path from the root to leaf.
Complexity O(log n)
Code:
Node closest(Node root, int value){
Node ans = root;
int diff;
if(!root) return ans;
diff = abs( ans->value - value);
while(root){
if(root->value == value){
ans = root;
break;
}
if(diff > abs(root->value - value)){
diff = abs(root->value - value);
ans = root;
}
if(value < root->value){
root = root->left;
}else{
root = root->right;
}
}
return ans;
}
1) Count # of1 in each row let represent it by count(i) for row i
2) If there are 2 rows exists for which count(i) - count(j) >= 2 then ans is "no" (it meas count for each row should be either x or x+1 where x is min( count(i) where 1<=i <=m)
3) Now create a column and set 0 for each row for which count(i) =x and set 1 for which count(i) = x+1
4) now search created column in matrix. If matrix has no such column then ans = "NO"
5) else if matrix has such column then remove column from matrix and check all columns of matrix IF all columns are same then ans ="yes" else ans = "NO"
Writing to a file is a two step operation
1) write data in file
2) increment file descriptor pointer by buffer size
File opened in append mode make sure atomicity of above both operation. OS take care of performing the above both operation in thread safe fashion.
Solution for thread safe is open log file in APPEND mode.
Store dictionary using B+ tree in a file (same as B+ tree index built in Database). Each page of a file will represent a node of a B+ tree. This will have high fan out of the Tree (for example if page size of a file is 4 KB and if we use 32 bit number to represent page number( pointer ) each node will have 4KB/ 4 B = 1024 fan out ). and hence very low depth of the tree.
B+ tree can be preferred over HashTable when size of hashtable is larger than RAM size. If size of hashtable is larger than RAM size it will increase threshing due to random access pattern of hashtable.
In this case B+ tree gives benefit of locality of reference by storing nodes which are at lower level in RAM (Cache)
void * createArray(int dimension[], int size)
{
if(size == 1){
void * array = malloc( sizeof(int) *dimension[0]);
return array;
}
void * array = (void *)malloc( sizeof(void *) *dimension[0]);
for(int i = 0; i< dimension[0]; i++){
array[i] = createArray( & dimension[1], size-1);
}
return array;
}
You are inserting same element multiple times in the heap.
For exmaple
when you cosider a[0]+b[0] as first element you will inert a[0]+b[1] and a[1]+b[0]
Now heap contains 2 element. Suppose a[0]+b[1] is largest in heap than you will add a[1]+b[1] and a[0]+b[2] in heap now heap contains a[1]+b[0], a[1]+b[1] and a[0]+b[2]
Now if a[1]+b[0] is largest in heap you will add a[1]+b[1] and a[2]+b[0] in heap.
but heap already contains a[1]+b[1] in heap and due to this you will loose track of elements.
Fix: for a[i] + b[j] insert a[i+1]+b[j] and a[i]+b[j+1] if i ==0
insert a[i] + b[i+1] else
bool validWord(char st[], char ch[4]){
int stlen = strlen(st);
int stindex = 0;
int n = 0;
for(int i =0; i<4; i++){
if(i==0){
while(stindex < stlen && st[stindex] == ch[i]){
n += 1;
stindex += 1;
}
}else{
int count = 0;
while( stindex < stlen && st[stindex] == ch[i]){
stindex += 1;
count += 1;
}
if(count != n)
return false;
}
}
if(stindex < stlen)
return validWord(&st[stindex], ch);
else
return true;
}
Use array of (int *) i.e array of array. int * array[1024];
Use array of 128 byte , i.e 1024 bits....
Whenever 128 byte array get full. create another 128 byte array and store its address in address array. Initially declare address array of size 1024. when it get full resize it to double and so on...... (here we are creating new address array and transferring only pointers from old array to new array. not 1024 bits )
For boolean get(int index) and set(int index, boolean b) query.
use array[ int(index/1024) ][ index%1024] for setting or getting index element.
void create_stack(Tree *root, Tree *node, stack *st, int *done)
{
if (root == NULL) return;
if (root == node) {
st.push(root);
done = 1;
return;
}
st.push(root)
crete_stack(root->left, node, st, done)
if(done) return;
crete_stack(root->right, node, st, done)
if(done) return;
st.pop(root)
}
void __findKnode(Tree *node, int k, List * ans)
{
if (node == NULL) return;
if( k == 0) {
append(ans, node);
return;
}
__findKnode(node->left, k-1,ans);
__findKnode(node->right, k-1,ans);
}
void findKnode(Tree *root, Tree *node, int k)
{
List *ans = NULL;
Tree * prev = NULL;
int dist = k
int done = 0
Stack *st;
create_Stack(root, node, st, &done)
while(top = st.pop()){
if (dist < 0)
break;
if(dist == 0){
append(ans, top);
break;
}
if(prev == NULL){
__findKnode(top, dist, ans);
} else if( top->left == prev)
__findKnode(top->right, dist-1, ans);
else
__findKnode(top->left, dist-1, ans);
dist -= 1
prev = top
}
return ans;
}
1) perform post-order traversal of tree. maintain stack explicitly.
also maintain whether particular number is already added or not in stack
2) whenever you reach at leaf node get stack[top - k]->value and add it to ans.
code:
int sumup(Node * tree, int K, stack * st)
{
if (tree == NULL) return
if (tree->left == NULL && tree->right == NULL)
{
if (stack->top < k || st->array[stack->top-K]->already_added) return 0;
st->array[stack->top-K]->already_added = True
return st->array[stack->top-K]->value ;
}
int ans = 0;
st.push(tree);
ans += sumup(tree->left, K, st);
ans += sumup(tree->right,K, st);
st.pop(tree);
return ans;
}
Find the frequency of each number. Consider the most frequent numbers.
We need two consider 2 cases to get ans:
Case 1) There is only one most frequent number ( in this case ans is most frequent no.)
say given array is {4,5,7,4, 7, 4,}.
most frequent number is {4}.
In this case ans is [4] since we can not create subarray which is more frequent then subarray[4].
case 2) more than one most frequent number
ex. given array is [4, 6, 5, 5, 4]
In this case most frequent nos are [4,5].
Possible ans could be [4,5] or [4/5] or [5,4]
If each occurrence of 4 (and 5) has next number 5 (and 4) then ans is [4,5] ( in second case [5,4]) and if it doesn't then again ans is only one number array i.e either [4] or [5]
struct min_max{
int min;
int max;
int isBst;
}
typedef min_max MN
bool validateBst(Node *head)
{
MN * ans = isBst(head);
boo a = ans->isBst;
free(ans);
return a;
}
MN * isBst(Node *head)
{
if(head == NULL)
return NULL;
MN* left_mn = isBst(head->left);
MN* right_mn = isBst(head->right);
MN * ans = (MN *)malloc(size(MN));
if(left_mn->isBst == 0 || right_mn->isBst == 0){
ans->isBst = 0;
free(left_mn);
free(right_mn);
return ans;
}
ans->min = left_mn==NULL? head->val: left_mn->min;
ans->max = right_mn==NULL? head->val: right_mn->max;
if(ans->isBst == 1 && left_mn->max <= head->val && head->val < right_mn->min )
ans->isBst = 1;
else
ans->isBst = 0;
free(left_mn);
free(right_mn);
return ans
}
If we use inorder + preorder/postorder, we are need to transfer/store each node twice.
if node size is large then we could have large redundant data.
If we have pre-order traversal and we have no. of node in left sub child tree at each node, then we can create binary tree from pre-order only.
lets write grammar for tree
Head := header . tree
header := size of each node . no of nodes in tree .
tree := no_of_left_child . root_node. post-order of left tree. post-order of right tree.
Assuming that emailid is unique, if it is not then conider Firstname_LastName_emaiid as a key.
Create tries for previous day.
From current day excel file, for each record check it is present in previous day's tries or not.
If its present delete it from tries, if its not present then add it to new_added list for today.
At the end we would have new_added list and deleted_list (remaining entries in tries)
Use union-find data structure to solve this problem.
get_parent(manager){
if parent[manager] != manager
m = get_parent(manager)
parent[manager] = m
return m
else
return manager
}
get_total(){
for e in (Emp and Manager):
parent[e] = e
total[e] = 0
for each (Emp Manager Salary ) record:{
p = get_parent(Manager)
parent[Emp] = p
total[p] += Salary
}
for p in parent:
if parent[p] <> p:
print p, total[p]
}
Let's assume that people are in queue. once person get one slice he will move to end of the queue. So we can say that slice will be distributed in following way.
Say there are 3 people A,B and C. then distribute slices in this sequence A,B,C,A,B,C,A,B,C........... and maintain counter of number of distributed slices at the end perform int(counter/nPeople) which will be ans.
Observation: if number of slices is >nPeople then we can assign slice to each person only once, So we can add nPeople in counter directly.
Python code
- jigs July 03, 2016