The string "PAYPALISHIRING "is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows.

The easiest way to solve this problem would seem to be to just place all the letters in "buckets" made for each row.  Let's take a look at that solution.  First lets start with the skeleton function from leetcode.

We will need to keep track of our "buckets" of letters.  We also need to create one bucket for each row.

We will also need to keep track of what row we are collecting letters for.  Since we will be using this in a for loop we will start the row counter at 0.

One final thing we need to track before we start looping through our input string is the direction that we art going in our rows.  Since we are alternating back and forth from the first row (started at 0) and the last row, which is the numRows - 1 (since we started our count at 0) we can basically have a toggle between adding 1 and subtracting 1.  We can initiate it with a value of - 1 for now.

We can now set up our loop to iterate over the input string.

Inside the loop we go through the letters adding them to the current rows "bucket".

Next we need to determine if we should change direction.  We already mentioned that we should do that at row 0 and the numRows - 1.  We can just toggle our direction by multiplying it by -1.

We are now just able to add that to our current row which will increment the row up until the last row, then decrement it back down to 0 and so on.

We can finally return back the buckets by joining them together to make our final string.

One thing to think about is if there are any special cases hat we can avoid all the looping and building up of letters into "buckets".  For instance if the numRows is 1, we know that the input string is the correct output string.  We will add that to the very top of our unction call so we can return early in that case.

Given a string s, return the longest palindromic substring in s.

In order to solve this problem we first need to understand what a palindrome is.  A palindrome is a word that is the same spelled backward and forward.  An example of a palindrome would be the word radar.  Now that we have the english out of the way let's take a look at how we would solve the problem. The first solution that comes to mind would be to loop through the string and build up all the substrings from within it.  We can then test each of the substrings to determine if they are palindromes.  All that would be left would be to find the longest of those substrings and return it.  Finding all the substrings of the string with loops would be O(n2) time.  That wouldn't be bad if that's where we stopped.  Unfortunately we still have to determine if the substrings are palindromes.  That's an additional loop taking us to O(n3).  Let's work through to see if we can find a better solution.  As always we will start with the skeleton problem.

We will need some way to keep track of the longest substring that is a palindrome, so we will start by setting up a variable to track that.  It will be an array that will store the starting and ending index of the substring in the input string.   We can initialize it with the indices of 0 and 1 since we know that the first letter is going to be a palindrome.

For our solution we can iterate over the letters in the string and check for the longest palindrome that is centered around that letter.   We can just use a for loop fo that.

Let's stop for a minute and think about palindromes again.  We mentioned before that radar would be a palindrome.  As you can see the palindrome is centered around the letter d.  We can check each letter of the input string to see if it is the center of a palindrome and if so what is the maximum length of a palindrome centered around that letter.  Let's pull that out into a separate function call.  It will take in the input string and the index of its adjacent letters.

All we need to do in there is compare the letters at the adjacent indices and if they are equal move the indices over to the next adjacent letter.  We would continue to do this until our lower index or upper index goes outside the bounds of our string.  At the end we will return a tuple with the start and ending index of the longest substring that has passed the test.

We can add that to our loop and check that for each letter in the string. 

We are now finding every palindrome that is centered on each letter of the input string.  Before we move on we should revisit our definition of palindrome.  Back to our original example we would find the palindrome radar when we encountered the letter d in that word.  But what about the palindrome deed?  We would completely miss that in our current iteration.  We need to figure out a way to account for those as well.  Fortunately we have a function that we can pass in indices to.  If we pass in the current index and the previous index we would change the palindrome to be centered around the space between the two letters vs the current letter of the loop.  

That will allow us to find both the palindromes centered around all the letters as well as the palindromes centered around all the spaces between the letters.  All that is left to do now is to compare the lengths of them all and keep track of the longest one.  First we compare the lengths of the longest palindrome centered around the letter and the longest palindrome centered around the space before the letter.

Finally we just need to compare that to the longest palindrome we have seen so far.  If it's larger we need to assign it to our maxLongest variable.

We can now just return the slice of the input string based on the indies we have stored that represent the longest palindrome substring.

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Follow up: The overall run time complexity should be O(log (m+n)).

In order to solve this problem we need to be clear about what a median is.  According to Wikipedia "the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution."  Since we are using it in the data set case we continue with their definition of "For a data set, it may be thought of as `the middle` value".  So, we are looking for the middle value of the combined inputs.  A trivial way to find this answer is to merge the two inputs together and split it at the middle.  The problem with this solution is that it has a time complexity of O(nlogn) and the question requires a runtime of O(log (m+n)).  However knowing that both inputs are sorted we can use that to basically do a binary search to find the places to split the arrays so that we have all the smallest numbers on one side and all the largest numbers on the other.  Let's get started with the problem skeleton.

Now we need to think about what we need to keep track of.  First since the inputs can be of different lengths we need to make sure that we are doing the search for a good split position on the shortest array.  We can set up a couple of variables to track the shortest and longest array.

