Repeated Character Whose First Appearance is Leftmost


Given a string, find the repeated character present first in the string.


Examples:


Input  : geeksforgeeks
Output : g
(mind that it will be g, not e.)

Input  : abcdabcd
Output : a

Input  : abcd
Output : -1
No character repeats

Asked in: Goldman Sachs internship

We have discussed different approaches in Find repeated character present first in a string.

How to solve this problem using one traversal of input string?


Method 1 (Traversing from Left to Right)
We traverse the string from left to right. We keep track of the leftmost index of every character. If a character repeats, we compare its leftmsot index with current result and update the result if result is greater

#include <bits/stdc++.h>

using namespace std;

#define NO_OF_CHARS 256

  

int firstRepeating(string& str)

{

    

    

    int firstIndex[NO_OF_CHARS];

    for (int i = 0; i < NO_OF_CHARS; i++)

        firstIndex[i] = -1;

  

    

    

    

    

    int res = INT_MAX;

    for (int i = 0; i < str.length(); i++) {

        if (firstIndex[str[i]] == -1)

           firstIndex[str[i]] = i;

        else

           res = min(res, firstIndex[str[i]]);

    }

  

    return (res == INT_MAX) ? -1 : res;

}

  

int main()

{

    string str = "geeksforgeeks";

    int index = firstRepeating(str);

    if (index == -1)

        printf("Either all characters are "

               "distinct or string is empty");

    else

        printf("First Repeating character"

               " is %c",

               str[index]);

    return 0;

}

Output:


First Repeating character is g

Time Complexity : O(n). It does only one traversal of input string.
Auxiliary Space : O(1)


Method 2 (Traversing Right to Left)
We traverse the string from right to left. We keep track of the visited characters. If a character repeats, we update the result.

#include <bits/stdc++.h>

using namespace std;

#define NO_OF_CHARS 256

  

int firstRepeating(string& str)

{

    

    bool visited[NO_OF_CHARS];

    for (int i = 0; i < NO_OF_CHARS; i++)

        visited[i] = false;

  

    

    

    int res = -1;

    for (int i = str.length() - 1; i >= 0; i--) {

        if (visited[str[i]] == false)

            visited[str[i]] = true;

        else

            res = i;

    }

  

    return res;

}

  

int main()

{

    string str = "geeksforgeeks";

    int index = firstRepeating(str);

    if (index == -1)

        printf("Either all characters are "

               "distinct or string is empty");

    else

        printf("First Repeating character"

               " is %c",

               str[index]);

    return 0;

}

Output:


First Repeating character is g

Time Complexity : O(n). It does only one traversal of input string.
Auxiliary Space : O(1)

The method 2 is better than method 1 as it does fewer comparisons.




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.

Article Tags :



1

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.








Source link

Congnizant ( CTS ) Placement Preparation




Be the First to upvote.

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.







Source link

Given two arrays count all pairs whose sum is an odd number


#include <bits/stdc++.h>

using namespace std;

  

int count_pairs(int a[], int b[], int n, int m)

{

  

    

    int odd1 = 0, even1 = 0;

    int odd2 = 0, even2 = 0;

  

    

    

    

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

        if (a[i] % 2)

            odd1++;

        else

            even1++;

    }

  

    

    

    

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

        if (b[i] % 2)

            odd2++;

        else

            even2++;

    }

  

    

    int pairs = min(odd1, even2) + min(odd2, even1);

  

    

    return pairs;

}

  

int main()

{

    int a[] = { 9, 14, 6, 2, 11 };

    int b[] = { 8, 4, 7, 20 };

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

    int m = sizeof(b) / sizeof(b[0]);

    cout << count_pairs(a, b, n, m);

  

    return 0;

}



Source link

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


#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


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.

Article Tags :



Be the First to upvote.

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.








Source link

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


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(N2)

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


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.

Article Tags :



Be the First to upvote.

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.








Source link