Welcome to your job interview. How do you go /g/?

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

>>60147929
you can re-apply in six months

>>60148125
allowing HR and filling it with women was a mistake

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

>>60148260
But I'm not American, gib job

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

public List<T> merge(List<T>... lists) {
    List<T> merged = new LinkedList<>();
    for(List<T> 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<Chararacter> set = new HashSet<>();
    for(char c : in.toCharArray()) { set.add(c); }
    return new String(set.toArray());
}

>>60148475
the second one is not guaranteed to work

>>60148534
HashSet in Java prevents duplicates.

>>60148260

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

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

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

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

>>60147781
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?

>>60148691
saw a thread on /tv/ about cowboy bebop. had to rewatch it!

>>60148757

you can reapply in 6 months

>>60148475
You can't use

Arrays.sort

on a List you fucking retard.

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

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

>>60147781
>hey /g/ do my homework for me
Kill yourself faggot.

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

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

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

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

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

>>60149149

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

>>60147781
for 4 you can do a modified mergesort probably

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

>>60149168
Wat

Degree?

File: face-with-tears-of-joy.png (58KB, 256x256px)

58KB, 256x256px

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

>>60148579

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

>>60149527
>not hire half the country
ok kid

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

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

File: tumblr_nspcja75Va1qgxas2o1_1280.jpg (350KB, 1280x1920px) Image search: [Google]

350KB, 1280x1920px

>>60148678

>>60149022
>underage b8

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

File: ran_delinquent1.png (714KB, 1281x900px) Image search: [Google]

714KB, 1281x900px

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

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

File: nogginjogged.jpg (36KB, 655x527px) Image search: [Google]

36KB, 655x527px

>>60149545

>half

Nice math, faggot

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

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

File: shed.jpg (145KB, 820x960px) Image search: [Google]

145KB, 820x960px

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

File: bernie.jpg (98KB, 825x631px) Image search: [Google]

98KB, 825x631px

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

>>60149149
You'll probably want to study some more.

t. Friends that took and shared their interviews with me

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

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

File: solve (9).png (490KB, 1280x720px) Image search: [Google]

490KB, 1280x720px

>>60149870
Algebraic geometry.

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

>>60150086
sounds good.

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

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

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

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

File: test (4).png (532KB, 602x699px) Image search: [Google]

532KB, 602x699px

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

>>60149305
That works give

dbcad
=>
abcd, not the expected bcad

File: mathwizard.jpg (74KB, 636x636px)

74KB, 636x636px

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

Going through all anon answers.

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

Welcome to /g/. OP what did you expect?

>>60150261

>1

// Merge k Sorted Lists
class Solution {
public:
  ListNode *mergeKLists(vector<ListNode *> &lists) {
    struct Cmp {
      bool operator()(const ListNode *x, const ListNode *y) const {
        return x->val > y->val;
      }
    };
    priority_queue<ListNode*, vector<ListNode*>, Cmp> 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;
  }
};

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

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

>>60147781
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<j in found range

File: Capture.png (30KB, 595x211px) Image search: [Google]

30KB, 595x211px

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

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

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

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

File: collegee.png (55KB, 571x553px) Image search: [Google]

55KB, 571x553px

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

>>60147781
#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;
}

File: [Asenshi] Amanchu! - 05 [A23728E9].mkv_snapshot_08.34_[2016.08.12_16.45.33].png (297KB, 440x534px) Image search: [Google]

297KB, 440x534px

>>60152919

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

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

>>60149577
I'm not the other anon but you're a hero

>>60153821
what school did you go to?

>>60153957
UC Berkeley

>>60153959
damn brah. How do you like google?

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

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

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

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

>>60154149
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
<< pop min(first(l),first(r)) and append it to new
return new // sorted list from two lists

O(2n)

def merge_sort_k(k)
< call merge() on pairwise elements of k, storing the merged k/2 lists in a new list, and calling merge_sort_k on the new list, until the new list contains no sub-lists

total of log_2(k) recursive calls in merge_sort_k

O(klog(k))?

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

>>60154244
you just go left...

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

>>60154255
try and think about why that would not work.

>>60150207
Why bcad? I don't follow.

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

File: bst.png (25KB, 796x412px) Image search: [Google]

25KB, 796x412px

>>60154341
for instance.

File: 1463774865587.jpg (43KB, 576x521px) Image search: [Google]

43KB, 576x521px

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

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

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

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

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

>>60154625
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?

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

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

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

>>60154772
most people solve this with a stack

>>60149545

>loses popular vote
>half

>>60149928

>not invented here

>>60154857
such exact

>>60147781
So this is it.
>>>/g/ has become a homework solver and consumerism shitboard.

>>60149022
post code or GTFO

>>60147781
had to do a similar version of Q2 last semester for uni using file i/o in c++, didn't have to solve it but instead had to check rows, columns, and blocks to confirm or verify a correct solution, was a real fucking pain in the ass, i don't think this was the best way, but i did get it working for a 9x9 sudoku grid using a 1x81 array

File: 1478746526895.jpg (74KB, 239x411px)

74KB, 239x411px

>>60154857
triggered af senpai lmao

>>60156507
Kek

>>60155848
There are quite a few answers posted including mine. Stfu.

>>60149022
>>Question 1
>Sort each one of them and then merge sort in one
They are already sorted

>>Question 2
>Backtracking algorithm
Nope, graph coloring

>>60149106
>There already is a function that merges 2 sorted lists. Just use that to merge k lists. The function will be called k times.
Inefficient, use PriorityQueues with priority depending on list length, then always merge the smallest two lists until only one remains

What are the best answers in thread? I haven't studied this stuff yet

File: 1492195533621.jpg (150KB, 1080x927px) Image search: [Google]

150KB, 1080x927px

>>60147781
Where would I even begin to start learning about this stuff?

I get my bachelors in IT this weekend and I had an internship at a major citys county IT department messing with switches and stuff for like 4 months last summer, will people hire me in networking and security or do I go straight to help desk? :(

>>60147781
But I'm not applying for a programming job. Hell, I've barely touched an IDE in the last 2 years because I'm too busy managing you autistic code monkeys.

>>60149928
Why not specify that you don't want library functions used or ask me to explicitly implement X function? I understand and can implement plenty of common functions, but would usually just opt to use the standard library because it's there for a reason and honestly I'd expect to be considered an idiot for not using it.

>>60149577
imagine the sweat under those tits

File: 1490844401091.png (123KB, 300x300px)

123KB, 300x300px

>>60147781
>mfw i learned to do all of that in my 3rd world college education
>mfw i graduated 1 year ago
>mfw i already forgot about how to do it already