Competitive Programming

Solution for day 78 question: Sudoku Solver: http://bit.ly/q_78 Please update your answers or queries in the comment section of the post.

Day 78 Question: Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid More details and hint in the below link. http://bit.ly/q_78 Please update your answers in the comment section of the post.

Solution for day 77 question: http://bit.ly/q_77 Please update your solutions in the comment section of the post

Day 77 Question: Gas Station There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. Note: If there exists a solution, it is guaranteed to be unique. Both input arrays are non-empty and have the same length. Each element in the input arrays is a non-negative integer. Additional Details in the link below. http://bit.ly/q_77 Update your solutions in the comment section of the post. Difficulty: Medium ============================= Linux command for the day: ============================= Linux Date Usage: Date command is used to display and to set the date in Linux. Options: -d Display the date described by STRING not by ‘now’. -I Display date in ISO 8601 format. --rfc-2822 Output date and time in RFC 2822 format. -s Set time described by string STRING. %a The abbreviated weekday name (e.g., Sun). %A The full weekday name (e.g., Sunday). %b The abbreviated month name (e.g., Jan). %B Locale's full month name (e.g., January). %c The date and time (e.g., Thu Mar 3 23:05:25 2005). %C The current century; like %Y, except omit last two digits (e.g., 20). Example: 1. To change the date to 2018-08-17 24:58:10 use” date -s "2018-08-17 24:58:10" “ 2. To display present date. “date” 3. To display current day use “date “+%a”” 4. To display current month use “ date ”+%b” “.

Solution to 76th question http://bit.ly/q_76

Day 76 Question: Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'. Additional Details in the link below. http://bit.ly/q_76 Update your solutions in the comment section of the post. Difficulty: Medium Companies Asked: Google Note: You can support this group by sharing the group link in whatsapp, telegram, social media. If you have a technical blog, you can share the link, it would be helpful for many programmers.

Solution To Provious Questions: 74: Single Number Solution: http://bit.ly/q_74 75: Palindrome Partitioning Solution: http://bit.ly/q_75

Solution To Provious Questions: 70. Check if Sudoku is valid or not Solution: http://bit.ly/q_70 71. Given a triangle, find the minimum path sum from top to bottom. Solution: http://bit.ly/q_71 72. Best Time to Buy and Sell Stock Solution: http://bit.ly/q_72 73. Word Ladder Solution: http://bit.ly/q_73

Day 75 Question: Palindrome Partitioning explanation and solution in CPP Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example: Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ] Difficulty: Medium Write your solution in below link: http://bit.ly/q_75 ============================= Linux command for the day: ============================= Linux Find Usage: Find command is used to find the file in a directory. General syntax of find command is below: find [options] [starting_path] [file_name] Options: -iname Search without regard for text case. -type f Search for files. -type d Search for directories. -maxdepth set the maximum depth of directory find command should search. Example: 1. To list all the files in a directory use “find” 2. To find the file “ifup-ppp” file in present directory use “find . –name ifup-ppp” 3. To list all the files ending with “.log” in present directory we use “find . –name “*.log”” 4. To find only directory with the name use “-type d” option. File having the same name will not be displayed. “find . –type d –name “hello” “. 5. To search multiple directories together use “find /usr/local /etc –name file.txt “

Day 74 Question: Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Example 1: Input: [2,2,1] Output: 1 Example 2: Input: [4,1,2,1,2] Output: 4 Difficulty: Easy ============================= Linux command for the day: ============================= Linux diff command Usage: “diff” command is used to compare files line by line. Options: -a Added -c changed -d deleted Example: I have 2 files. file1.txt contents: 1 2 3 4 file2.txt contents: 2 3 5 6 Now if we do “diff –c file1.txt file2.txt” then it will display the difference between the files.

Day 73 Question: Word Ladder Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Note: Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same. Example 1: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5. Example 2: Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in wordList, therefore no possible transformation. Difficulty: Medium Update your answers in below link: http://bit.ly/q_73 ============================= Linux command for the day: ============================= Linux less command Usage: Similar to “more” command, but faster. If the file is very large, “less” command will only load the contents that fits for one screen and access the contents page by page. Example: less num.txt

Day 72 Question: Best Time to Buy and Sell Stock Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one. Example 1: Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price. Example 2: Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0. Difficulty: Easy ============================= Linux command for the day: ============================= Linux more command Usage: “more” command is similar to “cat” command, but it will only display one screenful at a time. It means if you have a contents that cannot be fit in one screen, then it will display the contents at one screen at a time, below are the keys to move up and down the contents displayed. Space bar Go to next page Enter Key Move one-line down b Go to previous page / Search the page Options: -num It will be the number of lines that will make a one screenful. -d Display help text if you enter wrong character, instead of ringing a bell sound Example: more num.txt

