[a / b / c / d / e / f / g / gif / h / hr / k / m / o / p / r / s / t / u / v / vg / vr / w / wg] [i / ic] [r9k / s4s / vip / qa] [cm / hm / lgbt / y] [3 / aco / adv / an / asp / bant / biz / cgl / ck / co / diy / fa / fit / gd / hc / his / int / jp / lit / mlp / mu / n / news / out / po / pol / qst / sci / soc / sp / tg / toy / trv / tv / vp / wsg / wsr / x] [Settings] [Search] [Home]
Board
Settings Home
/g/ - Technology


Thread archived.
You cannot reply anymore.



Ok, anon.

To get this job you have to implement an algorithm tal tells whereas a word is an anagram (same word but in different order) of another.

E.g.
"abba" is an anagram of "bbaa"
"acco" is not an anagram of "cooa"

You can use any language you like. But don't use any special library or function except for the ones that let you read and print data. Don't look up for code on the internet or we will know you are cheating.

You can do it, right anon?
>>
> But don't use any special library or function except for the ones that let you read and print data
Define this.
>>
anagram :: String -> String -> Bool
anagram x y = sort (f x) == sort (f y)
where f n = filter (isAlpha) n

And then hook it into a dictionary to verify x and y are actually words, something that directly requires the use of an external library because no language has a built-in oxford's dictionary.
>>
>>69767271
You don't need to verify if they are words and you already failed the no special function rule
>>
>>69767315
>you already failed the no special function rule
No part of what is written is a special function.
>>
>>69767199
>have strings in an array
>sort them
>compare linearly
Is that supposed to be hard?
>>
>>69767231
It's already defined. No library-defined functions other than print and read.
>>
>>69767778
What about string data structures? The associated memory management thereof? Concatenation? Indexing? Comparison operators? Addition? Bitwise operators?

Where do you draw the line? There is always a line about what predefined stuff you CAN use, and you cannot possibly mean "nothing" because then "use any language you like" would be meaningless. If using the haskell standard library is over the line, yet string data structures aren't, you are being spectacularly unclear about what line you do have in mind. Doubly so if your line is one that is supposed to be reasonably coherent between different languages.
>>
Super easy. Use a hash table and use the letters as keys, and then store the number of occurrences for both words. If any key has an odd number, then there must an extra letter present in either the first or the second word, and therefore is not an anagram.
>>
Split to single character, sort, join and compare if same.
Literally 3 lines of code?

Or am I missing something
>>
>>69767881
>>69767881
It's restricting the functions you can use. A string data structure is fine. Using an attribute defined on the string, such as length, is fine. Using methods defined on the string is not fine. So if string.length isn't an attribute, but a method, in your chosen language, then you're shit out of luck on that front. Print and read ONLY.
>>
def isAnagram(w1, w2):
result = true
i = 0
while i < len(w1):
if not w1[i] in w2:
result = false
break
else:
w2.remove(w1[0])
w1.remove(w1[0])
return result
>>
>>69767965
>.remove
Failed.
>>
>>69767199
ON the phone but:
Sort the strings. Compare them.
For O(n) : create an array of the size of the alphabet. Increment for every letter in the first string. Decrement for every letter in the second string. Check that all indices are zero.

This has a large constant factor but for larger strings should be faster.
>>
>>69767915
So in haskell, would the < function be allowed? What about the + function? Yes, those are both builtin functions in haskell. Are you implying that your exercise has no solution in haskell at all?

