Welcome to your job interview. How do you go Sup Forums?

>Hi user. I don't give a shit about your resume.
>Let's dig into the good stuff & see if you are a retard.

>Question 1:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

>Question 2:
Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

>Question 3:
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

>Question 4:

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Other urls found in this thread:

leetcode.com/problems/remove-duplicate-letters/#/description
twitter.com/NSFWRedditVideo

Why not give me the latest bug that your retarded employees made from the bug tracker instead?

you can re-apply in six months

allowing HR and filling it with women was a mistake

Part of the job policy is if you voted for Drumpf you are out.

Fuck off cunt, how about you do your homework yourself you retarded shit.

I'm here for the marketing job, autismo...

But I'm not American, gib job

>Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
public List merge(List... lists) {
List merged = new LinkedList();
for(List list : lists) { merged.addAll(list); }
Arrays.sort(merged);
return merged;
}


>Write a program to solve a Sudoku puzzle by filling the empty cells.
what is a sudoku puzzle?

>Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once
public String removeDuplicates(String in) {
Set set = new HashSet();
for(char c : in.toCharArray()) { set.add(c); }
return new String(set.toArray());
}

the second one is not guaranteed to work

HashSet in Java prevents duplicates.

I wouldn't want to work for Asspained Snowflakes, Inc. anyway. You guys will be out of business in three months.

I thought I was here to fuck that girl in the pic.

>excuse me user. According to this covert footage we obtained you were watching anime at 7pm last night. Can you please explain yourself?

> smallest in lexicographical order among all possible results
I believe your Java HashSet solution will convert this:
zabcz
into this:
zabc
when it should be this:
abcz

Yeah it's pretty simple, I google the subsets of each problem (ie merge multiple lists python) and then piece it all together using an IDE. Work smarter not harder. When do I start?

saw a thread on Sup Forums about cowboy bebop. had to rewatch it!

you can reapply in 6 months

You can't use Arrays.sort on a List you fucking retard.

>Question 1
Sort each one of them and then merge sort in one

>Question 2
Backtracking algorithm

>Question 3
ummm idk I have to think

>Question 4
I don't know if I understand it correctly but this is just an if statement in a cycle and an incrementation.

I'm in 12th grade the first two are actually really easy ones, please correct me if I'm wrong. I only know Pascal so I won't bother now to write code.

Question 1:
There already is a function that merges 2 sorted lists. Just use that to merge k lists. The function will be called k times.

Question 2
Try solutions with naive backtracking until you find a satisfying one.
If that's not fast enough you could implement simple forward inference.
Arc consistency would be overkill for a job interview

Question 3
Is this a trick question?
>every letter appear once and only once
what if a letter doesn't appear at all? I'm only allowed to remove letters, not every letter can be guaranteed to appear once.

Question 4
Iterate i from 0 to length of the array and j from i+1 to length of array and check the condition and count the solutions.

>hey Sup Forums do my homework for me
Kill yourself faggot.

I have an interview with Google soon, and I can't answer any of these questions.

>I don't know if I understand it correctly but this is just an if statement in a cycle and an incrementation.

Yeah, that's what I thought too. the last question is almost on the level of fizzbuzz

i'm a professional developer and I can't either, don't worry man

How do you know this in 12th grade? My HS didn't offer a programming class. Why Pascal?

>Arc consistency
Where did you learn all the stuff you know in solving these problems? What resources?

op is just trolling

the most companies ever ask for is a fizzbuzz test and that's just to weed out the pajeets who bluffed their way through some bullshit certification

for 4 you can do a modified mergesort probably

Question 3
Wouldn't you just make the string an array and remove duplicates and then sort it?

Wat

Degree?

nah, web dev
i actually don't need any of that to do my job so yeah

You are the reason an employer might not want to hire a Trump voter.

>not hire half the country
ok kid

> What resources?
Artificial Intelligence lecture at my university. It had a chapter on solving constraint satisfaction problems.
If you're studying computer science, your university probably has some classes on advanced algorithmic problems like graph algorithms, csp solving algorithms, and optimization algorithms. Those are your best resources for problem solving skills.

>the most companies ever ask for is a fizzbuzz test
Definitely not this unless the company is Pajeet Infotech Technologies Company, LLC.

...

>underage b8

So you just sort it into a list and then dump to string and return.

3.
Since the order doesn't matter, map the letters to indeterminants of polynomials over C and use the Groebner basis and the elimination theorem to eliminate duplicate roots. Since the starting polynomial is always a monomial, this process eliminates repeating letters.

Then for "cba" you'd return "abc" when it should be "cba"

>half

Nice math, faggot

Thanks, I'll aim to take a grad level advanced algorithms course. Should that be enough to pass these interviews? At my school it's Data Structures -> Undergrad / Grad level Algorithms class -> Advance Algorithms (graduate level level class).

>Groebner basis
what kind of math do you have to solve these problems

lmao at using java library functions for the merge and sort.

Is this what java school graduates think is programming these days? lmfao. Can you even implement merge sort without a library senpai?

