Last date to Register
About
SOS TECH HACK is a community-focused 58 days Hackathon, designed
especially for the community's needs. Whether you are a beginner or an expert,
here is a perfect chance to showcase your skills and witness a competitive yet
inclusive community around it.
This year it is going to be organized from 10/10/2022 in online mode.
Challenges
Max Points on a Line
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line. Example 1: Input: points = [[1,1],[2,2],[3,3]] Output: 3 Example 2: Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Constraints: 1 <= points.length <= 300 points[i].length == 2 -104 <= xi, yi <= 104 All the points are unique.
Word Break II
Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order. Note that the same word in the dictionary may be reused multiple times in the segmentation. Example 1: Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] Output: ["cats and dog","cat sand dog"] Example 2: Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"] Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"] Explanation: Note that you are allowed to reuse a dictionary word. Example 3: Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: [] Constraints: 1 <= s.length <= 20 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 10 s and wordDict[i] consist of only lowercase English letters. All the strings of wordDict are unique.
String to Integer (atoi)
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function). The algorithm for myAtoi(string s) is as follows: Read in and ignore any leading whitespace. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2). If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1. Return the integer as the final result. Note: Only the space character ' ' is considered a whitespace character. Do not ignore any characters other than the leading whitespace or the rest of the string after the digits. Example 1: Input: s = "42" Output: 42 Explanation: The underlined characters are what is read in, the caret is the current reader position. Step 1: "42" (no characters read because there is no leading whitespace) ^ Step 2: "42" (no characters read because there is neither a '-' nor '+') ^ Step 3: "42" ("42" is read in) ^ The parsed integer is 42. Since 42 is in the range [-231, 231 - 1], the final result is 42. Example 2: Input: s = " -42" Output: -42 Explanation: Step 1: " -42" (leading whitespace is read and ignored) ^ Step 2: " -42" ('-' is read, so the result should be negative) ^ Step 3: " -42" ("42" is read in) ^ The parsed integer is -42. Since -42 is in the range [-231, 231 - 1], the final result is -42. Example 3: Input: s = "4193 with words" Output: 4193 Explanation: Step 1: "4193 with words" (no characters read because there is no leading whitespace) ^ Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+') ^ Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit) ^ The parsed integer is 4193. Since 4193 is in the range [-231, 231 - 1], the final result is 4193. Constraints: 0 <= s.length <= 200 s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.
Roman to Integer
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II. Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used: I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900. Given a roman numeral, convert it to an integer. Example 1: Input: s = "III" Output: 3 Explanation: III = 3. Example 2: Input: s = "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3. Example 3: Input: s = "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4. Constraints: 1 <= s.length <= 15 s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M'). It is guaranteed that s is a valid roman numeral in the range [1, 3999].
Regular Expression Matching
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Example 1: Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa", p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". Example 3: Input: s = "ab", p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)". Constraints: 1 <= s.length <= 20 1 <= p.length <= 30 s contains only lowercase English letters. p contains only lowercase English letters, '.', and '*'. It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.
Zigzag Conversion
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) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string s, int numRows); Example 1: Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR" Example 2: Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I Example 3: Input: s = "A", numRows = 1 Output: "A" Constraints: 1 <= s.length <= 1000 s consists of English letters (lower-case and upper-case), ',' and '.'. 1 <= numRows <= 1000
Reverse array in groups
Given an array arr[] of positive integers of size N. Reverse every sub-array group of size K. Note: If at any instance, there are no more subarrays of size greater than or equal to K, then reverse the last subarray (irrespective of its size). Example 1: Input: N = 5, K = 3 arr[] = {1,2,3,4,5} Output: 3 2 1 5 4 Explanation: First group consists of elements 1, 2, 3. Second group consists of 4,5. Example 2: Input: N = 4, K = 3 arr[] = {5,6,8,9} Output: 8 6 5 9 Your Task: You don't need to read input or print anything. The task is to complete the function reverseInGroups() which takes the array, N and K as input parameters and modifies the array in-place. Expected Time Complexity: O(N) Expected Auxiliary Space: O(N) Constraints: 1 ≤ N, K ≤ 107 1 ≤ A[i] ≤ 1018
Validate an IP Address
Write a program to Validate an IPv4 Address. According to Wikipedia, IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots, e.g., 172.16.254.1 . A valid IPv4 Address is of the form x1.x2.x3.x4 where 0 <= (x1, x2, x3, x4) <= 255. Thus, we can write the generalized form of an IPv4 address as (0-255).(0-255).(0-255).(0-255). Note: Here we are considering numbers only from 0 to 255 and any additional leading zeroes will be considered invalid. Your task is to complete the function isValid which returns 1 if the given IPv4 address is valid else returns 0. The function takes the IPv4 address as the only argument in the form of string. Example 1: Input: IPv4 address = 222.111.111.111 Output: 1 Explanation: Here, the IPv4 address is as per the criteria mentioned and also all four decimal numbers lies in the mentioned range. Example 2: Input: IPv4 address = 5555..555 Output: 0 Explanation: 5555..555 is not a valid IPv4 address, as the middle two portions are missing. Your Task: Complete the function isValid() which takes the address in the form of string s as an input parameter and returns 1 if this is a valid address otherwise returns 0. Expected Time Complexity: O(N), N = length of the string. Expected Auxiliary Space: O(1) Constraints: 1<=length of string <=50 Note: The Input/Output format and Example given are used for the system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.
Remove loop in Linked List
Given a linked list of N nodes such that it may contain a loop. A loop here means that the last node of the link list is connected to the node at position X(1-based index). If the link list does not have any loop, X=0. Remove the loop from the linked list, if it is present, i.e. unlink the last node which is forming the loop. Example 1: Input: N = 3 value[] = {1,3,4} X = 2 Output: 1 Explanation: The link list looks like 1 -> 3 -> 4 ^ | |____| A loop is present. If you remove it successfully, the answer will be 1. Example 2: Input: N = 4 value[] = {1,8,3,4} X = 0 Output: 1 Explanation: The Linked list does not contains any loop. Example 3: Input: N = 4 value[] = {1,2,3,4} X = 1 Output: 1 Explanation: The link list looks like 1 -> 2 -> 3 -> 4 |_________| A loop is present. If you remove it successfully, the answer will be 1. Your Task: You don't need to read input or print anything. Your task is to complete the function removeLoop() which takes the head of the linked list as the input parameter. Simply remove the loop in the list (if present) without disconnecting any nodes from the list. Note: The generated output will be 1 if your submitted code is correct. Expected time complexity: O(N) Expected auxiliary space: O(1) Constraints: 1 ≤ N ≤ 10^4
Diameter of a Binary Tree
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two end nodes. The diagram below shows two trees each with diameter nine, the leaves that form the ends of the longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes). Example 1: Input: 1 / \ 2 3 Output: 3 Example 2: Input: 10 / \ 20 30 / \ 40 60 Output: 4 Your Task: You need to complete the function diameter() that takes root as parameter and returns the diameter. Expected Time Complexity: O(N). Expected Auxiliary Space: O(Height of the Tree). Constraints: 1 <= Number of nodes <= 10000 1 <= Data of a node <= 1000
Next Smallest Palindrome
Given a number, in the form of an array Num[] of size N containing digits from 1 to 9(inclusive). The task is to find the next smallest palindrome strictly larger than the given number. Example 1: Input: N = 11 Num[] = {9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2} Output: 9 4 1 8 8 0 8 8 1 4 9 Explanation: Next smallest palindrome is 94188088149. Example 2: Input: N = 5 Num[] = {2, 3, 5, 4, 5} Output: 2 3 6 3 2 Explanation: Next smallest palindrome is 23632. Your Task: Complete the function generateNextPalindrome() which takes an array num, and an single integer n, as input parameters and returns an array of integers denoting the answer. You don't to print answer or take inputs. Expected Time Complexity: O(N) Expected Auxiliary Space: O(1) Constraints: 1 <= N <= 105 1 <= Num[i] <= 9
Longest Palindromic Substring in Linear Time
Given a string, find the longest substring which is palindrome in Linear time O(N). Input: The first line of input contains an integer T denoting the no of test cases . Then T test cases follow. The only line of each test case contains a string. Output: For each test case print the Longest Palindromic Substring. If there are multiple such substrings of same length, print the one which appears first in the input string. Constraints: 1 <= T <= 100 1 <= N <= 50 Example: Input: 2 babcbabcbaccba forgeeksskeegfor Output: abcbabcba geeksskeeg Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.
Binary Tree to DLL
Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In-Place. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the DLL. TreeToList Example 1: Input: 1 / \ 3 2 Output: 3 1 2 2 1 3 Explanation: DLL would be 3<=>1<=>2 Example 2: Input: 10 / \ 20 30 / \ 40 60 Output: 40 20 60 10 30 30 10 60 20 40 Explanation: DLL would be 40<=>20<=>60<=>10<=>30. Your Task: You don't have to take input. Complete the function bToDLL() that takes root node of the tree as a parameter and returns the head of DLL . The driver code prints the DLL both ways. Expected Time Complexity: O(N). Expected Auxiliary Space: O(H). Note: H is the height of the tree and this space is used implicitly for the recursion stack. Constraints: 1 ≤ Number of nodes ≤ 105 0 ≤ Data of a node ≤ 105
AVL Tree Deletion
Given a AVL tree and N values to be deleted from the tree. Write a function to delete a given value from the tree. Example 1: Tree = 4 / \ 2 6 / \ / \ 1 3 5 7 N = 4 Values to be deleted = {4,1,3,6} Input: Value to be deleted = 4 Output: 5 / \ 2 6 / \ \ 1 3 7 Input: Value to be deleted = 1 Output: 5 / \ 2 6 \ \ 3 7 Input: Value to be deleted = 3 Output: 5 / \ 2 6 \ 7 Input: Value to be deleted = 6 Output: 5 / \ 2 7 Your Task: You dont need to read input or print anything. Complete the function delelteNode() which takes the root of the tree and the value of the node to be deleted as input parameters and returns the root of the modified tree. Note: The tree will be checked after each deletion. If it violates the properties of balanced BST, an error message will be printed followed by the inorder traversal of the tree at that moment. If instead all deletion are successful, inorder traversal of tree will be printed. If every single node is deleted from tree, 'null' will be printed. Expected Time Complexity: O(height of tree) Expected Auxiliary Space: O(height of tree) Constraints: 1 ≤ N ≤ 500
Transpose File
Given a text file file.txt, transpose its content. You may assume that each row has the same number of columns, and each field is separated by the ' ' character. Example: If file.txt has the following content: name age alice 21 ryan 30 Output the following: name alice ryan age 21 30
Path Sum
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children. Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The root-to-leaf path with the target sum is shown. Example 2: Input: root = [1,2,3], targetSum = 5 Output: false Explanation: There two root-to-leaf paths in the tree: (1 --> 2): The sum is 3. (1 --> 3): The sum is 4. There is no root-to-leaf path with sum = 5. Example 3: Input: root = [], targetSum = 0 Output: false Explanation: Since the tree is empty, there are no root-to-leaf paths. Constraints: The number of nodes in the tree is in the range [0, 5000]. -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000
Path Sum
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children. Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The root-to-leaf path with the target sum is shown. Example 2: Input: root = [1,2,3], targetSum = 5 Output: false Explanation: There two root-to-leaf paths in the tree: (1 --> 2): The sum is 3. (1 --> 3): The sum is 4. There is no root-to-leaf path with sum = 5. Example 3: Input: root = [], targetSum = 0 Output: false Explanation: Since the tree is empty, there are no root-to-leaf paths. Constraints: The number of nodes in the tree is in the range [0, 5000]. -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000
Second Highest Salary
SQL Schema Table: Employee +-------------+------+ | Column Name | Type | +-------------+------+ | id | int | | salary | int | +-------------+------+ id is the primary key column for this table. Each row of this table contains information about the salary of an employee. Write an SQL query to report the second highest salary from the Employee table. If there is no second highest salary, the query should report null. The query result format is in the following example. Example 1: Input: Employee table: +----+--------+ | id | salary | +----+--------+ | 1 | 100 | | 2 | 200 | | 3 | 300 | +----+--------+ Output: +---------------------+ | SecondHighestSalary | +---------------------+ | 200 | +---------------------+ Example 2: Input: Employee table: +----+--------+ | id | salary | +----+--------+ | 1 | 100 | +----+--------+ Output: +---------------------+ | SecondHighestSalary | +---------------------+ | null | +---------------------+
Regular Expression Matching
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Example 1: Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa", p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". Example 3: Input: s = "ab", p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)". Constraints: 1 <= s.length <= 20 1 <= p.length <= 30 s contains only lowercase English letters. p contains only lowercase English letters, '.', and '*'. It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.
Reverse Nodes in k-Group
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is. You may not alter the values in the list's nodes, only nodes themselves may be changed. Example 1: Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5] Example 2: Input: head = [1,2,3,4,5], k = 3 Output: [3,2,1,4,5] Constraints: The number of nodes in the list is n. 1 <= k <= n <= 5000 0 <= Node.val <= 1000 Follow-up: Can you solve the problem in O(1) extra memory space?
Max Points on a Line
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line. Example 1: Input: points = [[1,1],[2,2],[3,3]] Output: 3 Example 2: Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Constraints: 1 <= points.length <= 300 points[i].length == 2 -104 <= xi, yi <= 104 All the points are unique.
Word Break II
Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order. Note that the same word in the dictionary may be reused multiple times in the segmentation. Example 1: Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] Output: ["cats and dog","cat sand dog"] Example 2: Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"] Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"] Explanation: Note that you are allowed to reuse a dictionary word. Example 3: Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: [] Constraints: 1 <= s.length <= 20 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 10 s and wordDict[i] consist of only lowercase English letters. All the strings of wordDict are unique.
String to Integer (atoi)
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function). The algorithm for myAtoi(string s) is as follows: Read in and ignore any leading whitespace. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2). If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1. Return the integer as the final result. Note: Only the space character ' ' is considered a whitespace character. Do not ignore any characters other than the leading whitespace or the rest of the string after the digits. Example 1: Input: s = "42" Output: 42 Explanation: The underlined characters are what is read in, the caret is the current reader position. Step 1: "42" (no characters read because there is no leading whitespace) ^ Step 2: "42" (no characters read because there is neither a '-' nor '+') ^ Step 3: "42" ("42" is read in) ^ The parsed integer is 42. Since 42 is in the range [-231, 231 - 1], the final result is 42. Example 2: Input: s = " -42" Output: -42 Explanation: Step 1: " -42" (leading whitespace is read and ignored) ^ Step 2: " -42" ('-' is read, so the result should be negative) ^ Step 3: " -42" ("42" is read in) ^ The parsed integer is -42. Since -42 is in the range [-231, 231 - 1], the final result is -42. Example 3: Input: s = "4193 with words" Output: 4193 Explanation: Step 1: "4193 with words" (no characters read because there is no leading whitespace) ^ Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+') ^ Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit) ^ The parsed integer is 4193. Since 4193 is in the range [-231, 231 - 1], the final result is 4193. Constraints: 0 <= s.length <= 200 s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.
Roman to Integer
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II. Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used: I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900. Given a roman numeral, convert it to an integer. Example 1: Input: s = "III" Output: 3 Explanation: III = 3. Example 2: Input: s = "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3. Example 3: Input: s = "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4. Constraints: 1 <= s.length <= 15 s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M'). It is guaranteed that s is a valid roman numeral in the range [1, 3999].
Regular Expression Matching
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Example 1: Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa", p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". Example 3: Input: s = "ab", p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)". Constraints: 1 <= s.length <= 20 1 <= p.length <= 30 s contains only lowercase English letters. p contains only lowercase English letters, '.', and '*'. It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.
Zigzag Conversion
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) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string s, int numRows); Example 1: Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR" Example 2: Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I Example 3: Input: s = "A", numRows = 1 Output: "A" Constraints: 1 <= s.length <= 1000 s consists of English letters (lower-case and upper-case), ',' and '.'. 1 <= numRows <= 1000
Reverse array in groups
Given an array arr[] of positive integers of size N. Reverse every sub-array group of size K. Note: If at any instance, there are no more subarrays of size greater than or equal to K, then reverse the last subarray (irrespective of its size). Example 1: Input: N = 5, K = 3 arr[] = {1,2,3,4,5} Output: 3 2 1 5 4 Explanation: First group consists of elements 1, 2, 3. Second group consists of 4,5. Example 2: Input: N = 4, K = 3 arr[] = {5,6,8,9} Output: 8 6 5 9 Your Task: You don't need to read input or print anything. The task is to complete the function reverseInGroups() which takes the array, N and K as input parameters and modifies the array in-place. Expected Time Complexity: O(N) Expected Auxiliary Space: O(N) Constraints: 1 ≤ N, K ≤ 107 1 ≤ A[i] ≤ 1018
Validate an IP Address
Write a program to Validate an IPv4 Address. According to Wikipedia, IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots, e.g., 172.16.254.1 . A valid IPv4 Address is of the form x1.x2.x3.x4 where 0 <= (x1, x2, x3, x4) <= 255. Thus, we can write the generalized form of an IPv4 address as (0-255).(0-255).(0-255).(0-255). Note: Here we are considering numbers only from 0 to 255 and any additional leading zeroes will be considered invalid. Your task is to complete the function isValid which returns 1 if the given IPv4 address is valid else returns 0. The function takes the IPv4 address as the only argument in the form of string. Example 1: Input: IPv4 address = 222.111.111.111 Output: 1 Explanation: Here, the IPv4 address is as per the criteria mentioned and also all four decimal numbers lies in the mentioned range. Example 2: Input: IPv4 address = 5555..555 Output: 0 Explanation: 5555..555 is not a valid IPv4 address, as the middle two portions are missing. Your Task: Complete the function isValid() which takes the address in the form of string s as an input parameter and returns 1 if this is a valid address otherwise returns 0. Expected Time Complexity: O(N), N = length of the string. Expected Auxiliary Space: O(1) Constraints: 1<=length of string <=50 Note: The Input/Output format and Example given are used for the system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.
Remove loop in Linked List
Given a linked list of N nodes such that it may contain a loop. A loop here means that the last node of the link list is connected to the node at position X(1-based index). If the link list does not have any loop, X=0. Remove the loop from the linked list, if it is present, i.e. unlink the last node which is forming the loop. Example 1: Input: N = 3 value[] = {1,3,4} X = 2 Output: 1 Explanation: The link list looks like 1 -> 3 -> 4 ^ | |____| A loop is present. If you remove it successfully, the answer will be 1. Example 2: Input: N = 4 value[] = {1,8,3,4} X = 0 Output: 1 Explanation: The Linked list does not contains any loop. Example 3: Input: N = 4 value[] = {1,2,3,4} X = 1 Output: 1 Explanation: The link list looks like 1 -> 2 -> 3 -> 4 |_________| A loop is present. If you remove it successfully, the answer will be 1. Your Task: You don't need to read input or print anything. Your task is to complete the function removeLoop() which takes the head of the linked list as the input parameter. Simply remove the loop in the list (if present) without disconnecting any nodes from the list. Note: The generated output will be 1 if your submitted code is correct. Expected time complexity: O(N) Expected auxiliary space: O(1) Constraints: 1 ≤ N ≤ 10^4
Diameter of a Binary Tree
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two end nodes. The diagram below shows two trees each with diameter nine, the leaves that form the ends of the longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes). Example 1: Input: 1 / \ 2 3 Output: 3 Example 2: Input: 10 / \ 20 30 / \ 40 60 Output: 4 Your Task: You need to complete the function diameter() that takes root as parameter and returns the diameter. Expected Time Complexity: O(N). Expected Auxiliary Space: O(Height of the Tree). Constraints: 1 <= Number of nodes <= 10000 1 <= Data of a node <= 1000
Next Smallest Palindrome
Given a number, in the form of an array Num[] of size N containing digits from 1 to 9(inclusive). The task is to find the next smallest palindrome strictly larger than the given number. Example 1: Input: N = 11 Num[] = {9, 4, 1, 8, 7, 9, 7, 8, 3, 2, 2} Output: 9 4 1 8 8 0 8 8 1 4 9 Explanation: Next smallest palindrome is 94188088149. Example 2: Input: N = 5 Num[] = {2, 3, 5, 4, 5} Output: 2 3 6 3 2 Explanation: Next smallest palindrome is 23632. Your Task: Complete the function generateNextPalindrome() which takes an array num, and an single integer n, as input parameters and returns an array of integers denoting the answer. You don't to print answer or take inputs. Expected Time Complexity: O(N) Expected Auxiliary Space: O(1) Constraints: 1 <= N <= 105 1 <= Num[i] <= 9
Longest Palindromic Substring in Linear Time
Given a string, find the longest substring which is palindrome in Linear time O(N). Input: The first line of input contains an integer T denoting the no of test cases . Then T test cases follow. The only line of each test case contains a string. Output: For each test case print the Longest Palindromic Substring. If there are multiple such substrings of same length, print the one which appears first in the input string. Constraints: 1 <= T <= 100 1 <= N <= 50 Example: Input: 2 babcbabcbaccba forgeeksskeegfor Output: abcbabcba geeksskeeg Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.
Binary Tree to DLL
Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In-Place. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the DLL. TreeToList Example 1: Input: 1 / \ 3 2 Output: 3 1 2 2 1 3 Explanation: DLL would be 3<=>1<=>2 Example 2: Input: 10 / \ 20 30 / \ 40 60 Output: 40 20 60 10 30 30 10 60 20 40 Explanation: DLL would be 40<=>20<=>60<=>10<=>30. Your Task: You don't have to take input. Complete the function bToDLL() that takes root node of the tree as a parameter and returns the head of DLL . The driver code prints the DLL both ways. Expected Time Complexity: O(N). Expected Auxiliary Space: O(H). Note: H is the height of the tree and this space is used implicitly for the recursion stack. Constraints: 1 ≤ Number of nodes ≤ 105 0 ≤ Data of a node ≤ 105
AVL Tree Deletion
Given a AVL tree and N values to be deleted from the tree. Write a function to delete a given value from the tree. Example 1: Tree = 4 / \ 2 6 / \ / \ 1 3 5 7 N = 4 Values to be deleted = {4,1,3,6} Input: Value to be deleted = 4 Output: 5 / \ 2 6 / \ \ 1 3 7 Input: Value to be deleted = 1 Output: 5 / \ 2 6 \ \ 3 7 Input: Value to be deleted = 3 Output: 5 / \ 2 6 \ 7 Input: Value to be deleted = 6 Output: 5 / \ 2 7 Your Task: You dont need to read input or print anything. Complete the function delelteNode() which takes the root of the tree and the value of the node to be deleted as input parameters and returns the root of the modified tree. Note: The tree will be checked after each deletion. If it violates the properties of balanced BST, an error message will be printed followed by the inorder traversal of the tree at that moment. If instead all deletion are successful, inorder traversal of tree will be printed. If every single node is deleted from tree, 'null' will be printed. Expected Time Complexity: O(height of tree) Expected Auxiliary Space: O(height of tree) Constraints: 1 ≤ N ≤ 500
Transpose File
Given a text file file.txt, transpose its content. You may assume that each row has the same number of columns, and each field is separated by the ' ' character. Example: If file.txt has the following content: name age alice 21 ryan 30 Output the following: name alice ryan age 21 30
Path Sum
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children. Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The root-to-leaf path with the target sum is shown. Example 2: Input: root = [1,2,3], targetSum = 5 Output: false Explanation: There two root-to-leaf paths in the tree: (1 --> 2): The sum is 3. (1 --> 3): The sum is 4. There is no root-to-leaf path with sum = 5. Example 3: Input: root = [], targetSum = 0 Output: false Explanation: Since the tree is empty, there are no root-to-leaf paths. Constraints: The number of nodes in the tree is in the range [0, 5000]. -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000
Path Sum
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children. Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The root-to-leaf path with the target sum is shown. Example 2: Input: root = [1,2,3], targetSum = 5 Output: false Explanation: There two root-to-leaf paths in the tree: (1 --> 2): The sum is 3. (1 --> 3): The sum is 4. There is no root-to-leaf path with sum = 5. Example 3: Input: root = [], targetSum = 0 Output: false Explanation: Since the tree is empty, there are no root-to-leaf paths. Constraints: The number of nodes in the tree is in the range [0, 5000]. -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000
Second Highest Salary
SQL Schema Table: Employee +-------------+------+ | Column Name | Type | +-------------+------+ | id | int | | salary | int | +-------------+------+ id is the primary key column for this table. Each row of this table contains information about the salary of an employee. Write an SQL query to report the second highest salary from the Employee table. If there is no second highest salary, the query should report null. The query result format is in the following example. Example 1: Input: Employee table: +----+--------+ | id | salary | +----+--------+ | 1 | 100 | | 2 | 200 | | 3 | 300 | +----+--------+ Output: +---------------------+ | SecondHighestSalary | +---------------------+ | 200 | +---------------------+ Example 2: Input: Employee table: +----+--------+ | id | salary | +----+--------+ | 1 | 100 | +----+--------+ Output: +---------------------+ | SecondHighestSalary | +---------------------+ | null | +---------------------+
Regular Expression Matching
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Example 1: Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa", p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". Example 3: Input: s = "ab", p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)". Constraints: 1 <= s.length <= 20 1 <= p.length <= 30 s contains only lowercase English letters. p contains only lowercase English letters, '.', and '*'. It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.
Reverse Nodes in k-Group
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is. You may not alter the values in the list's nodes, only nodes themselves may be changed. Example 1: Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5] Example 2: Input: head = [1,2,3,4,5], k = 3 Output: [3,2,1,4,5] Constraints: The number of nodes in the list is n. 1 <= k <= n <= 5000 0 <= Node.val <= 1000 Follow-up: Can you solve the problem in O(1) extra memory space?
Hackathon Mentors
Schedule
Sun Oct 09 2022 (Coordinated Universal Time)
Registrations Open
Thu Dec 01 2022 00:00:00 GMT+0000 (Coordinated Universal Time)
Registrations Close
Thu Dec 01 2022 18:30:00 GMT+0000 (Coordinated Universal Time)
Submissions Close
*Timeline is subject to change/tentative
Rewards and benefits
Swags
Winners
Hack 2 Skill
Swags
Winners
Hack 2 Skill
Partners
Upskilling Partner
Frequently Asked Questions
SOS TECH HACK is open to the Students, technologist, freelancers and professional developer community.
The entry should be functional for review by the judges.
There is no participation fee.
Yes, participants are required to submit a prototype. If you use any database like SQL Server or PostgreSQL you can also submit a database dump along with your submission.
The organizing team will approve and confirm your participation. Shortlisted teams will receive a confirmation email and it will reflect on the user dashboard.
Yes, all team members can login from their account and submit application.