What about malloc() in C? You're not going to have much fun manipulating arbitrarily-sized strings without that. I suppose it's not actually impossible given how far you can get with compile-time constants, though.
>>
>>69768005
And since we can use data structures but not sort, put the chars in a heap and compare as you pop. (java.util.PriorityQueue<Character> for example)
>>
>>69768023
>Are you implying that your exercise has no solution in haskell at all
Only if it's not Turing complete without functions. If so, it's a shit language.
>>
>>69767979
Arbitrary rule but OK, replace with call to this function:
def removeFirstOcurrence(w, c):
assert(c in w)
i=0
while i < len(w0):
if w0[i] == c:
w = w[:i] + w[i+1:]
break
return w
>>
>>69768023
>Are you implying that your exercise has no solution in haskell at all?
Perhaps it doesn't. Blame the interviewer for setting up such strict constraints. Of course, given that only a person familiar with Haskell would realize that those operators are actually functions, you might be able to slip it by.
>>
>>69768027
toCharArray is a function though.
>>
File: koume.jpg (108 KB, 1280x720)
108 KB
108 KB JPG
fun anagram = (str a, str b) => bool
{
return false if a.len <> b.len

chars = map {str : int}

loop uint n : a.len
{
chars{a[n]} = chars{a[n]} ?? 0
chars{b[n]} = chars{b[n]} ?? 0
chars{a[n]} += 1
chars{b[n]} -= 1
}

loop int v : chars.values
{
return false if v <> 0
}

return true
}
>>
>>69767199
No interviewer ever talks like this
>>
>>69767915
are you retarded?
literally everything is a function
declaring a variable? that a motherfucking function
>oh but anon there no () on it
>what an alias?
>whats syntactical sugar?
>>
<code>
function anagrams(stringA, stringB) {
return cleanString(stringA) === cleanString(stringB);
}

function cleanString(str) {
return str
.replace(/[^\w]/g, '')
.toLowerCase()
.split('')
.sort()
.join('');
}

</code>
>>
>>69768054
>.len
>.values
Failed
>>
int autism(){
char a[20] = "asdf";
char b[20] = "sadf";
int count[26];
int i = 0;
while(a[i] != '\0'){
count[a[i] - 65] += 1;
i++;
}
i = 0;
while(b[i] != '\0'){
if (count[a[i] - 65] == 0){
return 0;
}
count[a[i] - 65] -= 1;
i++;
}
return 1;
}
>>
>>69768079
><
Don't call us, we'll call you.
>>
>>69768034
Anon, it's a functional language. One of its key features is modeling as large a part of computation as possible through the medium of functions. If you think that makes it shit, I'll have to conclude that you are simply a moron.
>>
>>69768092
Forgot to fix some variable names but you get the idea
>>
>>69768099
So you're saying you can't do it?
>>
>>69768092
I'm too lazy to verify if this works, but it looks complicated and I don't see any functions. You're hired.
>>
>>69768092
>*blocks your path*
>>
>>69768092
This will fail if your strings contain characters other than lowercase alphabetic ones. Using (UCHAR_MAX + 1) would be better. (Also, you forgot to initialize count.) Other than that, this should work.

Challenge: can you think of a solution that doesn't involve as much memory as the size of the accepted alphabet?
>>
>>69768110
No, I'm saying you're a moron. Pay attention.
>>
Sort is O(nlogn) you fail.

Best solution is to count all the characters in each string into a dictionary and then iterate both dictionaries to show they are the same.

Replace dict with hash map if you prefer
>>
>>69768133
>fails the task
>calls the interviewer a moron
Instant hire.
>>
del([X|W], X, W).
del([Y|W], X, [Y|W2]) :- del(W, X, W2).

anagram([], []).
anagram([X|W1], W2) :- del(W2, X, W22), anagram(W1, W22).
>>
>>69767199
Implemented 100% from memory.
words = ["aaabbbAzZZ", "aa", "bbb", "bbb", "aba", "zad", "daz", "abababAzZZ"]

def f(word):
h = [0]*52
for letter in word:
v = ord(letter)
i = v - [71,65][v<97]
h[i] += 1
return h

def hsh(count, n):
s = 0
m = 1
for i in count:
s += i*m
m *= 31
return s%n

d = len(words)*2
table = [[] for _ in [0]*d]

for word in words:
key = f(word)
val = table[hsh(key, d)]
if not val:
table[hsh(key, d)] += [[key, 1, [word]]]
else:
i = 0
while i < len(val):
if val[i][0] == key:
val[i][1] += 1
val[i][2] += [word]
break
i += 1
for val in table:
if val:
for k in val:
if k[1] > 1:
print(k[2])

Output
['bbb', 'bbb']
['aaabbbAzZZ', 'abababAzZZ']
['zad', 'daz']

