We recently held the very first event of our new year and boy were we surprised with the overwhelming responses. It was a coding competition, obviously, hosted on hackathon. The participants were given problems based on data structures, to increase the skills of the novices and refresh the skills of the veterans.
The competition consisted of 3 questions. Participants were given a total of 3 days to solve them and a lot of them came up with ingenious solutions.
Since some of our participants faced some problems while solving the questions , the most basic approaches to the problems are listed below. We hope that our participants can build their own codes from the logics listed below.
SHERLOCK AND ARRAY:
PROBLEM
In this problem , the challenge is to find an element of the array such that the sum of all elements to the left is equal to the sum of all elements to the right.
SOLUTION
For this we can make use of 2 other arrays , one to store the elements to the right of the array[i] element and the other to store the elements to the left of the array[i]. we can then compare the sums of those 2 arrays and using a loop , we can iterate through the entire original array. The loop breaks either when the desired element is found or the array ends.
ICE CREAM PARLOR:
PROBLEM
This problem states that , Sunny and Johnny like to pool their money and go to the ice cream parlor. Johnny never buys the same flavor that Sunny does. The only other rule they have is that they spend all of their money.
Given a list of prices for the flavors of ice cream, select the two that will cost all of the money they have.
SOLUTION
The approach for this is we use 2 ‘for’ loops. We first run a for loop from k=0 to k=the length of the given array of prices. Inside that loop we again run a for loop starting from l=k+1 till l=the end of the array. Use a variable , say sum, and equate it to array[k]+array[l].Inside that use a conditional statement to check whether the sum is equal to the total money that Sunny and Johnny have. If it is enter the value of k and l inside an array using .append() , in increasing order and return the final array.
SPARSE ARRAYS:
PROBLEM
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results.
SOLUTION
Create an integer array for storing the results. Using a for loop to iterate through the input string , create a variable which will store the value of the input string element that we want to check in the input string. Inside this loop ,create a for loop to iterate through the query string and keep comparing the variable with the query elements , once comparison returns true , use a flag variable and once the array reaches its end, enter the flag variable into the new integer array and equate the flag variable to 0. Return the integer array once both loops end.
BUILD A PALINDROME:
PROBLEM
You have two strings ,a and b . Find a string, s, such that:
- s can be expressed as s=s(a)+s(b),where s(a) is a non-empty substring of a and s(b) is a non-empty substring of b .
- s is a palindromic string.
- The length of s is as long as possible.
SOLUTION
Make two strings S(a) and S(b). Compare both strings a and b at the same time. If you encounter the same letter , add the letter from a to S(a) and the letter from string b to S(b).Check whether the next letters of the strings match. If they don’t , return string ‘s’=-1. If they do match , keep checking and concatenating letters to S(a) and S(b) till the letters stop matching. As soon as that happens , stop moving through the strings and then take one letter from string a and add it to S(a) as well . Make sure that you reverse the string S(b) before adding it to ‘s’. Now make s=S(a)+S(b). Reverse s and compare it to the original string to check if it’s a palindrome or not. Return s.
If anyone of you wishes to contribute to the solutions , the link for the Git repository is given below. Do enter your optimized solutions there.
— Shreya Mandal, on behalf of Team Loop
