ashot madatyan
BAN USERBelow is the complete code and the driver program to return the k-th minimum node in the BST, with all the corner case tests implemented. Just do an in-order traversal of the BST nad count the number of the nodes processed up to the current point. As soon as the counter (initially set to "k") turns 0, we know that we have reached the k-th minimum node, so return it.
#include <stdio.h>
#include <stdlib.h>
////////////////////////////////////////////////////////////////////////////////
struct Node {
int data;
Node* left;
Node* right;
Node() : data(-1), left(NULL), right(NULL) {};
};
bool bst_add_node(Node* root, Node* newnode)
{
if (NULL == root || NULL == newnode)
return false;
if (newnode->data <= root->data) {
if (NULL == root->left){
root->left = newnode;
return true;
}
else { // the left node exists
return bst_add_node(root->left, newnode);
}
}
else { // the new node's value is GT the root's value
if (NULL == root->right){
root->right = newnode;
return true;
}
else {
return bst_add_node(root->right, newnode);
}
}
return true;
}
bool bst_add_value(Node* root, const int& val)
{
Node* newnode = new Node;
newnode->data = val;
return bst_add_node(root, newnode);
}
void print_bst(Node* root)
{
if (root->left)
print_bst(root->left);
printf("%d\n", root->data);
if (root->right)
print_bst(root->right);
}
////////////////////////////////////////////////////////////////////////////////
/** Do an in-order of the BST here */
void kthmin(Node* node, Node*& retnode, int& k)
{
if (node->left)
kthmin(node->left, retnode, k);
// Process the node itself
--k;
if (0 == k) {
//print_node(node);
retnode = node;
return;
}
if (node->right)
kthmin(node->right, retnode, k);
}
int main(int argc, char* argv[])
{
Node root;
Node* kthnode = NULL;
int kth = 1;
int kthstore = kth;
int arr[] = { 5, 1, 12, 24, 38, 20, 15, 6, 83, 33 };
int cnt = sizeof(arr) / sizeof(arr[0]);
if (argc > 1) {
kth = atoi(argv[1]);
kthstore = kth;
}
root.data = 18;
// Add some values to the BST
for (int i = 0; i < cnt; ++i){
bst_add_value(&root, arr[i]);
}
kthmin(&root, kthnode, kth);
print_bst(&root);
if (kthnode)
printf("%d-th minimum node value: %d\n", kthstore, kthnode->data);
else
printf("%d-th minimum node not found\n", kthstore);
return 0;
}
- ashot madatyan June 04, 2013You may think of creating the Voronoi diagram of a 2D space and group all the cities based on that diagram. See the link below:
en.wikipedia.org/wiki/Voronoi_diagram
@AB: It is the correct algo, see the complete working code below:
#include <stdio.h>
#include <list>
using std::list;
int list_sum(const list<int>& L1, const list<int>& L2)
{
int sum = 0;
list<int>::const_iterator it1, it2;
it2 = L2.begin();
for(it1 = L1.begin(); it1 != L1.end(); ++it1, ++it2){
int crv = *it1 + *it2;
sum *= 10;
sum +=crv;
}
return sum;
}
int main(int argc, char* argv[])
{
// add the two integers stored in the lists
// L1 3 8 5 6 7
// L2 4 9 1 2 8
int sum = 0;
int l1[] = {3, 8, 5, 6, 7 };
int l2[] = {4, 9, 1, 2, 8 };;
list<int> L1(l1, l1 + 5);
list<int> L2(l2, l2 + 5);
sum = list_sum(L1, L2);
printf("SUM: %d\n", sum);
}
It's a simple mathematics problem and no additional DS or additional traversal
are required. Just do a single traversal of both LL's from start to end,
and add up the current two values (CRV=L1[i] + L2[i]), multiply the stored
accumulator by 10 and add the CRV.
Below is the pseudo code:
L1[], L2[], CRV = 0, RES=0
for (i = 0; i < L1.size(); ++i)
{
CRV = L1[i] + L2[i]
RES = RES * 10
RES = RES + CRV
}
That's all.
- ashot madatyan May 18, 2013You will also have to take care for the situation when the LL size is even. In that case, there is no middle element per se, so the range to be reversed are the elements [ n/2 ; n-1 ], where "n" is the size of LL.
0 1 2 3 4 5
a->b->c->c->b->a // original LL
a->b->c->a->b->c // reversed at mid-point LL
The inner while loops should look like below:
while ( i <= j && a[i]==0) i++;
while (j >= i && a[j]==1) j--;
This is the minimum edit distance algorithm. You can look it up at various sources, some of them listed below (AKA "Levenshtein distance"):
w_ww.stanford.edu/class/cs124/lec/med.pdf
w_ww.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/
e_n.wikipedia.org/wiki/Levenshtein_distance
Considering the question as is, Evgeny's solution seems to be the right choice to eliminate the recursion, as well as the space overhead of O(n).
- ashot madatyan December 04, 2012See my complete implementation at:
codepad.org/upGbOBdY
Just use a single traversal, which is even more effective than element counting followed by generating a new sequence:
char *pstart, *pend;
while (pstart < pend){
while (*pstart == '0')
++pstart;
while (*pend == '1')
--pend;
char tmp = *pstart;
*pstart = *pend;
*pend = tmp;
++pstart;
--pend;
}
- ashot madatyan November 30, 2012I think you do not need to substitute any variable for any random value. Instead, just build the expression trees for both input strings and see whether those trees are identical in their structures and input parameters. For the most cases, it's going to be a binary tree, since most of the operators are binary (require two operands), though there can be nodes where the root may contain 3 children, which will be the case for ternary operators.
- ashot madatyan November 30, 2012BTW, are you familiar with the tail recursion paradigm?
- ashot madatyan November 23, 2012I some how missed that part - the "reverse the characters of each word". The problem is now even easier with my algo - at step #2, just do not do the in-place reversal of each word. Thanks for noting that, pal.
- ashot madatyan November 22, 2012@sonny<...>
I'd suggest you to ask your late dog about how smart you are, you still may get some clever hints from it. Not sure about your kids - if they have gone after their father, then ... guess you already understood what they are in for. Live and learn (if you can)..
For the case when there is more than one number occurring odd number of times, use the following algorithm
create a hash table
for each x in array
if the x is found in the hash table
remove it from the HT
else
add it to the HT
The resulting hash table will eventually contain all the elements that occur odd number of times.
- ashot madatyan November 22, 20121. Perform in-place reversal of the original string.
e.g. "How arE you doinG today" => "yadot Gniod uoy Era woH"
Note that the words to be removed now have their first character in upper case.
2. Scan the resulting reversed string and reverse each term (word) in place, while
skipping those starting with upper case.
At this point, you will need to store the position of the last delimiter
encountered so far, because as soon as you skip any word starting with the
upper case, you will need to move it (copy over) the next valid word to the
position following the last encountered whitespace (space in this example)
The above example will result in the following string "today you How"
@CameronWills
The "contains" function is very straightforward - starting from the input node it just looks for the node with the given value. First it checks the input node's value, if it is not the one being sought, it looks in the left and then in the right subtrees of the given node.
Time complexity of this function is O(N). The overall time complexity of the given solution is quadratic, with constant space.
@sonny.c.patterson
Would you please bother yourself commenting the "Ugh" - for me this term does not contain any logic, neither does it provide us with any counterarguments or some constructive reasoning.
See my O(N) time and O(1) space implementation at stackoverflow.com/a/13502863/1832586 along with description of how it works.
- ashot madatyan November 21, 2012Assuming single-byte encoded stream, you can solve this problem in linear time
and using constant space by simply utilizing the counting sort algorithm with an
array of a data structure that stores the first position of the encountered character.
As soon as the stream has no more characters in it, we simply exit the while loop,
which has already built the stream statistics for us - the count of each character
and its first occurence position in the stream.
So, the problem is reduced to finding the character that has occurred only once
and that has the least occurrence position (the first unique).
================================================================================
static const int STAT_SIZE = 256;
static const int INVALID_POS = (-1);
struct char_pos {
int count;
int position;
char_pos() : count(0), position(-1){};
};
int main()
{
char_pos stream[STAT_SIZE];
char_pos *chstat;
int pos = 0, curpos;
char chunique;
/* Accumulate the stream statistics */
while (hasNextChar()){
char ch = getNextChar();
chstat = &stream[ch];
chstat->count++;
if (chstat->position == INVALID_POS)
chstat->position = pos;
++pos;
}
pos = INVALID_POS;
/* Iterate over the statistics and find the first unique character */
for (int i = 0; i < STAT_SIZE; ++i){
if (stream[i].count == 1) {
chunique = (char) i;
curpos = stream[i].position;
if (INVALID_POS == pos) {
pos = curpos;
}
else {
if (curpos < pos)
pos = curpos;
}
}
}
if (INVALID_POS == pos)
printf("No unique character found in the stream\n");
else
printf("The first unique character: 0x%02x found at position %d\n", chunique, stream[chunique].position);
return 0;
}
- ashot madatyan November 17, 2012Implemented along with a driver program in c++ at the link below.
stackoverflow.com/questions/5037503/how-can-i-manipulate-an-array-to-make-the-largest-number
@codinglearner
From the point of view of information retrieved by weighing the marbles, each weighing may yield us
three different results: the left pan is heavier, the right pan is heavier and the pans are in balance.
If we weigh two equal-sized groups of marbles, we are not using the complete information about the weighing - the case when the pans are in balance.
In that case (splitting into two equal-sized groups), we lose 1/3 of the information that comes from weighing.
This is why we need to maximize the use of information coming from weighing result, i.e. what part
of the marbles can be safely skipped as having no bad (heavier or lighter) marble.
So, to maximize the information usage, we will need to divide our marbles into three possibly equal-sized groups.
As soon as we weight the first two equal-sized groups and have the result, we can safely eliminate 2/3 of the total count
of marbles. We proceed with this logic until we are left with a single marble.
The task of repeatedly dividing by 3 eventually leads us to the formula
C = log3(N), where
N - the total count of marbles
C - the count of weighings required to identify the bad (heavier or lighter) marble
Complete code with all inlined comments for both BST definition and algorithm:
struct Node {
Node *left;
Node *right;
int value;
};
/**
Definition of a BST and algorithm.
Given tree is considered a BST if: (1 || (2 && 3))
1. It is an empty tree;
2. All the nodes in the left subtree of any node have values less than
or equal to the given node's value && is a BST itself;
3. All the nodes in the right subtree of any node have values greater than
the given node's value && is a BST itself;
@param lbValue - the minimum allowed value of the given node
@param ubValue - the maximum allowed value of the given node
Any node should meet this constraint: lbValue <= node.value < ubValue
The value range for any node is as follows:
For any node in the left subtree of node N:
lbValue <= child.value < N.value
For any node in the right subtree of node N:
N.value < child.value <= ubValue
*/
bool IsBST(Node *node, const int& lbValue, const int& ubValue)
{
if (NULL == node)
return true;
/* Using a tail recursion here to eliminate the stack frame inflation */
return ( (IsBST(node->left, lbValue, node->value)) &&
(IsBST(node->right, node->value, ubValue)) );
}
int main ()
{
Node *root = GenerateBinaryTree(...); // code to generate a BT (not necessarily a BST)
bool bIsBST = IsBST(root, INT_MIN, INT_MAX);
return 0;
}}
- ashot madatyan November 09, 2012Have you read the original question ? You have to find (and presumably return it) the LCA node, while your code just returns integers.
- ashot madatyan November 08, 2012LCA of two nodes in a binary tree - complete implementation that also checks whether the nodes are in the tree at all. Algorithm description are inline, as well as inlined are the comments to help you understand the complete flow of the algo:
bool contains(Node *root, Node *sought)
{
if (NULL == root)
return false;
if (root->data == sought->data)
return true;
return (contains(root->left, sought) || contains(root->right, sought));
}
/**
Algorithm description:
Find the subtrees where the two nodes are contained.
if either of the nodes is not found
return NULL
else
return the node starting from where the two nodes being sought are in different subtrees (the two nodes diverge)
*/
Node* LCA (Node *root, Node *firstnode, Node *secondnode)
{
bool ffound_in_left, ffound_in_right, sfound_in_left, sfound_in_right;
ffound_in_left = contains(root->left, firstnode);
if (ffound_in_left) {
sfound_in_left = contains(root->left, secondnode);
if (sfound_in_left) {
return LCA(root->left, first, second);
}
else {
sfound_in_right = conatins(root->right, second);
if (sfound_in_right) // the nodes diverge here (the first is in the left and the second is in the right, so return root)
return root;
return NULL; // the right node has not been found at all
}
}
else { // the first node not in left, try to find it in the right subtree
ffound_in_right = contains(root->right, first);
if (ffound_in_right) {
sfound_in_right = contains(root->right, second);
if (sfound_in_right) {
return LCA(root->right, first, second); // both the first and second nodes are in the right subtree, go to there
}
else { // the first found in the right and the second not found in the right, check to see whether the second exists in the tree at all
sfound_in_left = contains(root->left, second);
if (sfound_in_left == true) { // second found in the left subtree, while the first is in the right, so they diverge
return root; //
}
else { // second not found in the tree at all
return NULL;
}
}
}
}
// first not found in the right subtree either, so it is not present in the tree at all
return NULL;
}
- ashot madatyan November 08, 2012It depends on bunch of requirements and/or restrictions, such as the size of the dictionary, how many suggestions should the user see, how the word matching should be done (prefix- or suffix-matching), how many character are to be typed initially to begin suggesting words, etc.
Suppose I type the first character as "a", what do you think the dictionary/db data should I see as a suggestion - all the words beginning with "a" or only some of the first words? Also agree to eugen.yarovoi's counter question.
So, depending on the answers to all (or some) of the above questions/restrictions, you could think of different approaches, e.g. caching the DB data, creating your own trie-like DS, etc.
I think that cheating upon oneself is not a good idea - both during any interview and beyond it. Even if someone can make it through the phone screening, he/she will eventually face the interviewers. So, I think the best thing to do before the interview is to prepare properly for it and try to stay focused during the interview itself and do not get into temptation to look up some stuff in internet or books. The interviewers are also people :), and they can easily figure out whether you are cheating or not.
- ashot madatyan July 26, 2012Pointers are special types of variables that can hold the memory location (point to the address) of another variable
or just point directly to a specific memory location, which should be within the valid range for your process.
Below are some use cases for pointers:
1. Allocate a storage for a specific variable and store that location address in a pointer;
2. Use pointers to pass the variable to other functions (compare with pass by value scenario).
The called function will actually change the original variable's value when using the passed in
pointer to modify that variable inside the function (again, compare with the "by value" scenario
when the modified variable does not affect the original variable);
3. Pointers are very extensively used in h/w programming, e.g storing the address of a variable in h/w registers;
4. For all the other cases, please consult any C/C++ books :) or just use Wiki
Moreover, if you use the " if ... else " constructs instead of virtual functions, you will have to change your top level processing code whenever a new subtype needs to be handled, while with virtual functions the only thing that needs to be doen is to pass the pointer or reference of the proper instance to the top level function that expects a pointer or reference to the base class.
See the below code that I have created for specifically this comment and see the diffs of conditional and dynamic processing:
class Base{
public:
Base() : class_type(0){};
virtual ~Base() {};
virtual void process(void) {// some processing};
int class_type;
};
class D1 : public Base{
public:
D1() : class_type(1){};
virtual ~D1() {};
virtual void process(void) {// some processing};
int class_type;
};
class D2 : public Base{
public:
D2() : class_type(2){};
virtual ~D2() {};
virtual void process(void) {// some processing};
int class_type;
};
void handle_objects_conditionally(Base *obj)
{
if (obj->type == 0)
//call some Base class specific handler
else if (obj->type == 1)
//call some D1 class specific handler
else if (obj->type == 2)
//call some D2 class specific handler
}
void handle_objects_dynamically(Base *obj)
{
obj->process(); // the proper handler shall be called automagically for you
}
Below is the iterative implementation using a single stack of size of the tree height. Also including the driver program to test it (complete working version).
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
struct Node {
int data;
vector<Node*> children;
};
Node *add_node(Node *root, int data)
{
if (NULL == root)
return NULL;
Node *node = new Node;
node->data = data;
root->children.push_back(node);
return node;
}
void delete_nodes_iterative(Node *root)
{
stack<Node*> stnodes;
Node *cur = root;
stnodes.push(cur);
while (true) {
cur = stnodes.top();
printf("size: %d; cur: %d\n", stnodes.size(), cur->data);
if(cur->children.size() > 0) {
stnodes.push(cur->children[0]);
cur->children.erase(cur->children.begin()); // unlink from parent but do not delete the node itself
}
else { // leaf node
stnodes.pop();
printf("\tdel: %d\n", cur->data);
delete cur;
}
if (stnodes.empty())
break;
}
}
int main()
{
Node *root = new Node;
root->data = 1;
Node *n2 = add_node(root, 2);
Node *n3 = add_node(root, 3);
Node *n4 = add_node(root, 4);
Node *n5 = add_node(n2, 5);
Node *n6 = add_node(n2, 6);
Node *n7 = add_node(n2, 7);
Node *n8 = add_node(n3, 8);
Node *n9 = add_node(n3, 9);
Node *n10 = add_node(n3, 10);
Node *n11 = add_node(n4, 11);
Node *n12 = add_node(n4, 12);
Node *n13 = add_node(n4, 13);
Node *n14 = add_node(n4, 14);
Node *n15 = add_node(n5, 15);
Node *n16 = add_node(n5, 16);
Node *n17 = add_node(n5, 17);
Node *n18 = add_node(n6, 18);
Node *n19 = add_node(n11, 19);
Node *n20 = add_node(n11, 20);
Node *n21 = add_node(n16, 21);
Node *n22 = add_node(n16, 22);
delete_nodes_iterative(root);
}
@Evgeny
I am not sure that I quite understood the idea of using the " char* " as a key in a map for associating the identity. Could you please elaborate on that?
Yes, you can. But this is going to be pretty useless cause the key comparison is going to be done for pointers themselves, not for the memory content they point to, which is what is presumed the char* is meant to be used for. Consider the less predicate acting upon two pointers: char *p1 < char*p2. Is this what we want ? Definitely not.
- ashot madatyan July 24, 2012Having made sure that sorting is OK, please see the implementation at the link below:
codepad.org/niDD5OZ1
See my implementation of the configurable and very fast MRU cache at:
codepad.org/jlzNbum3
@Evgeny: You have suggested the exact combination of DS's that I have implemented at the link above (btw, this was one of the FB phone interview questions)
Well, that's a logical approach and meets the space constraint (hope you are suggesting using slow and fast pointers to identify the middle of the LL). Just would like to add some notes:
1. At the end, the reversed part of the LL would most probably need to be reverted;
2. When finding the middle, make sure that you take care of both cases when the LL may have either odd or even count of elements;
This is the same question as posted here: careercup.com/question?id=14097726
See my implementation at the link above.
@sun.wael
The "sizeof" operator returns the number of bytes not the number of elements.
memcpy copies symbols from source to destination nad its parameters are void*. And, please note that it makes no difference whether the data is string or not, it treats them as simply binary data.
- ashot madatyan July 07, 2012//Assuming array B has enough space for array A
// and the arrays are not overlapping (for overlapping arrays, use memmove)
template <typename T>
void array_cpy(T A[], T B[])
{
size_t sizeA = sizeof(A);
memcpy((void*)&B[0], (void*)&A[0], sizeA);
}
Base 26 with an exception of zero.
- ashot madatyan June 30, 2012This is basically a number represented in base 26 with an exception that it has no 0 value (numbers go from 1 to 26 through).
So, to convert for example the "ABCD" to base 10 integer, just sum up as follows: pow(26,0)*('D'-'A' + 1) + pow(26,1)*('C'-'A' + 1) + pow(26,2)*('B'-'A' + 1) + pow(26,3)*('A'-'A' + 1).
See my implementation at codepad.org/3Xlsia9d
Could you please post the question(s) and the answer(s). I think this is a good place to put it to discussion and try to see "who is who in the zoo" :)
Anyway, I think you should be prepared for facing this kind of "google kids" even in interviews with the companies in Forbes top 500. What I mean is that the company name
does not guarantee you against being interviewed by a stupid and/or "pompous" haughty employer/interviewer. On the other hand, as you may be knowing, they do not like the interview being hijacked. Being in your shoes, I would try to find fuel even in that situation and move ahead without looking back at previous misfortunes, beacause the world is full of fools, which often fail to see those smarter than them.
Good luck !!!
Very easy - keep track of the first vowel encountered or the first vowel placed before the very first consonant and this vowel shall be your head pointer. If there are no vowels at all, just return the original head pointer, which will naturally be a consonant.
- ashot madatyan June 27, 2012Scan the list and keep track of the last vowel encountered. As soon as the current element is non-vowel(consonant), just skip it and continue scanning towards the end of the list. When the current element is a vowel, remove it from the list and add it as the next element of the last encountered vowel and make this newly added element as the last encountered vowel.
- ashot madatyan June 27, 2012@saurabh
OK, this seems really to be a kid's stuff. What will you answer when you are asked why do you devide into three groups , etc. How would you describe the algorithm, if you are given not 9 marbles, but say 120, or some other number of them? This is the main point in posing this types of problems - to find out how the person thinks about attacking the problem, and how he/she would scale his solution and generalize the algorithm.
I dare believe they are "marbles" not "maples" :)
Anyway, this is a known problem and the heavier one can be identified in just two weighings (I also believe the fact that you are given a scale is also missing from the problem statement :)).vDivide those marbles into 3 groups, each conating 3 marbles:
Weigh the group 1 and 2. If they are in balance, then the heavier one is in the third group - weigh any 2 of the remaining marbles in the third group, if they are in balance, then the third one is the guy. Similarly do for the case, when the first weighing identified the heavier group. Anyway, the total count of weighings is 2.
@shondik
Though the implementation works properly, I wouldn't call it a "backtracking algorithm", because you do not discard any intermediate solutions based on some criteria. Instead, you incrementally build the solution.
@marti
In "find the no of ways the third string can be generated" could you please specify what is meant by "the third string" then? I think the problem statement is defined somewhat bad. In suggesting the algorithm, I presumed that the problem is like: "Given two strings find all the proper shuffles of those strings". If this is not what the problem poster had in mind, then I think the problem needs to be re-worded to make it unambigous and clearly defined.
You do not need to check for the third string, just generate the proper shuffle series as described in the above algorithm. As for DP, I do not think this is required here, because we do not need to store any intermediate values to help us eliminate any recomputing - just a simple recursive algorithm is fine here, something similar to what shondik's code snippet does.
- ashot madatyan June 23, 2012Hey folks. This is not strict permutation or combination problem as suggested
by some guys above. This is a classic proper shuffling problem, when you have to
shuffle two sets while maintaining their relative order (e.g. a1 a2 a3 shuffled
with b1 b2 b3 b4 => b1 a1 a2 b2 a3 b3 b4).
This can be easily solved recursively using the following algorithm:
Suppose we have two strings to shuffle: "abc" and "de"
1. take the second string "de"
2. for each char of the string "de", insert it into every possible positions in the string "abc"
e.g. d + "abc" => [dabc; adbc; abdc; abcd;] (1)
3. Now, insert all the following chars of the string "de", in this case only the "e",
into all the possible positions in the strings (1), while noting that in each
case the letter "e" should succeed the letter "d".
For our example (the strings "abc" and "de") it will result in:
add "d" to every possible positions of "abc"
dabc (tmp1)
adbc (tmp2)
abdc (tmp3)
abcd (tmp4)
add the "e" to every possible position after letter "d" in the strings tmp1-tmp4
for "dabc"
deabc (s1)
daebc (s2)
dabec (s3)
dabce (s4)
for "adbc"
adebc (s5)
adbec (s6)
adbce (s7)
for "abdc"
abdec (s8)
abdce (s9)
for "abcd"
abcde (s10)
Adding the link to my solution of the problem:
codepad.org/gT4EdzdG
It was a correct note to use set instead of a map, since we only need to keep track of existing (encountered) values, but not a key-value pair.
- ashot madatyan June 19, 2013