I could remove function calls to len and ord but the replacement functions would just be boring loop and if chain.
>>
def isAnagram(string1, string2):
dic = {}
for i in string1:
if i not in dic:
dic[i] = 1
else:
dic[i] += 1
for i in string2:
if i not in dic:
return False
else:
dic[i] -= 1
for i in dic:
if dic[i] != 0:
return False
return True
>>
>>69768226
Forgot case in hash table.
for word in words:
key = f(word)
val = table[hsh(key, d)]
if not val:
table[hsh(key, d)] += [[key, 1, [word]]]
else:
i = 0
while i < len(val):
if val[i][0] == key:
val[i][1] += 1
val[i][2] += [word]
break
i += 1
else:
val +=[[key, 1, [word]]]
>>
File: :^).gif (546 KB, 255x255)
546 KB
546 KB GIF
module Anagram
def anagram?(other)
return self.chars.tally == other.chars.tally
end
end

class String
include Anagram
end
>>
>>69768135
Instead of using a hash I wonder if could use a couple longs to store the counts for most words.
>>
>>69768226
>uses ord
>uses len
>>
>>69768238
simple and functional enough,

>>69768226
hash tables are overkill whatever at least u can use them
>>
first, compare lengths of the strings, if they are a diffferent size, return false
then, create a flag array of equal size of the second string.
step through the first array.
for each char in a, see if the letter is in b and the flag is not checked. if the letter is in b and the flag is not checked, increment a counter and mark the flag.

if the counter is equal to the length of the sting, then return true.

no sorting needed.
>>
>>69768306
def mylen(x):
n = 0
for i in x: n += 1
return n

def myord(a):
i = 0
for c in "abcdefghijklmnopqrstuvwxyz":
if c == a:
return i+97
i += 1
for c in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
if c == a:
return i+39
i += 1
return 0

wow
>>69768331
I thought we had to find all anagrams in a word list.
>>
>>69767199
Just bubble sort both, then compare.
>>
>>69768126
Haven't tested it but here we go
int superautism(){
char a[20] = "asdfgh";
char b[20] = "saghdf";
int i = 0;
int j = 0;
while(a[i] != '\0'){
while (b[j] != '\0'){
if (a[i] == b[j]){
b[j] = '\0';
break;
}
j++;
if (j == i){
return 0;
}
}
i++;
}
return 1;
}

I'm not going through the autism of counting downwards and recounting the string every time I do anything to get rid of that extra variable, at least not tonight.
>>
Thanks for the coffee but I don't think I'd be a good fit for the company.
I have multiple offers to juggle and I don't want to hold up your search :^)
>>
File: 1528678312193.png (573 KB, 851x846)
573 KB
573 KB PNG
>Okay now that we've done the warm-up let's move on to the real problems
>>
 test [\code]
>>
#include <stdio.h>

int main(int argc, char **argv)
{
char c[2][26] = {0};
for (int i = 1; i <= 2; i++)
while (*argv[i])
c[i-1][*argv[i]-'a']++, *argv[i]++;
for (int i = 0; i < 26; i++)
if (c[0][i] != c[1][i])
return 1;
}
>>
>>69768043
It reads data from a string so it is allowed.
>>
string a,b;
cin>>s1>>s2; //hope this works
for(char a:s1){
bool found=false;
for(char& b:s2){
if(a==b){
found=true;
b='#'; //could be '\0' if needed
goto loop;
}
}
if(!found)
return false;
loop: ;
}
return true;
>>
>>69767199
K&R chapter 1 tier, not even worth the effort
>>
>>69768433
*
string a,b;
cin>>s1>>s2; //hope this works
for(char a:s1){
for(char& b:s2){
if(a==b){
b='#'; //could be '\0' if needed
goto loop;
}
}
return false;
loop: ;
}
return true;
>>
>>69768377
1. nth root of how many eggs you have, in this case, 2

2. Retarded. You have n^10249 things give an O(n) alg to find this biggest thing. You're just arbitrarily redefining the input size