If you pulled this chinky shit at my interview the next problem would be some impossible dynamic programming problem that only grad students and hyper jews can solve. Then I'd tell my boss you bombed the interview question and we can't hire a poser despite his resume.

my friend just got a job at google. they didn't ask him any tricky dynamic programming shit or anything above basic depth first search and basic divide and conquer techniques.

the way to get a job at google is to put lots of radical leftist shit on your social media and to casually bring it up during the interview. then just find the kth element in a bst and you're in the club.

You'll probably want to study some more.

t. Friends that took and shared their interviews with me

b..but I only know fizzbuzz sum of primes under 2 mil and traversing a binary tree

k thanks. I still think i'll go for the advanced algos course for overkill

Algebraic geometry.

yea probably it will be enough.
just make sure you practice enough, so you know how to apply your knowledge

sounds good.

nice, i'm beginning to learn category theory. ever hang out on /sci/? i like math

Women in HR make hiring decisions based on potential mates. Literally nothing else you do matters if you don't pass that test.

Open CLRS
>mergesort
>backtracking
>radix sort, if you want to get fancy, then 4-way inplace radix sort
>fizzbuzz

There is a faster algorithm for number 4. Also, number 3 is a hard problem.

>ever hang out on /sci/? i like math
Sometimes. I'm usually in the math general.

That works give

dbcad
=>
abcd, not the expected bcad

Excellent, I'll be on the look out for you.

Going through all user answers.

Not a single serious attempt to solve the problems OP posted.

Welcome to Sup Forums. OP what did you expect?

>1
// Merge k Sorted Lists
class Solution {
public:
ListNode *mergeKLists(vector &lists) {
struct Cmp {
bool operator()(const ListNode *x, const ListNode *y) const {
return x->val > y->val;
}
};
priority_queue pq;
for (auto x: lists)
if (x)
pq.push(x);
ListNode *head = NULL, **cur = &head;
while (! pq.empty()) {
*cur = pq.top();
pq.pop();
ListNode *x = (*cur)->next;
if (x)
pq.push(x);
cur = &((*cur)->next);
}
return head;
}
};

We aren't going to just give the hw answers to the guy.

>3
// Remove Duplicate Letters
#define REP(i, n) for (int i = 0; i < (n); i++)

class Solution {
public:
string removeDuplicateLetters(string s) {
int n = s.size(), last[26] = {};
bool in[26] = {};
string r;
REP(i, n)
last[s[i]-'a'] = i;
REP(i, n)
if (! in[s[i]-'a']) {
while (r.size() && s[i] < r.back() && i < last[r.back()-'a']) {
in[r.back()-'a'] = false;
r.pop_back();
}
in[s[i]-'a'] = true;
r.push_back(s[i]);
}
return r;
}
};

1. Combine the lists to a markov chain, identify cycles etc.
2. Recursion
3. Sort and delete duplicates
4. Loops

Unless you're trying to optimize performance, these problems are kind of trivial

C++
>1
make a k-set of structs containing list interators and list end()s
feed corresponding lambda comparator to std::set template
erase first element sequentially after copying it to new list and increment iterator until end reached for each struct
>2
make a table of std::set
known fields' sets contain only one number
unknown fields contain all numbers
cycle through known fields list and exclude corresponding values according to game rules until all fields are known
if there is a stall in progress (no fields vere changed after a full run) make a copy of set with one possibility removed and continue solving it. If it succeeds it's the result. If it does not, make a copy of set with another possibility removed
>only one unique
LOL
>3
make a vector of sets: each vector contains a set of letter positions and bools indicating that char was output already
for(i=0; i!=iStr.size(); i++ ) V[iStr[i]-'a'].insert(i);

consume iStr: for each char output char find equal run (one pass for everything):
if there are no dups of char and it was not output, output it.
else if equal run is smaller than number of dups and next not output character is smaller (find it) remove equal run from dubs set, do not output char
else output char and mark as output
>4
O(N^2):
int counter=0;
for(int i=0; i!=nums.size(); i++)
for(int j=i+1; j!=nus.size(); j++)
if(nums[i]>2*nums[j]) counter++;

O(N^2) but may have better average performance:
sort nums indexes range from 0 to size-1 by nums[i]
for(int i=0; i!=nums.size(); i++)
binary search for range in which num[sorted[i]]>2*num[sorted[j]] and accumulate number occurences of i

>Question 1
My question: By "k" you mean a size represented by k, right? It's basically MergeSort but with the sort already taken care of.
Space is O(n), time is O(1).

>Question 2
Breadth first search.
Space is O(n^2). Time is O(n log n).

>Question 3
Chain contains() and the ASCII table together.
Space is O(256). Time is O(n^2) or O(n log n). (I forget how long contains() needs to run.)

>Question 4:
Could you give me an example input and output, as well as explain it a little better? Also, what is the maximum number of items in the nums array? And what data type is the nums array?

All in all, these are shit questions that only Amazon and Google ask because they don't know how to interview their candidates.

