Open Side Menu Go to the Top
Register
Interview  Test Questions Problems, Solutions, Links, Discussion Interview  Test Questions Problems, Solutions, Links, Discussion

08-25-2016 , 10:07 PM
Quote:
Originally Posted by ddubois
I did and wasn't able to find out how, although maybe my Google Fu was deficient.
https://en.wikipedia.org/wiki/Logarithm#Calculation
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
08-26-2016 , 01:14 AM
Quote:
Originally Posted by Victor
well, if you have the opportunity to research then fine, but I doubt many ppl know the equation to calculate a logarithm off hand.
If you went to college and got a CS degree and don't know what a logarithm is, you either cheated on every course from CS 101 and Calculus on up, or your school is running a massive education scam and the entire staff should be sent to prison. Log2 is so fundamental to CS that the study couldn't exist without it.

The research is literally clicking the first random search result:

given a^x = b, solve for x. This is translated to log_a (b) = x.

For example, log2(8) = x translates to 2^x = 8, which means x = 3.

Even if you know nothing about logarithms, you can deduce a few facts. To keep it simple, we'll assume the base is a positive integer greater than 1.

-- x = 0 if and only if b = 1.
This follows from n^0 = 1

-- if b = a; x = 1
2^1 = 2. This is an inflection point.

-- if b is a fraction, x must be negative.
This follows from 2^-1 = 1/2.

Using this inflection point, we can deduce:
-- if b = a; x = 1
-- if b > a; x > 1
-- if b < a; x < 1

we now have some lower bounds, but before continuing, we can see a relationship here:
-- if x^1 = 1/x, then it stands to reason that, if b < 1, we can compute the reciprocal of b and change x to negative.

if log2(32) = 5, then log(1/32) = -5.

now for an upper bound. We know that x can't be greater than b if b > 1. In fact, the upper bound is going to be smaller than b, perhaps much smaller, but let's just assume we can go up to one infinitesimal pip below b.

With the above facts in place, creating a log calculator isn't that difficult. In fact, we already divided the space with the reciprocal statement, but we can divide the space to smaller segments by using the bisection method, fixed point methods, Newton's method, etc. (I'd probably look for a Taylor series, but at a white board, I'd just go along with the bisection method).

Kind of ironic, because the bisection method is logarithmic, so we end up using log to solve log.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
08-26-2016 , 08:58 AM
like I said, I dont think most ppl would know how to solve a logarithm without looking it up.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
08-26-2016 , 09:50 AM
Quote:
Originally Posted by daveT
If you went to college and got a CS degree and don't know what a logarithm is, you either cheated on every course from CS 101 and Calculus on up, or your school is running a massive education scam and the entire staff should be sent to prison. Log2 is so fundamental to CS that the study couldn't exist without it.
I think this is not something that would be fresh in my mind during an interview, and a question like that would have thrown me off. More than likely I'd ask them to confirm the equation for solving a logarithm, and then I'd go from there. In general it's an obnoxious question because you're going to make most people feel self-conscious or embarrassed, and they're not going to be thinking clearly for the rest of the interview.

Depending on what you're trying to get out of the question, you could either begin it with "This is how you'd write an equation to solve a Logarithm. Write a program to do this." Or if you want to make sure they understand the idea of logarithms, you could just ask "Why are logarithms important?"
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
08-26-2016 , 03:51 PM
What I did wasn't magic at all. I only know what a log is and I know any continuous function can be bisected. The deductions were created without looking up any other information. Of course, there are better ways of coming up with a solver, but it was what I came up with the goal of bisecting specifically log.

Regardless of the equation you are given, as long as it is continuous, you can solve it all with the same logic geared to bisection. You can do it with x^3 and you can do it with log. Of course, doing all of this by hand like that is tedious and it is better to find something more general.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
08-26-2016 , 03:59 PM
Well I mean truly all the stuff daveT mentioned is superfluous, you can just solve the whole thing with bisection as long as you know that
y = log_10(x)
also means
10^y = x
and if you don't know that, then you don't know what a log is
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
08-27-2016 , 03:47 AM
Yeah, it was way superfluous, but I enjoy splashing around with stuff and seeing where it goes, hoping for some insight, but nothing much happened that time (plus my learning style is derivation-based, so kind of roundabout at times).
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
08-28-2016 , 04:09 PM
Quote:
Originally Posted by daveT
-- a function random_nums(M, N).
M - quantity of random numbers to return
N - all generated random numbers must be less than N
each generated number should be unique.

I didn't think this one was too hard, but it's possible my solution wasn't super efficient? I just added a random integer to a set until the len(set) = M.
If M << N, then what you have is fine. However, if you are trying to generate nonnegative integers and M is large then your algorithm is pretty slow, say with M=N average-time around O(M ln(M)), compared with O(M). (Expected number of random calls needed to generate the k-th random number is N/(N-k+1).)