If we pick some random place to split the shorter of the two arrays we need a way to figure out where to split the longer so that sides will be equal (or that the lower values will have at most 1 more item).  We can do this by finding the middle of the array if we merged the two arrays together and subtracting out the place we split the shortest array.  Javascript only has a `number` type and we only want an `integer` here so we will use the `Math.ceil` (or add 1) to make sure that if the merged array would be odd our smaller number half has the extra value.

Finally keep track of the starting and ending point of what we are splitting on the smaller array.  Since we are splitting the entire array the first time we do the split we will initialize them with values that encompass the entire short array.

We need to continue splitting the smaller array until we find the point where all the values on the "left side" of our two splits are all less than all the values on the "right sides".  We can set up a loop and run it until our start or end overlaps the other value.

We will now start a binary search on the smaller array trying to find the point in that array where when we split it, it allows us to get the numbers for both arrays split at the points where all of our low values are collected and all our high values are collected.  Let's split the shorter array right in the middle and based on that split figure out where we need to split the longer array.  Remember we said that we can find thiat by finding the middle of the array if we merged the two arrays together and subtracting out the place we split the shortest array. 

Okay, we now have places that we can split the input arrays that will give us equal numbers of values if we add the two bottom splits together and compare them to the number of values of the two upper splits.  Next we need to make sure that those splits give us all the lower numbers for all the total numbers in the lower splits and all the higher numbers for all the total numbers in the upper split. Since the original input arrays were sorted we know that the highest number in each lower split is less than the lowest number in it's corresponding split so really we just need to check if the highest number in the first inputs split is lower than the lowest number in the second inputs higher split and vice versa for the second inputs lower split and first inputs higher split.  Let's see if we can make more sense of that in code.  Let's first compare the top value in the shorter input's lower split to the lowest value in the longer input's upper split.

We also made a check to verify that our split is still higher than the beginning index of our current split.  If the highest value is greater than the lowers value of the longer inputs lowest value in its upper split we haven't got our splits correctly and we need to slide our split left or lower to remove that higher number. 

We will do the same thing if we find that the larger array's upper lower bound has a number higher than the smaller arrays higher bound. If this is the case we will need to slide the starting point up or to the right. 

If neither of these cases are true it means we found the perfect splits to the input arrays that keep all the lower numbers in a lower bounds and all the higher numbers in the higher bounds.  If this is the case we just need to get the highest number from the lower bounds groups and the lowest number from the higher bounds groups.  Let's work on getting the maximum from the left splits first since if the total merged array would be odd and we stored that extra value on the left splits we know that we can just return that number.   If either split was done at index 0 then we know that it's going to be empty, which tells us that we just need to return the last number from the other split.  Remember that the `shortestSplit` and `longestSplit` variables are just references to an index in the input arrays where the split would happen.

If both of the splits would have values then we just need to take the max of the last value of each split.  

Again, if the total merged array would be odd we know that this value would be the median since we stored the extra value on the lower side.  We make our check for that and return that value if it's true.

If the merged array would end up having an even number of items in it we need to find the average of the highest low value and the lowest high value.  Since we already have the highest low value we just need to find the lowers high value.  We will do nearly the same thing as when we found the highest low, we will make sure both splits would have values or return the first item of the one with values or if both splits would have values we return the min of the lowest value in each.

All that is left to do now is to return the average of those value.

Given a strings, find the length of the longest substring without repeating characters.

Looking for a brute force solution of this problem would be looking through all the possible substrings of the input and finding any that don't have duplicate characters allowing us to return the count of the longest one.  I think we can do better.  Here is the problem skeleton from leetcode:

The first thing we can do is add a simple check to make sure the string is not empty.  If the string is empty then we know that it contains no substrings.  Then answer should be 0.

In order to solve this problem we are going to need to iterate over the strings and building up substrings.  We need to keep track of where are substring starts and what letter in the string our current substring is.  Since we will be looking at multiple substrings in the word we will also need to keep track of our current longest substring starting index and ending index.  Let's set up some variables to keep track of that.

We have set up `startIndex` here to keep track of the beginning of our current substring and started it at 0 or the beginning of the input string.  We also have set up `longest` to hold the starting and ending index of the longest substring that we have found so far.  Since we know that the string has at least one character (because we checked if it was empty) we know that at least the first letter will be a substring that doesn't repeat characters. We start with that as the longest and store the indices in our array.  Finally we need to keep track of letters that we have seen to make sure we start our substring again once we see a repeat letter.  

We are ready to start looking for substrings now.  Lets create our loop over the input string keeping track of the current letter and the index in the string