3. 100%
>>
>>69767199
Yes I can, but your weird function rules are stupid so I will not.
>>
>>69767199
Bitch I own my own software how the fuck did you get in here?
>>
>>69768377
1. iterate every third number. once an egg breaks on the third, try current_floor-1, if it breaks then the floor is current_floor-2.
2. start at a random point, keep following the neighboring minimums til no smaller num is found. this one is easy mode.
best case is O(1).
3. this is gay.
>>
>doing OP's homework
>>
>>69767199
something like this:
isAnagram(word1 : String, word2 : String) -> Bool {
if word1.count == word2.count {
// ... put each letter in a set
// ... count each set letter and compare the result to the other word's set
// If everything matches:
return true
}
return false
}
>>
>>69768126
If you want to save size you have to sort the strings and then check for equality.
If you want to save in time, that solution is the fastest, but you can halve the memory by having the first loop add, and the second substract, from the same array, and then checking for zeroes.
>>
>>69768457
>2. Retarded. You have n^10249 things give an O(n) alg to find this biggest thing. You're just arbitrarily redefining the input size
Wut? If you just traverse the grid you'll get O(n^2).
>>69768473
>2. start at a random point, keep following the neighboring minimums til no smaller num is found. this one is easy mode.
>best case is O(1).
Not O(n).
>>
>>69768492
>Not O(n).
prove it.
worst case is at lease less than O(n^2)
>>
File: 1525250310629.jpg (54 KB, 800x576)
54 KB
54 KB JPG
>>69768457
0/3
>>
>>69768519
If the grid has a snake of descending numbers separated by "walls" of high numbers you'll follow the snake and traverse ~1/2 of the grid which is O(n^2).
>>
>>69768054
What language is this thing?
>>
>>69768533
ah shit. n-ish *1/2 n is still n^2.. you got me.

hmm....
sample arr[1][1]q, arr[2][2], etc. and try the same "follow the min" game until you get to a local min. seems less intuitive but is theoretically faster. making sure to stop following the min path if you already have visited a point.
>>
>>69768563
i.e. you have n follow the min paths running, deleting repeat paths.
>>
>>69768520
while I see what they're asking now for 2, I know for a fact 1 and 3 are right you idiot weeb
>>
>>69767979
this is how you tell that getting this job is not worth it
>>
>>69768692
It's not just nth root it's root of the sum quadratic.
3 is definitly not 100% write a sim script if you don't beleieve.
>>
>>69768717
https://itsiastic.wordpress.com/2013/08/15/algorithms-design-chapter-2-exercise-8/
it's the nth root you fucking moron, this is a classic question in alg design courses.

also learn english if you're gonna post here, I don't know what the fuck 'root of the sum quadratic' even means you god damn mongoloid
>>
>>69768763
The question in the blog you linked is finding a solution that is sublinear, nth root satisfies that okay but it is not optimal.
It should be red flag that you jump even steps because it makes number of steps to find floor uneven depending on where it is. You should reduce step size by one every time you go up. How to find optimal size?
Well if we reduce by one it is sum 1+2+...=n(n+1)/2=100 so solution is solve for root of this quadratic.
It will do better than nth root strategy on 100 floors with two eggs.
>>
>>69768818
Even if your alg is correct (which I doubt) your explanation is so incoherent I can't even begin to deduce your methodology. Until you can actually explain what the fuck your talking about, I have an O(n^1/2) alg and you have jibberish.
>>
>>69768900
Your strategy is go up by sqrt(n) then when break test the remaining interval correct?
>>
File deleted.
from irrelevant_library import anagram

Where's my $300k?
>>
File: 1548073649125.jpg (62 KB, 640x640)
62 KB
62 KB JPG
>>69768900
class Floors(object):
def __init__(self, break_height):
self.break_height = break_height
self.drop_counter = 0

def drop(self, floor):
self.drop_counter += 1
if floor < self.break_height:
return False
return True

def anon(floors):
step = 10
safe = 0
trial = step
while not floors.drop(trial):
safe = trial
trial += step
for i in range(safe+1, trial):
if floors.drop(i):
return i
return trial

def me(floors):
step = 14
safe = 0
trial = step
while not floors.drop(trial):
safe = trial
step -= 1
trial += step
for i in range(safe+1, trial):
if floors.drop(i):
return i
return trial

def run_tests(strategy):
results = []
for i in range(1,101):
test = Floors(i)
solution = strategy(test)
if solution != i:
print("Incorrect!", i)
break
else:
results.append(test.drop_counter)
return results

