Ok, user

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

>.remove
Failed.

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.

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.

And since we can use data structures but not sort, put the chars in a heap and compare as you pop. (java.util.PriorityQueue for example)

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

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

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

toCharArray is a function though.

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
}

Attached: koume.jpg (1280x720, 108K)

No interviewer ever talks like this

are you retarded?
literally everything is a function
declaring a variable? that a motherfucking function
>oh but user there no () on it
>what an alias?
>whats syntactical sugar?

function anagrams(stringA, stringB) {
return cleanString(stringA) === cleanString(stringB);
}

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

>.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;
}

>

user, 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.

Forgot to fix some variable names but you get the idea

So you're saying you can't do it?

I'm too lazy to verify if this works, but it looks complicated and I don't see any functions. You're hired.

>*blocks your path*

Attached: 250px-Unicode_logo.svg.png (250x270, 11K)

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?

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

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

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

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

module Anagram
def anagram?(other)
return self.chars.tally == other.chars.tally
end
end

class String
include Anagram
end

Attached: :^).gif (255x255, 546K)

Instead of using a hash I wonder if could use a couple longs to store the counts for most words.

>uses ord
>uses len

simple and functional enough,

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.

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
I thought we had to find all anagrams in a word list.

Just bubble sort both, then compare.

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 :^)

>Okay now that we've done the warm-up let's move on to the real problems

Attached: 1528678312193.png (851x846, 573K)

test [\code]

#include

int main(int argc, char **argv)
{
char c[2][26] = {0};
for (int i = 1; i

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;

K&R chapter 1 tier, not even worth the effort

*
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;

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%

Yes I can, but your weird function rules are stupid so I will not.

Bitch I own my own software how the fuck did you get in here?

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

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
}

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.

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

>Not O(n).
prove it.
worst case is at lease less than O(n^2)

0/3

Attached: 1525250310629.jpg (800x576, 54K)

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

What language is this thing?

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.

i.e. you have n follow the min paths running, deleting repeat paths.

while I see what they're asking now for 2, I know for a fact 1 and 3 are right you idiot weeb

this is how you tell that getting this job is not worth it

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.

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

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.

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.

Your strategy is go up by sqrt(n) then when break test the remaining interval correct?

from irrelevant_library import anagram
Where's my $300k?

Attached: dabbin on dem jannies.gif (554x400, 120K)

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 user(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("user's worst case:", max(run_tests(user)))
print("My worst case:", max(run_tests(me)))

result
user's worst case: 19
My worst case: 14

Attached: 1548073649125.jpg (640x640, 62K)

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

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
#include

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

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()

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')

Attached: autism speaks.jpg (711x711, 67K)

>c = [char for char in a]
`c = list(a)`

I don't think I'd enjoy working for your company as I don't particularily enjoy writing quicksort for character arrays every day.

For 3 i'm getting 0.038095 by direct calculation and approximately by trial.

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

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

Attached: patrick.png (500x365, 231K)

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.

Since 2 is only asking for the local minimum the answer is greedy gradient descent.

Consider the case where the "path" towards the minimun is a spiral.

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")
}

made a typo
list1.lenght()

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.

See

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(a[i])]++;
count[static_cast(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 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;
}

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