Open Side Menu Go to the Top

05-27-2016 , 03:48 PM
Quote:
Originally Posted by Barrin6
Any of you guys ever have to go research a particular data structure and then have to code it up from scratch?

Usually I am pretty good at looking at psueocode and converting it to real code. But man I think I finally hit the wall with suffix trees. I understand what suffix trees are, but the O(n) ukkonen's method for constructing it, is such a hard thing to wrap my head around. I have read a few stackoverflow posts explaining it, and also research papers but my head still hurts.
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **
150% up to $2,000 Welcome Bonus on CoinPoker
Join the action now
Daily Rewards • Splash Pots • CoinRaces
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **
05-27-2016 , 03:56 PM
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 04:11 PM
Quote:
Originally Posted by Barrin6
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 04:30 PM
Quote:
Originally Posted by just_grindin
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 04:31 PM
Quote:
Originally Posted by ChrisV
He's correct though that the "industry standard" solution to stuff like this is Bootstrap.

Say you have something like this:

Code:
<div class="container">
	<div class="floatingdiv">Floating Div</div>
	<div class="floatingdiv">Floating Div</div>
	<div class="floatingdiv">Floating Div</div>
	<div class="floatingdiv">Floating Div</div>
	<div class="floatingdiv">Floating Div</div>
	<div class="floatingdiv">Floating Div</div>
	<div class="floatingdiv">Floating Div</div>
	<div class="floatingdiv">Floating Div</div>
</div>
If you just want the container horizontally centered and fluid there are many ways of doing that, most simply setting text-align: center on its parent and display: inline-block plus a max-width on the container. Float the items left inside the container.

The problem is that your items will be left-aligned inside the container, and therefore won't look centered on screen unless the container happens to be the width of x items. Making the items "floating, but centered" and thus achieving the "responsive grid" look you want is very difficult in pure CSS. You pretty much have to use the @media directive and resize the container at different screen widths. The difficulty of doing these sort of grid layouts is exactly why things like Bootstrap and Foundation exist.
Thanks again for this. Extremely useful!
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 04:34 PM
Quote:
Originally Posted by Barrin6
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.
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
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 05:38 PM
Quote:
Originally Posted by daveT
The blog post specifically mentions algorithms. FWIW, that test is the most difficult one I've ever done.
You did the triple byte test? Their algorithm test section was difficult, or just the whole test?
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 07:21 PM
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 07:25 PM
Quote:
Originally Posted by Noodle Wazlib
You did the triple byte test? Their algorithm test section was difficult, or just the whole test?
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 07:57 PM
Quote:
Originally Posted by Barrin6
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.
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 08:13 PM
Barrin, not sure if this insight helps, but regex are finite automata, which is why they are so fast.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 08:20 PM
Quote:
Originally Posted by Ryanb9
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.
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.

Quote:
Originally Posted by daveT
Barrin, not sure if this insight helps, but regex are finite automata, which is why they are so fast.
Ah didn't know that. Too bad I can't use regex in this case!
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 09:52 PM
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?
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 09:56 PM
the video ID afaik
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 11:02 PM
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-27-2016 , 11:23 PM
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.

Spoiler:

I chose a subset of the subject of his PhD research
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-28-2016 , 06:27 AM
Quote:
Originally Posted by Ryanb9
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.
Bad news, friend: guess what browser HR types are likely to use. >.>
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-28-2016 , 08:24 AM
Quote:
Originally Posted by Noodle Wazlib
Bad news, friend: guess what browser HR types are likely to use. >.>
+1 and it's likely to be an older version.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-28-2016 , 11:10 AM
Quote:
Originally Posted by Ryanb9
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?
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 "&":

Code:
https://www.youtube.com/watch?v=C0DPdy98e4c&some_other_key=blah
if you're asking if youtube specifically has a name for the key "v", i think noodle's guess is probably right.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-28-2016 , 01:59 PM
Quote:
Originally Posted by RustyBrooks
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.

Spoiler:

I chose a subset of the subject of his PhD research
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-28-2016 , 02:29 PM
He's a witch!
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-28-2016 , 03:24 PM
The marching cubes algorithm for turning a 3d field of floats into a 3d skin
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-28-2016 , 03:43 PM
That hurts my brain, thanks.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-28-2016 , 03:48 PM
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)
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
05-28-2016 , 04:17 PM
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.
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** Quote
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **
150% up to $2,000 Welcome Bonus on CoinPoker
Join the action now
Daily Rewards • Splash Pots • CoinRaces
** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

      
m