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

Big O of fixed size array linear search
const a = Array.apply(null, Array(50)).map((x, i) => i);
This array will never be changed, it will always contain 50 elements.
Would
a.includes(x)
(linear search) be O(n) OR O(50) OR technically O(50) but we call is O(n) 
Hungarian Algorithm what to do when some 'jobs' are unavailable to certain workers?
In my program, there will be students (from multiple year groups/grades) submitting choices for activities running from Monday to Friday.
Each activity may be applicable to one, or multiple year groups. Each student has say 4 choices (1st, 2nd, 3rd and 4th) per day. This is being stored in each student object as int[][] studentCosts which will be
studentCosts=new int[5][4]
.I have finished my hungarian algorithm but I need to decide how to add all the students' choices to an int[][].
I will be executing the algorithm separately for each day, so I will need to collate all the students' choices for that particular day into an int[][] costsForThatDay.
My problem is with how some year groups may be offered certain activities which are not offered to others, for example, on Monday, Year 7 are offered Windsurfing on Monday, whereas Years 8 and 9 are offered Golf on Monday.
If I were to execute the algorithm by day would it be best to set the 'costs' for unavailable activities to something like
Integer.MAX_VALUE
to make sure there is absolutely no way it will ever be chosen? E.g. Make Golf 'cost' for year 7 students and Windsurfing 'cost' for year 8 and 9 studentsInteger.MAX_VALUE

Longest Substring Without Repeating Characters
I have been spending hours on Longest Substring Without Repeating Characters  LeetCode
 Longest Substring Without Repeating Characters
Medium
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
The problem could be solved using two pointer mixed kadane's algorithms to manipulate subarray
class Solution: def lengthOfLongestSubstring(self, s: str) > int: logging.debug(f"{list(enumerate(s))}") slo = fas = 0 #slow as the fisrt character in a subarray which not duplicate, fast as the fast. #relation: length = fas  slo current = set() glo = loc = 0 while fas < len(s): logging.debug(f"pre_current: {current}, slow: {slo}, fast: {fas}") if s[fas] not in current: current.add(s[fas] loc = fas  slo glo = max(glo, loc) fas +=1 else: current.remove(s[slo]) slo += 1 logging.debug(f"post_current: {current}, slow: {slo}, fast: {fas} \n") return glo
TestCase
def test_g(self): s = "abccefg" answer = 4 check = self.solution.lengthOfLongestSubstring(s) self.assertEqual(answer, check)
The solution is very clear to move slow and fast alternatively
$ python 3.LongestSubstring.py MyCase.test_g DEBUG [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'c'), (4, 'e'), (5, 'f'), (6, 'g')] DEBUG pre_current: set(), slow: 0, fast: 0 DEBUG post_current: {'a'}, slow: 0, fast: 1 DEBUG pre_current: {'a'}, slow: 0, fast: 1 DEBUG post_current: {'b', 'a'}, slow: 0, fast: 2 DEBUG pre_current: {'b', 'a'}, slow: 0, fast: 2 DEBUG post_current: {'b', 'c', 'a'}, slow: 0, fast: 3 DEBUG pre_current: {'b', 'c', 'a'}, slow: 0, fast: 3 DEBUG post_current: {'b', 'c'}, slow: 1, fast: 3 DEBUG pre_current: {'b', 'c'}, slow: 1, fast: 3 DEBUG post_current: {'c'}, slow: 2, fast: 3 DEBUG pre_current: {'c'}, slow: 2, fast: 3 DEBUG post_current: set(), slow: 3, fast: 3 DEBUG pre_current: set(), slow: 3, fast: 3 DEBUG post_current: {'c'}, slow: 3, fast: 4 DEBUG pre_current: {'c'}, slow: 3, fast: 4 DEBUG post_current: {'c', 'e'}, slow: 3, fast: 5 DEBUG pre_current: {'c', 'e'}, slow: 3, fast: 5 DEBUG post_current: {'e', 'f', 'c'}, slow: 3, fast: 6 DEBUG pre_current: {'e', 'f', 'c'}, slow: 3, fast: 6 DEBUG post_current: {'g', 'e', 'f', 'c'}, slow: 3, fast: 7 .  Ran 1 test in 0.001s
As a conclusion, the solution employed two pointer technique and the idea of the Kadane algorithms. I assumed that it is possible to finally work it out after spending hours on debugging as a beginner.
However, I read such a delicate solution
class SolutionA: def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ #slow is the first which not duplicate in a subarray #fast is the last whichi not duplicate in a subarray lookup, glo, slo, fas = {}, 0, 0, 0 for fas, ch in enumerate(s): if ch in lookup: slo = max(slo, lookup[ch]+1) elif ch not in lookup: glo = max(glo, fasslo+1) lookup[ch] = fas #update the duplicates and add new return glo
The solution is very smart, I honestly don't believe one could design such a solution in hours if one did not read it before.
It used hash map , two times of kadane's algorithms idea and very concise structure.
Is it a common technique as two pointers? what's the name of it