As an alternative: shuffle the range with an efficient algorithm and just stop after you have the first M integers, something like this for example might be the best.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
08-29-2016 , 04:22 AM
Ah yes, there was the first and the second variation on that. I suppose I could have generated an array of numbers and shuffled, but I wasn't sure what to make of the fact that there was a second variation on the theme. I may have shuffled the second variation, but not entirely sure what I did without looking it up.

I suppose another approach is to generate the array and grab a a randint up to range(array), then pop from A and insert into B until len(B) == M? On the outside, it looks pretty expensive, but knowing that Python has a meta tag on len(array), it would probably be fast, yeah? Sometimes, I'm really not sure what these are calling for. Is it okay to use shuffle() or do I have to make my own Fisher-Yates?
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
08-29-2016 , 04:24 AM
and, for anyone wondering about the log() algorithm using bisection, here is my little version:

Spoiler:
Code:
def log(base, n):
    high = n
    low = 0
    guess = n / 2
    epsilon = 0.005
    cnt = 0
    while cnt <= 100:
        r = base**guess
        if abs(r - n) < epsilon:
            return guess
        if r > n:
            high = guess
        if r < n:
            low = guess
        cnt += 1
        guess = (low + high) / 2
    return guess

for i in range(2, 17):
    print(i, "=", log(2, i))

>>> 2 = 1.0
3 = 1.5849609375
4 = 2.0
5 = 2.32177734375
6 = 2.583984375
7 = 2.807861328125
8 = 3.0
9 = 3.170654296875
10 = 3.321533203125
11 = 3.458984375
12 = 3.58447265625
13 = 3.70068359375
14 = 3.8076171875
15 = 3.90655517578125
16 = 4.0


