Two Plus Two Publishing LLC
Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > >

Notices

Programming Discussions about computer programming

Reply
 
Thread Tools Display Modes
Old 07-18-2018, 08:29 PM   #33826
well named
poorly undertitled
 
well named's Avatar
 
Join Date: Jun 2007
Location: esse est coesse
Posts: 76,043
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Code:
function findFirstRepeat(test) {
  const firstSeen = {};
  
  let candidatePosition = 99999999,
      updateCandidate,
      candidate = false;

  for (let i = 0; i < test.length; i++) {
    const c = test[i];
    updateCandidate = true;

    if (typeof firstSeen[c] === 'undefined') {
      firstSeen[c] = i;
      updateCandidate = false;
    }

    if (updateCandidate && firstSeen[c] < candidatePosition) {
      candidatePosition = firstSeen[c];
      candidate = c;
    }
  }
  
  return candidate
}

console.log(`earliest repeat: ${findFirstRepeat('hello everyone')}`);
Playing in Chrome scratchpad.
well named is offline   Reply With Quote
Old 07-18-2018, 08:39 PM   #33827
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 24,377
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by suzzer99 View Post
What kind of data structure could you use thatís like a hash map, but automatically sorted by creation order? You could do that, where the key to the hash map is the letter, and the value is the number of occurrences. Then loop over the word once, and then loop over this sorted Hashmap thing until you hit the first instance with a value > 1. So thatís more like N+x instead of N^2.
The string itself is already in order by the order of letters in the string, there's no need for another kind of structure for it
RustyBrooks is offline   Reply With Quote
Old 07-18-2018, 09:04 PM   #33828
:::grimReaper:::
veteran
 
:::grimReaper:::'s Avatar
 
Join Date: Jul 2010
Posts: 2,579
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by suzzer99 View Post
What kind of data structure could you use thatís like a hash map, but automatically sorted by creation order? You could do that, where the key to the hash map is the letter, and the value is the number of occurrences. Then loop over the word once, and then loop over this sorted Hashmap thing until you hit the first instance with a value > 1. So thatís more like N+x instead of N^2.
Balanced binary tree, but that's also not efficient, nor do you need counts. Just use a set.

And I stand corrected by Rusty. It does require traversing the string twice, just don't need counts.
:::grimReaper::: is offline   Reply With Quote
Old 07-18-2018, 09:15 PM   #33829
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 24,377
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by :::grimReaper::: View Post
Balanced binary tree, but that's also not efficient, nor do you need counts. Just use a set.

And I stand corrected by Rusty. It does require traversing the string twice, just don't need counts.
How would you do it without counts? You need to know which letters occur more than once. If you traverse the list once and put every letter in a set, all that tells you is... what letters exist at some point in the string. For "abba" your set would look like {a, b}, how does that help?
RustyBrooks is offline   Reply With Quote
Old 07-18-2018, 09:21 PM   #33830
well named
poorly undertitled
 
well named's Avatar
 
Join Date: Jun 2007
Location: esse est coesse
Posts: 76,043
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

My snippet above does it without counts, in one traversal
well named is offline   Reply With Quote
Old 07-18-2018, 09:28 PM   #33831
RustyBrooks
Carpal \'Tunnel
 
RustyBrooks's Avatar
 
Join Date: Feb 2006
Location: Austin, TX
Posts: 24,377
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by well named View Post
My snippet above does it without counts, in one traversal
I just read it, that's pretty clever.
RustyBrooks is offline   Reply With Quote
Old 07-18-2018, 10:19 PM   #33832
jjshabado
Carpal Tunnel
 
jjshabado's Avatar
 
Join Date: Jul 2006
Posts: 22,555
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

That is pretty clever. Total nitpick, but you can get rid of the 'updateCandidate' by using else if.
jjshabado is offline   Reply With Quote
Old 07-18-2018, 10:26 PM   #33833
well named
poorly undertitled
 
well named's Avatar
 
Join Date: Jun 2007
Location: esse est coesse
Posts: 76,043
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

You're right. I was thinking about it a bit while I ate dinner and then dashed that off in like 5 minutes. I stopped when it worked.

This is cleaner:

Code:
function findFirstRepeat(test) {
  const firstSeen = {};
  
  let candidatePosition = 99999999,
      candidate = false;

  for (let i = 0; i < test.length; i++) {
    const c = test[i];

    if (!firstSeen.hasOwnProperty(c)) {
      firstSeen[c] = i;
    } else if (firstSeen[c] < candidatePosition) {
      candidatePosition = firstSeen[c];
      candidate = c;
    }
  }
  
  return candidate;
}

console.log(`earlist repeat: ${findFirstRepeat('we all live in a yellow submarine')}`);
I'd originally tried to do the if/else block in the opposite order which doesn't work, and instead of just swapping them I added the variable because I'm a silly person.
well named is offline   Reply With Quote
Old 07-18-2018, 10:41 PM   #33834
Grue
Pooh-Bah
 
Grue's Avatar
 