print("Anon's worst case:", max(run_tests(anon)))
print("My worst case:", max(run_tests(me)))

result
Anon's worst case: 19
My worst case: 14
>>
>>69767199
Obligatory fagJS solution. It could probably be written more efficiently, but it doesn't break the 'no functions' rule.
function isAna(a,b) {
if (a.length !== b.length) return false;
var ca = {}, cb = {};
for (var i = 0; i < a.length; i++) ca[a[i]] = ca[a[i]] ? ++ca[a[i]] : 1; // use .charAt instead
for (var i = 0; i < b.length; i++) cb[b[i]] = cb[b[i]] ? ++cb[b[i]] : 1; // replace this with a function instead of repeating ourselves
for (c in ca) if (ca[c] !== cb[c]) return false;
return true;
}
>>
>>69767900
This, though first I'd compare length and quit if they're different sizes.
>>
noob C solution to see if two strings are an anagram, I used strlen I mean I could write a for that give me that number but I decided to use it instead.

#include<stdio.h>
#include<string.h>

#define MAXSTR 50
#define TOTALCHAR 256
enum anagram {NOT_ANAGRAM, ANAGRAM};

int isAnagram(char sample1[], char sample2[]);

int main(){

char sample1[TOTALCHAR];
char sample2[TOTALCHAR];

// initialize samples
int i;
for(i = 0; i < TOTALCHAR; ++i){
sample1[i] = 0;
sample2[i] = 0;
}

char string1[MAXSTR] = "aabb";
char string2[MAXSTR] = "baba";

// increment char positions in samples
for(i = 0; i < strlen(string1); ++i)
++sample1[string1[i]];

for(i = 0; i < strlen(string2); ++i)
++sample2[string2[i]];

if(isAnagram(sample1, sample2))
printf("The two words are an anagram.\n");
else
printf("The two words are not an anagram.\n");
}

int isAnagram(char sample1[], char sample2[]){

int i;
for(i = 0; i < TOTALCHAR; ++i)
if(sample1[i] != sample2[i])
return NOT_ANAGRAM;
return ANAGRAM;
}
>>
>>69767199
import sys

def is_anagram(x, y):
return sorted(x) == sorted(y)

def main():
print(is_anagram(*sys.argv[1:3]))

if __name__ == '__main__':
main()
>>
File: autism speaks.jpg (67 KB, 711x711)
67 KB
67 KB JPG
a, b = 'anagram', 'gramana'
c = [char for char in a]
for char in b:
try:
c.remove(char)
except ValueError:
c.append(420)
if not c:
print('is anagram')
else:
print('not an anagram')
>>
>>69769788


