Assign inorder index to Binary Tree
How do we assign inorder index to binary tree?
Given a tree below:
1
2 3
4 5 6 7
Assign an index below to above tree as you can see below:
4
2 6
1 3 5 7
Following code does not work for case 6 as it assigns 10 as we are double counting passed down index from the argument and from the left child. Can we achieve this without using global variable?
int assignIndex(Node root, int index) {
if (root == null)
return 0;
int leftIndex = assignIndex(root.left, index);
root.index = leftIndex + index + 1;
int rightIndex = assignIndex(root.right, root.index);
if (rightIndex == 0)
return root.index;
else
return rightIndex;
}
1 answer

The problem in the above program is return of two different values at two different occasions. So the issue can be solved by returning only latest index values at all occasions if you don't want to use global variables.
int assignIndex(Node root, int index) { if (root.left != null) index = assignIndex(root.left, index); index++; root.index = index; if (root.right != null) index = assignIndex(root.right, index); return index; }
See also questions close to this topic

App uses weak Hash algorithm
After sending my app to automation testing we got an issue saying
"App uses weak Hash algorithm"
in a particular utility class in the java class.
Got some link but still didnt get any solution for the issue
https://github.com/italia/cieideaapp/issues/4
Thank you.

Given two arrays A and Q, foreach element of of Q, find the element in A with smallest difference
Given 2 unsorted array A and Q of differing length. For each element in Q, find a element in A that has the smallest differences.
int[] findSmallestDifference(int A[], int Q[]){ int []result = new int[Q.length]; // insert code to find difference for each Q return result; }
I encountered this problem during a interview, which I provided a couple of solution, but it was mentioned that it wasn't optimal yet.
Solutions I provided:
 Brute force: foreach A, foreach Q compute difference, O(A*Q)
 Sort Array A, foreach element of Q, perform binary search to find smallest difference, O(AlogA + QlogA)
 Sort both A and Q, then we have two pointer on each array to find difference, O(AlogA + QlogQ)
What is the optimal solution that I haven't thought of?

generate all key of DES
I want generate all key of DES cryptography algorithm(2^56), but don't know how can do that.
I have a algorithm that generate truth table(in C++), but this algorithm can generate small truth table.
you can see this algorithm :
#include <iostream> #include <vector> #include <math.h> int main() { const unsigned n = 3; long long size = pow(2, n); std::vector<std::vector<long long> > output(n, std::vector<long long>(size)); unsigned num_to_fill = 1U << (n  1); for (unsigned col = 0; col < n; ++col, num_to_fill >>= 1U) { for (unsigned row = num_to_fill; row < (1U << n); row += (num_to_fill * 2)) { std::fill_n(&output[col][row], num_to_fill, 1); } } // These loops just print out the results, nothing more. for (unsigned x = 0; x < (1 << n); ++x) { for (unsigned y = 0; y < n; ++y) { std::cout << output[y][x] << " "; } std::cout << std::endl; } return 0; }
I don't say this algorithm is ok, and also I need a help you for do that, me by you have best algorithm

Changing data structure in R
I am currently having the following data structure (as data.frame)
NA a1 a2 a3
t1 y11 y21 y31
t2 y12 y22 y33
t3 y13 y23 y33and want to change it into
t1 s1 y11
t2 s1 y12
t3 s1 y13
t1 s2 y21
t2 s2 y22
t3 s2 y23
t1 s3 y31
t2 s3 y32
t3 s3 y33any suggestion how to proceed? Thanks for your help ;)

itinerary: making double array String into a Map of String, String (Key & Value)
I have a
String[][]
. So it basically looks like this:{ { "Dublin", "NYC"}, { "Moscow", "LosAngeles"}, { "London", "Paris" } }
And I have to add them to
Map
, so that Keys will be first column(Dublin, Moscow, London), and Values will be second (NYC, LA, Paris)Can you please help, I don't know where to start

Reading a text file line by line into a structure in c
I am kind of new to c programming but I want to create a c function that can read contents of a text file line by line separated by the tab delimiter(\t) and store them into a data structure, then after clear the file but have still failed. My code is
struct Busy_list{ int client_socket; char JOB[1024]; int characters; int No_jobs; int IsReplace; int Priority; }; char** PriorityEvaluator(int client_socket){ struct Busy_list Array; FILE *Ufptr; Ufptr = fopen("Unsorted_busy_list.txt","r+"); for(int i;!EOF;i++){ fscanf(Ufptr, "%d\t%s\t%d\t%d\t%d\n",&Array.client_socket,&Array.JOB,&Array.characters,&Array.No_jobs,&Array.IsReplace); } fclose(Ufptr); }
My Unsorted_busy_list file contains
/* 4 double fish 4 1 0 5 double praise 6 2 0 5 replace peter 2o,4o 5 2 1 */