It works for N < 1 as well, without all of the superfluous fluff.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
08-29-2016 , 06:28 PM
Quote:
Originally Posted by daveT
Ah yes, there was the first and the second variation on that. I suppose I could have generated an array of numbers and shuffled, but I wasn't sure what to make of the fact that there was a second variation on the theme. I may have shuffled the second variation, but not entirely sure what I did without looking it up.
Yeah, you can reduce the second problem to the first, as you say, randomizing the indices, but you can also shuffle "incrementally" from an arbitrary source (there's an example of this is in the wiki) which is what you want here.

Quote:
Sometimes, I'm really not sure what these are calling for. Is it okay to use shuffle() or do I have to make my own Fisher-Yates?
I think it's OK to ask. If I were the interviewer, I'd point out that, shuffle isn't great when M << N but saying "this is in the standard library" is always a fine way to start as long as you're willing to roll your own when asked.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
08-29-2016 , 08:55 PM
I liked the like the link you provided. Find that stuff fascinating. For some reason, I never looked at shuffling algorithms. I've been implementing them.

What I was meaning was in the context of a take home test, where I'm not able to ask questions. In theory, I could create my own of random() as well (well, look up the Knuth version) .
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
08-29-2016 , 11:17 PM
Took the google online screening test this past Friday. They have their own coding platform that is similar to hacker rank.

Two questions, first one was somewhat easy but I spent too much time on it (40 mins), leaving me only 20 mins for the 2nd one which was harder.

Anyways, I got the first one right but didn't manage to finish the second. However I still got an email from a recruiter today for a follow up chat.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
08-30-2016 , 12:13 PM
Quote:
Originally Posted by Barrin6
Took the google online screening test this past Friday. They have their own coding platform that is similar to hacker rank.

Two questions, first one was somewhat easy but I spent too much time on it (40 mins), leaving me only 20 mins for the 2nd one which was harder.

Anyways, I got the first one right but didn't manage to finish the second. However I still got an email from a recruiter today for a follow up chat.
Congrats! Good luck.

Sent from my SM-G900R4 using Tapatalk
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-08-2016 , 12:53 PM
Just did an Amazon coding and logic test a few days ago. The coding test requires you to read code and fix a bug that was usually one line of code. That part was stupid easy. Unfortunately the second part, the reasoning portion for me was hard. The reasoning questions were equivalent to logic questions you would see on the SATs. Didn't manage time well and ended up having to guess on many of them. Got the rejection email 2 days later :/
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-08-2016 , 02:51 PM
Quote:
Originally Posted by Barrin6
Just did an Amazon coding and logic test a few days ago. The coding test requires you to read code and fix a bug that was usually one line of code. That part was stupid easy. Unfortunately the second part, the reasoning portion for me was hard. The reasoning questions were equivalent to logic questions you would see on the SATs. Didn't manage time well and ended up having to guess on many of them. Got the rejection email 2 days later :/
Hiring process is a long drawn out one is my understanding at Amazon. Are you interested in working in the Seattle area?
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-08-2016 , 11:34 PM
No not at all. My plan is to try to get experience interviewing and also using other offers as leverage for negotiation.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-14-2016 , 09:01 PM
I tried something a little new last week. I applied for a place, then, for the first time ever, sent a follow up email saying that I thought the startup idea was really cool, etc. It actually worked and I had a phone call the other day.

To be sure, I really was (still am) impressed by this particular company, so the follow up wasn't an experiment. I did mention that I seldom do something like that, had my reasons for wanting to work with the company, why I liked the idea, my impression of the founders, etc.

I didn't get the impression that I am an odds favorite for this company, but keeping my fingers crossed. I never want to get a rejection email, but this time, I'm sort of wishing that, if I'm getting the "no," it would come now and not next week.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 03:31 AM
given this matrix:

Code:
1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16
17 18 19 20
generate this output

Code:
1 2 3 4 8 12 16 20 19 18 17 13 9 5 6 7 11 15 14 10
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 11:12 AM
Written in C - It compiles but couldn't test it due to the environment I'm in. I believe this will work for any size matrix:

Spoiler:
Code:
#define X_SZE 4
#define Y_SZE 5

const int matrix[Y_SZE][X_SZE] = {1,  2,  3,  4,
				  5,  6,  7,  8,
				  9,  10, 11, 12,
				  13, 14, 15, 16,
				  17, 18, 19, 20};

void spiral(void)
{
  int i, dir, x_min, y_min = 0;
  int x_max = X_SZE-1;
  int y_max = Y_SZE-1;

  while((x_min <= x_max) && (y_min <= y_max))
    {
      switch(dir%4)
	{
	case 0:
	  for(i=x_min;i<=x_max;i++)
	    printf("%d ", matrix[y_min][i]);
	  y_min++;
	  break;
	case 1:
	  for(i=y_min;i<=y_max;i++)
	    printf("%d ", matrix[i][x_max]);
	  x_max--;
	  break;
	case 2:
	  for(i=x_max;i>=x_min;i--)
	    printf("%d ", matrix[y_max][i]);
	  y_max--;
	  break;
	case 3:
	  for(i=y_max;i>=y_min;i--)
	    printf("%d ", matrix[i][x_min]);
	  x_min++;
	  break;
	default:
	  printf("Error!");
	  break;
	}
      dir++;
    }
}

Last edited by Lattimer; 09-20-2016 at 11:41 AM.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 12:24 PM
meh, rows and cols would've been better than x and y, but whatever
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 01:57 PM
My solution in python:

Spoiler:
Code:
def spiral(A):
    _spiral(A,"")

def _spiral(A,string):
    for j in range(len(A[0])):
        string += str(A[0][j]) + ' '

    for i in range(1,len(A)):
        string += str(A[i][len(A[0]) - 1]) + ' '

    for j in reversed(range(len(A[0]) - 1)):
        string += str(A[len(A) - 1][j]) + ' '

    for i in reversed(range(1,len(A) - 1)):
        string += str(A[i][0]) + ' '

    if (len(A) > 2) and (len(A[0]) > 2):
        _spiral([x[1:len(A[0]) - 1] for x in A[1:len(A) - 1]],string)
    else:
        print(string)
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 02:39 PM
Here's my solution in JS:

Spoiler:
I basically output the first row of the matrix, then remove the row, then rotate the matrix counter-clockwise. Repeat until the matrix is gone.

Code:
let matrix = [
[1,  2,  3,  4],
[5,  6,  7,  8],
[9, 10, 11, 12],
[13, 14, 15, 16],
[17, 18, 19, 20]];

const output = [];
while (matrix.length) {
  matrix[0].map(val => { output.push(val); }); 
  matrix.shift();
  if (matrix.length) matrix = rotateCounterClockwise(matrix);
}

console.log(output);

function rotateCounterClockwise(array) {
  const rightColIndex = array[0].length-1;
  return array[0].map((col, i) => { 
    return array.map(row => { return row[rightColIndex-i]; });
  });
}
Not sure what the rules are about googling. I had to google a transpose function, then adapt it to rotate counter-clockwise instead. That one would have taken me a lot longer to work out on my own. Also of course i had to google shift() to remove the first row of the array. I never remember that stuff.

But either way I could have talked through exactly what I was trying to do while I tried to get my rotate function working.

Last edited by suzzer99; 09-20-2016 at 02:44 PM.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 03:05 PM
Fun fact you don't need let for that array, let is only for vars you want to reassign or increment (same thing), array mutation is not that. OK not so fun fact.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote
09-20-2016 , 03:07 PM
Notice I am reassigning. I had const but it complained.
Interview  Test Questions Problems, Solutions, Links, Discussion Quote

      
m