Pic related, also daily reminder.

Bro, no offense. But those answers are terribly wrong. You don't need any extra space for number 1. Number 2 can not be solved in nlogn. Also, you don't say the memory is n^2 just because of the matrix input. Number 3 would not work either.

I thought this thread was about Pajeets needing someone to help them with their comp sci homework. You must be very upset. Very mad. Lots of anger.

Enjoy the next 4 years, you faggot.

I'm a Gurllll Koder and went to Klossy school! That should be enough! ~_^ silly boyz

how is BFS O(n^2) in space? It's clearly linear m8.

#3


function removeDuplicate(var s){

var t = '';

for(var i = 0; i < s.length; i++)
if(!t.includes(s.chartAt(i)))
t += s.chartAt(i);

return t;
}

#4


function getReversePairCount(var a){

var c = 0;

for(var i = 0; i < a.length; i++)
for(var j = 0; j < a.length; j++)
if(i != j && i < j && a[i] > 2 * a[j])
c++;
return c;
}

...

1. Implement a priority queue where each element points to a head of a list. Every iteration, take the min, append it to the merged list, insert the next value of the list the min was taken from into the queue

2. Recursive backtracking, simple stuff.

3. Go through the string and make a set of which letters appear after the first appearance of a letter for every letter. Append the smallest letter still available that has all the remaining letters in the set of letters that appears after it until all have been appended.

4. Use any sorted data structure with logn insert, find, and countmore, like a binary tree. Go through the list, every i add countmore(2*i) to the total, then add i to the tree.

>t. Google SWE

Not to worry, the half we're hiring is the half that actually produces code.

I'm not the other user but you're a hero

what school did you go to?

UC Berkeley

damn brah. How do you like google?

It's like any other programming job except you get paid a lot.

Did you do a lot of competitive programming/interview prep before you interviewed with them?

I'm about to graduate this semester and work at a financial services company as a SWE after failing interviews for Google, Bloomberg, Palnatir, and other prestigious tech companies. I've started doing a lot of competitive programming training recently to prepare myself for later interviews and I can see myself making some improvements.

No, not really. I don't like to meme but I've always been able to do well in anything academic without putting in much effort. I had a 4.0 GPA for what it's worth. Not trying to discourage you or anything, just answering honestly.

>3. Go through the string and make a set of which letters appear after the first appearance of a letter for every letter. Append the smallest letter still available that has all the remaining letters in the set of letters that appears after it until all have been appended.

This doesn't look correct.

Yeah, I've actually encountered a lot of people who are good at these kinds of problems with little preparation or practice. I'm not one of the,, for whatever reason, but it's fun to work on these and get better at them.

>Question 1:

laziness:
let K be a list of k sorted lists

def merge(l,r)
< new // an empty list
< while l & r not empty

>interviewed with amazon
>find the least sum path of a BST
>expected fizz buzz tier question
>could only think of naive O(n) solution

you just go left...

1. ask the indian dude nearest you.
2. nah
3. how much does this pay?
4. when is lunch?

try and think about why that would not work.

Why bcad? I don't follow.

oh yeah. Is there something better than O(n)?

for instance.

I have no idea what the fuck you're talking about. I'm applying for a manager position. Not to be some god damned code monkey.

Here is the implementation:
function removeDuplicates(input) {
const seen = new Set();
const afterMap = {};
input.split('').forEach(c => {
if (!seen.has(c)) {
seen.add(c);
afterMap[c] = new Set();
}
seen.forEach(k => afterMap[k].add(c));
});
console.log(afterMap);

let output = '';
while (seen.size > 0) {
const nextChar = Array.sort([...seen].filter(c => afterMap[c].size == seen.size))[0];
output += nextChar;
seen.delete(nextChar);
delete afterMap[nextChar];
Object.values(afterMap).forEach(vals => vals.delete(nextChar));
}
return output;
}

Find an input that does not work.

You didn't answer my question, but you answered my other question, so I'm good with that.

I get a timeout here leetcode.com/problems/remove-duplicate-letters/#/description

I'm not going to make a shitty account on a botnet site. It's perfectly fine javascript, copy and paste it in the developer console you lazy bum.

I got it to run and it failed with "cbacdcbc"

Output:
"abcd"
Expected:
"acdb"

Merge two lists by insert the lowest numbers.
You only have to compare the head of each list, but you need to make the tree of actions, which means n*log(n)

Don't really know about the soduku. Basically you could implement the rules and eliminate options for each cell. If there is a cell with a single option, lock the answer. When there is more than two answers, push each state into a heap, sort after missing numbers or something, then see if a solution is found.
I guess informed breadth first search?

Bucket sort, don't repeat.

Simple for loop with the checks you gave.

Don't want to write the code for these questions.
Who are they for?

You work at Google and you're complaining about botnets?

Right you should generate the map from scratch each time instead of trying to reuse it, my mistake. It is still linear for a finite alphabet.

Oh wait, now I see. I'm dumb.