Binary Tree pointer confusion
I am making a basic binary search tree. One of my methods is called insert, and is defined in a header file (since it is a templated class, I have to include both the implementation and the declaration in the same place). This is what the code looks like, with all irrelevant methods removed.
#ifndef __B_TREE__ #define __B_TREE__ #include <iostream> #include <deque> template<class obj> class b_tree { private: class tree_node { public: obj val; tree_node* left = nullptr; tree_node* right = nullptr; tree_node(obj _val) { val = _val; } }; tree_node* head = nullptr; void insert(obj add, tree_node* curnode) { if(curnode == nullptr) { curnode = new tree_node(add); return; } if(add > curnode>val) { insert(add, curnode>right); return; } if(add <= curnode>val) { insert(add, curnode>left); return; } } public: void insert(obj add) { std::cout << "\nPassing in value " << add; if(this>head == nullptr) { std::cout << "\nhead is nullptr"; } insert(add, this>head); } }; #endif // __B_TREE__
This is what the main looks like:
#include <iostream> #include "b_tree.hpp" using namespace std; int main() { b_tree<int> tree; for(int a = 0; a<10; a++) { tree.insert(a); } }
However, when I run this, even after it changes head from nullptr into a pointer to a new tree_node, it still keeps it as a nullptr. It does this only once the insert() function is over, as if I test to see if it is a nullptr in the ifbranch that sets it to a new tree_node, it returns that it is successfully a tree_node. However when I run insert from main a second time, it reads head as a nullptr again, even though I just set it to be a new tree_node in the last iteration of the for loop. Basically, If I were to run this, I get as output:
Passing in value 0 head is nullptr Passing in value 1 head is nullptr Passing in value 2 head is nullptr Passing in value 3 head is nullptr Passing in value 4 head is nullptr Passing in value 5 head is nullptr Passing in value 6 head is nullptr Passing in value 7 head is nullptr Passing in value 8 head is nullptr Passing in value 9 head is nullptr
Can anyone help me? Thanks.

Is using hashtable a good DS if you need data in sorted order?
Fairly new to programming world and wondering if using hashtable a good DS if you need data in sorted array?

c++ Why is my else statement not executing
I'm doing past papers for an upcoming exam and I'm trying to write a function to delete the minimum value from a BST, however, whenever I reach the case where my BST size is 2, and the minimum value is at the root, an else statement which should execute is not(Indicated in the code comments).
template<class T> inline void BST<T>::deleteMin(){ if(parent == nullptr && count == 0)// empty tree return; BST<T> *smallest = getMin();// get the minimum value in the tree BST<T> *smallestParent = smallest>parent;// get the minimum value's parent, for linking up stray nodes BST<T> *replacement = smallest>getInOrderSuccessor();// replace the smallest with inorder successor if exits if(!smallest>isLeaf()){// the smallest value cannot have a left subtree, but it can have a right subtree if(replacement != nullptr){ if(!replacement>isLeaf()){ if(replacement>parent>left == replacement) replacement>parent>left = replacement>right; else replacement>parent>right = replacement>right; replacement>right>parent = replacement>parent; replacement>right = nullptr; } else if(replacement>parent>left == replacement){ replacement>parent>left = nullptr; } else{// THIS IS NOT EXECUTING replacement>parent>right == nullptr; } } smallest>data = replacement>data; delete replacement; return; } else if(!smallest>isRoot()){ smallest>parent>left = nullptr; } delete smallest; smallest = nullptr; }
The main program looks as follows: #include "BST.h"
int main(){ BST<int> bst; bst.insert(15); bst.insert(16); unsigned int count = bst.size(); for(unsigned int i = 0; i < count; i++){ bst.deleteMin(); } return 0; }
Other functions used by the deleteMin() function:
template<class T> inline BST<T>* BST<T>::getMin(){ if(left != nullptr) return left>getMin(); return this; } template<class T> inline bool BST<T>::isLeaf(){ return left == NULL && right == nullptr; } template<class T> inline BST<T>* BST<T>::getInOrderSuccessor(){ if(right != nullptr){ return right>getMin(); } else{// have to find it by going through the parent BST<T> *curr = this; while(curr>parent != nullptr){ if(curr>parent>left == curr) return curr>parent; curr = parent; } return nullptr; } }
Can someone shed some light into why that else statement is always being skipped. I'm using visual studio enterprise 2017.

Given an array of integers, find the first missing positive integer in linear time and constant space
In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well. This question was asked by Stripe in it's programming interview. I have devised a solution for the same as below:
#include<bits/stdc++.h> using namespace std; int main(){ int arr[]={1,1,5,3,3,4,2,8}; int size= sizeof(arr)/sizeof(arr[0]); sort(arr, arr+size); int min=1; for(int i=0; i<size; i++){ if(arr[i]>min) break; if(arr[i]==min) min=min+1; } cout<<min; return 0; }
Here, I am first sorting the array, and then traversing the array once. Before traversing the array, I have initialized a variable named "min" as 1. Now, while traversing the array, when we get an integer that is equal to min, we simply increment the value of min. This ensures that the min variable hold the latest least positive integer that has not occurred yet. Can you think of any better approach? Thanks in advance.

Range and update queries
Given an array there are two types of queries :
1) Add index*(given_val) to each array element where index is the index of the element of array
2) Find the minimum over a range
Example :
Array : 1 3 4 Type 1 query : 5 New array : 6 13 19 Type 2 query : ans = 6
I am not able to figure out a way to do the above thing in efficient time .

Please describe this JavaScript functional representation
https://leetcode.com/problems/transposematrix/discuss/147063/JSonelinesolution
/** * @param {number[][]} A * @return {number[][]} */ var transpose = function(A) { return A[0].map((val, ind) => A.map(row => row[ind])); };
I can hardly understand part
A[0].map((val, ind) => A.map(row => row[ind]))
.I think
A[0].map((val, ind)
is the purpose of extracting the index.But I do not know about
=> A.map(row => row[ind])
. Map methods and arrow functions are intertwined, making it difficult to understand.Could you explain it to me in an easy to understand way?