We first need to check and see if we have seen the letter before.  We make a quick check in our hash to find out if it is there.  If it is there we will need to move our `startIndex` to begin a tracking a new substring.  We will want to see if the starting index of our substring needs to be updated.  In order to do this we will compare the current starting index of our substring to the index when we last saw the current character.  If that index (the one for the last time we saw our character) is before our starting index of this substring it's not currently part of the substring so we don't need to update anything.  If the index is greater than or equal to (meaning we saw that letter before in this current substring we want to move our starting index to the index immediately after it. 

We also need to check if the current substring is now longer than our previous longest substring.  If it is we need to update the indices in our array.

Finally we need to update the hash table of previously seen characters.

Once we have that we can just return the difference between the 2 indices that we have in our longest array.

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

The number of nodes in each linked list is in the range [1, 100].

It is guaranteed that the list represents a number that does not have leading zeros.

There are a couple of ways to solve this problem both involving traversing the linked lists and doing arithmetic on the values.  One way is to traverse the lists and build the actual numerical value of each input and do normal addition on the results.  You would then need to create a new list based on the sum.  The other way is to look at it as if you were back in grade school doing arithmetic problems and just sum each node (column) and pass any carryover to the next node.  Lets take a look at how we would do that.

Let's set up some variables that we will need to keep track of where we are in our traversal of the inputs.  We will need to keep separate variables as we aren't guaranteed that the input lists will have the same length.  This means we could run out of nodes in one list before we finish traversing the other list.  

We also need a way to keep track of the carryover from one node to the next.  Lets add that next.

And finally we will need some way to track our new list that we will be creating as we traverse and do our math.  Lets create a new ListNode and set a pointer to the head of the node.  We will start it with a dummy value of 0 since it will be easier to just ignore this when it's time to return our list than it would be to set up special checks in the looping process to make sure our pointer actually points to something.  We need to also track where in our new list we are similar to what we did with the input lists.  Let's create a variable for that as well.

Now that we have the setup out of the way, we need to figure out how to traverse the lists, adding up the values (if they exist) and keeping track of any carryover.  We need to continue to do this while either of the lists still have values or there is still a carryover that needs to be applied.  Let's set up that loop.

Next we need to find the values that we need to add up for the current node of our new list.  Even though we make a check for null in the while loop we still need to make that check when getting the value as one or both of the nodes could still be null.  We also need to add any carryover we have kept track of from the previous calculations.

We now have the sum from the current node values, we just need to take that and turn it into an integer and a carryover.  We will use the modulo operator to get the integer part and then divide the value by ten to get the "tens" column potion.  JavaScript number division works as floating point division so we also need to make sure we only keep the integer portion.  We will use the `Math.floor()` built in to do that.

All that's left to do in the loop is to assign all these values to the correct variables that we are tracking.  We already did that with the carryover value.  We just need to do that with the new list values.  We will create a new node with the new value we just calculated and assign that back to the next value of the currentNode which is the tail of the new list that we are building up.  Once we set that we can set then currentNode (or tail of the list) to be the new node we just created.  

Almost there!  We still need to make sure that we are advancing through the input lists before we start the loop over again.  The tricky part here is that if either of the nodes are already null they won't have a next to advance to.  One more check for that and if the node exists we go ahead and move it to the next, if not we leave it as null.

There you go!  We now have our new list of summed nodes built up.  If you are wondering about the carryover, just remember we keep looping even if both node have been traversed completely if we have some carryover that isn't 0.  All we have left to do is return the new list that we built up.  But remember in the beginning we added in the node with a value of 0?  I told you that would help us to not have a bunch of checks for null?  Well it's still the head of our new list so if we return the list now it would be one place off.  The easy part of these lists is you can just return the newListPointer.next.  That returns everything that we built up but leaves off the 0.  

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Let's start out with the skeleton problem.

We will start with a brute force method.  In most cases if this were an interview it would probably be good enough to just talk through this example without actually implementing the code for it, but for the sake of completeness we will go ahead and implement it.  We could solve this problem by nesting loops reading each number and then checking all of the remaining numbers to see if there is a match that would sum up to the target.

Here we have a working first solution.  It's a simple nested loop where we start the outer loop at the beginning of the array and keep track of the number we are on in a new variable.  We then use the inner loop to run the remainder of the array checking if any item plus the item being tracked in the variable equals the target.  If so we return the variable and the item.  If no two numbers in the array equal the target we just return an empty array.  Although this works, it has a runtime of O(n2).  Let's see if we can do better if we use some form of hashmap.  Let's create one.

Next we will still need to iterate over the input array.

Inside the loop we need to check if there is a value that equals the target number minus the current number.  If there is we can return the indices of the two numbers.  If not we can then add the new number and it's index to the hash.  

Finally if we didn't find a matching pair we just need to return an empty array at the end.

Using the hash we can do constant time lookups of the past numbers giving us a runtime of O(n).  We have increased the space complexity here up to O(n) but we will see that sorting the array can help to minimize this issue when we get to `Two Sum II.- Input array is sorted`.  

ZigZag Conversion

Longest Palindromic Substring

Median of Two Sorted Arrays

Longest Substring without Repeating

Add Two Numbers

Two Sum