Facebook software engineer interview process

I have no idea what you're trying to say

The idea was not just to count the number of non-zero elements, but also to remove the zeros from the array. However he said that they could be replaced with anything, as long as they were all on the end of the array. Basically I could just move the zeros to the end.

Hmm I see. Yeah that is tricky to do in O(n) time elegantly.

The idea that I came up with that I didn't have time to implement was this:

Iterate from the beginning of the array and when you come to a zero, start iterating backwards from the end of the array. When you get to a non-zero while iterating backwards, swap the two elements. Then continue from where you left off again, find a zero, continue where you left off at the end, find a non-zero, swap again, etc until the iterations meet each other. That would take O(n) time and constant space since it is done in place.

This just sounds like the faggot wanted a sorting function but tried to obfuscate it since it's a big and scary word.

In fact this shit would be faster if you just called a quick sort on it which is O(logn).

It is O(n log n), user

Interesting. So now that you sorted it, how would you get the number of nonzero elements without iterating over the array again?

Oh wait that would just be the index of the left section, right? That is clever.

The woman who wrote Cracking the Coding Interview literally works for facebook and basically teaches classes on how to get hired at facebook for free

Be able to solve the harder stuff, but also be able to manipulate bits and strings (really simple stuff you would never do on the job)

make sure you know dynamic programming and graph questions, but also reversing strings efficiently, palindrome detection, that sort of thing

I think it was just a first question fizzbuzz level to check if you're not a complete reatrd. They would give you real problems after you finish it preferably in less than 5 minutes.

A more simple idea should be:

i := 0; nNonZero := 0;
WHILE i < LEN(a) DO
IF a[i] # 0 THEN
a[nNonZero] := a[i]; nNonZero := nNonZero + 1
END IF;
i := i + 1
END WHILE

Damn this feels bad. I thought I was cool for being 99th percentile on codewars but apparently i'm retarded with anything that actually matters

Nope, actually many coders are really retarded than average Veeky Forumstards here

>quicksort is O(logn)
LMAO

>quicksort would always move the zeros to the end of the array
LMAO

my solution

numZeroes = 0
for i = 0, i < a.length
while a[i] == 0
numZeroes++
a[i] = a.pop()

>I was wondering if any of you guys have interviewed at Facebook and what your experience was like?

LOL. DO YOU KNOW WHERE YOU ARE? ARE YOU LOST?

Don't be stupid, you were asked to create code under pressure, it's meant to trip you up.

This is a very interesting thread, and a lot of people on biz do have some experience in compsci

Not an expert coder but my thought process would be:-
1) confirm purpose of exercise is not to optimist for speed of the algorithm. Confirm how many dimensions in the array
2) in this case I'd try and do it in the fewest lines of code, simplest way so others could maintain it.
3) id do this by writing a function if one didn't already exist.
4) my function / subroutine would take a reference to the array and return number of non zero chars, with an option to return
5) code in function would then simply iterate through each array element and increment a non zero charachters.

If it's Python which I don't like very much I think there is some kind of nonzero function.

>remove all of the 0s from an array of integers and return the number of non-zero elements in the array
>while altering the original array as well
>O(n)
Did you ask if the array is sorted or not? If it's sorted, you don't have the most optimal case.

That being said, these types of interviews are shit and designed to weed out anyone who can think of anything other than algorithms (aka anyone who would point out all the ethical issues with the work FB would probably have them do). Don't feel bad if you don't move on. Just use it as a learning experience and try better at another company.

>think of anything other than algorithms
By this, I mean people with actual personalities and ethics standards.
>inb4 facebook people are geniuses
Have you even met a tech worker from a large tech firm? 90% of them will begin to evangelicalize whatever product(s) their company is doing the second you talk to them. They literally know nothing but work.

On the flip side, it makes FB/MSFT/GOOG have an easier time making them work on sketchy projects.

>linear traversal
No wonder you failed :^)

>competent programmers don't have personalities or ethics

are you sure?

It sorts the array user....... You fucking dumb? If the 0's end up in front just adjust the sorting condition. And yes nLogn

>We went through a couple example inputs to test it and it seemed to work fine. He then asked me how we could make it more efficient and I came up with an optimal solution (O(n) time and O(1) space). However, there was no time remaining to actually implement the optimal solution.
>In the beginning of the interview he specifically mentioned that he was not terribly concerned with efficiency and more concerned with "correctness" so I think that bodes well, but I'm still not incredibly optimistic that I'll get to continue the interview process.
I'm sorry user but you failed the interview, and to put it really bluntly I don't even know how you got an interview to begin with

Did you write the question wrong? This is stupidly straightforward and easy - literally just iterate over the array while keeping a pointer to the "top" and every time the element you're iterating over is non-zero, swap the element and the top, and increment a counter of each time it's not zero

This is definitely a warmup question not your real question.

Who says zero is the smallest value in the array?
retard

He could be useful, our anonymous mole on the inside, patiently lying in wait for the chance to cripple suckerturd's empire with a single crushing blow. You remember when he tried to give internet to all of Africa? Dude, fuck that guy. You know what the internet would be like if it was full of Africans? It would be like Africa.

2 points:

1. To say that you think I shouldn't have gotten the interview in the first place is to say that you think my work experience and resume are unimpressive, which doesn't make any sense because you don't know anything about either of those, unless you are implying there is a strong correlation between the ability to solve this problem on a white board under pressure and the ability to be a good software engineer, which is silly.

2. Your solution does not work. By "top" do you mean the end of the array? You can't just swap the non-zero element with the element at the end of the array. What if the last element in the array is a zero? Also, the last element of the array WILL be a zero after your first swap. You have to implement a solution like the one I described earlier, where you iterate inward from both sides and swap when the left iterator hits a zero and the right iterator hits a non-zero. I don't think this is an obvious solution to anyone.