Day 71 Question: Given a triangle, find the minimum path sum from top to bottom. In each step you can only move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). Follow up question: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle. Difficulty: Medium More details in the below link: http://bit.ly/q_71 ============================= Linux command for the day: ============================= Linux tac command Usage: As “tac” is reverse of “cat” it displays the output reverse order. Example: “tac number.txt”

Day 70 Question: Check if the given board is valid Sudoku or not explanation with solution in CPP Determine if a 9×9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3×3 sub-boxes of the grid must contain the digits 1-9 without repetition. Difficulty: Medium More details in the below link: http://bit.ly/q_70 ============================= Linux command for the day: ============================= Linux cat command Usage: “cat” stands for concatenate. The basic function of this command is to display the contents of the file. In various situation “cat” command is used to copy the file contents from one file to another. We shall see them in the example below. Note: “cat” command will display the contents of entire file. Not part of contents like we saw it “head” and “tail” command. Options: -A Command is used to show all the contents. -E Display “$” at the end of every line -n Show the line numbers > Copy the contents from one file to another. >> Append the content of first file to second file. Example: I have a “numbers.txt” file, having numbers from 1 to 20. “cat numbers.txt”. Displays the contents of the file. “cat –E numbers.txt”. Displays “$” at end of every line. “cat –n numbers.txt”. Displays the line number. “cat numbers.txt > new.txt”. Copy the number.txt contents to new.txt . “cat numbers.txt >> new.txt”. Appends the number.txt contents to new.txt .

Solutions to previous questions Restore IP Addresses http://bit.ly/q_66 Insert Interval http://bit.ly/q_67 Pascal’s triangle explanation with solution http://bit.ly/q_68 Pascal’s triangle 2 explanation with solution http://bit.ly/q_69

Solution to previous problems: 61: Gray code http://bit.ly/q_61 62: Subsets 2 http://bit.ly/q_62 63: Valid Number http://bit.ly/q_63 64: Decode Ways http://bit.ly/q_64 65: Reverse Linked List II http://bit.ly/q_65

Day 69 Question: Pascal's triangle 2 Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle. Note that the row index starts from 0. In Pascal's triangle, each number is the sum of the two numbers directly above it. Example: Input: 3 Output: [1,3,3,1] Follow up: Could you optimize your algorithm to use only O(k) extra space? Write your answers in below link: http://bit.ly/q_69 Difficulty: Easy ============================= Linux command for the day: ============================= Linux tail command Usage: Like “head”, tail will display last 10 lines from the file. If no file is specified, then it will read from standard input. “tail” command is useful for reading log messages. As these messages are updated frequently, we can check the last error message without opening the file. Options: -c Display the number of bytes specified from the end of the file. -f Continuously display the last part of the file. It will loop the file, if there is any new data at the end of the file, then it will be displayed. -n Display the last “n” number of lines as specified. -v Display the file name. Example: 1. “tail number.txt”. This will display the last 10 lines from the file. 2. “tail –n 5 number.txt”. This will display the last 5 lines from the file. 3. “tail –f /var/log/messages”. This will continuously loop the file, and will display if any new data appears.

Day 68 Question: Given a non-negative integer numRows, generate the first numRows of Pascal's triangle. Example: Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] Difficulty: Medium Companies asked: Amazon, Adobe Post your answers in below link: http://bit.ly/q_68 ============================= Linux command for the day: ============================= Linux head command Usage: “head” command is used to display first 10 lines from the file. If no file is specified, then it will read 10 lines from the input. Options: -c Print number of bytes of each file. -n Print number of lines specified. -q Do not display the file name. -v Display the file name while printing. Example: I have a “number.txt” file, that has numbers from 1 to 20. 1. “head”. As we have only entered the command without entering the file name, it will take input from the console and displays it immediately. 2. “head –n 5 number.txt” . It will print first 5 lines from the specified file. 3. “head –q number.txt”. It will not print the file name. 4. “head –v number.txt”. It will print the file name.

Solutions to previous questions Remove Duplicates from Sorted List II in CPP http://bit.ly/q_59 Partition List in CPP http://bit.ly/q_60

Day 67 Question: Insert Interval Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Example 2: Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10]. Difficulty: Hard ============================= Linux command for the day: ============================= Linux objdump Usage: objdump is used to get the details about the object file. Options: -a If any of the object file is an archive, it will display that information -h Display header section -g Display debugging information -d Display assembly information from the machine instructions. Example: 1. objdump –a hello_world.o 2. objdump –h hello_world.o 3. objdump –g hello_world.o 4. objdump –d hello_world.o