Join Date: Mar 2004
Location: It is pitch black.
Posts: 5,638
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Anyone a principal/staff/architect SE (next step above lead)? What'd you do to get there? Its my medium term goal (~2 years) at my current place.
Grue is offline   Reply With Quote
Old 07-18-2018, 10:45 PM   #33835
Grue
Pooh-Bah
 
Grue's Avatar
 
Join Date: Mar 2004
Location: It is pitch black.
Posts: 5,638
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by Grue View Post
I had the most stereotypical day of phone screen interviewing ever:

Candidate #1: seemed pretty good, answered most of my questions, I'll probably never hear from him again.
Candidate #2: awful, had react and CSS all over the resume, couldn't tell me what a lifecycle method was, couldn't tell me what flexbox was.
Candidate #3: 1st call went to voicemail, 2nd call 5 minutes later he answered and hung up on me.

FFS. We went through with attempting to hire (contract) 1st guy, he said OK, 5 days from he start date he bailed. Never want to be a manager now what a ****show hiring people in this economy is.
Grue is offline   Reply With Quote
Old 07-18-2018, 10:53 PM   #33836
Grue
Pooh-Bah
 
Grue's Avatar
 
Join Date: Mar 2004
Location: It is pitch black.
Posts: 5,638
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Since I'm chain posting, my game got record amount of players today, over 250 on at once, crazy. Server (2gb ram 2 core) isn't super happy about it but doesn't crash any more after I did some "duh" upgrades to the backend that cut down on size of ws emits.

I do UI/react for a living and yeah its surprising how important server side code is. The game has a playerlist component - if a player logs in, it pushes their info into an array and then emits that whole array to everyone. You server pros are probably thinking "yeah thats stupid" but for whatever reason it never occurred to me that that could cause problems at scale. IDK after this it def made me respect that role more..
Grue is offline   Reply With Quote
Old 07-18-2018, 11:55 PM   #33837
Wolfram
Carpal \'Tunnel
 
Wolfram's Avatar
 
Join Date: Jan 2006
Location: You can be my wingman any time
Posts: 14,733
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by suzzer99 View Post
I have my first live interview tomorrow for a job I'm pretty sure I don't want. I spent $600 at Nordstrom's on my best attempt at a "CTO outfit". Dress for the job you want lol.
Ok, you can't just put this out there and not post a picture.
Wolfram is offline   Reply With Quote
Old 07-18-2018, 11:57 PM   #33838
:::grimReaper:::
veteran
 
:::grimReaper:::'s Avatar
 
Join Date: Jul 2010
Posts: 2,579
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by RustyBrooks View Post
How would you do it without counts? You need to know which letters occur more than once. If you traverse the list once and put every letter in a set, all that tells you is... what letters exist at some point in the string. For "abba" your set would look like {a, b}, how does that help?
Using two sets. Though technically t's keeping track of whether count > 1 just like a hash would, but conveys intent better imo.

Code:
def find_first_repeat(string):
    seen     = set()
    repeated = set()
    for c in string:
        if c in seen:
            repeated.add(c)
        else:
            seen.add(c)
    for c in string:
        if c in repeated:
            return c

if __name__ == '__main__':

    print('abcdebcd => ' , find_first_repeat('abcdebcd'))
    print('abba => '     , find_first_repeat('abba'))
:::grimReaper::: is offline   Reply With Quote
Old 07-19-2018, 12:32 AM   #33839
Barrin6
Carpal \'Tunnel
 
Barrin6's Avatar
 
Join Date: Dec 2005
Location: beyond legal blindness
Posts: 6,880
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by :::grimReaper::: View Post
Using two sets. Though technically t's keeping track of whether count > 1 just like a hash would, but conveys intent better imo.
Why not just use one set? Am I missing something, this is a pretty straightforward problem.

Code:
def find_first_repeat(string):
    seen     = set()
    for c in string:
        if c in seen:
            seen.add(c)
        else:
            return c

if __name__ == '__main__':

    print('abcdebcd => ' , find_first_repeat('abcdebcd'))
    print('abba => '     , find_first_repeat('abba'))
Barrin6 is offline   Reply With Quote
Old 07-19-2018, 12:34 AM   #33840
Barrin6
Carpal \'Tunnel
 
Barrin6's Avatar
 
Join Date: Dec 2005
Location: beyond legal blindness
Posts: 6,880
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by blackize5 View Post
Not true based on the example output.

It doesn't want the character that repeats first. It wants the character closest to the beginning of the string that has a repeat. This requires two passes.
Oops okay so that's why you need two passes.
Barrin6 is offline   Reply With Quote
Old 07-19-2018, 12:36 AM   #33841
well named
poorly undertitled
 
well named's Avatar
 
Join Date: Jun 2007
Location: esse est coesse
Posts: 76,043
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by Barrin6 View Post
Why not just use one set? Am I missing something, this is a pretty straightforward problem.
I think you have your if/else blocks reversed, but you also have the problem where you're returning the first duplicate found rather than the first character in the string which has a duplicate regardless of how late in the string the duplicate is found. Compare your output to the expected for the problem:

Quote:
findFirstRepeat("abcdebcd") // should return "b"
well named is offline   Reply With Quote
Old 07-19-2018, 12:38 AM   #33842
well named
poorly undertitled
 
well named's Avatar
 
Join Date: Jun 2007
Location: esse est coesse
Posts: 76,043
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by well named View Post
I'd originally tried to do the if/else block in the opposite order which doesn't work, and instead of just swapping them I added the variable because I'm a silly person.
This was wrong actually, the order doesn't matter. I must have had some other problem.

Incidentally, this is why I don't like whiteboard problems. I tend to think of some general approach (use a hash to store the first position each character was seen in, keep track of the earliest duplicate...) and then I start writing some code and it doesn't work and I don't quite understand why and then I play with it -- running it a bunch of times -- and then it works. That iterative process works well for me IRL but isn't easy to do at a whiteboard.

Basically I think I have trouble keeping an entire problem in my head, I need the scratch space.
well named is offline   Reply With Quote
Old 07-19-2018, 12:39 AM   #33843
Barrin6
Carpal \'Tunnel
 
Barrin6's Avatar
 
Join Date: Dec 2005
Location: beyond legal blindness
Posts: 6,880
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by Barrin6 View Post
Also anyone who says algorithms donít matter, I was able to whip up KMP string matching for one of our services and was able to benchmark and found our injestions running 3x faster locally. Going to deploy tomorrow and hope everything holds up.
Follow up to this - deployed and our service is consuming at 2.5x the speed. Huge win for us since we are processing terabytes of data over a course of weeks.
Barrin6 is offline   Reply With Quote
Old 07-19-2018, 12:43 AM   #33844
:::grimReaper:::
veteran
 
:::grimReaper:::'s Avatar
 
Join Date: Jul 2010
Posts: 2,579
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by Barrin6 View Post
Why not just use one set? Am I missing something, this is a pretty straightforward problem.
Did you try running it? 'abcdebcd' should return 'b' and 'abba' should return 'a'.

Even if you meant to say
Code:
if c not in seen:
, it's still incorrect because it fails for 'abba'. Yours would return 'b'.
:::grimReaper::: is offline   Reply With Quote
Old 07-19-2018, 12:49 AM   #33845
OmgGlutten!
Pooh-Bah
 
OmgGlutten!'s Avatar
 
Join Date: Aug 2016
Posts: 4,999
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

it has been awhile, but I think Suzzers problem is actually like the first problem in Cracking the Coding Interview (or a slight deviation of it). you are splitting a string and creating a hash with an incremented count.

Code:
def double_letter(string)
  results = Hash.new(0)
  string.length.times do |x|
    results[string[x]] += 1
  end
  results.find {|k,v| break k if v > 1}
end
ruby is so visually satisfying when it comes to this ****.
OmgGlutten! is offline   Reply With Quote
Old 07-19-2018, 12:55 AM   #33846
Wolfram
Carpal \'Tunnel
 
Wolfram's Avatar
 
Join Date: Jan 2006
Location: You can be my wingman any time
Posts: 14,733
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

would be a lot more visually satisfying if you put it in a code block
Wolfram is offline   Reply With Quote
Old 07-19-2018, 01:03 AM   #33847
:::grimReaper:::
veteran
 
:::grimReaper:::'s Avatar
 
Join Date: Jul 2010
Posts: 2,579
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

I would rewrite that as:

edit: Close enough. Didn't know what Hash.new(0) did. Learn something new everyday.

Code:
def find_first_repeated(string)
  chars = string.split("")
  char_to_count = chars.each_with_object(Hash.new(0)) { |c, h| h[c]  += 1 }
  chars.each { |c| return c if char_to_count[c] > 1 } 
end

puts 'abcdebcd => ', find_first_repeated('abcdebcd')
puts 'abba=> '     , find_first_repeated('abba')
:::grimReaper::: is offline   Reply With Quote
Old 07-19-2018, 02:02 AM   #33848
OmgGlutten!
Pooh-Bah
 
OmgGlutten!'s Avatar
 
Join Date: Aug 2016
Posts: 4,999
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

suzzer, i would google cracking the coding interview questions solved with javascript and look that over before your next white board.
OmgGlutten! is offline   Reply With Quote
Old 07-19-2018, 02:08 AM   #33849
suzzer99
Save the Cheerleader, Save the World
 
suzzer99's Avatar
 
Join Date: Nov 2005
Location: on top of the bell curve
Posts: 92,150
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Quote:
Originally Posted by Wolfram View Post
Ok, you can't just put this out there and not post a picture.
Once I (literally) iron out the kinks, I will.
suzzer99 is offline   Reply With Quote
Old 07-19-2018, 02:08 AM   #33850
jmakin
 
jmakin's Avatar
 
Join Date: Jan 2008
Location: Streaming
Posts: 28,520
Re: ** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD **

Good solution, i probably do the naive way every time if put on the spot
jmakin is offline   Reply With Quote

Reply
      

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off


Forum Jump


All times are GMT -4. The time now is 02:53 AM.


Powered by vBulletin®
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright © 2008-2017, Two Plus Two Interactive
 
 
Poker Players - Streaming Live Online