algos
BAN USERthis can be done in single pass.
1. traverse k nodes, and store kth node in TEMP1 variable
2. now take two pointers, first pointer starts from head of the list, and second starts from kth node
3. traverse both first and second pointers one node at a time, till second pointer reaches end of the list, by that time first pointer will be pointing at kth node from end, and store first pointer in TEMP2 variable
4. now swap TEMP1 & TEMP2
enter each element in hash table and store starting and ending index. first time inserting an element in hash table starting and ending index is same, after that for duplicate elements update the ending index...
for each element the max distance will be (end index - start index + 1)
initial position is at (row, col), int ch=0
if(a[i] == 'N' || (a[i] == 'M' && ch == 1))
{
row--;
ch = 1;
}
else if(a[i] == 'S' || (a[i] == 'M' && ch == 2))
{
row++;
ch = 2;
}
else if(a[i] == 'E' || (a[i] == 'M' && ch == 3))
{
col++;
ch = 3;
}
else if(a[i] == 'W' || (a[i] == 'M' && ch == 4))
{
col--;
ch = 4;
}
final position will be at (row, col)
time complexity is O(log n)
variation of binary search i.e.. reverse binary search.
check the target number is present in below index ranges i.e.. 2^n index range
0-1
2-3
4-7
8-15
16-31
32-63
.
.
if target number is found in any of the above range then apply binary search on that data
int start=0, end = 1;
if target <= a[end]
apply binary search for the range start and end
else
start = end +1;
end = end*2+1;
2 3 -4 -1 6
sum array: 0 2 5 1 0 6
index arra: -1 0 1 2 3 4
now sort the sum array including index array
0 0 1 2 5 6 (sum array)
-1 3 2 0 1 4 (index array)
now check the absolute difference between any 2 elements is minimum in sum array...here difference between 0 & 0 is minimum that is 0
so the solution is starting from index -1+1 to 3 that is index 0 to 3 ( 2 + 3 + -4 + -1 = 0)
for remainder array verify below conditions:
1. there should be even number of 0's
2. for every element a[i] in remainder array there should be K-a[i] exists in array. to verify this hash all elements and and keep the count of each element and check whether a[i] and K-a[i] exists in hash table and the count should be also equal for both
any two numbers sum should be divisible by K means sum of remainders of two numbers should be K or 0
lets K=5, and data is 8 & 9, here sum of these numbers to be divisible by 5 (K) for below cases
1. both numbers should be divisible by 5 means remainders will be 0 & 0
2. sum of the remainders should be divisible by 5, here remainders are 3 & 4 sum of these is not divisible by 5... lets take 8 & 12, sum of remainders is 3+2, which is divisible by 5.
here we don't know which two numbers remainders sum is divisible by 5, each pair should be equal to K and there should be N/2 such pairs...each pair is a[i] & K-a[i]
lets take another example:
9 15 21 4 5 6 and K=10, and N=6
here remainders are 9 5 1 4 5 6
time complexity O(n) and space complexity O(n)
ex: 4 11 7 6 3 9 8 12 and K=5, N=8 (array size)
get the remainder of all elements by dividing with K, so the array becomes
4 1 2 1 3 4 3 2
for remainder array verify below conditions:
1. there should be even number of 0's
2. for every element a[i] in remainder array there should be K-a[i] exists in array. to verify this hash all elements and and keep the count of each element and check whether a[i] and K-a[i] exists in hash table and the count should be also equal for both
index 0-1 is valid word then next valid word should start from index 2.
ex..
higoogle
here first valid word is "hi" index from 0-1
next valid word should start from index 2 and end at index 3(go) / 7(google)
question is to break the sentence into meaningful words, means to insert spaces in sentence that should form words exists in dictionary
this can be done in n^2 time...
ex: googlesearchengine
1. for i=0 to n, look for all words till i to n i.e..
start, end indexes
g 0, 0
go 0, 1
goo 0, 2
goog 0, 3
googl 0, 4
google 0, 5
googles 0, 6 ... do this till end of sentence
.
.
o 1, 1
oo 1, 2
oog 1, 3
oogle 1, 4
oogle 1, 5 ... do this till end of sentence
.
.
s 6, 6
se 6, 7
sea 6, 8
sear 6, 9
searc 6, 10
search 6, 11
searche 6, 12 ... do this till end of sentence
.
.
.
e 12, 12
en 12, 13
eng 12, 14
engi 12, 15
engin 12, 16
engine 12, 17
---------------
here existing words in dictionary are
go 0, 1
google 0, 5
sea 6, 8
search 6, 11
ear 7, 9
a 8, 8
arc 8, 10
hen 11, 13
engine 12, 17
here for existing words in dictionary, hash all the starting indexes as keys and ending indexes as data in hash table.
1. now start from 0 key in hash table
hash key hash data
0 1
so there exists word from 0-1 index, if this is valid word then next word should start from index 2 that is previous hash data+1
now look for key 2 in hash table, this is not exist so previous word is not valid
2. now try for hash key 0 and hash data 5, there exists word (0-5),
now look for 6 key in hash, this exists and data is 11, there exists word (6-11)
now look for 12 key in hash, this exists and data is 17, there exists word (12-17) and end of sentence
-----------------------
this also can be done with 2D array of nxn... n is sentence length
one more condition is missing here... both left and right are negative values and root is positive value or negative value greater than left and right then we should take only root value
left = root->data + root->left->data;
right = root->data + root->right->data;
leftright = root->data + root->right->data + root->left->data;
d = root->data;
if(d > left && d > right && d > leftright)
return d;
int a[] = {1,3,7,5,2,8,6,4,9};
int n = 9;
int index = getIndexOfNthLargest(n); // index of smallest data
reverseArray(index);
for(int i=n-1,j=1; i>0; i--,j++)
{
int index = getIndexOfNthLargest(i);
reverseArray(index);
reverseArray(index - j);
reverseArray(index);
}
lets the stream is 1 2 3 4 5 6 7 8 9 10, initially count = 0, is number of data read so far
1. enqueue data into queue, increment count
2. if count is ODD then MID is just read the data at front of the queue
3. if count is EVEN then MID is read the data at front and dequeue that data
4. if count >= M/2 then return
here k=3, num=2
0's - 3
1's - 5
actually expected number of unique elements are 3(K), but here only 2 are there, so there is one number duplicate(K-2 = 1)
this duplicate should be 1, so for every set there should be 110...
here number of zeros are more than number of 1's (11, 11, 1)
so, series should start with element which is max occurrences
if number of 1 are 6 then 11 11 11 0 0 0, here number sets of 1's and 0's are same, in this case it works either order
array = {80,17,90,82,27,19}, k=3, NUM=63
1. after modulus all array elements with NUM
array = {17,17,27,19,27,19}, exclude all zeros if there
2. hash all data and keep the count of each element
3. there should be K unique elements
4. sum of all unique elements should be equal to NUM
5. difference between the counts of any two elements should be at most differ by 1.
17 19 27 17 is Correct
17 19 27 17 19 is Correct
17 19 27 17 17 is not NOT Correct as 17 are 3 but 19's 27's are 1
proof: lets 17+19+27 is equal to 63 with K elements
next 19+27+x=63, so x should be 17
next 27+17+x=63, here again x should be 19
so the series would be like 17 19 27 17 19 27 (as per original array)
here series should start with element with max count and then next max count etc...
if the count of all elements are same then the order can be anything.
17 19 27 17 19 27
19 17 27 19 17 27 both are correct
if number of unique elements are less than K then
ex:
arr={2 ,5, 0 ,9 ,1, 9 ,9 ,4}
k=3, NUM=2,
hash array={0,1,0,1,1,1,1,0}
0's - 3
1's - 5
actually expected number of unique elements are 3(K), but here only 2 are there, so there is one number duplicate(K-2 = 1)
this duplicate should be 1, so for every set there should be 110...
here number of zeros are more than number of 1's (11, 11, 1)
so, series should start with element which is max occurrences
if number of 1 are 6 then 11 11 11 0 0 0, here number sets of 1's and 0's are same, in this case it works either order
that depends on question. there are 2 scenarios
case 1. inserting data is duplicate then simply discard
case 2. add one extra variable in hash table "count" that will keep the count of each data... when data is inserted then increment the count. when data is deleted then decrement count and if count becomes zero then only delete the hash entry and and in index array
this can be solved using hash table + array implementation
hash data ---- index to array
40 -------------- 0
10 -------------- 1
20 -------------- 2
30 -------------- 3
array index -- 0 1 2 3 4
data ---------- 40 10 20 30
initially index = 0;
insert(data)
1. insert the data into hash table if it is not available
2. enter the index to the hash associated to the key (data)
3. enter the data into array[index] location
4. increment the index by 1 i.e.. index++;
delete(data)
1. verify the data is available in hash table if yes then get the index of the data
i = get_index(data) // index
2. move data from array in location index-1 to i
a[i] = a[index-1];
3. data in a[i] is changed now, so change the index of a[i] in hash table to i
4. decrement index by 1 i.e.. index--;
5. delete the data from the hash table...delete_hash(data)
get_random()
1. generate a random number 0 - (index-1)
r = rand() % index;
2. return array[r]
i/p str: a 1 b 2 c 3 d 4 e 5
index: 0 1 2 3 4 5 6 7 8 9
o/p str: a b c d e 1 2 3 4 5
index: 0 1 2 3 4 5 6 7 8 9
here string length is L = 10/2 = 5
numbers are moving from i/p location to o/p location
1 to 5 => L+1/2
3 to 6 => L+3/2
5 to 7 => L+5/2
7 to 8 => L+7/2
and characters are moving from i/p location to o/p location
2 to 1 => 2/2
4 to 2 => 4/2
6 to 3 => 6/2
8 to 4 => 8/2
now traverse the string array and move the data according to above logic... if the location is odd then move to L+i/2 and if the location is even then move it to i/2 location
initially
1st location is 1 so move it to 5+1/2 = 5th location ----- a[5] = 1
5th location is 3 so move it to 5+5/2 = 7th location ------a[7] = 3
7th location is 4 so move it to 5+7/2 = 8th location ----- a[8] = 4
8th location is 'e' so move it to 8/2 = 4th location ----- a[4] = 'e'
4th location is 'c' so move it to 4/2 = 2nd location ----- a[2] = 'c'
2nd location is 'b' so move it to 2/2 = 1st location ----- a[1] = 'b'
at this point we started with 1st location and we reached again to 1st location...
now the array looks like
array: a b c 2 e 1 d 3 4 5
index: 0 1 2 3 4 5 6 7 8 9
now traverse the array till L-1 location and check there is any number is still present, if no we are done... else there is a number then continue the above operation...
here L-1 is 4 but at location 3 there is number '2' so move it to L+3/2 => 5+3/2 = 6 ----- a[6] = 2
6th location is 'd' so move it to 6/2 = 3rd location ----- a[3] = 'd'
final array is {a b c d e 1 2 3 4 5}
time complexity O(n) and space complexity O(1)
this is for a sub tree with definition: A sub tree of a tree T is a tree consisting of a node in T and all of its descendants in T should be uni-value (en.wikipedia.org/wiki/Tree_data_structure)
int UniValueSubTrees(node *root, int &count)
{
if(!root)
return 0;
if(!root->left && !root->right)
{
count++;
return 0;
}
int L_C = UniValueSubTrees(root->left, count);
int R_C = UniValueSubTrees(root->right, count);
int L_data=0, R_data=0;
if(root->left)
L_data = root->left->data;
if(root->right)
R_data = root->right->data;
if(((root->data == L_data) && (root->data == R_data)) || root->data == L_data || root->data == R_data)
{
if(L_C == 0 && R_C == 0)
{
count++;
return 0;
}
return 1;
}
else
return 1;
}
en.wikipedia.org/wiki/Tree_data_structure
This is different from the formal definition of subtree used in graph theory, which is a subgraph that forms a tree – it need not include all descendants. For example, the root node by itself is a subtree in the graph theory sense, but not in the data structure sense (unless there are no descendants).
a tree or sub-tree can have one or more than one node... sub tree can or can't have root node, it can be any where in the tree but should be linked to each other.
------------1
-------2--------3
----4----5 --6----7
lets consider all of the node values are equal to 10..
here few of the sub trees are
1. all single values
2. (1,2) (1,3) (2,4) (2,5) (3,6) (2,4,5)
3. but NOT (2,4,6) and (1,3,5)
this is for a sub tree / sub graph with definition: A sub tree/sub graph of a tree T is a tree consisting of a node in T with zero or more of its descendants in T can be uni-value (en.wikipedia.org/wiki/Tree_data_structure)
there are 3 cases for this one, and for each case find number of uni-value sub trees and number of nodes that are equal to root node
1. for a given root, left data and right data is equal to root data then
a. number of uni-value nodes are left_count+right_count+1
b. number of sub trees are left_count*right_count + left_count + right_count + 1
2. for a given root, only left data is equal to root data then
a. number of uni-value nodes are left_count + 1
b. number of sub trees are left_count + 1
3. for a given root, only right data is equal to root data then
a. number of uni-value nodes are right_count + 1
b. number of sub trees are right_count + 1
int UniValueSubTrees(node *root, int &count)
{
if(!root)
return 0;
int L_C = UniValueSubTrees(root->left, count);
int R_C = UniValueSubTrees(root->right, count);
int temp = 1, L_data=0, R_data=0;
if(root->left)
L_data = root->left->data;
if(root->right)
R_data = root->right->data;
if((root->data == L_data) && (root->data == R_data))
{
temp = L_C + R_C + (L_C * R_C) + 1;
count += temp;
}
else if(root->data == L_data)
{
temp = L_C + 1;
count += temp;
}
else if(root->data == R_data)
{
temp = R_C + 1;
count += temp;
}
else
count += temp;
return temp;
}
//function is called with count = 0 and finally count will have the number of uni-value sub trees
take two arrays, sum array and index array of size n+1, fill the array with sum from 0 to i for all array elements, i.e sum[i] = sum of all elements from a[0] to a[i]
ex: 2 3 -4 9 1 7 -5 6 5
sum array : 0 2 5 1 10 11 18 13 19 24
index array: -1 0 1 2 3 4 5 6 7 8
now sort sum array in ascending order including index array.
sum array: 0 1 2 5 10 11 13 18 19 24
index array: -1 2 0 1 3 4 6 5 7 8
now find the absolute difference between any 2 elements is minimum from the above sum array. here from sum array (0,1), (1, 2), (10,11) and (18,19) absolute difference is minimum that is 1.
lets take case 1, 2
here the index is 0 and 2 so we need to take sum from index 1 to 2 in original array that is 3 to -4
lets take case 10, 11
here the index is 3 and 4 so we need to take sum from index 4 to 4 in original array that is 1 to 1
lets take case 18, 19
here the index is 5 and 7 so we need to take sum from index 6 to 7 in original array that is -5 to 6
time complexity O(n log n) that is for sorting and space complexity is O(n)
stack 1 stack 2
push(5) push(5)
push(2) push(2) (in stack2 if new data is less than top of stack then push new one)
push(7) push(2)
push(20) push(2)
push(9) push(2)
push(1) push(1)
now if you pop an element from stack 1, pop from second stack which is having min value till that point
stack 1 stack 2
pop()=>1 pop()=>1 1 is min so far
pop()=>9 pop()=>2 2 is min so far
pop()=>20 pop()=>2
variation of flood fill algorithm
- algos May 27, 2013