Friend Circle - Hackerrank

 Posted on June 26, 2015  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Reference - Hackerrank Problem There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature, i.e., if A is friend of B and B is friend of C, then A is also friend of C. A friend circle is a group of students who are directly or indirectly friends. You are given a N×N−matrix M which consists of characters Y or N. [Read More]
kodeknight  incomplete  hackerrank 

Convert Binary Tree to Doubly linked list in level order

 Posted on May 16, 2015  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Question: write an algorithm to convert a binary tree into a double linked list. For example, if the input is the binary tree below: The output will be a double linked list like this: Solution: there are two tasks in converting a binary tree to a linked list. First of all, we must traverse the tree and visit all the nodes. Second of all, we must break each node from the tree and add it into the linked list. [Read More]
conversion  Binary Tree  BT  kodeknight  incomplete  Doubly Linked List  DLL 

Number of steps required to convert string 1 to string2 when only bring character to first index operation is giving

 Posted on May 3, 2015  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Given 2 strings - s1 and s2, when only 1 operation is allowed - Moving character at a time but only to the first position. Example Example 1 Input s1 = abcd s2 = bacd Output Ans = 1 Reason, just move b forward and we get it. Example 2 Input A = (a)b(cd)e(f)g(hij) B = ahdjcifbeg Output Ans =7 Explanation A = (a)b(cd)e(f)g(hij) B = ahdjcifbeg Characters b,e,g are in the order, rest characters have to brought first. [Read More]
conversion  Dynamic Programming  DP  incomplete  directi 

Find the largest subarray with sum of 0 in the given array

 Posted on April 17, 2015  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem An array contains both positive and negative elements, find the largest subarray whose sum equals 0. Example int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2} int output = {4, 6, 3, -9, -5, 1} of length 6 Solution Method 1 - Brute force This is simple. Will write later (incomplete) Method 2 - Storing the sum upto ith element in temp array Given an int[] input array, you can create an int[] tmp array where [Read More]
sub-array  Dynamic Programming  DP  incomplete  array  sum 

Skiplists

 Posted on July 25, 2014  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

Goal To understand skiplist. Definition Skiplist is a dynamic search structure, as it is dynamic when it comes to insertion and deletion, which supports search). Other dynamic search structure: Treaps Red black tree B-Trees (2-3 trees etc) Operations on skiplist Search - O(log n) Insert - O(log n) Delete - O(log n) These operations are with high probability, 1/polynomial depending on polynomial number of operation. [Read More]
kodeknight  incomplete  Data Structure  linux  unix  concurrency  skip-list 

Find max subsquare whose border values are all 1

 Posted on July 24, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels. Solution We are going to scan column by column, checking to see if this column can be the left-border of the desired subsquare. Along each column, we build “sliding windows”, from large size to small size. [Read More]
kodeknight  hard  incomplete  CrackingTheCodingInterview 

Game of Master Mind

 Posted on July 18, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem The Game of Master Mind is played as follows: The computer has four slots containing balls that are red (R), yellow (Y), green (G) or blue (B). For example, the computer might have RGGB (e.g., Slot #1 is red, Slots #2 and #3 are green, Slot #4 is blue). You, the user, are trying to guess the solution You might, for example, guess YRGB. When you guess the correct color for the correct slot, you get a “hit” If you guess a color that exists but is in the wrong slot, you get a “pseudo-hit”. [Read More]
kodeknight  Moderate  incomplete  CrackingTheCodingInterview