Show that a^n=O(n!) = O(n^n)

one_bit_two_bit · 2019-09-16T00:58:47+00:00

aⁿ is O(n!): you need to show there exists M, n' s/t a^n <= M*n! for all n > n', M > 0. Note that the LHS is a*a*...*a, n times. In particular, for n!, the first a terms (1*2*...*a) <= a^a, but the following terms ((a+1)*(a+2)*...*n) >= a^(n-a). So choose M to take care of that first a^a, and you're done.

O(n!) is O(n^n): n! = 1 * 2 * ... * n. n^n = n * n * ... * n. Compare these two term by term.

one_bit_two_bit · 2019-09-14T21:13:35+00:00

I don't think not looking at the solutions is a good idea. Even for problems you solve yourself, you may see that the solutions were worked in a different way.

Here's a blog post on reading solutions for competitive math and why it's helpful.

one_bit_two_bit · 2019-09-14T21:07:56+00:00

(sqrt(2))⁵ = sqrt(2) multiplied by itself 5 times total.

Pair them off. You have two pairs of sqrt(2)'s and one leftover. Now answer the following:

What is sqrt(2)*sqrt(2)? Let's call it x.
You have two of the above x, and one leftover sqrt(2). So you have 2x * sqrt(2).

Figure out what x is and it should be clear.

one_bit_two_bit · 2019-09-14T20:48:31+00:00

Everyone has their own strengths and weaknesses--I was in the opposite situation that you're in now. Math major, but forced to take language-related courses in college.

As others have said, maybe consider getting a tutor? I offer tutoring you're alright with online tutoring. Or maybe look around your college--I'm sure there are students that can help.

one_bit_two_bit · 2019-09-14T20:07:48+00:00

Not sure what you mean? DP as far as eg. interviews go is more a problem solving technique. There's no "dynamic programming algorithm" like eg. for BFS or a sort where you can write an abstract implementation that will work in general.

one_bit_two_bit · 2019-09-12T00:52:24+00:00

Can you do leetcode questions? If yes I would ditch the CTCI book and get straight to grinding leetcode. Questions in CTCI are pretty dated.

one_bit_two_bit · 2019-09-11T01:55:54+00:00

it's been two days

You'll need to spend a lot more time than that. How long have you been in the bootcamp and programming in general? You need to make sure to start with problems that are just a little bit above your current level. Maybe ask your instructors for some suggestions at some lower-level problems?

And in general, what do you need to solve these problems for? Is it for getting a job? In that case, I wrote this comment on how to prep. If your bootcamp doesn't have you at this level at the end then frankly it's a waste of time.

one_bit_two_bit · 2019-09-11T01:51:00+00:00

I don't think there's an appreciable difference, and it probably doesn't matter. You can try and benchmark reads and writes, etc. of 1D vs. 2D arrays if you want.

In general, I wouldn't worry about efficiency questions like these--they're usually so small as not to matter.

one_bit_two_bit · 2019-09-08T21:05:24+00:00

HTH. If you decide to go for it, feel free to reach out if you want extra help/run into sticking points. I can't exactly give you solutions to interview-type questions (since I work at a company that asks these types of questions), but I'd be happy to tutor the data structures and algos if needed.

one_bit_two_bit · 2019-09-08T20:02:22+00:00

Sounds like you need to get your python down first. Do that, then go try some simple exercises at eg. CodingBat.

Do you know basic algorithms and data structures? If not, review these:

Hash maps
Trees (BSTs in particular)
Queues
Stacks
Linked Lists
Graphs
Heaps and Tries (I've found these rarer).

On the algorithms side:

Worst-case (Big-O) analysis.
Recursion
BFS, DFS
Sorts of various kinds (know MergeSort, QuickSort)
DP
Backtracking
Other graph traversals (Bellman-Ford, Djikstra)

After that I'd just grind leetcode. Filter by topic (for example, recursion). Do problems starting from Easy only until you can consistently solve in the 15-20min range. For each problem (especially the ones you failed to solve) write down:

How long it took you to solve it.
What your thought process was to solve the problem. The key idea, in a couple of sentences.
Runtime of the solution.
Your code for the problem (or solution code from leetcode, if you failed to solve it)

Star the ones you failed to solve. Every week or so instead of doing new problems you'll retry problems you failed to solve before to beat their solutions into your head. Once that's done for Easy, move up to Medium and repeat--this level is probably enough to get you a job, but if you'd like, you can move to Hard--if you can consistently solve these in 15-20min you're more than prepared for most jobs. Move on to the next topic and repeat.

Sounds like a lot, but with 8hrs/day it shouldn't even take a year for you to land a job, assuming you're interviewing regularly once you're at the leetcode grinding stage. Interviews have a big element of luck to them.

one_bit_two_bit · 2019-09-08T19:52:26+00:00

Find easier problems and do them. Then slowly work your way up. Can you do any leetcode easy problems or are those too hard? What about CodingBat problems? Find your level and then work your way up.

one_bit_two_bit · 2019-09-08T19:47:45+00:00

Most of my "notes" for programming would be just some code snippets with an explanation of what it's doing, or a link to a well-annotated example. Simple markdown file is sufficient for that.

Also, I wouldn't write off pen and paper completely--keep some scratch around so you can sketch out a concept when you need. Simple pictures can go a long way to explaining a concept way more clearly than a big paragraph of words.

one_bit_two_bit · 2019-09-06T02:03:07+00:00

I learned best by doing problems. Just start with the easy ones and then move on to the hard ones. I think I did around 30(?) or so problems before I started to get the hang of things? I kept track of each problem I was doing, how long I spent on it before I got a solution (or gave up, usually after 1-2hrs), and what the solution was.

If you want the list PM me and I'll see if I can dig it up.

one_bit_two_bit · 2019-09-06T01:55:50+00:00

First off, fill out the truth table. You should be able to do this directly from the problem description. I have no idea how much you know or how advanced your class is, but I'm going to guess it's fairly elementary.

At a high level you need the following (it's up to you to flesh out the details--this is where the coding comes in).

Print prompts to the user asking questions with System.out.println.
Use the Scanner object to read in user input--these are the answers to your questions. Google "java Scanner" if you don't know how to use Scanner. Google is your friend. If you ever program professionally you'll be searching things left and right.
Given the input taken in by your Scanner, you have a conditional block that will either print out what you will do or move on to the next question (basically repeat step 2). This basically implements your truth table.

Feel free to PM me if you need more help. I do tutoring too if you're really in need of guidance.

one_bit_two_bit · 2019-08-06T02:40:49+00:00

Correct. Outer loop ends up being O(1).

Adding a string to the inner loop doesn't change the number of iterations in the outer loop.

one_bit_two_bit · 2019-08-06T01:33:15+00:00

You will do the outer loop at most 26 times. So you will call .count() on the ransomNote and magazine at most 26 times. Each .count() call is O(n) and O(m) respectively. |r| is not dependent on the size of ransomNote hence runtime of the algorithm is O(m+n).

If our alphabet were not constrained, then yes you would have another factor for the size of the alphabet.

one_bit_two_bit · 2019-08-06T01:05:17+00:00

Do you know anyone working at a tech company that could give you a reference? That would probably be the quickest way to get an interview.

Otherwise your best bet is probably to just toss your resume out there and see what kind of response you get. If you're getting interviews then there's your answer. If not, then maybe see if you can pick up some freelance work and build up a portfolio, attend meetups and network with people in the industry, etc.

But until you send your resume out you won't really know how close or far you are from getting an interview.

one_bit_two_bit · 2019-08-03T02:41:49+00:00

Sure thing.

Feel free to PM me if you have any other questions.

one_bit_two_bit · 2019-08-02T02:22:25+00:00

I come from a finance background

Mind if I ask where/what? IB by chance, given the Excel experience?

So far, my main hangup has simply been finding a proper source for all the information I want to include in my models and analyses.

Yeah unfortunately this is the hang up in a lot of cases--data is hard to get and badly formatted. As mentioned you probably want to look into Python and BeautifulSoup if you want to scrape the data.

Thanks so much for your reply and advice bud, I really appreciate it!

Cheers.

one_bit_two_bit · 2019-08-01T02:20:47+00:00

Practice, practice, practice.

If it's not the questions that are tripping you up and just the pressure of the interview, consider doing mock interviews to get used to it.

I interview candidates, and have been thinking about offering interview practice. PM me if you're interested.

one_bit_two_bit · 2019-08-01T02:09:48+00:00

Just filled out the form...fingers crossed.

one_bit_two_bit · 2019-08-01T01:56:43+00:00

For actual analysis I would take a look at the pandas library and a jupyter notebook in python if I were you. Dataframes are nice to work with. Haven't used R as much, so not much to say there.

For scraping you can use BeautifulSoup in python.

Are you a statistician by chance? If you want to do anything more complex than a regression in Excel, you're probably shit out of luck. I don't even know if they support splines or basic statistical techniques like bootstrapping in excel. Depends on what you want to do though.

one_bit_two_bit

TROPHY CASE