<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Nick Maslov on Medium]]></title>
        <description><![CDATA[Stories by Nick Maslov on Medium]]></description>
        <link>https://medium.com/@kategorychnost?source=rss-1ebc4df229f3------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*hvZenHGcqmxUwBLsW7Qusg.jpeg</url>
            <title>Stories by Nick Maslov on Medium</title>
            <link>https://medium.com/@kategorychnost?source=rss-1ebc4df229f3------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 20:02:20 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@kategorychnost/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Essential Coding Interview Questions with Javascript (Part III)]]></title>
            <link>https://medium.com/@kategorychnost/essential-coding-interview-questions-with-javascript-part-iii-8c8addc8a3fb?source=rss-1ebc4df229f3------2</link>
            <guid isPermaLink="false">https://medium.com/p/8c8addc8a3fb</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[trees]]></category>
            <category><![CDATA[linked-lists]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[coding-interviews]]></category>
            <dc:creator><![CDATA[Nick Maslov]]></dc:creator>
            <pubDate>Wed, 05 Sep 2018 17:43:17 GMT</pubDate>
            <atom:updated>2018-09-05T18:14:56.808Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>(Linked Lists and Trees)</strong></p><p>It is very important to get acquainted with various data structures and how to apply them correctly. This article presents the most common interview questions and popular problems with arrays, two-dimensional arrays, queues, stacks, binary search trees, graphs, etc. To be comfortable with this article, you should be familiar with these data structures and have some basic knowledge of Javascript. Examples of these problems I got in Python tutorials, but I wanted to solve them using JavaScript because JS is one of the most popular programming languages and is required for any web developer.</p><p>Links to other problems: <a href="https://medium.com/@kategorychnost/essential-coding-interview-questions-with-javascript-part-i-b4ab3101660d">Part I</a>, <a href="https://medium.com/@kategorychnost/essential-coding-interview-questions-with-javascript-part-ii-99e62af06a88">Part II</a></p><h3>#9 N-th Element of a Linked List</h3><p>Given a Linked List and a positive number n, write a function that returns the value at the n-th node from end of the Linked List.</p><p>For example, if input is below list and n = 1, then output is “E”; n = 4 , output is “B”; n = 7, output is null.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/690/1*I2zYy8t2QPXXT5AheIhv2w.png" /></figure><p><strong>Examples:</strong></p><pre>Input : <br>Linked list: 1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;6-&gt;7,<br>n = 3<br>Output : 5</pre><pre>Input : <br>Linked list: 11-&gt;23-&gt;35-&gt;41-&gt;5-&gt;656-&gt;17-&gt;0,<br>n = 8<br>Output : 11</pre><p>As we can see on visualization of linked list above node with the value “A” is pointing to the node with value “B” and so on. Last node with value “E” in this linked list is pointing to null. To get referral to this list we can by assigning a variable called “head” to the first item in the linked list. Each item or each node in this linked list is an object and the class might look like this:</p><pre>class <strong>Node</strong> {<br>  constructor(value) {<br>    this.value = value;<br>    this.child;<br>  }<br>};</pre><pre>class <strong>LinkedList</strong> {<br>  constructor(){<br>    this.head;<br>  }<br>};</pre><p>There this problem let’s initialize two variables, left pointer and right pointer, pointing at the first node. Then move the right pointer to the right node n times. After that move both of the pointers to the right, one by one, until the right pointer is pointing at null. When the right pointer will be pointing at null, the left pointer will be pointing at the node we are looking for. If n is bigger than the length of the linked list, right then we should return null.</p><p><strong>Solution:</strong></p><pre>function <strong>nthFromLast</strong>(head, n) {<br>  let left = head,<br>    right = head;<br>  for (let i = 0; i &lt; n; i++) {<br>    if (!right) return null;<br>    right = right.child;<br>  }<br>  while (right) {<br>    right = right.child;<br>    left = left.child;<br>  }<br>  return left;<br>}</pre><h3>#10 Is This a Binary Search Tree?</h3><p>Given a binary tree, determine if it is a valid binary search tree (BST).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/420/1*lwaDg8aL0XtdEndSDBtyvQ.png" /></figure><p><strong>Examples:</strong></p><pre>Input : <br>     5  = root<br>    /  \<br>   2    7<br>  /\    /\<br> 0  3  8 10<br>Output : true</pre><pre>Input : <br>     5  = root<br>    /  \<br>   2    7<br>  /\    /\<br> 0  3  4 10<br>Output : false<br><em>(4 in the right subtree is less than 5 in the root) </em></pre><p>A tree is an abstract model of a hierarchical structure and consists of nodes with a parent-child relationship.</p><p>A node in a binary tree has two children at most: one left child and one right child. This definition allows us to write more efficient algorithms to insert, search, and delete nodes to/from a tree. Binary trees are largely used in computer science.</p><p>A binary search tree is a binary tree, but it only allows you to store nodes with lesser values on the left-hand side and nodes with greater values on the right-hand side.</p><pre>class <strong>Node</strong> { <br>  constructor(value){<br>    this.value = value;<br>    this.left;<br>    this.right;<br>  }<br>};</pre><pre>class <strong>BinarySearchTree</strong>{<br>  constructor(){<br>    this.root; <br>  }<br>};</pre><p>A simple solution is for each node, check if the left node of it is smaller than the node and right node of it is greater than the node, but how we can see in the second example it won’t work. We have to create two new variables, which will take track of the current biggest and the current smallest value for current node we are checking. We are starting from the root and our variables will be <em>upperLimit</em> = null, <em>lowerLimit </em>= null, but when we go down for example to the right node side we’ll know that it’s value, new upper limit, should be at least greater than or equal to root’s value, new lower limit. And that when we go to the left node, we know that this value needs to be between the lower limit and upper limit to be a binary search tree. After we check this conditions we have to recursively check if the left subtree and the right subtree is a binary search tree themselves with the new limits that we are going to give them. If they are, return true from our function.</p><p><strong>Solution:</strong></p><pre>function <strong>isBST</strong>(node, upperLimit = null, lowerLimit = null) {<br>  if (lowerLimit &amp;&amp; node.value &lt; lowerLimit) return false;<br>  if (upperLimit &amp;&amp; node.value &gt; upperLimit) return false;<br>  let isLeftBST = true,<br>    isRigthBst = true;<br>  if (node.left) isLeftBST = <strong>isBST</strong>(node.left, node.value, lowerLimit);<br>  if (isLeftBST &amp;&amp; node.right)<br>    isRigthBst = <strong>isBST</strong>(node.right, upperLimit, node.value);<br>  return isLeftBST &amp;&amp; isRigthBst;<br>}</pre><h3>#11 Lowest Common Ancestor</h3><p>Given a binary tree, find the lowest common ancestor (<a href="https://en.wikipedia.org/wiki/Lowest_common_ancestor">LCA</a>) of two given values in the tree. Assume that there are no duplicates in the tree.</p><p><strong>Example:</strong></p><pre>BT:<br>      5   = root<br>     /  \<br>   11    7<br>   /\    /\<br>  0  3  8 10<br> / \<br>1   4</pre><pre>Input : root<br>n1 = 3<br>n2 = 4<br>Output : 11</pre><pre>Input : root<br>n1 = 11<br>n2 = 5<br>Output : 5</pre><pre>Input : root<br>n1 = 10<br>n2 = 10<br>Output : 10</pre><p>This is a very popular problem and there are many potential solutions to it. Our solution for an interview has to be simple and efficient. As we know from the previous problem, a binary tree has a parent-child structure with up to 2 children.</p><pre>class <strong>Node</strong> { <br>  constructor(value){<br>    this.value = value;<br>    this.left;<br>    this.right;<br>  }<br>};</pre><pre>class <strong>BinaryTree</strong>{<br>  constructor(){<br>    this.root; <br>  }<br>};</pre><p>To solve this problem, first we have to find nodes that corresponds to given integers in tree before finding their lowest common ancestor. And to find each node will take <em>O(n)</em> in time complexity because our tree is not necessarily sorted and the extra space complexity or auxiliary space will be <em>O(log n), </em>n is the number of nodes in this tree.</p><p>We will divide our problem into two parts. First, find a path between the root node, or any other node for that matter, and the integer that we’re looking for. This path will be the stack of nodes from the node with given value to the root node. Once we have these two paths we can examine which elements are common between these two paths, counting from the top. The last item in the common elements in these two paths will be the lowest common ancestor between the given integers.</p><p>Now let’s think about how to implement the path to our node. Our function will take two arguments: root and x — one of the given items. We are trying to find the path to x from the node root. We are going to do this recursively. The base case is when we are going to the end node, nonexistent node, we return undefined. And another base case is if the root is equal to an item we are trying to find, we return new Stack with single value — array with the current node. Then we need to ask what the path to the left node and to the right node and move to the subtrees. If x is not under subtree we don’t return anything. Otherwise, if x in the subtree, add the current root to the pass and return that path as the new pass. If x not in the left subtree, not in the right subtree, we return undefined.</p><p>Using this function <em>pathToX</em> we can implement our main function <em>lca</em>, which takes three arguments: root node of the tree we are examining, and x1, x2 two integers that we want to find the lowest common ancestor for. We’re going to find the path to x1 and x2 with our <em>pathToX</em> function. If there is no occurrence of x1 or x2 in this tree, we are going to return null. After that we are going to find LCA, initializing variable result. We are going to iterate our path, stored as stacks, from the top one by one, and assigning current equal item to the result until we find different item. Last assigned item to our variable result is our LCA.</p><p><strong>Solution:</strong></p><pre>function <strong>pathToX</strong>(root, x) {<br>  if (!root) return;<br>  if (root.value === x) return [root];<br>let leftPath = <strong>pathToX</strong>(root.left, x);<br>  if (leftPath) {<br>    leftPath.push(root);<br>    return leftPath;<br>  }<br>  let rightPath = <strong>pathToX</strong>(root.right, x);<br>  if (rightPath) {<br>    rightPath.push(root);  <br>    return rightPath;<br>  }<br>  return;<br>}</pre><pre>function <strong>lca</strong>(root, x1, x2) {<br>  pathTo1 = <strong>pathToX</strong>(root, x1);<br>  pathTo2 = <strong>pathToX</strong>(root, x2);<br>  if (!pathTo1 || !pathTo2) return null;<br>  let result;<br>  while (pathTo1.length &gt; 0 &amp;&amp; pathTo2.length &gt; 0) {<br>    pop1 = pathTo1.pop();<br>    pop2 = pathTo2.pop();<br>    if (pop1 === pop2) result = pop1;<br>    else break;<br>  }<br>  return result;<br>}<br></pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8c8addc8a3fb" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Essential Coding Interview Questions with Javascript (Part II)]]></title>
            <link>https://medium.com/@kategorychnost/essential-coding-interview-questions-with-javascript-part-ii-99e62af06a88?source=rss-1ebc4df229f3------2</link>
            <guid isPermaLink="false">https://medium.com/p/99e62af06a88</guid>
            <category><![CDATA[trees]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[arrays]]></category>
            <category><![CDATA[coding-interviews]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Nick Maslov]]></dc:creator>
            <pubDate>Wed, 05 Sep 2018 17:42:05 GMT</pubDate>
            <atom:updated>2018-09-05T17:43:55.136Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>(two-dimensional array, tree search problem)</strong></p><p>It is very important to get acquainted with various data structures and how to apply them correctly. This article presents the most common interview questions and popular problems with arrays, two-dimensional arrays, queues, stacks, binary search trees, graphs, etc. To be comfortable with this article, you should be familiar with these data structures and have some basic knowledge of Javascript. Examples of these problems I got in Python tutorials, but I wanted to solve them using JavaScript because JS is one of the most popular programming languages and is required for any web developer.</p><p>Links to other problems: <a href="https://medium.com/@kategorychnost/essential-coding-interview-questions-with-javascript-part-i-b4ab3101660d">Part I</a>, <a href="https://medium.com/@kategorychnost/essential-coding-interview-questions-with-javascript-part-iii-8c8addc8a3fb">Part III</a></p><h3>#6 Assign Numbers in Minesweeper</h3><p>Remember the old Minesweeper ? We play on a square board and we have to click on the board on the cells which do not have a mine. And obviously we don’t know where mines are. If a cell where a mine is present is clicked then we lose, else we are still in the game.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/503/1*sabwQJt5s1NitjYGZ0I6kQ.jpeg" /></figure><p>In this problem we are going to create a minesweeper board. Output should be a two dimensional array, where bombs will have value -1, and other cells will be filled with 0 and +1 to cell for each bomb, it has border with.</p><p>The input is bombs — array of coordinates, number of rows , and number of columns</p><p><strong>Examples:</strong></p><pre>Input : <br>bombs = [[2,3],[2,1]]<br>numRows = 4<br>numCols = 4<br>Output : <br>[0,  0,  0,  0]<br>[1,  1,  2,  1]<br>[1, -1,  2, -1]<br>[1,  1,  2,  1]</pre><pre>Input : <br>bombs = [[2,3],[2,1],[6,6]]<br>numRows = 10<br>numCols = 10<br>Output : <br>[0,  0, 0,  0, 0, 0,  0, 0, 0, 0]<br>[1,  1, 2,  1, 1, 0,  0, 0, 0, 0]<br>[1, -1, 2, -1, 1, 0,  0, 0, 0, 0]<br>[1,  1, 2,  1, 1, 0,  0, 0, 0, 0]<br>[0,  0, 0,  0, 0, 0,  0, 0, 0, 0]<br>[0,  0, 0,  0, 0, 1,  1, 1, 0, 0]<br>[0,  0, 0,  0, 0, 1, -1, 1, 0, 0]<br>[0,  0, 0,  0, 0, 1,  1, 1, 0, 0]<br>[0,  0, 0,  0, 0, 0,  0, 0, 0, 0]<br>[0,  0, 0,  0, 0, 0,  0, 0, 0, 0]</pre><p>To solve this problem we have to initialize a two-dimensional array with numbers of rows and number of columns from the input, as our field. Then give to our bombs with given coordinates<em> (x, y)</em> value -1 and all cells around <em>(x+/- 1, y+/- 1) </em>will have increment +1. Make sure that you do not get out of the board and don’t cause the error. Our map is ready. Just return the field.</p><h4>Solution:</h4><pre>function <strong>mineSweeper</strong>(bombs, numRows, numCols) {<br>  let field = [];<br>  for (let i = 0; i &lt; numRows; i++) {<br>    field[i] = [];<br>    for (let j = 0; j &lt; numCols; j++) {<br>      field[i][j] = 0;<br>    }<br>  }<br>  for (let bomb of bombs) {<br>    let rowB = bomb[0];<br>    let colB = bomb[1];<br>    field[rowB][colB] = -1;<br>    for (let i = rowB - 1; i &lt;= rowB + 1; i++) {<br>      for (let j = colB - 1; j &lt;= colB + 1; j++) {<br>        if (<br>          0 &lt;= i &amp;&amp;<br>          i &lt; numRows &amp;&amp;<br>          0 &lt;= j &amp;&amp;<br>          j &lt; numCols &amp;&amp;<br>          field[i][j] !== -1<br>        ) {<br>          field[i][j] += 1;<br>        }<br>      }<br>    }<br>  }<br>  return field;<br>}</pre><h3>#7 Find Where to Expand in Minesweeper</h3><p>Here is another problem with minesweeper. You should check the previous problem if you are not familiar with the game. In minesweeper, when you click on a cell that is not a bomb, all surrounding cells that do not have bombs will be shown.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/516/1*46x22Q4NpaRv47EZptw-fQ.png" /></figure><p>The problem is to find where to expand exactly when you click on a correct cell, and express it by changing all 0 values to -2 in this area. So, in your function you should modify given array and return new one with first click changes like in examples. If clicked not 0 value, nothing change.</p><p><strong>Examples:</strong></p><pre>Input : <br>field = <br>[[0,  0,  0,  0],<br> [1,  1,  1,  0],<br> [1, -1,  1,  0],<br> [1,  1,  1,  0]]<br>clickX = 0<br>clickY = 1<br>Output : <br>[[-2, -2, -2, -2],<br> [ 1,  1,  1, -2],<br> [ 1, -1,  1, -2],<br> [ 1,  1,  1, -2]]</pre><pre>Input : <br>field = <br>[[ 0,  1,  1,  1],<br> [ 0,  1, -1,  1],<br> [ 1,  2,  1,  1],<br> [-1,  1,  0,  0]]<br>clickX = 3<br>clickY = 2<br>Output : <br>[[ 0,  1,  1,  1],<br> [ 0,  1, -1,  1],<br> [ 1,  2,  1,  1],<br> [-1,  1, -2, -2]]</pre><p>When a user clicks on a first cell (x, y), we need to find all zero cells connected to the first cell. The first zero is directly connected to the nine cells (x +/- 1, y +/- 1), and each of this nine cells is connected to other cells. This structure is a graph, where you trying to find all the zero cells connected to the first cell, which is the first node in this graph. There are two simple ways to solve a search problem in a graph: Depth-First Search and Breadth-First Search. Which do we want to use? Let’s think about the worst case scenario when all cells are 0, and you need to traverse the entire array.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/763/1*3_AvF7lZa1Z-tC9R02nPpA.png" /></figure><p>Let’s first think about how Depth-First Search will work. Suppose that user clicks the cell <em>(0, 0)</em>. Depending on the order of direction that you check in your algorithm you can get spider pattern or snake pattern like on the picture behind. Either way, we need to store the positions of all the zero cells in this array. Extra space complexity or auxiliary space would be <em>O(n*m)</em>, where n is the number of rows in given field, and m is the number of columns. The time complexity will be also <em>O(n*m)</em> because we need to traverse the entire array. <br>Let’s now think about how Breadth-First Search will work. Suppose that user clicks the cell <em>(2, 2)</em>. You see the pattern on the picture which expands outward from the first cell. The entire outer edges in total will have about <em>O(2(n+m))</em> cells. Thus, auxiliary space complexity will be <em>O(n+m)</em>, which is better than <em>O(n*m)</em>, and the time complexity for this algorithm is <em>O(n*m)</em> because we still need to consider the entire array.<br>Thus, these search algorithms have the same time complexity, but the auxiliary space or the extra space complexity of Breadth-First Search is better than the auxiliary space of Depth-First Search. So let’s use Breadth-First Search instead of Depth-First Search for a search in our solution.</p><p>Let’s now think about how Breadth-First search would work. The first step will initialize a queue to keep track of which positions to check later. If clicked cell is 0, we add it to our queue, turning its value to -2, than check all surrounding cells <em>(x +/- 1, y +/- 1)</em>, and if they equal 0, add them to our queue, turn them to -2, and remove our cell <em>(x, y)</em> from the queue. We are going to repeat the same to the next position in the queue with while loop till the time when our queue is empty. Our changes on the board are done.</p><h4>Solution:</h4><pre>function <strong>click</strong>(field, clickX, clickY) {<br>  let numRows = field.length,<br>    numCols = field[0].length,<br>    toCheck = [];<br>  if (field[clickX][clickY] === 0) {<br>    toCheck.push([clickX, clickY]);<br>  }<br>  while (toCheck.length) {<br>    let [x, y] = toCheck.shift();<br>    for (let i = x - 1; i &lt;= x + 1; i++) {<br>      for (let j = y - 1; j &lt;= y + 1; j++) {<br>        if (<br>          0 &lt;= i &amp;&amp;<br>          i &lt; numRows &amp;&amp;<br>          0 &lt;= j &amp;&amp;<br>          j &lt; numCols &amp;&amp;<br>          field[i][j] === 0<br>        ) {<br>          field[i][j] = -2;<br>          toCheck.push([i, j]);<br>        }<br>      }<br>    }<br>  }<br>  return field;<br>}</pre><h3>#8 Rotating 2D Array</h3><p>You’re given a two-dimensional array which is square, a number of columns is equal to a number of rows. Write a function, that rotates this array by 90 degrees clockwise direction.</p><p><strong>Examples:</strong></p><pre>Input : <br>arr = [[1,2,3],<br>       [4,5,6],<br>       [7,8,9]]<br>Output : <br>      [[7,4,1],<br>       [8,5,2],<br>       [9,6,3]]</pre><p>To solve this problem we need to known where the new coordinates should be for each item after rotating by 90 degrees. Item in the top left corner goes to the top right corner, the second item ends up the last item in the second row… Is there a simple equation to express these movements? In our example you can see that the new row index is simply equal to the old column index. Top side in a given array corresponds to the right side in a new array, row becomes a column. So, new column index equal previous row index, and the new row index we can get from old column, where old column index was from 0 to n-1, where n is number of rows, becomes new row index from n-1 to 0 order. So, new row index is equal n-1minus previous column index.</p><p>Here is out of place solution, look at <em>rotateOutOfPlace</em> function. Create a new two dimensional array of the same shape and the same size as the original one by copying the original array or initializing new one with the same size. Then copy each item of original array to the new location in the new array. In the end, return a reference to the newly created two dimensional array.</p><p>Very common interview question is to solve this problem without using any extra space, modifying existing array and auxiliary space is <em>O(1)</em>, look at <em>rotateInPlace </em>function. Item in the top left corner goes to the top right corner, item in the top left corner will go to the right bottom corner…</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*pngYhNYlox8Ie0CtWsjmeQ.jpeg" /></figure><p>When we shuffle elements around an array, we need to track the values ​​in these positions so that we do not lose them. An easy way to do this is to create an array of four elements. We can move these values ​​in two steps. First go through these elements and save the values ​​in a temporary array. Then repeat these steps, copying the items from the previous position again. The center does not move when we rotate this array 90 degrees. Unlike the previous solution, we can not simply go through the whole array in rows using this method. If we do this, each element will be rotated four times, moving everything back to its original position.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/506/1*uJ-yO46s2ds0h09NlDhUOQ.jpeg" /></figure><p>If the array has an even number of rows and columns, then we just need to iterate through sub array, whose size is exactly one quarter of the given array. What if the given array has an odd number of rows and columns? We won’t be able to slice array to four equivalent sections anymore. Instead, you need to consider a rectangle shaped region. This way you will be able to cover the whole given two-dimensional array except for the value in the center, which we can ignore, it doesn’t move anywhere when array rotate by 90 degrees. We can consider the even case and the odd case separately. Another way is to simply iterate the row index from zero to floor of array length over two minus one. The floor operation selects the largest integer value that is less or equal to the given value. The column index should go from zero to ceil of array length over two minus one. Ceil operation is similar to floor, but exactly the opposite, it would return the smallest integer value that is greater than or equal to the given value. The idea is for each square cycle, we swap the elements involved with the corresponding cell in the sub array from top to left, left to bottom, bottom to right and from right to top one at a time storing them in temporary array with four elements and then we swap our four sub arrays in the entire array.</p><h4>Solution:</h4><pre>function <strong>rotateOutOfPlace</strong>(arr) {<br>  let rotatedArr = arr.map(a =&gt; a.slice());<br>  for (let i = 0; i &lt; arr.length; i++) {<br>    for (let j = 0; j &lt; arr.length; j++) {<br>      let newI = j,<br>        newJ = arr.length - 1 - i;<br>      rotatedArr[newI][newJ] = arr[i][j];<br>    }<br>  }<br>  return rotatedArr;<br>}</pre><pre>function <strong>rotateInPlace</strong>(arr) {<br>  for (let i = 0; i &lt; Math.ceil(arr.length / 2); i++) {<br>    for (let j = 0; j &lt; Math.floor(arr.length / 2); j++) {<br>      let tmp = [-1, -1, -1, -1],<br>        curI = i,<br>        curJ = j;<br>      for (let k = 0; k &lt;= 3; k++) {<br>        tmp[k] = arr[curI][curJ];<br>        let t = curI;<br>        curI = curJ;<br>        curJ = arr.length - 1 - t;<br>      }<br>      for (let k = 0; k &lt;= 3; k++) {<br>        arr[curI][curJ] = tmp[(k + 3) % 4];<br>        let t = curI;<br>        curI = curJ;<br>        curJ = arr.length - 1 - t;<br>      }<br>    }<br>  }<br>  return arr;<br>}</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=99e62af06a88" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Essential Coding Interview Questions with Javascript (Part I)]]></title>
            <link>https://medium.com/@kategorychnost/essential-coding-interview-questions-with-javascript-part-i-b4ab3101660d?source=rss-1ebc4df229f3------2</link>
            <guid isPermaLink="false">https://medium.com/p/b4ab3101660d</guid>
            <category><![CDATA[coding-interviews]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[string]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[arrays]]></category>
            <dc:creator><![CDATA[Nick Maslov]]></dc:creator>
            <pubDate>Wed, 05 Sep 2018 17:40:06 GMT</pubDate>
            <atom:updated>2018-09-05T17:44:31.129Z</atom:updated>
            <content:encoded><![CDATA[<p><strong>(Array and String Problems)</strong></p><p>It is very important to get acquainted with various data structures and how to apply them correctly. This article presents the most common interview questions and popular problems with arrays, two-dimensional arrays, queues, stacks, binary search trees, graphs, etc. To be comfortable with this article, you should be familiar with these data structures and have some basic knowledge of Javascript. Examples of these problems I got in Python tutorials, but I wanted to solve them using JavaScript because JS is one of the most popular programming languages and is required for any web developer.</p><p>Links to other problems: <a href="https://medium.com/@kategorychnost/essential-coding-interview-questions-with-javascript-part-ii-99e62af06a88">Part II</a>, <a href="https://medium.com/@kategorychnost/essential-coding-interview-questions-with-javascript-part-iii-8c8addc8a3fb">Part III</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/750/1*bUoMzQnhJqivADUyepojXA.jpeg" /></figure><h3>#1 Most Frequently Occurring Item in an Array</h3><p>Given an array, find the most frequent element in it. If there are multiple elements that appear maximum number of times, print any one of them.</p><p><strong>Examples:</strong></p><pre>Input : arr = [1, 3, 2, 1, 4, 1]<br>Output : 1<br>1 appears three times in array which<br>is maximum frequency.</pre><pre>Input : arr[] = [10, 20, 10, 20, 30, 20, 20]<br>Output : 20</pre><p>The naive approach is to run two loops. The time complexity of this approach is <em>O(n²)</em>. An efficient solution, which is requiring to know on interviews, is to use hashing and time complexity <em>O(n)</em>. <br>We create a hash table and store elements and their frequency counts as key-value pairs. At the same time, we dynamically store the maximum repeating element and its frequency in individual variables, so when the loop through the array is completed, we already have the answer.</p><p><strong>Solution:</strong></p><pre>function <strong>mostFrequent</strong>(arr) {<br>  let maxCount = -1,<br>    maxItem = null,<br>    count = {};<br>  for (let i of arr) {<br>    if (!count.hasOwnProperty(i)) count[i] = 1;<br>    else count[i] += 1;<br>    if (count[i] &gt; maxCount) {<br>      maxCount = count[i];<br>      maxItem = i;<br>    }<br>  }<br>  return maxItem;<br>}</pre><h3>#2 Common Elements in Two Sorted Arrays</h3><p>Given two arrays sorted in ascending order, print all intersections - common elements in these arrays.</p><p><strong>Examples:</strong></p><pre>Input :<br>a = [1, 5, 10, 20, 40, 80]<br>b = [6, 7, 20, 80, 100]<br>Output: 20, 80</pre><pre>Input :<br>a = [1, 5, 5]<br>b = [3, 4, 5, 5, 10]<br>Output: 5, 5</pre><p>First, we have to initialize an empty array for the result, and two pointers which point to first elements at given two arrays. Pointer with smaller number will move to the next element each step. If numbers are equal, we are adding this item to our result and move pointers to next items. The time complexity will be <em>O(max(n, m))</em>, where is <em>n</em> is a number of items in first array, <em>m</em> is a number of items in second.</p><p><strong>Solution:</strong></p><pre>function <strong>commonElements</strong>(a, b) {<br>  let p1 = 0,<br>    p2 = 0,<br>    result = [];<br>  while (p1 &lt; a.length &amp;&amp; p2 &lt; b.length) {<br>    if (a[p1] === b[p2]) {<br>      result.push(a[p1]);<br>      p1 += 1;<br>      p2 += 1;<br>    } else if (a[p1] &gt; b[p2]) {<br>      p2 += 1;<br>    } else {<br>      p1 += 1;<br>    }<br>  }<br>  return result;<br>}</pre><h3>#3 Is One Array a Rotation of Another?</h3><p>Determine if two arrays are a rotated version of each other, return boolean, assume that no duplicates.</p><p><strong>Examples:</strong></p><pre>Input : <br>a = [1, 2, 3, 4, 5, 6, 7]<br>b = [5, 6, 7, 1, 2, 3, 4]<br>Output : true</pre><pre>Input : <br>a = [1, 2, 3, 4, 5, 6, 7]<br>b = [5, 6, 7, 8, 9, 10]<br>Output : false</pre><p>To solve this problem first of all what we need is to check if array<em> A </em>and <em>B</em> has the same length. If they don’t, rotation impossible. After that let’s pick any element from array <em>A</em> and find the same in <em>B</em>. If you can’t find it, there is no rotation. If you do find it, check if the elements after that the same, and after, and so on. Any different items - return false. When you get last item, without returning false, than you should return true.<br>Following algorithm has time complexity <em>O(N)</em>.</p><p><strong>Solution:</strong></p><pre>function <strong>isRotaion</strong>(a, b) {<br>  if (a.length !== b.length) return false;<br>  let key = a[0],<br>    keyI = -1;<br>  for (let i = 0; i &lt; b.length; i++) {<br>    if (b[i] === key) keyI = i;<br>  }<br>  if (keyI === -1) return false;<br>  for (let i = 0; i &lt; a.length; i++) {<br>    let j = (keyI + i) % a.length;<br>    if (a[i] !== b[j]) return false;<br>  }<br>  return true;<br>}</pre><h3>#4 Non-Repeating Character</h3><p>Write a function to find the first non-repeated character in a string.</p><p><strong>Examples:</strong></p><pre>Input : str = &#39;abacddbec&#39;<br>Output : &#39;e&#39;</pre><pre>Input : str = &#39;hello world&#39;<br>Output : &#39;h&#39;</pre><p>Here’s a linear solution <em>O(n)</em> to the non-repeating character problem. We need to iterate through the entire string with the fo loop, counting a number of times each character appears using a hash table. Then iterate through the string again and return character whose count is only one. If there is no such a character, return null.</p><p><strong>Solution:</strong></p><pre>function <strong>nonRepeating</strong>(str) {<br>  let charCount = {};<br>  for (let c of str) {<br>    if (charCount.hasOwnProperty(c)) charCount[c] += 1;<br>    else charCount[c] = 1;<br>  }<br>  for (let c of str) {<br>    if (charCount[c] === 1) return c;<br>  }<br>  return null;<br>}</pre><h3>#5 One Edit Away Strings</h3><p>Given two string s1 and s2, find if s1 can be converted to s2 with exactly one edit. An edit between two strings is one of the following changes:</p><ol><li>Insert a character</li><li>Remove a character</li><li>Replace a character</li></ol><p>Return true or false.</p><p><strong>Examples:</strong></p><pre>Input :<br>s1 = &#39;hello&#39;<br>s2 = &#39;hell0&#39; <br>Output: true</pre><pre>Input :<br>s1 = &#39;hello&#39;<br>s2 = &#39;hell&#39;<br>Output: true</pre><p>We have to check 4 cases. <br>First, if the length between two strings differs by more than 1 character, we return false, because we have to edit several times. <br>Secondly, in case two strings are of equal length, we need to compare each character in the strings, if there are several differences, return false, if less, true. <br>In case, if s1 is longer than s2, we have to count difference, starting from, and when difference will be equal 1, just change index to index + 1 of longer s1 string. If by the last character of s2, the difference didn’t change return true, else false.<br>The last case, when we need to add character to s1, we can just use the previous method, but compare s2 with s1.<br>This problem has a lot of problems in it, so the best way to organize code is to divide it to subfunctions.</p><p><strong>Solution:</strong></p><pre>function <strong>isOneAway</strong>(s1, s2) {<br>  if (s1.length - s2.length &gt; 1 || s2.length - s1.length &gt; 1) return false;<br>  else if (s1.length === s2.length) return isOneAwaySameLength(s1, s2);<br>  else if (s1.length &gt; s2.length) return isOneAwayDiffLength(s1, s2);<br>  else return isOneAwayDiffLength(s2, s1);</pre><pre>function <strong>isOneAwaySameLength</strong>(s1, s2) {<br>    let countDiff = 0;<br>    for (let i = 0; i &lt; s1.length; i++) {<br>      if (s1[i] !== s2[i]) {<br>        countDiff += 1;<br>        if (countDiff &gt; 1) return false;<br>      }<br>    }<br>    return true;<br>  }</pre><pre>function <strong>isOneAwayDiffLength</strong>(s1, s2) {<br>    let i = 0,<br>      countDiff = 0;<br>    while (i &lt; s2.length) {<br>      if (s1[i + countDiff] === s2[i]) {<br>        i += 1;<br>      } else {<br>        countDiff += 1;<br>        if (countDiff &gt; 1) return false;<br>      }<br>    }<br>    return true;<br>  }<br>}</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b4ab3101660d" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>