    # SOS TECH HACK #sostechhack

Tech Is Future Of World

view more...

online Solo Entry

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) ##### 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  ##### Remove loop in Linked List ##### 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 ##### Divjot Singh

Software Engineer

View More

### Schedule

00:00
00:00
To Be Announced
###### Submissions Close

*Timeline is subject to change/tentative

### Rewards and benefits Winners

Hack 2 Skill