>c = [char for char in a]
`c = list(a)`
>>
>>69767915
I don't think I'd enjoy working for your company as I don't particularily enjoy writing quicksort for character arrays every day.
>>
>>69768377
For 3 i'm getting 0.038095 by direct calculation and approximately by trial.
>>
>>69768377
The egg one is really cool. Conventional wisdom says binary search, but it's obviously wrong. Next you'd think the root is the best increment, however this means you need 18 drops in the worst case, so you're better off dropping a larger number of floors on the first drop. I don't have paper in front of me, but I'm thinking start at 14th or 15th floor, then reduce by 1 per drop
>>
File: patrick.png (231 KB, 500x365)
231 KB
231 KB PNG
>>69768377
I think I have figured out #2.
For an NxN grid, consider a new grid where each cell is 3x3 (so a (N/3)x(N/3) grid. We can explore one point on this new grid, which will either be a local minimum, or have it's lowest point at one of the edges. So a point is assigned a value and a direction.

Next, "split" the grid in two by exploring the points in the middle. Either we find a minium, or we find which point was lowest and consequently it's "direction". Next split the rectangle the direction arrow points at. We have now narrowed down the area which a minimum must be located at to one of the four quadrants. Since n + n/2 + n/4 ... = 2n this approach is also O(n)

r8
>>
>>69768377

>>69769941
>>69770342
here, reporting my progress on 3:
I'm currently considering the base cases [0, {1, N}] and seeing how many ways I can build each back to some [M,N] case.
>>
>>69768377
Since 2 is only asking for the local minimum the answer is greedy gradient descent.
>>
>>69770443
Consider the case where the "path" towards the minimun is a spiral.
>>
>>69767199
list1, list2 = string1, string2 as Lists
i = 0
while i < len1.length() {
j = list2.index_of(list1[i])
if j != -1 {
list1.delete(i)
list2.delete(j)
} else {
i = i + 1
}
}
if list1.length() == 0 and list2.length() == 0 {
print("anagram")
}
>>
>>69770548
made a typo
list1.lenght()
>>
>>69768377
So the furthest I get on 3 is to create the lattice, then start at the top and enumerate the probability of each state in a BFS fashion. I can't really reduce it further than that.

The value of lattice point [M,N] is P([M,N] | [M+1, N]) * P([M+1, N] | [M+1, N+1]) +
P([M,N] | [M,N+1]) * P([M,N+1] | [M+1,N+1])

so you can see why I need to implicitly memoize it using my lattice structure.
>>
>>69768083
See >>69767915
>>
>>69768172
The best solution so far
>>
bool is_anagram(const char* a, const char* b) {
int count[256]{};

int i{ 0 };
while (a[i] && b[i]) {
count[static_cast<unsigned int>(a[i])]++;
count[static_cast<unsigned int>(b[i])]--;
i++;
}

if (a[i] || b[i])
return false;

for (i = 0; i < 256; i++)
if (count[i]) return false;

return true;
}

int main()
{
char a[]{ "-öasニdfg" };
char b[]{ "gfニaö-sd" };

return !is_anagram(a, b);
}


This can have false positives with Unicode, since UTF8 characters can span multiple bytes, and this only checks if it's an anagram in terms of bytes.

For example, these charcaters are UTF8 byte anagrams:
>か (b'\xe3\x81\x8b')
> (b'\xe3\x8b\x81')

It's not terribly difficult to do this with proper UTF8 support, but not without a hash map, because obviously a count array is out of question, when one character can span up to 4 bytes. However, hash map is a bit too complicated of a data structure to implement from scratch for a problem like this.

Here's UTF8 compatible anagram checker without OP's constraints:
bool is_anagram_utf8(const char* a, const char* b) {
if (strlen(a) != strlen(b))
return false;

std::unordered_map<uint32_t, int> count;

auto n_bytes = [](char c){
return ((c & 0b1110'0000) == 0b1100'0000) ? 2 :
((c & 0b1111'0000) == 0b1110'0000) ? 3 :
((c & 0b1111'1000) == 0b1111'0000) ? 4 :
1;
};

auto codepoint = [](const char* str, char len){
uint32_t c{ 0 };
memcpy(&c, str, len);
return c;
};

int i{ 0 };
while (a[i]) {
int n{ n_bytes(a[i]) };
count[codepoint(a + i, n)]++;
i += n;
}

i = 0;
while (b[i]) {
int n{ n_bytes(b[i]) };
count[codepoint(b + i, n)]--;
i += n;
}

for (const auto& [str, c] : count)
if (c) return false;

return true;
}


Using memcpy here is arguably maybe a bit dirty, but it's better than std::string. Also, it's not safe code. It could try to access out of bounds, if the string is not correct UTF8.
>>
typedef unsigned char uchar;

int
anagram(char *s1, char *s2)
{
unsigned h1, h2;
uchar *s;
s = (uchar *)s1;
for (h1 = 0; *s; s++)
h1 += *s;
s = (uchar *)s2;
for (h2 = 0; *s; s++)
h2 += *s;
return h1 == h2;
}
>>
. >>69770756

I even sketched up a program. Dunno if it runs correctly, but I'm fairly sure it's the correct thought process.

object thingy {
case class Node(p: Double, red: Int, blue: Int){
val pRed = (red.toDouble/(red.toDouble + blue.toDouble))
val pBlue = 1.0 - pRed

val pTakeBlue = pBlue*pBlue
val pTakeRed = 1.0 - pTakeBlue
}

def buildLayer(nodes: List[Node]): List[Node] = {
val leftmost = Node(
nodes.head.pTakeRed,
nodes.head.red - 1,
nodes.head.blue)

val rightmost = Node(
nodes.last.pTakeBlue,
nodes.last.red,
nodes.last.blue - 1)

leftmost ::
(nodes zip nodes.tail).map{ case(left, right) =>
val nextRed = left.red
val nextBlue = left.blue - 1
val pFromLeft = left.p*left.pTakeBlue
val pFromRight = right.p*right.pTakeRed
Node(pFromLeft + pFromRight, nextRed, nextBlue)
}
::: List(rightmost)
}

def buildLayers(reds: Int, blues: Int): (Node, Node) = {
val finalLayer = (0 until reds + blues).foldLeft( List(Node(1.0, reds, blues)) ){ case(prev, _) =>
buildLayer(prev)
}

(finalLayer.filter(n => (n.red == 0)).head, finalLayer.filter(n => (n.blue == 0)).head)
}

// Leave the rest as exercise to the reader
}
>>
>>69770870
It seems like it dropped the other Unicode character. It should look like 2月 combined into one character. You can see it by running this in Python:
>b'\xe3\x8b\x81'.decode("utf-8")

Also, I included a few brain farts like "char len".

>>69768377
1. Start by dropping the first egg from 14th floor, then reduce the spacing by 1 each time, so you go like this:
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

If the egg breaks, start from the previous safe floor and check every floor. This way the worst case scenario is 14 drops. The average is 9.47.

As you can see, there's a little bit of leeway at the end, so it can be changed slightly. I'm not sure what the optimal is, but I'm getting 9.45 average with this:
14, 27, 39, 50, 60, 69, 77, 83, 88, 92, 96, 98, 100

#include <fmt/core.h>
#include <array>
#include <vector>
#include <algorithm>
#include <numeric>

int test(const std::vector<int>& test_floors, int break_point) {
int n{ 0 };
int safe{ 0 };
for (auto floor : test_floors) {
n++;
if (floor >= break_point) {
for (int f{ safe + 1 }; f < break_point; f++)
n++;
return n;
} else {
safe = floor;
}
}
fmt::print("test_floors should include 100!\n");
exit(1);
}

int main()
{
std::array<int, 100> n_drops;

std::vector test_floors{
14, 27, 39, 50, 60, 69, 77, 83, 88, 92, 96, 98
//14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100
//10, 20, 30, 40, 50, 60, 70, 80, 90, 100
};

for (int floor{ 1 }; floor <= 100; floor++) {
n_drops[floor - 1] = test(test_floors, floor);
}

auto max{ std::max_element(n_drops.begin(), n_drops.end()) };
fmt::print("Max: {}\n", *max);

auto avg{ std::reduce(n_drops.begin(), n_drops.end()) / 100.0 };
fmt::print("Average: {}\n", avg);
}
>>
280 byte elf
unicode is for niggers
# palindrome.s

# Checks if an ascii string is a palindrome.
#
# Usage:
# palindrome <string>


.equ ARGC, 0
.equ ARGV_1, 8
.equ EXIT_SUCCESS, 0 # not used; for completeness
.equ EXIT_FAILURE, 1
.equ SYS_EXIT, 1
.macro SYSCALL
int $0x80
.endm

.section .text
.globl _start
_start:
movl ARGC(%esp), %eax # check for no input
cmpl $1, %eax
jna exit_failure

movl ARGV_1(%esp), %esi
xorl %ecx, %ecx
decl %ecx
loop1:
incl %ecx
movb (%ecx, %esi, 1), %al
testb %al, %al # check for null byte
jnz loop1

xorl %ebx, %ebx
decl %ebx
loop2:
incl %ebx
decl %ecx
cmpl %ecx, %ebx
jge exit_success
movb (%ebx, %esi, 1), %al
movb (%ecx, %esi, 1), %dl
cmpb %dl, %al
je loop2

exit_failure:
movl $EXIT_FAILURE, %ebx
jmp 1f
exit_success:
xorl %ebx, %ebx # $EXIT_SUCCESS
1: movl $SYS_EXIT, %eax
SYSCALL
>>
>>69767199
>translate every letter to the first 26 prime numbers. eg a->2, b->3, c->5 etc.
>Multiply all the numbers for a given word together.
>Repeat for second word
>Compare Values.
This is an O(n) solution.
>>
>>69771724
Multiplication is actually not O(n) where n is size in bits.
>>
>>69767199
def anagram(a, b):
return sorted(a) == sorted(b)


>wow that was hard
>>
>>69767199
Just count the numbers. Best solution coming through.
function anagram(w1, w2){
const chrs = {}
for(c of w1) chrs[c] = (chrs[c] || 0) + 1;
for(c of w2) chrs[c] = (chrs[c] || 0) - 1;
return chrs.every(c => c === 0);
}

>>69772142
That's not O(n).
>>
>>69767199
>tal tells whereas a word
I dial 911 and explain that that someone is having a stroke at $office_building in $room.
>>
>all the nlogn slowlets
>>
File: 07urk85p4ja11.jpg (38 KB, 432x767)
38 KB
38 KB JPG
>>69774067
let's see you take on these dubs then >>69768377
>>
>>69772142
>don't use any special library or function except for the ones that let you read and print data
imagine being so smug yet so fucking incompetent
>>
>>69774532
While you're right, I'd like to interject for a moment and say that any interview that doesn't allow me to use sort unless they're explicitly asking me to implement some sorting algo can get FUCKED
>>
>>69767199
Everyone's already done it by sorting so here's a stupid implementation for shits 'n' g's

#include <iostream>

using namespace std;

inline char upper(char c)
{ return (c < 'a' || c > 'z') ? c : c + ('A' - 'a'); }

struct Signature
{
public:
Signature(const string& s): _sig{}
{
for (char c : s)
{
if ((c = upper(c)) < 'A' || c > 'Z') continue;
++_sig[c - 'A'];
}
}

bool operator== (const Signature& s)
{
for (unsigned int i = 0; i < 26; ++i)
if (_sig[i] != s._sig[i]) return false;

return true;
}

string::size_type _sig[26];
};

int main()
{
cout << (Signature("abba") == Signature("bbaa")) << endl;
cout << (Signature("hello") == Signature("bbaa")) << endl;
return 0;
}
>>
>>69768377
1) Binary search.

2) Just find the lowest number in the grid, if they're all distinct numbers then the lowest number will be a local minimum won't it?

3) Assuming you can't get the same ball straight back again after putting the blue ball back in, and the balls are chosen at random, then 100%. After randomly picking balls, eventually you'll end up in a scenario where you've got only 1 blue ball left. Every time you pick it, you'll put it back in, and every time you pick a red ball, you'll discard it. Eventually this blue ball will be your last one. This happens no matter what order you pick balls in.
>>
>>69767199
I would just walk out at that point because if their interview process is based on these 5 IQ tier questions then it would mean that all my coworkers would be braindead onions retards so no thanks
>>
>>69775868
>binary search

100 floors.
Drop egg from 50th floor -> breaks
Drop egg from 25th floor -> breaks

You're out of eggs, what's the exact lowest floor the egg breaks from again?
>>
>>69767334
He's saying don't use "sort" dumbass.
>>
>>69775934
Correction: s/sort/filter/
>>
>>69775868
>Assuming you can't get the same ball straight back again after putting the blue ball back in

You can, that's the whole problem.
And here I was wondering why everyone was complaining about not getting offers while I passed every interview.
>>
>>69775868
>Just find the lowest number in the grid
WOW
>>
File: 1549120181336.jpg (42 KB, 1280x720)
42 KB
42 KB JPG
>>69775868
1. Wrong
2. Wrong
3. Wrong
>>
>>69768083
not even len? Wtf kys what kind of shitty interview is this. I've interviewed for companies asking awful arbitrary questions and even they allowed shit like sort
>>
>>69776337
Is dis CSbabby for real
>>
>>69768265
Topkek this is nice
>>
>>69767199
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0fad052289b61188fe091cbcdd7cee61

And if anyone says "you can't use btreemaps" but defends named dictionaries in another language just because they are built into the language syntax, then fuck off.
>>
>>69775868

>Binary search
You only have two eggs

>Lowest number in the grid
Takes O(n^2) time. This would find a global minimum, but we only need a local minimum.

>Assuming that can't...
No such assumption can be made.



Delete Post: [File Only] Style:
[Disable Mobile View / Use Desktop Site]

[Enable Mobile View / Use Mobile Site]

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.