I was using java and the idea was that the array is immutable, so we can't pop elements off. I think if I were using javascript or some language where you could call "pop" on an array, he would have altered the question.

I disagree that it's a fizzbuzz question. I've gone through onsite interviews with Google before and I own that cracking the coding interview book, and I think this question is on middle of the spectrum, or maybe slightly on the easy side. But also this depends on your expertise... some people may find tree questions harder or DP questions harder, but it all depends on what each person knows well. Personally I would rather have gotten a tree or DP question than this one, because I'm pretty comfortable with most of those.

I briefly suggested sorting during the interview, pointing out that negative numbers would cause a problem. However, this can be solved by using a custom comparator. In Java, that's something along these lines:

Arrays.sort(inputArray, (a, b) => {
if (a == 0) return 1
if (b == 0) return -1
if (a > b) return 1
else if (b > a) return -1
else return 0;
});

>essentially to remove all of the 0s from an array of integers and return the number of non-zero elements in the array

>>> import numpy as np
>>> arr = np.random.randint(0,10,(1000)) #array of random integers
>>> len(arr[arr != 0]) #return amount of non-zero integers

Can I get a job at facebook now? I honestly refuse to believe they would give such a simple task.

This solution doesn't alter the array, the zeros are still there. You need to basically move them all to the end in-place.

THe example input he gave me was not sorted.

But yeah you bring up good points about th nature of working for a company like that and the kind of people you work with. Even going through the office I got the impression that they take excellent care of their software engineers but expect their life to revolve around work. That being said, they pay a fuck-ton of money.

what the fuck is going in this thread?

Thanks, I completely forgot what this website was called.

>Veeky Forums - Technology

>That being said, these types of interviews are shit and designed to weed out anyone who can think of anything other than algorithms (aka anyone who would point out all the ethical issues with the work FB would probably have them do

dumbest thing I've ever heard

Used to do a little coding with Android and java
Shit was fun trying to figure out cools way to implement cool shit
After few months of working on project , I completely burned out on overload and realized that I fucking can't stand coding
Now I torque on wrenches and do IT for small biz , making stupid programs here and there to make it easier for the normies
Am happy and am still a wage cuck, but it's a lil different when u actually like it job for most part

Intelligent people discussing something other than memecoins

yes, n log n, not log n as you first wrote. making it worse than OPs solution without sorting.

I had a summer job at a national park for two years while I was in college. I got paid literally less than 1/4 of what I make now, and even less than what I would make if I got a job at Facebook. I would take that summer job full time over Facebook in a second if that were possible. Unfortunately it is seasonal though and only possible for a few months per year. Best job I ever had though by far... hanging out outside every day in one of the most beautiful places on the planet.

You did well. You came up with a solution; managed to optimise it. An interview is an extraordinary scenario that can make you lose your cool.

Tips:
Stay professional
Have a healthy, friendy attitude
Dress well and sharp
Remember the business etiquette

and you're good to go.

Thanks, yeah I think I did pretty well but I know I could have done better, and I don't know if I did better than other candidates. I'm just not sure if doing well is good enough to move on in their interview process. I'll find out soon I guess.

Thanks for the tips though!

Sounds like you handled the situation well. Former Amazon employee here. Honestly I hated my time at Amazon and the only good thing to come from it is that every other company takes your resume seriously once they see you worked at one of the big tech companies.

what if the array contains both positive AND negative numbers?

MIND = BLOWN
quicksort cucks BTFO

firm handshake?

Just be yourself.

FYI the code you quoted solves the problem when negative numbers are involved. That is the purpose of the custom comparator.

You didn't even understand the question. So i think not.

I actually interviewed with Amazon on site not that long ago. The recruiter told me they came down to just me and one other guy, and they chose the other guy because he had mobile experience and I guess they had some need for that. I was still uncertain though, always hearing a lot of bad things about Amazon.

for(i=0;i=0;i--)
{
if(array[i2]!=0)
array[i]=array[i2];
array[i2]=0;
}
else
nonzero++;
}

there's my solution in crude c

And I just realised I fucked it up

Blow my ass fag interviewer

Int[] RemoveZeroes(ref int[] zeroes){

int[] newArray =zeroes.Where(p=>p!=0).ToArray();
zeroes=newArray.ToArray().
return newArray;
}

Lol yeah I was a little confused looking at that

Whatever, OP didn't state it correctly until the replies.

I mentioned in the OP that you have to alter the original array

Add a nonzero++ into the if statement in the second for loop to account for non-zeros at the end of the array, and a new variable which tracks the location of the piled up zeros at the end of the array (breaking the first for loop when that index position is reached), and it's fixed.

It was unclear.

What you wanted to say:

In an immutable array containing integers, count the number of non-zero integers by moving all zeroes to the end in optimal solution (O(n) time and O(1) space, which means one for loop and using the same array. I.e. not allocating space for another.

This is the true final stage of capitalism before it all comes tumbling down

>C
JUST

Congratulations OP. I loved programming when I took a few classes on it in college but my career has never really required me to use it, except a little VBA, but I was thinking about going back to start practicing and studying again.

Anyway that sounds like you did fine. I hope it works out for you.

Maybe my description wasn't perfect. What you are saying isn't how the problem was presented though. He basically said to remove all zeros from an array, return the number of non zeros, and everything to the right of the non zeros can be any value.

Thanks user! You should totally start learning again. Great skill to have, very marketable and also fun to build projects on the side

Programmers are absolutely some of the most immoral people out there. Giant chip on their shoulder, low empathy and a belief their knowledge in one area of expertise translates everywhere else makes for a devastating recipe.

Lol not all of us are like that. There are definitely some, but not all.