The h Bar

1:02 AM

Ha . . . I can't make my answer pass all test cases. Let me just grab a burrito first

Ok I am listening to Enya right now and solving this problem (duplicates) I think I can pass all the test cases, especially since I don't live in Rindler space

loocsieulb

1:25 AM

@Phase thanks for the heads up i'll keep that in mind

2:39 AM

Crap!!!!!!! Execution time limit exceeded

Will relax by reading about black hole information hehe (yes I said it lol :P)

@BernardoMeurer can you help me do this in O(n) time, O(1) space and in minimal execution time. I am trying to find duplicates. My firtst working pass is this function firstDuplicate(a){

var temp = [];

for (var i = 0; i < a.length; i++){
for (var j = 0; j < a.length; j++){

if( a[i] === a[j] && i != j ) {

if(i<j){
temp.push(j);
}

}

}
}

if(temp.length === 0){
return -1;
}

var sorted = temp.sort();
return a[(sorted[0])];

}

@Cows That is some hideous formatting

And I have no clue what that code is supposed to do or what language it is in

Are you trying to dedup an array?

Is that it

yup

I think the site did horrible formating

hang on let me give you a link so we can explore the code together

Are you concerned with time complexity or space complexity?

You kind of have to pick one here

Also, can we assume the array to be sorted, or no?

@Cows ?

yeah that is what i was thinking, but they want all those constraints too. Presumably there is a trick. lol I don't know what it is

So you want it to be low time and low memory?

2:51 AM

@BernardoMeurer Note: Write a solution with O(n) time complexity and O(1) additional space complexity, since this is what you would be asked to do during a real interview.

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

Guaranteed constraints:
1 ≤ a.length ≤ 10^5,
1 ≤ a[i] ≤ a.length.

Traverse the array. Do following for every index i of A[].
{
    check for sign of A[abs(A[i])] ;
    if positive then        make it negative by   A[abs(A[i])]=-A[abs(A[i])];
    else  // i.e., A[abs(A[i])] is negative
    this   element (ith element of list) is a repetition
}

hmm let me see if I can get a shareable online editor so we can try this

I tried something similar but it failed 4 test cases and the edge cases

@BernardoMeurer Let's try it here

jsfiddle.net/#&togetherjs=QCPGne0ANI

@BernardoMeurer actually that editor does not work well

Yeah, it doesn't

@BernardoMeurer can you write an example in c++?

Look, the algorithm I outlined has the requirements

No. I can write a C example

2:58 AM

that will be good too

please don't use pointers lolz, those things scare me

#include <stdio.h>
#include <stdlib.h>

void printRepeating(int arr[], int size)
{
  int i;

  printf("n The repeating elements are");

  for(i = 0; i < size; i++)
  {
    if(arr[abs(arr[i])] > 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      printf(" %d ", abs(arr[i]));
  }
}

int main()
{
  int arr[] = {1, 3, 2, 2, 1};
  int arr_size = sizeof(arr)/sizeof(arr[0]);
  printRepeating(arr, arr_size);
  getchar();
  return 0;
}

From: geeksforgeeks.org/?p=7953

oh nice

That's not good C code though, I didn't bother to change it

And if you're scared of pointers you ought to grasp them before trying to achieve complex array manipulation

And also, the whole thing is a trick question, if you're worried about duplicates you should use a Hashset and have them ignored at insertion time

@BernardoMeurer yo

sup

@0celo7 What uuuuuup

3:04 AM

nephews got baptized this weekend

Nice!

Ok cool knocked that out

I might be going to NY and DC in July-ish

I'll try to see you

In July I'll be in Knox or Chicago

Not sure

Dam

We can't fucking meet

3:06 AM

@BernardoMeurer Do I need a visa when I go to Rio in Aug?

Ye

fuck

It's easy to get tho

how do I do that

@BernardoMeurer can you give me a quite run through of linked lists?

3:07 AM

@BernardoMeurer are you not gonna be in Rio during the beginning of Aug?

I'll be in the Baja area

@0celo7 travel.state.gov/content/travel/en/international-travel/…

@0celo7 Nothing set yet

I was waiting on your schedule to make mine

I want to attack a cs problem on it but I want to see if may be you can give me some insights about this stuff

I should go see my mother in NY for a week or so

Then I'm free

I was planning on going home in August when you go

@BernardoMeurer thanks

@Cows Linked lists are absolute this, and almost useless

3:08 AM

*singly linked . .

Give me a second, I have an article

@Cows cglab.ca/%7Eabeinges/blah/too-many-lists/book/…

@BernardoMeurer cool, cool

wow

Rio seems to be crazy

@Cows If you think you need linked lists, odds are you don't

Use a Hashmap, a Hashset, a B+ Tree, a Quadtree, an array, a rope, anything

@0celo7 Rio is insane

I shaved a guy's head in a party over new years

And I had sex on top of a fork and got my ass pierced

It's fun

3:10 AM

@BernardoMeurer the author of amazon.com/Algebraic-Topology-Edwin-H-Spanier/dp/0387944265 was robbed at gunpoint 3 times in 6 months while in rio

Oh and I got to set people's new year resolutions on fire too

@0celo7 When was that?

in the 60s I think

Ah, yeah

It was a whole other city back then

@BernardoMeurer I changed the formatting of my thesis

@0celo7 Send it my way

3:16 AM

@BernardoMeurer done

@0celo7 How come it's not dedicated to me

I am offended

Cuz Bob buys me books

skullpatrol

who's Bob?

no one you need to know

@BernardoMeurer basically pages 5-19 are done

do you like the font?

skullpatrol

You were supposed to answer "my uncle"

en.wikipedia.org/wiki/Bob%27s_your_uncle?wprov=sfti1

3:25 AM

Yeah, I do like the font :)

It looks very nice

@BernardoMeurer thanks, many hours were spent doing that

Implementing linked list in javascript

then will use it to solve some problem in O(n)

time

@BernardoMeurer this is volume 1 of my manifesto

@Cows Use a hashset

You don't need a linked list

vzn

5:01 AM

← still reeling from todays wild chat session, but wanted to thank all the well-intentioned SE mods who work hard to make SE a great place in cyberspace, incl esp all those who got their msgs deleted... am dedicating this song to you :) metrolyrics.com/shiny-happy-people-lyrics-rem.html

5:29 AM

@Slereah did you write this arxiv.org/abs/1802.04362

@0celo7 what's up with this gluing of spacetime everyone is doing these days?

@Cows why not?