What to do when converting infix to postfix expression using stack?
Problem I am facing is that what to do when two operators of same priorities are their? Example: If ^ is in the top of stack and ^ comes that what to do? Should I enter it in stack or just pop out one ^ or both ^ comes out of the stack?

Can XML be used effectively to create a schema from data to parse it with?
Note I currently program in C though as time permits I will learn another language.
Often I get a database of text/line encoded information that is far too large to model the format of by hand. There could be millions of lines so there is no way to see it all and understand the structure.
What I've started to do is a first pass preprocess and then begin to break out structures with XML tags. As a simplified example if you were looking at a dump of enrolled students in a school you might notice a change that delineates the group "grade" and one that delineates "class".
What I've started to try to do is translate the data into XML and then use a tool to create a schema and take a look at it. The next thing is to find sub patterns which can be used to develop the data structure model further, and this can be easy with regex searches.
I run into a problem; the schema generator may differentiate CLASS because it sees in one context only 11th grade students are enrolled and in another only freshmen. Then it fractures the CLASS as though there are unique variants when really they are functionally the same. This can vastly increase the complexity of the model.
In any data stream a few types of data are common. Structural/organizational, referential, markup/encoding, and raw content.
When the data is modeled and can be guaranteed to conform to a schema I can either stream parse it (with a stack perhaps?) Or parse it via functions that get called for each data structure. Stream parsing has suffered when the data is not ordered in a linear sequence. Functional parsing is perhaps the goal but I haven't used it much yet because I've been unable to codify structure.
The QUESTION: what would you recommend to improve on the method or what alternative method do you think is better?

What would be the output of each query operation?
Consider the social media network of N people represented by disjoint set. Following queries are performed on them. What will be output of each of them if N = 10 ?
M 2 8
Q (2)
M 3 9
Q (F (2))
M 1 6
U(F{3}, F(2})
M(F{2}, F{3})
M 5 4
QM(F{2}F{3})
QU(F{3},F{2})
Where M indicates Merging operation U indicates Union operation Q indicates printing F indicates find set
I am not getting how to answer this question What is the difference between the Merge and Union operations? Also what would be the output of Find? What would the Q operation print? Please can anyone solve this question

Implement a Binary Tree using array
in HW i am asked to implement a Binary Tree using pointers and then using the array implementation of bt. The problem is that while i know how to do both , they have to share the same main file . By that i mean , the exact same code i used for the pointers implementation is to be used by the array implementation. This means that when i am refercing to insertTree(tree,tree>left) must works for the array also .i am totally lost. My node is:
Typedef struct BTNode{ itemtype data; Struct BTNode * left; Struct BTNode * left; }BTNode;

Trying to use getInorderIterator but its not printing my tree InOrder
I created a binary search tree and I am able to add and remove to it but when i try to use the getInorderIterator method and print the tree it prints "TreePackage.BinaryTree$InorderIterator@2e817b38"
maybe im just calling the method the wrong way?
This is how i print it in my main class:
System.out.println("Inorder: " + tree.getInorderIterator());
this is my implementation of getInorderIterator():
public Iterator<T> getInorderIterator() { return new InorderIterator(); } private class InorderIterator implements Iterator<T> { private StackInterface<BinaryNode<T>> nodeStack; private BinaryNode<T> currentNode; public InorderIterator() { nodeStack = new LinkedStack<>(); currentNode = root; } public boolean hasNext() { return !nodeStack.isEmpty()  (currentNode != null); } public T next() { BinaryNode<T> nextNode = null; while (currentNode != null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } if (!nodeStack.isEmpty()) { nextNode = nodeStack.pop(); assert nextNode != null; currentNode = nextNode.getRightChild(); } else throw new NoSuchElementException(); return nextNode.getData(); } public void remove() { throw new UnsupportedOperationException(); } }

How many nodes and how many leaves does a tree have?
How many nodes and how many leaves does a tree have the height h of degree y at least? How many nodes does it have at the most?
I tried to solve the question.
max number of nodes = (degree )^high + degree + 1
min number of leaves = degree
Is my solution right?

