What’s Difference?

Count pairs of non-overlapping palindromic sub-strings of the given string

Leave a Comment

#include <bits/stdc++.h>

using namespace std;

#define N 100

void pre_process(bool dp[N][N], string s)

{

int n = s.size();

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++)

dp[i][j] = false;

}

for (int j = 1; j <= n; j++) {

for (int i = 0; i <= n - j; i++) {

if (j <= 2) {

if (s[i] == s[i + j - 1])

dp[i][i + j - 1] = true;

}

else if (s[i] == s[i + j - 1])

dp[i][i + j - 1] = dp[i + 1][i + j - 2];

}

int countPairs(string s)

{

bool dp[N][N];

pre_process(dp, s);

int n = s.length();

int left[n];

memset(left, 0, sizeof left);

int right[n];

memset(right, 0, sizeof right);

left[0] = 1;

for (int i = 1; i < n; i++) {

for (int j = 0; j <= i; j++) {

if (dp[j][i] == 1)

left[i]++;

}

right[n - 1] = 1;

for (int i = n - 2; i >= 0; i--) {

right[i] = right[i + 1];

for (int j = n - 1; j >= i; j--) {

if (dp[i][j] == 1)

right[i]++;

}

int ans = 0;

for (int i = 0; i < n - 1; i++)

ans += left[i] * right[i + 1];

return ans;

}

int main()

{

string s = "abacaba";

cout << countPairs(s);

return 0;

}

Source link

Hike Interview Experience | Set 7(For SDE iOS) | 2+ Years Experience

Leave a Comment

I have recently attend Hike Hiring Drive for iOS Developer in Delhi office. Candidates are 0-2, 2-4 and 4+ years of experience . I have got referral from recruiter on LinkedIn .

Round 1: Mobile App – (1:30 hour ) They have provided Flickr Api, task is build iOS App that fetch images using search bar input and display the images . Make sure UI should not blocked, mulitple request handling while user typing, code structure, pagination and readability and image caching is plus if you have implemented .

I have build the app in 50 minutes – Link to see https://github.com/Vasu05/Hike-Messenger-Hiring-iOS-Test

After the completion of app, My App is reveiwed by iOS manager .He was cool and friendly .He asked model structure I’ve followed, there is crash in my app, asked me debug and I did , told him the crash reason . He asked about GCD , asked for code optimization .He asked how to detect if user scrolled bottom of page . He inspect the app thoroughly, he was typing, cancelling, clearing data to see behaivour of app. He was impressed since I’ve build all the major features with code optimization . Then we have discussion on current projects I’m into, what I have built in past .This reveiw round was around for 1:20 hr . He asked me to have a lunch and wait for second round .

Round 2: DS Algo (30 min) –

Find two elements with sum equal to value x in Array.I did it using hashmap .
Is Tree is BST or Not.
LRU Implementation
Discussion on threads handling in iOS

Proper code was required, they have given enough time to think and asked for better approach . I code all three on board with explanation . Interviewer was impressed, asked me wait for another round .

Round 3: This round was supposed to taken by Vice President of company but he was busy with another candidates so another lead come and asked me for another round . He asked two questions

Detect loop in linkedlist and remove the loop.
get merging point of two linkedlist.

Meanwhile I was writing code for second questions on paper, he said he was done with interview and asked me to meet VP for further round .

Round 4 : This round taken by VP of company . He gaves introduction, what he did, what they are focusing on and talk about how they are different from another messaging apps in market . He asked me whether you prefer pen and paper or writing on screen, then he asked me come to board, it was samsung TV where i supposed to write code with pen . He asked –

Infinite stream of words you have to tell k most occuring words . I told him approach with heap and trie, he asked me use another data structure for searching, i gave him ternary tree apporoach still he was expecting better and gave me hint to use map then gave solution using heap and hashmap . He asked me to code .
check wether binary tree is min heap or not . He left the room and asked me think optimise solution . He comes after 30 minutes break in between i’ve written properties of binary tree and heap then write code for checking tree is min heap or not .He was satisfied .
He gave me design question – he asked me build sticker search option while user is typing . I told him about memory caching he asked me what all typing of caching we can used . I told him there is App cache maintain by app, disk memory and network memory . I have made diagram how search query will work step by step . Then we have discussion on multiple characters handling when user typing, I said we can use timer to process new request . Then he asked me main thread should not be blocked while user interacting with screen . I told him to use GCD’s and we have long discussion on this . He was satisfied, it was long round, he was helping me when I’m stuck . Then we discussed about company culture, whether he still code, how he started with Hike messenger . He asked me to wait for another round .
There are many another questions which I’m not remember .

This round goes for 1:40 hour .

After All this i was very exhaused since I have given all question correctly this continous evaluation was starts from 10:30 in morning .

It was around 5:30 when they scheduled another round of interview .

Round 5: Interviewer scanned my resume, aksed me for brief introduction.I explained him my current company projects and college projects. He was senior backened developer . He starts asking me Java questions . I told him I was not able in touch with since 1.5 years still he asked.

write code for 1 writer and n reader problem . I told him we can use locks (mutes and semaphore) and gave him solution .
He asked virtual pointers – I told him I don’t remember .
Stack vs Heap Memory . I gave him explanation with example .
Singleton class, why we are using this . He was not satisfied with explaination .
He asked basic java questions like what public, private, why there is single main function in Java .

After all this recruiter asked me to leave and next day they said last round was not as per expectation . I’m not selected. Tips – prepare your interview like college placement, they can aks anything even if its not related to your hiring post .

Join Free Interview Preparation Course

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please Improve this article if you find anything incorrect by clicking on the “Improve Article” button below.

Source link

Maximum volume of cube for every person when edge of N cubes are given

Leave a Comment

Given an array of N integers which denotes the edges of N cubical structures respectively. Also given are M integers which denotes the number of peoples. The task is to find the maximum amount of volume of a cube that can be given to every person.

Note: Cubes can be cut of any shape from any of the N cubes.

Examples:

Input: a[] = {1, 1, 1, 2, 2}, m = 3
Output: 4
All three person get a slice of volume 4 each
Person 1 gets a slice of volume 4 from the last cube.
Person 2 gets a slice of volume 4 from the last cube.
Person 3 gets a slice of volume 4 from the second last cube.

Input: a[] = {2, 2, 2, 2, 2}, m = 4
Output: 8

Naive Approach: A naive approach is to first calculate the volume of all of the cubes and then linearly check for every volume that it can be distributed among all M people or not and find the maximum volume among all such volumes.

Time Complexity: O(N²)

Efficient Approach: An efficient approach is to use binary search to find the answer. Since the edge lengths are given in the array, convert them to the volume of the respective cubes.

Find the maximum volume among volumes of all of the cubes. Say, the maximum volume is maxVolume. Now, perform binary search on the range [0, maxVolume].

Calculate the middle value of the range, say mid.
Now, calculate the total number of cubes that can be cut of all of the cubes of volume mid.
If the total cubes that can be cut exceed the number of persons, then that amount of volume of cubes can be cut for every person, hence we check for a larger value in the range [mid+1, maxVolume].
If the total cubes do not exceed the number of persons, then we check for an answer in the range [low, mid-1].

Below is the implementation of the above approach:

#include <bits/stdc++.h>

using namespace std;

int getMaximumVloume(int a[], int n, int m)

{

int maxVolume = 0;

for (int i = 0; i < n; i++) {

a[i] = a[i] * a[i] * a[i];

maxVolume = max(a[i], maxVolume);

}

int low = 0, high = maxVolume;

int maxVol = 0;

while (low <= high) {

int mid = (low + high) >> 1;

int cnt = 0;

for (int i = 0; i < n; i++) {

cnt += a[i] / mid;

}

if (cnt >= m) {

low = mid + 1;

maxVol = max(maxVol, mid);

}

else

high = mid - 1;

}

return maxVol;

}

int main()

{

int a[] = { 1, 1, 1, 2, 2 };

int n = sizeof(a) / sizeof(a[0]);

int m = 3;

cout << getMaximumVloume(a, n, m);

return 0;

}

Time Complexity: O(N * log (maxVolume))

Striver(underscore)79 at Codechef and codeforces D

Please Improve this article if you find anything incorrect by clicking on the “Improve Article” button below.

Source link

Program to calculate the value of nPr

Leave a Comment

Given two numbers n and r, the task is to find the value of nPr.

nPr represents n permutation r which is calculated as n!/(n-k)!. Permutation refers to the process of arranging all the members of a given set to form a sequence. The number of permutations on a set of n elements is given by n!, where “!” represents factorial.

ⁿP_r = n! / (n - r)!

Program:

import java.util.*;

public class GFG {

static int fact(int n)

{

if (n <= 1)

return 1;

return n * fact(n - 1);

}

static int nPr(int n, int r)

{

return fact(n) / fact(n - r);

}

public static void main(String args[])

{

int n = 5;

int r = 2;

System.out.println(n + "P" + r + " = "

+ nPr(n, r));

}

Optimization for multiple queries of nPr
If there are multiple queries for nPr, we may precompute factorial values and use same for every call. This would avoid computation of same factorial values again and again.

Please Improve this article if you find anything incorrect by clicking on the “Improve Article” button below.

Source link

Python | Bigram formation from given list

Leave a Comment

When we are dealing with text classification, sometimes we need to do certain kind of natural language processing and hence sometimes require to form bigrams of words for processing. In case of absence of appropriate library, its difficult and having to do the same is always quite useful. Let’s discuss certain ways in which this can be achieved.

Method #1 : Using list comprehension + enumerate() + split()
The combination of above three functions can be used to achieve this particular task. The enumerate function performs the possible iteration, split function is used to make pairs and list comprehension is used to combine the logic.

test_list = ['geeksforgeeks is best', 'I love it']

print ("The original list is : " + str(test_list))

res = [(x, i.split()[j + 1]) for i in test_list

for j, x in enumerate(i.split()) if j < len(i.split()) - 1]

print ("The formed bigrams are : " + str(res))

Output :

The original list is : [‘geeksforgeeks is best’, ‘I love it’]
The formed bigrams are : [(‘geeksforgeeks’, ‘is’), (‘is’, ‘best’), (‘I’, ‘love’), (‘love’, ‘it’)]

Method #2 : Using zip() + split() + list comprehension
The task that enumerate performed in the above method can also be performed by the zip function by using the iterator and hence in a faster way. Let’s discuss certain ways in which this can be done.

test_list = ['geeksforgeeks is best', 'I love it']

print ("The original list is : " + str(test_list))

res = [i for j in test_list

for i in zip(j.split(" ")[:-1], j.split(" ")[1:])]

print ("The formed bigrams are : " + str(res))

Output :

The original list is : [‘geeksforgeeks is best’, ‘I love it’]
The formed bigrams are : [(‘geeksforgeeks’, ‘is’), (‘is’, ‘best’), (‘I’, ‘love’), (‘love’, ‘it’)]

Please Improve this article if you find anything incorrect by clicking on the “Improve Article” button below.

Source link

Python | Convert case of elements in a list of strings

Leave a Comment

Given a list of strings, write a Python program to convert all string from lowercase/uppercase to uppercase/lowercase.

Input : ['GeEk', 'FOR', 'gEEKS']
Output: ['geeks', 'for', 'geeks']

Input : ['fun', 'Foo', 'BaR']
Output: ['FUN', 'FOO', 'BAR']

Method #1 : Convert Uppercase to Lowercase using map function

out = map(lambda x:x.lower(), ['GeEk', 'FOR', 'gEEKS'])

output = list(out)

print(output)

Output:


['geek', 'for', 'geeks']

Method #2: Convert Lowercase to Uppercase using List comprehension

input = ['fun', 'Foo', 'BaR']

lst = [x.upper() for x in input]

print(lst)

Output:


['FUN', 'FOO', 'BAR']

Please Improve this article if you find anything incorrect by clicking on the “Improve Article” button below.

Source link