** UnhandledExceptionEventHandler :: OFFICIAL LC / CHATTER THREAD ** - Page 1354 - Computer Technical Help

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.

Quote

07-18-2018 , 08:39 PM

#33827

RustyBrooks

Carpal \'Tunnel

Join Date: Feb 2006 Posts: 24,647

Quote:

Originally Posted by suzzer99

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

Quote

07-18-2018 , 09:04 PM

#33828

:::grimReaper:::

veteran

Join Date: Jul 2010 Posts: 3,113

Quote:

Originally Posted by suzzer99

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.

Quote

07-18-2018 , 09:15 PM

#33829

RustyBrooks

Carpal \'Tunnel

Join Date: Feb 2006 Posts: 24,647

Quote:

Originally Posted by :::grimReaper:::

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?

Quote

07-18-2018 , 09:21 PM

#33830

well named

poorly undertitled

Join Date: Jun 2007 Posts: 78,077

My snippet above does it without counts, in one traversal

Quote

07-18-2018 , 09:28 PM

#33831

RustyBrooks

Carpal \'Tunnel

Join Date: Feb 2006 Posts: 24,647

Quote:

Originally Posted by well named

My snippet above does it without counts, in one traversal

I just read it, that's pretty clever.

Quote

07-18-2018 , 10:19 PM

#33832

jjshabado

Carpal Tunnel

Join Date: Jul 2006 Posts: 22,732

That is pretty clever. Total nitpick, but you can get rid of the 'updateCandidate' by using else if.

Quote

07-18-2018 , 10:26 PM

#33833

well named

poorly undertitled

Join Date: Jun 2007 Posts: 78,077

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.

Quote

07-18-2018 , 10:41 PM

#33834

Grue

Pooh-Bah

Join Date: Mar 2004 Posts: 5,667

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.

Quote

07-18-2018 , 10:45 PM

#33835

Grue

Pooh-Bah

Join Date: Mar 2004 Posts: 5,667

Quote:

Originally Posted by Grue

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.

Quote

07-18-2018 , 10:53 PM

#33836

Grue

Pooh-Bah

Join Date: Mar 2004 Posts: 5,667

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..

Quote

07-18-2018 , 11:55 PM

#33837

Wolfram

Carpal \'Tunnel

Join Date: Jan 2006 Posts: 15,066

Quote:

Originally Posted by suzzer99

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.

Quote

07-18-2018 , 11:57 PM

#33838

:::grimReaper:::

veteran

Join Date: Jul 2010 Posts: 3,113

Quote:

Originally Posted by RustyBrooks

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'))

Quote

07-19-2018 , 12:32 AM

#33839

Barrin6

Carpal \'Tunnel

Join Date: Dec 2005 Posts: 6,947

Quote:

Originally Posted by :::grimReaper:::

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'))

Quote

07-19-2018 , 12:34 AM

#33840

Barrin6

Carpal \'Tunnel

Join Date: Dec 2005 Posts: 6,947

Quote:

Originally Posted by blackize5

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.

Quote

07-19-2018 , 12:36 AM

#33841

well named

poorly undertitled

Join Date: Jun 2007 Posts: 78,077

Quote:

Originally Posted by Barrin6

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"

Quote

07-19-2018 , 12:38 AM

#33842

well named

poorly undertitled

Join Date: Jun 2007 Posts: 78,077

Quote:

Originally Posted by well named

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.

Quote

07-19-2018 , 12:39 AM

#33843

Barrin6

Carpal \'Tunnel

Join Date: Dec 2005 Posts: 6,947

Quote:

Originally Posted by Barrin6

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.

Quote

07-19-2018 , 12:43 AM

#33844

:::grimReaper:::

veteran

Join Date: Jul 2010 Posts: 3,113

Quote:

Originally Posted by Barrin6

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'.

Quote

07-19-2018 , 12:49 AM

#33845

OmgGlutten!

Pooh-Bah

Join Date: Aug 2016 Posts: 5,273

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 ****.

Quote

07-19-2018 , 12:55 AM

#33846

Wolfram

Carpal \'Tunnel

Join Date: Jan 2006 Posts: 15,066

would be a lot more visually satisfying if you put it in a code block

Quote

07-19-2018 , 01:03 AM

#33847

:::grimReaper:::

veteran

Join Date: Jul 2010 Posts: 3,113

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')