The Big Programming Thread - Page 856

Prev 1 854 855 856 857 858 1031 Next

Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks.

Wrath

3174 Posts

March 03 2017 13:55 GMT

#17101

Love the new thread name :D

Acrofales

Spain17842 Posts

March 03 2017 13:56 GMT

#17102

On March 03 2017 22:36 travis wrote:
hanh or slmw or acrofales or anyone else, could you check over this? (really, I just want one step explained in it. anyone who is good at algebra could explain it)

the problem is to prove this sequence with strong induction

sequence:


a_0 = 12
a_1 = 20
(for all n >= 2)[a_n = 2a_(n-1) + 3a_(n-2)

Show that for all n, a_n <= 12*3^n

so my proof was to first show the base cases.

12 <= 12 * 1
20 <= 12*3

Now make inductive hypothesis.

For some k>= a_1, and for every i: 0 <= i <= k, assume that P(i) holds.
Therefore a_i = 12*3^i

Now do the inductive step by proving P(K+1):


a_(k+1) = 12 * 3^(k+1)

= 2a_k + 3a_(k-1)
= 2(12*3^k)+3(12*3^(k-1))
= 12 * (2*3^k + 3*3^k-1)

and here is where I don't know algebraically what to do next.
I mean obviously, (2*3^k + 3*3^(k-1)) = 3^(k+1)
But what steps are used to prove that?

You need to write your proof in a slightly more rigorous form.

The inductive step works like this:

Assume for any k >=2 that:

a_k <= 12*3^k and a_(k-1), and a_(k-1) <= 12*3^(k-1)

Now prove:

a_(k+1) <= 12*3^(k+1).

Hint: use the fact that 3^k = 3*3^(k - 1)

+ Show Spoiler [not allowed to look until you solve it] +

+ Show Spoiler [really] +

+ Show Spoiler [stop cheating] +

+ Show Spoiler [ok] +


a_(k+1) = 2a_k + 3a_(k-1) From definition
<= 2(12*3^k)+3(12*3^(k-1)) From inductive assumption
= 24*3^k + 12*3^k 
= 3^k*(24 + 12) 
= 3^k*3*(8+4) 
= 3^(k+1)*12 

QED

Hanh

146 Posts

March 03 2017 13:57 GMT

#17103

+ Show Spoiler +

3*3^(k-1) = 3^k // definition of power
2*3^k + 3^k = (2+1).3^k // factorize 3^k
= 3.3^k = 3^(k+1)

Deleted User 3420

24492 Posts

March 03 2017 14:06 GMT

#17104

ah yeah hanh that last step... obvious once i see it lol
acrofales your way was really elegant
thank you guys.

Deleted User 3420

24492 Posts

March 03 2017 21:39 GMT

#17105

ok here is a question
im doing questions in "cracking the coding interview"

it asks: "Given two strings, write a method to decide if one is a permutation of the
other. "

My solution (in java) was to compare their length (make sure they are same length)
then put string one into a hashset.
then check if the hashset contains each character of of string two

Their solution was to sort the strings and see if they are equal. Is my method better?

Zocat

Germany2229 Posts

March 03 2017 22:18 GMT

#17106

What does "better" mean? There are multiple things you can think about: Speed, memory, readability... are the obvious ones that immediately come to mind. And one version could be better at metric X and worse at metric Y.

Apart from that, I haven't done Java in a long time, but I think your HashSet variant will fail in the case of repeated characters. Example strings "aab" and "abb".

Deleted User 3420

24492 Posts

March 03 2017 22:23 GMT

#17107

It won't because I have already checked that the strings were the same length. So if there is a repeated character, but the strings have the same length, then it won't be able to find a later character in the string because it will be missing.

By better I am primarily thinking of speed, here. I don't know how they compare in memory, because I don't know how much memory a hashset takes up.

spinesheath

Germany8679 Posts

March 03 2017 22:44 GMT

#17108

On March 04 2017 07:23 travis wrote:
It won't because I have already checked that the strings were the same length. So if there is a repeated character, but the strings have the same length, then it won't be able to find a later character in the string because it will be missing.

By better I am primarily thinking of speed, here. I don't know how they compare in memory, because I don't know how much memory a hashset takes up.

One string can repeat one character, the other another. Same length, no permutation. Look at the example above. Sorting is the best you can do in terms of runtime complexity ( O(n log n) ) unless you assume that your string has only a small number of different possible characters, in which case you can do something similar to a bucket sort ( O(n) ). The hashtable approach mentioned below is faster.

Deleted User 3420

24492 Posts

March 03 2017 22:57 GMT

#17109

oh right yeah.. i feel stupid now
sorry zocat

frogmelter

United States971 Posts

March 03 2017 23:10 GMT

#17110

You can use a HashMap<Character, Integer> for count and compare the characters in O(N) time.

HashSet doesn't work for the above case as you lose duplicates, but a HashMap to the frequency of the character can do it. Something like this StackOverflow

Zocat

Germany2229 Posts

March 04 2017 03:32 GMT

#17111

On March 04 2017 07:44 spinesheath wrote: Look at the example above.

My initial example was "aa" and "a"; then I realized that he mentioned checking for length, so I changed it. So his response could've been "correct" (regarding my example).

On March 04 2017 07:23 travis wrote:
By better I am primarily thinking of speed, here. I don't know how they compare in memory, because I don't know how much memory a hashset takes up.

You (and me) also don't know what kind of sorting Java uses (thus we have now clue about the mem req). But you need to change your questions and start thinking about that.

Example: I currently have a problem where a kd-tree is fucking efficient and awesome. But I currently need it for 2 lookups. Building the kd-tree is way more complicated and it needs memory to be stored in. The solution is to have a decent solution with a comment "If we need a lot more lookups consider a kd-tree." and let someone else worry about it in the future.

phar

United States1080 Posts

March 04 2017 03:56 GMT

#17112

java default sort uses mergesort (like collections.sort), but then it uses timsort for arrays.sort, but then if that arrays.sort is on numbers then it's a quicksort.

or something like that. Been awhile.

frogmelter's histogram approach is probably what you'd expect as a canonical answer to that interview question. But don't sweat it too much.

bucket sort is roughly equivalent to the hashmap solution. In either case you're potentially having like 1million+ keys.

Manit0u

Poland17187 Posts

March 04 2017 03:58 GMT

#17113

It depends on the hash size, architecture, implementation, language etc. (check the link I posted on the previous page - people were discussing hash optimizations in ruby in it - as in, how they're actually implemented in it and various other languages).

And your solution is pretty bad when it comes down to optimization since for each letter in one string you have to check all the letters in the other. The sorting solution is much better since with sorted arrays you simply compare their respective elements.

If you want to practice such interview questions, you can go ahead and tackle another popular one:

Given an input string, return the first non-duplicate letter in it or false if there is none.

Hanh

146 Posts

March 04 2017 15:18 GMT

#17114

In some cases, for example if you have a lot of strings to check, pre-screening can save you a lot of time.

XOR/sum/multiply (any operation that is fast & commutative) all of your chars together. If the result is different then they can't be permutations.If they are equal, check for real.

Deleted User 3420

24492 Posts

March 04 2017 22:30 GMT

#17115

probably a really easy proof question

essentially In my homework I am being told to "prove" that 69 cannot be written as a sum of multiple of 8 and 11.

Would the correct way to prove this to go through the cases of ( 69 - n(11) ) (mod 8), showing that for each case there is a non zero remainder? Or is there a more elegant way?

meatpudding

Australia520 Posts

March 04 2017 23:57 GMT

#17116

On March 05 2017 07:30 travis wrote:
probably a really easy proof question

essentially In my homework I am being told to "prove" that 69 cannot be written as a sum of multiple of 8 and 11.

Would the correct way to prove this to go through the cases of ( 69 - n(11) ) (mod 8), showing that for each case there is a non zero remainder? Or is there a more elegant way?

I guess one way to do it is to note that 69 (mod 8) = 5.
Then by factorising you must have 8a + 11b (mod 8) = 5.
This reduces to 0 + 3b (mod 8) = 5.
So b = 3^(-1) * 5 = 3 * 5 = 7.
Since a is anything and b is 7, then from the original factorisation we have at least 11 * 7 which is 77 > 69. So the factorisation isn't possible.

WarSame

Canada1950 Posts

March 05 2017 21:29 GMT

#17117

In angularjs, I have 3 models from HTML elements with ng-model. These elements are sliders. When I leave them like this they start off undefined until you move the slider. I would like to know a way to have them start off as defined(default 0).

I set them in the scope of my controller, but then the values do not get updated when I move the sliders.

How can you make it so that the model can be initialized to the same value as the slider, while also updating based on the slider being moved?

Thaniri

1264 Posts

March 05 2017 23:50 GMT

#17118

I'm just learning angular as well, maybe these code snippets might help:

Directive:


 myDirectives.directive('myStars', function () {
        return {
            restrict: 'A',
            replace: true,
            scope: {
                rating: '=',
                max: '='
            },
            link: function ($scope) {
                var updateStars = function () {
                    $scope.stars = [];
                    for (var i = 0; i < $scope.max; i++) {
                        if (i < $scope.rating)
                            $scope.stars.push({ filled: true });
                        else
                            $scope.stars.push({ filled: false });
                    }
                };
                $scope.toggle = function (index) {
                    $scope.rating = index + 1;
                    updateStars();
                };
                updateStars();
            },
            templateUrl: function () { return 'views/stars.html' },
        }
    });

Partial View:


<ul class="rating">
    <li ng-repeat="star in stars  ">            
        <span ng-switch on="star.filled">
            <div ng-switch-when="true" class="filled">&#9733;</div>
            <div ng-switch-default class="rating">&#9733;</div>
            
            
        </span>
    </li>
    <p>{{rating}} out of {{max}} stars.</p>
</ul>

If you make an element <div my-stars rating="3" max="5"></div> the dynamically generated text displayed will be 3 out of 5 stars.

Hopefully that helps a little bit, I'm not an expert >>

Shield

Bulgaria4824 Posts

March 06 2017 00:42 GMT

#17119

Can we please rename thread to what it was? It makes TL look amateur this way.