Competitive programming questions

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

Day 66 Question: Restore IP Addresses Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] Difficulty: Medium ============================= Linux command for the day: ============================= Linux readelf Usage: In Linux, whenever you compile a program and get the object file, it will be in ELF format. “readelf” command is used to read the ELF details of the file. “readelf” and “objdump” makes sense if you are a programmer. It is good to know. Options: -a Displays all the information about the file. -h Displays the header information -l Display the program headers -s Display the symbol table of the file. Example: For the example, I have written a C program and compiled and got the object file. So we shall see what the command will give the output for different options. 1. readelf –a hello_world.o 2. readelf –h hello_world.o 3. readelf -l hello_world.o

Day 65 Question: Reverse Linked List II Reverse a linked list from position m to n. Do it in one-pass. Note: 1 ≤ m ≤ n ≤ length of list. Example: Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL Difficulty: Medium solution to the previous questions will be provided soon. ============================= Linux command for the day: ============================= Linux mv Usage: “mv” command is used to move the file from source to destination. It is like cut and paste. It can also be used to rename a file or directory. Options: -b Backup the destination file if it exists. The backup file will be appended by “~” symbol. -f If the destination file is read only, force option will forcefully replace the destination file and delete the original file. If “-f” option is not used, then “mv” command will ask for confirmation before replacing the destination file, if it is read only file. -i Interactive mode, will prompt before overwriting an existing file. -n Never overwrite an existing file. -u Never update an existing file if it is newer. If the existing file is older than the soruce file, then overwrite the destination file. -v Print the output of the operation. --help Display help message --version Display version information. Example: 1. mv –v source.txt destination.txt

Day 64 Question: Decode Ways A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. Example 1: Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6). Difficulty: Medium Companies Asked: Facebook Amazon Note: The group link is the group description section. Request you to please share it with your firends and in other whatsapp groups. It will help others to get interested in programming. ============================= Linux command for the day: ============================= Linux cp Usage: “cp” command is used to copy files and directory from one place to another. Copying the files from Options: -a Copy the file and retain the metadata of the file as much as possible. --attributes-only Don’t copy the file, create the file and copy the attributes. If the file already exists then update the attributes. -f Force copy, if there is a file already exist at the destination, then delete it and copy the file. -r Copy the directory contents recursively. -v Verbose mode. Display information after completion of the command. -u Update, when source is newer than the destination Example: 1. Simple Copy. “cp source.txt destination.txt” 2. Copy related files. “cp *.txt myDir”. From the image below, we have copied the files ending with “txt” extension to “myDir” directory. 3. Copy in interactive mode. If the destination file already exists, then it will prompt a message. “cp -i source.txt destination.txt”. In the image below, as there is already file called as “copied_file.txt”, it will ask for confirmation before replacing the file.

Day 63 Question: Valid Number Validate if a given string is numeric. Some examples: "0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true Difficulty: Hard ============================= Linux command for the day: ============================= Linux rm Usage: “rm” command is used to delete files and directories in Linux. Options: -f Force remove all the files and sub directories specified. -i Prompt before deleting a file. -r Delete directories recursively. -d remove empty directory Example: 1. Remove file. “rm hello.txt” 2. Force remove files and directory including sub directories. “rm –fr test_dir” 3. Ask confirmation before deleting any file every time. “rm –i hello.txt”

Day 62 Question: Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. Example: Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] Difficulty: Medium Update with your answers in comment section of below link: http://bit.ly/q_62 ============================= Linux command for the day: ============================= Linux touch Usage: Touch command is used to create, modify date, time of a file. Options: -a Change the access time only. -c If the file doesn’t exist then, don’t create a new file. -d update access and modified time -m change modified time only -t create file using specified time. [YYDDHHMM] Example: 1. Create a new file. “touch hello.txt” 2. Change the access time. “touch –a hello.txt”. By using “stat” command we can see the access time and modified time as shown in below image. File was accessed and modified at “12:08”. After running the “touch –a hello.txt”, the access time has been changed to “12:10” 3. Change the access and modified time. “touch –d hello.txt”. Same explanation as above, but additional to changing accessed time, it will also change the modified time. 4. Create a file using specified time [YYDDHHMMte. “touch –t test.txt”t 5. Don’t create new file, if it is not exist. “touch –c test_1.txt”

Solution to Queston 61: http://bit.ly/q_61 Update with your answers in the comment section of the post above.

Day 61 Question: The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. Example 1: Input: 2 Output: [0,1,3,2] Explanation: 00 - 0 01 - 1 11 - 3 10 - 2 For a given n, a gray code sequence may not be uniquely defined. For example, [0,2,3,1] is also a valid gray code sequence. 00 - 0 10 - 2 11 - 3 01 - 1 Example 2: Input: 0 Output: [0] Explanation: We define the gray code sequence to begin with 0. A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1. Therefore, for n = 0 the gray code sequence is [0]. Difficulty: Medium ============================= Linux command for the day: ============================= Linux file Usage: File command is used to determine the type of the file. Options: -b Brief mode. It will display only the type of file without the file name. -i --mime Displays the mime type of the file. -z Look inside a compressed files. * Displays the type of all the files. Example: 1. To know type of file. Use “file ”. 2. To know the file name in brief mode. “file –b ”. 3. To know the mime type of the file. “file –i ” 4. To know the file type inside a compressed file. “file –z ” 5. To know the file types of all the files inside a directory. “file *”.