I did this for 5 months in a class I just completed. I recently finished a B-Tree from scratch in java that would read / write to disk based on block size, took over 100 hours.

Well I can't use AVL anyways, since when I have to extend the characters (the nodes), the BST gets out of ordered

For example



The window slides and adds "e" as a character. Now the bst is out of order.

I'm sure you went down the same Wikipedia hole that I did as I researched this but did you happen to see this?

https://en.m.wikipedia.org/wiki/Dete...tate_automaton

I don't know if it's useful for you but thought I'd share.

Oh nice thanks! I have seen the term but never looked into it. I'll look this over.

Thanks again for this. Extremely useful!

There are rules you have to use. They are usually called "right rotation" and "left rotation." Left and Right rotations both have 2 cases: 1 general case and 1 specific case involving the .... balance? of the node .... (its found by doing height(leftChild) - height(rightChild) iirc ). I dont have my class notes in front of me but the specific case for left rotation is something like "if doing left rotation on node, if node ballance is -2 and node.leftChild balance is -1, first do right rotation on node.leftChild, then left rotation on node)

If you have to change a node, you can still use a binary tree with AVL as long as you remove node -> change node -> re-add node. This should take 2*log(n) iirc

You did the triple byte test? Their algorithm test section was difficult, or just the whole test?

In my diagram, I forgot to include the inserted node "e".

Ryanb9,

I understand the rotations, but that only occurs after either a deletion or insertion. Since that is the only time when the tree could become "unbalanced". In my example, the balance factor isn't the concern, it is the changing of the values that violates how "ce" will not be searched.

You start at the root, and since we are looking for "ce", we would go to the right since (ce is lexicographically after cde). But "ce" is actually on the left of the root. The integrity of the tree is now gone.

I did it a few months ago. No, you will not do well on it if you have random background. I got past the algorithm test fine. The final project section was the part that stuck me hard. The project is a combination of design and algorithms.

It was probably more to do with the time down and the fact I forgot how to deal with what the project called for. Nothing too esoteric if you read Corman, but not simple stuff to pull out on a moment's notice. It required squaring the matrix, which I know is all over the web now, so I'm guessing they changed it... then again, maybe not since all the answers I found were laughably wrong and seriously slow.

Still, you cant change a value that is in a b tree and expect it to be a valid btree. If you want to change something you have to remove it, change it, and re-insert it. Maybe someone has come up with a good algorithm for changing a value in a btree that is faster than 2*log(n) but I dont know of it.

Barrin, not sure if this insight helps, but regex are finite automata, which is why they are so fast.

Only problem is that I would have to change every node. So doing that would be O(nlgn) in that case since I'll be reinserting everything. So any type of tree would not be useful in my case.

The DAFSA that just_grindin linked is looking more promising in terms of what I might need.

Ah didn't know that. Too bad I can't use regex in this case!

What do you call the ending string of a youtube video link? The part that comes after the "="?

https://www.youtube.com/watch?v=C0DPdy98e4c

Is there a name for this?

the video ID afaik

Thanks.


If I'm making a portfolio website to include on my resume for potential employers to view, should I bother with making it functional in Internet Explorer? Currently I think 6.8% of users use IE, but I would guess that 0% of potential employers would be looking at my website in IE. It looks great in firefox and chrome, looks like **** in IE currently.

So I heard an interesting variation on an interview question today. The interviewer asks "what's an interesting algorithm you remember from CS, your recent work, something you heard about etc" with the obvious followup being "explain how it works"

The good is that obviously you get to pick something that you know something about, but also it needs to be non-trivial and you need to be able to nail it, because *you* chose it.

Bad news, friend: guess what browser HR types are likely to use. >.>

+1 and it's likely to be an older version.

everything after the "?" is called the query string. it consists of keys and values.

in the example above, "v" is the query string key and the value is "C0DPdy98e4c". if there was an addtional pair it would be preceded by "&":

if you're asking if youtube specifically has a name for the key "v", i think noodle's guess is probably right.

Well, what was it?

My favorite isn't really an algorithm, but it always blows my mind:

The number of ways to select n donuts when k flavors are available is the same as the number of length-n binary sequences with k - 1 ones.


Explanation (copy / paste, sry):

The most direct way to count one thing by counting another is to find a bijection
between them, since if there is a bijection between two sets, then the sets have the
same size. This important fact is commonly known as the Bijection Rule.

The Bijection Rule acts as a magnifier of counting ability; if you figure out the size
of one set, then you can immediately determine the sizes of many other sets via
bijections. Consider

A = all ways to select a dozen donuts when five varieties are available
B = all 16-bit sequences with exactly 4 ones

An example of an element of set A (donuts) is:
00 -- chocolate filled
__ -- lemon filled
0 0 0 0 0 0 -- sugar
00 -- glazed
00 -- plain

Here, we’ve depicted each donut with a 0 and left a gap between the different
varieties. Thus, the selection above contains two chocolate donuts, no lemon-filled,
six sugar, two glazed, and two plain. Now let’s put a 1 into each of the four gaps:

00 -- chocolate filled
1
__ -- lemon filled
1
0 0 0 0 0 0 -- sugar
1
00 -- glazed
1
00 -- plain

-- and close up the gaps:
0011000000100100 :

We’ve just formed a 16-bit number with exactly 4 ones —an element of B!

Not knowing the size of either set, you can map one set to the other to figure it out.

He's a witch!

The marching cubes algorithm for turning a 3d field of floats into a 3d skin

That hurts my brain, thanks.

Few good articles on HN today:

For those beginners among us feeling heavy with imposter syndrome
https://news.ycombinator.com/item?id=11791284

For the more experienced and/or managers among us
https://news.ycombinator.com/item?id=11791444
(Still a good one for newbs to know what to keep an eye out for re: culture)

Noodle, in my experience, imposter syndrome lasts about 5 minutes. Before you can dwell on it, you have a world of stuff to do. Focusing on the task sort of interrupts those feelings.