jtr.hkcr
BAN USER- 3of 3 votes
AnswersFind the k'th largest element in a binary search tree. Write code for
- jtr.hkcr in United Statesstruct Node { int val; struct Node *left; struct Node *right; } Node; Node * kth_largest(Node *root, unsigned int k);
| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Coding
Total no of combinations in a round table arrangement = (n-1)!
Ordering we are interested = 2 (PS. Ascending and descending order are different as for a person, the one sitting on left and the one sitting on right will be interchanged when the ordering moves from ascending to descending)
So, probability = 2/(n-1)! = 2/4! = 1/12
We can use array for storage + some data structure to manage the storage. We could load the first million data to an array "int A[1000000]". Since we need to insert some data in the middle, we wouldnt want to resize this big array and shift the elements. We can just create the new array of B[500] to store the new 500 members that should be inserted after A[9999]. Then there should be a managing data structure to say that the array is contiguous from 0-9999, then read from B[0-499] and then continue reading from A[10000-999999].
Below is the data structure
class bigIntArray {
public:
bool loadData(string filename) {/*load data from file; first data load*/};
int getAt(long index) {/*look at data_list to identify the memory location for index */}; // or operator []
bool loadAt(long index, string filename) {/* Load new data at index*/};
private:
std::list<pair<int *, long>> data_list; // Chain of arrays, dynamically created
}
/*
1) In loadData(filename), will malloc int array of 1 million elements (assume starting address as A); load the data from file. Add to data_list the starting pointer and size as 1 million. data_list will only have "pair<&A[0], 1000000>"
2) in loadAt(10000, newfile), will malloc int array of size 500 (no of elements in newfile, assume starting address as B) and split data_list to have B in between A. Now data_list will be "pair<&A[0], 10000>", "pair<&B[0], 500>" and "pair<&A[10000], 990000>".
So, we dont split the original array physically, but logically we do.
*/
O(n) Time, space O(1).
Using the idea of hashing of characters (someone mentioned earlier) to check if the string is a palindrome. Can use SHA1 or MD5 or custom hasing logic.
Thought is -
1) Reverse the linked list in forward walk (interatively). In this step, add each character to the hash. So the hashing would be done on the string "abcdefgfedcba"
2) Now that the linklist is reversed, we can reverse this reversed linked list back to the original list. During this step, we will hash the characters from last to first. For e.g.: for the 2nd node in original list "bcd", we should hash characters in the reverse order (ie. "dcb") during this step.
3) f the string is a palindrome, forward walk hash value and backward walk hash value will be same. Return true if so. Else false.
Buy at local minima, sell at local maxima
1) Find the gradient of stock price with respect to days. ie, tomorrows stock price - todays stock price.
2) We buy or sell only when the gradient moves to either side of zero.
2.a) Buy stock on the day when tomorrows price - todays price moves from -ve value (or zero) to +ve value
2.b) Sell the stock on the day when tomorrows price - todays price moves from +ve value (or zero) to -ve value
O(n)
- jtr.hkcr March 11, 2013Here is the code that takes care of duplicates as well. Complexity O(n). If swap() is done inline, it will take only 1 extra space (int tmp). Plus 1 for 'int i' and plus 1 for 'int size'. So not more than 3 variable used. :-)
#include <stdio.h>
void swap(int *a, int *b)
{
int tmp = *a; *a = *b; *b = tmp;
}
void find_missing(int *a, int size)
{
int i = 0;
for (i=1; i<=size; i++) {
while (a[i-1] != -1 && a[i-1] != i && a[a[i-1]-1] != a[i-1]) {
swap(&a[i-1], &a[a[i-1]-1]);
}
}
for (i=0; i<size; i++)
if (a[i] != i+1)
printf("%d ", i+1);
}
int main()
{
#define SIZE 12
/* array with enough space for n elements
extra space padded with -1*/
int a[SIZE] = {6,4,9,4,5,8,3,11,-1,-1,-1,-1};
find_missing(a, SIZE);
}
Here is the code that takes care of duplicates as well. Complexity O(n). If swap() is done inline, it will take only 1 extra space (int tmp). Plus 1 for 'int i' and plus 1 for 'int size'. So not more than 3 variable used. :-)
#include <stdio.h>
void swap(int *a, int *b)
{
int tmp = *a; *a = *b; *b = tmp;
}
void find_missing(int *a, int size)
{
int i = 0;
for (i=1; i<=size; i++) {
while (a[i-1] != -1 && a[i-1] != i && a[a[i-1]-1] != a[i-1]) {
swap(&a[i-1], &a[a[i-1]-1]);
}
}
for (i=0; i<size; i++)
if (a[i] != i+1)
printf("%d ", i+1);
}
int main()
{
#define SIZE 12
/* array with enough space for n elements
extra space padded with -1*/
int a[SIZE] = {6,4,9,4,5,8,3,11,-1,-1,-1,-1};
find_missing(a, SIZE);
}
Here, no of bits set in the memory layout is what we need, right? We could use a union as below:
#include <stdio.h>
int main()
{
union u {
float num;
int i;
} u1;
u1.num = 0.15625; /* floating number to check */
int num_bits = 0;
while (u1.i) {
num_bits++;
u1.i = u1.i & (u1.i-1);
}
printf("No of bits is %d\n", num_bits);
}
Wouldnt this do?
- jtr.hkcr March 10, 2013Nice! Esentially,
1) Find the kth smallest element in O(n) time (en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm)
2) Partition the elements to less than and greater than k in O(n) time (en.wikipedia.org/wiki/Partial_sorting#Direct_application_of_the_linear-time_selection_algorithm)
Essentially O(n) overall..!
Aaha! Nice!!! :-)
Here is the code that will uncompress even when the no of repetitions are >=10 (two digits or more)
Logic:
1. Two pass. First pass will identify the length of the output string
2. Second pass will run from the end to the beginning of string and writes the repeated character back
Code below -
#include <stdio.h>
#include <string.h>
#include <ctype.h>
void uncompress(char *str, int len)
{
/* First pass to find the length of decompressed string */
int read_idx = 0, new_len = 0;
while ( read_idx < len ) {
read_idx++; /* Skip char */
int curr_char_len = 0;
/* Run till we find a char or reach the end;
and count the no of characters that will be written */
while ( isdigit( str[read_idx] ) && read_idx < len )
curr_char_len = 10 * curr_char_len + ((int) str[read_idx++] - '0');
new_len += curr_char_len;
}
/* Second pass to write the uncompressed string. Will start reading and writing from the end */
str[new_len] = '\0';
int write_idx = new_len - 1;
while ( --read_idx > 0 ) { /* Skipping char in the loop check */
int curr_char_len = 0, power_of_ten = 1;
while ( isdigit( str[read_idx] ) && read_idx >= 0) {
curr_char_len = curr_char_len + power_of_ten * ((int) str[read_idx--] - '0');
power_of_ten = 10 * power_of_ten;
}
/* Write the char at str[read_idx] to write_idx position curr_char_len times */
while (curr_char_len--) str[write_idx--] = str[read_idx];
}
}
int main()
{
char str[100] = "A12B3C24D1E7D11K1";
uncompress(str, strlen(str));
printf("Uncompressed string is %s\n", str);
}
Hope this suffices. Please update if you find any issues.
- jtr.hkcr March 04, 2013Guess this fits into publish subscribe model - Observer design pattern
1. Each user owns his/her data in his/her user area (data structure). Can be
class User {
UserID id; // unique id
std::list<Update> self_updates; // owned by user; list of updates in reverse chrono order
std::list<Update *> friend_updates; // owned by user friends; list of updates in reverse chronological order
std::list<User *> friends; // Friend list
};
class Update {
UpdateType type; // media type of this update - can be photo/video etc
DateTime timestamp;
Message msg; // Message text in this update
Media *media; // can be pointer to photo/video/audio in the update OR NULL
List<Comment> comments; // Comments on this update
}
Now Publish(user, msg) will
1. Wrap the msg into Update data structure and add to the front of 'self_updates' list
2. For all the friends in 'friends' list, update their 'friend_updates' list with a pointer to this Update data structure (This is where the observer pattern comes).
Note: A user logged into the FB web UI will see the update when the browser polls the user area for any self/friend updates.
GetNewsFeed(user) will
1. Get the first 30 updates from 'self_updates' and 'friend_updates' sort them according to timestamp (these two are sorted according to timestamp individually). This will interleave self_updates between friend_updates.
2. Take the latest 30 updates from this sorted list to send back to browser UI.
Hope this design suffices.
Hi Jean,
This is C++ (Except for the usage of STL queue container class, this is C code. Didnt want to write code for queue in C).
Logic:
Node *create_string_tree(const char * str)
BFS traversal is => First root, then roots left child, then roots right child, then roots left childs left child, and so on. Shown below
1. root
2. root->left
3. root->right
4. root->left->left
5. root->left->right
6. root->right->left
7. root->right->right
8. root->left->left->left
9. root->left->left->right
10. root->left->right->left
...and so on
queue<Node **> insert_q is used to keep track of this order. We will insert the address of left or right pointer in this queue and hence "Node **".
Root of the binary tree will be the first character in the string. Once the root node is created, the next elements will be inserted to the left child pointer first, then the right pointer. Hence adding them to the insert_q in that order.
For loop will run through the rest of the characters in the string. For each character in the string, for loop will
- Insert each of them to the first address from the insert_q (and removes that address from the queue).
- Once the node for a character is attached to the tree, we put that nodes left and right address to the queue for future insertion.
Once all the characters are inserted, insert_q is discarded and the root pointer is returned.
This is the logic of create_string_tree(). Logic for get_string_from_tree() is similar except that we use a queue of "Node *" instead of "Node **" as the operation is only reading the elements from tree.
Hope this description is clarifies. Thanks.
Programming is an art. Practice makes any skill perfect, including programming. Just look at how artists better their skills. They practice their stuff over and over again and learn in this process. They just love what they are doing, and they just cant stop doing it!
Ok, getting back to programming. Practice solving as many CS problems as possible.
1. Solve as many problems from careercup.com as possible.
2. Get the book Programming Interviews Exposed (latest edition), solve all the problems in it.
3. Once this book is done, get the book Cracking The Coding Interview (latest edition), solve all the problems in that. Suggesting to go with P I Exposed first as the other book (CTCI) is a little more complicated.
4. Do some mock interviews in your friend circle.
5. Pray! :-P Even if you are the best hacker around, it all depends on how well the interview goes! :-)
1. Insert the characters into a binary tree using preorder breadth first traversal. Insertion will be O(n).
2. Retrieve the characters using preorder BFS traversal. Will be O(n).
Code below-
#include <iostream>
#include <queue>
using namespace std;
struct Node {
char ch;
Node *left;
Node *right;
};
Node *create_node(char ch)
{
Node *n = new Node;
n->ch = ch;
n->left = n->right = NULL;
return n;
}
// Insert using breadth first traversal. This will help keep the tree balanced
Node * create_string_tree(const char *str)
{
queue<Node **> insert_q; // Stores address of left and right subtree pointers of a node
Node * root = create_node(str[0]);
insert_q.push(&(root->left));
insert_q.push(&(root->right));
for (int i=1; i<=strlen(str); i++) {
Node *n = create_node(str[i]);
Node **parent_addr = insert_q.front();
*parent_addr = n;
insert_q.pop();
// Add to end of queue;
insert_q.push(&(n->left));
insert_q.push(&(n->right));
}
return root;
}
string get_string_from_tree(Node *root)
{
//Do BFS traversal and add to str
string str;
queue<Node *> read_q;
read_q.push(root);
while (!read_q.empty()) {
Node *n = read_q.front();
read_q.pop();
str += n->ch;
if (n->left) read_q.push(n->left);
if (n->right) read_q.push(n->right);
}
return str;
}
int main()
{
Node *tree = create_string_tree("abcdefghijklmn");
string str = get_string_from_tree(tree);
cout << "String is " << str << endl;
}
Lemme know if there are any issues in this... Thanks.
- jtr.hkcr March 03, 2013Hi,
we can do this in O(n logn).
1. Have two arrays, one sorted on arrival time and the other sorted on departure time. O(n logn)
2. Then, we can do a walk on the arrival array from time 0 to max, finding total no of people at any moment. Will be no of arrivals till time T (index of arrival array for time T) - no of departures till time T (index of departure array for time less than or equal to T). This operation will be O(n) (by using one index each on arrival and departure arrays).
3. The max of total no of people at any moment will be the answer.
Hence order O(n logn); (Data structure mentioned in post below)
Hi,
(indexA - indexD) will give the no of people present in the event at any moment (lets say T);
where indexA => no of people arrived till time T,
and indexD => no of people departed till time T.
Looks like the answer is not complete since the questions is "find out the maximum number of people present at any time during the entire event"
In order to find the maximum no of people present at any time in the entire event, we need to keep track of the no of people currently present at the event when each person arrived. We can keep another array (or vector) for each element in sorted arrival array that will store the no of people present (including the person just arrived) at the event when each new person arrived at the event. This will be (indexA-indexD) for all moment T when an arrival happened. Max value from this third array will be the answer to this question.
Hi Abhishek, i did not understand steps 3 to 7 you mentioned.
data structures:
struct person_time {
int person_id; /* or char person name */
datetime time;
};
vector<person_time> arrival;
vector<person_time> departure;
1. Take all arrival time (ai's) and sort it in the increasing order of time and load to a vector (or list) *arrival*.
2. Similarly take the departure time (di's), sort in increasing order and load to vector *departure*.
To see number or people present in the event at any given time T:
1. Do a binary search on *arrival* to get the index of highest element lower than time T. This index (say indexA) represents total number of people came/arrived to the event till time T.
2. Similarly do a binary search on *departure* to get the index of highest element lower than time T. This index (say indexD) will represent the no of people departed from the start of the event till time T.
3. (indexA - indexD) will be the total number of people present at the event at any given time.
Update:
To find the max no of people present at the event at any given time -
1. Walk through each element in *arrival*. No of people arrived till arrival[i].time will be the index of the arrival vector, ie. "i".
2. No of people departed till arrival[i].time will be the no of elements in the *departure* that have departure[j].time <= arrival[i].time. So, no people departed will be "j".
3. Total no of person at arrival[i].time = (i - j);
Max of (i-j) for each i will be the answer to this Q.
O(n logn)
1. Generate NxN probability matrix P(x,y,1) for all (x, y) coordinates (x & y ranges from 0 to N-1). P(x,y,1) is the probability of staying alive after taking 1 step
2. Now using this, we need to calculate the NxN probability matrix P(x,y,2) for all x and y - will be P(x,y,1) * { {Valid among P(x+1, y, 1) + P(x, y+1, 1) + P(x-1, y, 1) + P(x, y-1, 1) } / num of valid adjascent slots }. Now we have P(x,y,2) probability matrix.
3. Using induction, we can calculate P(x, y, k) using P(x, y, k-1). Repeat this N times, we have our probability matrix after N steps
float probabilityofalive(int x, int y, int N, int num_steps)
{
if (N <= 0) return 0;
if (x < 0 || x >= N) return 0;
if (y < 0 || y >= N) return 0;
if (N == 1) return 0; // only one square. first step will cause exit from island and die.
/* Probability matrix for staying alive after K steps for all (x,y) coordinates. */
double *P_old = calloc(N*N, sizeof(double));
/* Probability matrix for staying alive after K+1 steps for all (x,y) coordinates. */
double *P_new = calloc(N*N, sizeof(double));
int i, j;
/* Initialize for K = 1 */
for (i = 0; i<N; i++) {
for (j=0; j<N; j++) {
double prob;
if (i>0 && i<N-1 && j>0 && j<N-1) {
prob = 1.0;
} else if ((i == 0 || i == N-1) && (j == 0 || j == N-1)) {
prob = 0.5;
} else
prob = 0.75;
P_new[N*i + j] = prob;
}
}
int k = 0;
for (k=2; k<=num_steps; k++) { /* First step already taken in K == 1 matrix above */
/* Copy new to old */
for (i = 0; i<N; i++) {
for (j=0; j<N; j++) {
P_old[N*i+j] = P_new[N*i+j];
}
}
/* Calculate new probability matrix */
for (i=0; i<N; i++) {
for (j=0; j<N; j++) {
double sum_prob = 0;
int num_prob = 0;
if (i > 0) {
sum_prob += P_old[N*(i-1) + j];
num_prob++;
}
if (i < N-1) {
sum_prob += P_old[N*(i+1) + j];
num_prob++;
}
if (j > 0) {
sum_prob += P_old[N*i + (j-1)];
num_prob++;
}
if (j < N-1) {
sum_prob += P_old[N*i + (j+1)];
num_prob++;
}
/* New probability when person starting at (i,j) coordinate after k steps*/
P_new[N*i + j] = P_old[N*i + j] * sum_prob/num_prob;
}
}
}
return P_new[N*x + y];
}
int main()
{
int x = 3;
int y = 3;
int N = 4;
int num_steps = N;
float prob = probabilityofalive(x, y, N, num_steps);
printf("Probability of staying alive after %d steps starting at coordinates (%d, %d) on an %d x %d grid is '%f'\n", num_steps, x, y, N, N, prob);
}
/*
For N = 4, probability fo survival after 1 step is given below
-------------------------------------
| | | | |
| 0.50 | 0.75 | 0.75 | 0.50 |
| | | | |
-------------------------------------
| | | | |
| 0.75 | 1.00 | 1.00 | 0.75 |
| | | | |
-------------------------------------
| | | | |
| 0.75 | 1.00 | 1.00 | 0.75 |
| | | | |
-------------------------------------
| | | | |
| 0.50 | 0.75 | 0.75 | 0.50 |
| | | | |
-------------------------------------
Probability fo survival after 2 steps will be
-------------------------------------
| | | | |
| 0.38 | 0.56 | 0.56 | 0.38 |
| | | | |
-------------------------------------
| | | | |
| 0.56 | 0.88 | 0.88 | 0.56 |
| | | | |
-------------------------------------
| | | | |
| 0.56 | 0.88 | 0.88 | 0.56 |
| | | | |
-------------------------------------
| | | | |
| 0.38 | 0.56 | 0.56 | 0.38 |
| | | | |
-------------------------------------
... and so on
*/
Believe this logic/code is correct. Please update if you find any issue
- jtr.hkcr March 02, 2013
RepNirvedPerez, abc at 8x8
To make sure a thorough investigation is done if discrepancies occur. Execute the Brand Customer Service standards to meet or ...
RepBriannaWright, Analyst at A9
I am a skilled project manager with years of exemplary service in diverse IT roles. I am passionate about utilizing ...
1. Identify kth element from beginning (say kth_first), also reverse the list.
2. Identify kth element from beginning on the reversed link list (say kth_last), and reverse the reversed list (Now the list will become original list).
3. swap the values in kth_first and kth_last.
Logic is in swap_kth_node() function. O(n) time complexity.
- jtr.hkcr March 25, 2013