How to print the maximum sum subsequence of an array with non adjacent elements?
I've the code to find the maximum sum that can be formed with non adjacent elements of an array. How to print the elements that contributed to the sum?
def find_max_sum(arr): incl = 0 excl = 0 for i in range(len(arr)): if excl>incl: new_excl = excl else: new_excl = incl incl = excl + arr[i] excl = new_excl return (excl if excl>incl else incl)

Large Number Multiplication With Arrays
I am writing a function that will take two integers and insert them in to a character array and do multiplication on them. The idea behind is that I can take numbers and multiply them to get a result larger than 64bits. I understand that there are tons of other ways of doing this but I want to do it this way.
I am able to successfully multiply any number by a number that is of single digit i.e.
366 * 9 = 3294
However, when I do do something like
10 * 10
I get the result
10
I think this is because that I do not handle the case of properly adding the numbers together into the result array to make it a three digit number. Below is my code.
int multiply(digit *res, digit *a, int m, digit *b, int n) { // 'a' and 'b' are my numbers to add // 'm' and 'n' are the respective lengths of 'a' and 'b' int i, j, max, low; // i is the length of the sum`1 digit ad, bd, mult, carry; if (m > n) { max = m; low = n; } else { max = n; low = m; } carry = 0; for (i = 0; i < low; i++) { for (j = 0; j < max; j++) { if (j >= m) ad = 0; else ad = a[j]; if (i >= n) bd = 0; else bd = b[i]; mult = (ad * bd) + carry; if (mult < 10) carry = 0; if (mult > 10) { carry = mult / 10; mult = mult % 10; } res[j] = mult; } } if (carry != 0) { res[j] = carry; j++; } return j; }
Does anyone have suggestions on how to handle this case upon adding into the result array? Below I have code as well that works for adding any size numbers numbers together
int add(digit *res, digit *a, int m, digit *b, int n) { // 'a' and 'b' are my numbers to add // 'm' and 'n' are the respective lengths of 'a' and 'b' int i, max; // i is the length of the sum`1 digit ad, bd, sum, carry; if (m > n) { max = m; } else { max = n; } carry = 0; for (i = 0; i < max; i++) { if (i >= m) ad = 0; else ad = a[i]; if (i >= n) bd = 0; else bd = b[i]; sum = ad + bd + carry; // what is the biggest sum can be? if (sum >= 10) { sum = sum  10; carry = 1; } else carry = 0; res[i] = sum; } if (carry == 1) { res[i] = carry; i++; } return i; }

I need help troubleshooting my code for MergeSort and Merge
So I've been working on MergeSort for an Algorithm project, but I've ran into various problems when it comes to getting the code to sort the arrays. Whenever I generate a string and put it into MergeSort, it seems to just come out exactly the same. I want some help in finding where the mistake in my code is, why is it giving me this, and a solution with a simple, but good explanation.
Here's what I've tried in the past:
 I've tried to use return arr[0] instead of arr, but it throws me an error with it being unable to convert from int to int[].
 I've looked in my merge class and everything seems to be ok there.
 I've discussed the issue with my teacher and he says that everything looks fine, but I know that there must be something wrong somewhere.
 I've tried to remove return merge(arr1, arr2) but the system throws an error telling me I have to return something.
 I've tried to print out the arrays individually, but it still shows no changes and is the exact same as the original string.
Merge method:
private static int[] merge(int[] a, int[] b) { int[] c = new int[a.length + b.length]; int counterA = 0; int counterB = 0; int counterC = 0; while(counterA != a.length && counterB != b.length) { if(a[counterA] < b[counterB]) { c[counterC] = a[counterA]; counterA++; counterC++; } else { c[counterC] = b[counterB]; counterB++; counterC++; } } while(counterB == b.length && counterA != a.length) { c[counterC] = a[counterA]; counterA++; counterC++; } while(counterA == a.length && counterB != b.length) { c[counterC] = b[counterB]; counterB++; counterC++; } return c; }
MergeSort method:
public static int[] mergeSort(int[] arr) { if(arr.length == 1) { return arr[0]; } int[] arr1 = new int[arr.length / 2]; int[] arr2 = new int[arr.length  arr1.length]; for(int i = 0; i < arr1.length; i++) { arr1[i] = arr[i]; } for(int i = 0; i < arr2.length; i++) { arr2[i] = arr[i + arr1.length]; } arr1 = mergeSort(arr1); arr2 = mergeSort(arr2); return merge(arr1, arr2); }
Because the array is randomly generated, an example would be this: 9, 1, 7, 5, 7, 2, 2, 9, 8, 9
The intended result should be this: 1, 2, 2, 5, 7, 7, 8, 9, 9, 9
However, this is what the output is instead: 9, 1, 7, 5, 7, 2, 2, 9, 8, 9 (The array comes out unchanged)