zdmytriv
BAN USER- 0of 0 votes
AnswersYou are given a Linked List and a function declaration as node* KReverse(node* head, int k);
- zdmytriv
KReverse is a function that reverses the nodes of a Linked List k at a time and then returns the modified Linked List.
For Example
Linked List : 1->2->3->4->5->6->7->8->9->10->11
For k = 2
Return Value: 2->1->4->3->6->5->8->7->10->9->11
For k = 3
Return value: 3->2->1->6->5->4->9->8->7->10->11
Write a solid secure definition for the function KReverse.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Data Structures Algorithm
void reverse_string(char * string)
{
int n = strlen(string); // number of characters in the string
for(int i = 0; i < n; ++i) {
if((string[i] >= 'a') && (string[i] <= 'z')) {
string[i] -= 32;
} else if((string[i] >= 'A') && (string[i] <= 'Z')) {
string[i] += 32;
}
}
return;
}
"Present" string as binary. If i-th bit ON print character i.
L - length of the string;
2^(L-1) - number of combinations
void combinations(const char * string)
{
int n = strlen(string); // number of characters in the string
long c = pow((float)2, n); // number of combinations
for(int i = 1; i <= c; ++i) {
int tmp = i;
int index = 0;
while(tmp > 0) {
if(tmp & 1) { printf("%c", string[index]); }
tmp >>= 1;
++index;
}
printf("\n");
}
}
int main()
{
char string[12] = "abcdefghxyz";
combinations(string);
}
typedef struct node Node;
struct node {
Node * next;
};
bool is_cyclic(Node * list)
{
if(!list || !list->next) return false;
if(list->next == list) return true; // one element list pointed to himself
Node * first = list;
Node * second = list->next->next;
bool result = false;
while(second) {
if(first == second) {
result = true;
break;
}
first = first->next;
if(second->next == 0) { break; }
second = second->next->next;
}
return result;
}
Jimmy Jose, your method are not efficient at all.
Equation F(n) = F(n - 1) + F(n - 2) - looks pretty much like recursion, but in this case you shouldn't use recursion. That's the whole point.
int fibonacci(int N)
{
int first = 0;
int second = 1;
if(N <= 1) { return first; }
int i = 1;
int current = second;
while(++i < N) {
current = first + second;
first = second;
second = current;
}
return current;
}
I've sent this:
int uniques(int * arr, int size)
{
if(size < 3) return size;
int i = 0;
int j = i + 1;
short do_swap = 0;
while(j < size) {
if(do_swap) {
if(arr[i] == arr[j]) {
j++;
} else if(arr[i] != arr[j]) {
i++;
// swap
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
j++;
}
} else {
if(arr[i] != arr[j]) {
i++;
j++;
} else {
do_swap = 1;
}
}
}
return (i + 1);
}
bool check_ip(char * IP)
{
//char IP[16] = "255.255.255.255";
if(strlen(IP) > 16)
return false;
char * range = strtok(IP, ".");
short c = 0;
while ((range != 0) && (c < 4)) {
if((strlen(range) <= 3) && (atoi(range) >= 0) && (atoi(range) <= 255)) ++c;
else break;
range = strtok(0, ".");
}
return (c == 4);
}
Heap principle will work:
For example:
LL: 0->1->2->3->4->5->6->7->8->9->10->11
Tree:
0 -> [1, 2]
1 -> [3, 4]
2 -> [5, 6]
3 -> [7, 8]
4 -> [9, 10]
5 -> [11]
6 -> X
typedef struct object Object;
struct object {
// THESE FIELDS ARE ALREADY DEFINED; YOU MAY NOT MODIFY THEM
Object* next_ptr; // Next object in list; NULL if end of list.
unsigned int ID; // unique identifier for this object.
unsigned int parent_ID; // 0, if object is root of tree.
// THESE FIELDS REPRESENT THE TREE WHICH NEED TO BE FILLED
Object* parent_ptr; // Initialized as NULL.
unsigned int child_count; // Initialized as 0.
Object** child_ptr_array; // Initialized as NULL.
};
void convert_list_to_tree_helper(Object * list_head, int skip)
{
int c = 0;
Object * first = list_head;
while((c++ != skip) && first) {
first = first->next_ptr;
}
if(!first) return;
Object * second = first->next_ptr;
if(!second) {
list_head->child_ptr_array = (Object **)malloc(sizeof(Object *));
list_head->child_ptr_array[0] = first;
first->parent_ptr = list_head;
list_head->child_count = 1;
return;
}
list_head->child_ptr_array = (Object **)malloc(sizeof(Object *) * 2);
first->parent_ptr = list_head;
second->parent_ptr = list_head;
list_head->child_ptr_array[0] = first;
list_head->child_ptr_array[1] = second;
list_head->child_count = 2;
convert_list_to_tree_helper(first, 2*skip);
convert_list_to_tree_helper(second, 2*skip + 1);
}
Object * convert_list_to_tree(Object * list_head)
{
convert_list_to_tree_helper(list_head, 1);
return list_head;
}
typedef struct btreenode
{
char name;
btreenode * left;
btreenode * right;
};
btreenode * CreateBinaryTree(char * preorder, char * inorder, int length)
{
if(length == 0) {
return 0;
}
btreenode * root = new btreenode();
root->left = 0;
root->right = 0;
root->name = preorder[0];
if(length == 1) {
return root;
}
char left_preorder[length];
char right_preorder[length];
char left_inorder[length];
char right_inorder[length];
int l = 0;
do {
left_preorder[l] = preorder[l + 1];
left_inorder[l] = inorder[l];
++l;
} while(inorder[l] != preorder[0]);
++l;
int r = 0;
do {
right_preorder[r] = preorder[l + r];
right_inorder[r] = inorder[l + r];
++r;
} while(l + r <= length);
root->left = (l > 0) ? CreateBinaryTree(left_preorder, left_inorder, l - 1) : 0;
root->right = (r > 0) ? CreateBinaryTree(right_preorder, right_inorder, r - 1) : 0;
return root;
}
/* strtok example */
#include <stdio.h>
#include <string.h>
int main ()
{
char str[] ="- This, a sample string.";
char * pch;
printf ("Splitting string \"%s\" into tokens:\n",str);
pch = strtok (str," ,.-");
while (pch != NULL)
{
printf ("%s\n",pch);
pch = strtok (NULL, " ,.-");
}
return 0;
}
Output:
Splitting string "- This, a sample string." into tokens:
This
a
sample
string
Processes are independent execution units that contain their own state information, use their own address spaces, and only interact with each other via interprocess communication mechanisms.
A single process might contains multiple threads; all threads within a process share the same state and same memory space, and can communicate with each other directly, because they share the same variables.
Postorder traversal + Stack.
For example you have tree:
+
+ 4
1 *
2 3
Postorder traversal will be 123*+4+
For each postorder traversal nodes call funtion calculate_expression();
calculate_expression(Node * node, Stack * stack) {
char data = node.data;
if(Node is number) {
stack.push(data)
} else {
if(data == '+') {
stack.push(stack.pop() + stack.pop());
} else if (data == '*') {
stack.push(stack.pop() * stack.pop());
}
// ... u can add other operations like '-', '/', etc
}
}
Everything is wrong!
> construct the BST with larger array
> and search the elements in the smaller
> array in BST, if found print or store
> those numbers which are nothing but insersection.
Construct BST with the smaller array would be more efficiently from the point of memory view
> arrays a[m],b[n] with m>n
> constructing BST for 'a' would take O(log m)
Construct BST from array will take O(m).
Imagine you have array 1,2,3,4,5,....,N-1 => BST with root at 1 will look like one branch tree. So, to insert Nth element you should iterate from 1 to N-1.
To find an element in BST take O(n) in worth case. Binary Search Tree and Binary search is not the same.
I would suggest use hash, or sort smaller and then binary search.
char * get_letters(unsigned short n)
{
switch(n) {
case 1: return "AB"; break;
case 2: return "CDE"; break;
case 3: return "FGH"; break;
case 4: return "IJK"; break;
case 5: return "LM"; break;
case 6: return "NO"; break;
case 7: return "PQ"; break;
case 8: return "UV"; break;
case 9: return "WX"; break;
case 0: return "YZ"; break;
default: return "";
}
}
void print_letters_helper(const char * phone, char * letter_phone, unsigned short index, unsigned short length)
{
if(index >= length) {
printf("%s\n", letter_phone);
return;
}
char * letters = get_letters(phone[index] - '0');
short letter_phone_length = strlen(letter_phone);
for(short i = 0; i < strlen(letters); i++) {
char * tmp_letter_phone = (char *)malloc(sizeof(char) * (letter_phone_length + 1));
sprintf(tmp_letter_phone, "%s%c", letter_phone, letters[i]);
print_letters_helper(phone, tmp_letter_phone, index + 1, length);
}
}
void print_letters(const char * phone)
{
print_letters_helper(phone, "", 0, strlen(phone));
}
int main()
{
print_letters("1234567");
}
char * get_letters(unsigned short n)
{
switch(n) {
case 1: return "AB"; break;
case 2: return "CDE"; break;
case 3: return "FGH"; break;
case 4: return "IJK"; break;
case 5: return "LM"; break;
case 6: return "NO"; break;
case 7: return "PQ"; break;
case 8: return "UV"; break;
case 9: return "WX"; break;
case 0: return "YZ"; break;
default: return "";
}
}
void print_letters_helper(const char * phone, char * letter_phone, unsigned short index, unsigned short length)
{
if(index >= length) {
printf("%s\n", letter_phone);
return;
}
char * letters = get_letters(phone[index] - '0');
short letter_phone_length = strlen(letter_phone);
for(short i = 0; i < strlen(letters); i++) {
char * tmp_letter_phone = (char *)malloc(sizeof(char) * (letter_phone_length + 1));
sprintf(tmp_letter_phone, "%s%c", letter_phone, letters[i]);
print_letters_helper(phone, tmp_letter_phone, index + 1, length);
}
}
void print_letters(const char * phone)
{
print_letters_helper(phone, "", 0, strlen(phone));
}
int main()
{
print_letters("1234567");
}
1. Dictionary principle
For the smaller file create tries tree.
Than for each username from bigger file check the tries tree which will take O(1).
If username contain only 26 alphabets characters and not longer than 10 than tree is going to have 26^10 nodes.
But for longer usernames and not only alphabets it might be not the best solution.
or
2. Use hash
Create BigHash
For example:
hash1: key1 = MD5(phone); value = "A: address"
hash1: key2 = MD5(name); value = "K: key1"
hash2: key3 = MD5(accountID); value = "K: key1"
...
BigHash := hash1 + hash2 + hash3 + ...
Lets say you are looking by PARAMETER (phone, name, accountID, etc...):
char * address = BigHash.getvalue(PARAMETER);
if(address starts with A) then remove "A: " and print address
else remove "K: " from address and look again
address = BigHash.getvalue(address);
Using parentheses:
A(B(D,E),C(F(,G(H(K,L),)),))
For small trees which nodes can be presented as ansichar (1byte) (below), for bigger trees should use hashmap for nodes and extend string reading algorithm
1.
typedef struct node Node;
struct node {
char data;
Node * left;
Node * right;
}
typedef struct tree Tree;
struct tree {
Node * root;
}
2.
void print_tree(Node * node)
{
printf(node->data);
if(node->left || node->right) {
printf("(");
if(node->left) {
print_tree(node->left);
}
printf(",");
if(node->right) {
print_tree(node->right);
}
printf(")");
}
}
// print to file
print_tree(tree->root); // A(B(D,E),C(F(,G(H(K,L),)),))
3.
// A(B(D,E),C(F(,G(H(K,L),)),))
void read_tree(const char * string)
{
int str_length = strlen(string);
if(str_length == 0) { return; } // empty tree
Node * parent_node = create_node(string[0]); // root
if(string[1] == '(') {
read_tree_helper(parent_node, string, 2);
}
}
void read_tree_helper(Node * parent_node, const char * string, unsigned int index, int str_length)
{
if(index >= str_length) { return; }
if(string[index] != ',') {
parent_node->left = create_node(string[index + 1]);
if((string[index + 2] == ',') && (string[index + 3] != ')')) {
parent_node->right = create_node(string[index + 3]);
if(string[index + 4] == '(') {
read_tree_helper(parent_node->right, string, index + 5, str_length);
}
} else {
if(string[index + 2] == '(') {
read_tree_helper(parent_node->left, string, index + 3, str_length);
}
}
}
}
RepEvieBBlack, AT&T Customer service email at ASAPInfosystemsPvtLtd
I am Evie from Santa Fe Springs USA, I am working as a manager in a worldwide company. I also ...
No difference, but there are difference between static function in C and method in C++
- zdmytriv March 15, 2008