Ibibo Interview Questions (Tradus.in, goIbibo.com, payU.in)

Interview Questions for Software Engineer Profile

Ibibo Web Pvt Ltd - May 2012

round1

1. Linked list contain alphabets.find if it is palindrome or not
2. Array of unsorted no. is given, find triplets which satisfy a² + b² = c².
3. Duplicate a linked list.

round2

1. Sorted array cyclically right-shifted unknown no of times. find an element in it.
2. Stack which does push, pop and findMin in O(1).

round3

1. Given 2 arrays unsorted, insert common elements in third array in O(n).
2. Given 2 arrays unsorted, insert unique elements in third array in O(n).
3. Fill n*n matrix clockwise starting from center. Write efficient code.
ex.   7   8  9
        6   1  2
        5   4  3
4. Print 2D matrix in spiral order.

round4

1. Lots of technical questions from Resume.
2. Given three arrays A,B,C containing unsorted numbers.  Find three numbers a, b, c from each of array A, B, C such that |a-b|, |b-c| and |c-a| are minimum.

Sorted array rotated unknown times, find an element Interview Question

Sorted array has been rotated unknown times, find an element in it

Amazon Interview (April 2012)

Problem Statement

A sorted array has been rotated for unknown no of times, find an element in it in O(logn). Write production ready and bug free code.
Ex if {2,4,6,8,10} is rotated 2 times it becomes{6,8,10,11,2,4}

Solution 

#include<stdio.h>

int find(int a[], int l, int r, int x);

int main()
{

int arr[6] = {6,8,10,11,2,4};
printf("%d",  find(arr,0,5,2));
scanf("%d", arr[0]);

}

int find(int a[], int l, int r, int x) {

while(l <= r) {

    int m = (l+r)/2;
   
    if(a[m] == x) return 1;
   
    if(a[l] <= a[m]) {
       if(x > a[m])
          l = m+1;
       else if(x >= a[l])
          r = m-1;
       else l = m+1;
    }
   
    else {
   
        if (x < a[m])
          r = m-1;
        else if (x <= a[r])
          l = m+1;
        else r = m-1;       
    }
}

return 0;
}


//If you have a different approach in mind, please share it in comments section for our readers.

Time Complexity

O(logn) for  array size is reduced by half every time one enters loop.

Merge two special arrays O(n) Code

Merge two special arrays with given conditions. 

Amazon Interview (May 2012).

 

 Problem Statement

Given two arrays having some elements in common, write a program to merge them such that all the elements occurring before common elements in both arrays also lie before common elements in merged array also and common element occurs only once in merged array.
Array can contain both alphabets and integers.
The elements lying before common element of both arrays can appear in any order in merged array.
Write a O(n) time complexity code.
Ex. A = [z,a,b,c,d,e,f]
       B = [k,g,a,h,b,f]
   Ans = [z,k,g,a,h,b,c,d,e,f]

Algorithm

1) Put elements of one array in hash-table.
2) Start incrementing pointer in 2nd array from 1 to n, if the element lie in hash-table put all elements before it in 1st array into the merged array else put this element into merged array.
3) Put any remaining elements into the merged array

If you have a different approach in mind, please share it in comments section for our readers.

Solution

import java.util.Map;
import java.util.HashMap;

class Solution
{

public static void main(String arg[])
{
char a[] = arg[0].toCharArray();
char b[] = arg[1].toCharArray();
char c[] = new char[a.length+b.length];
merge(a,b,c);
String s = new String(c);
System.out.println(s);
}

private static void merge(char a[], char b[], char c[]) {

Map<Character, Integer> m1 = new HashMap<Character, Integer>();

int i,j,k,l;

for(i=0;i<a.length;i++)
    m1.put(a[i],i);
       
l=0;i=0;j=0;
while(j<b.length) {
   
    if(m1.containsKey(b[j])) {
   
        k = m1.get(b[j]);
        while(i<=k)
            c[l++] = a[i++];
        j++;
    }
    else c[l++] = b[j++];
}
while(i<a.length)
    c[l++] = a[i++];
   
}
}   

Time Complexity: 

O(2n+m) where n is size of first array and m is size of second array. We travel first array twice once while putting its elements into merged array and second time while merging, therefore 2n for first array.



If you find this blog somewhat helpful, please give a +1.

Binary Search on array of numbers: C Code, O(logn)

Interview Question: Find Element

Problem Statement

There is an array of numbers where the number are continuously increasing until any position. After which they are continuously decreasing. Find the element where this has changed.

Solution

#include<stdio.h>

int find(int a[], int l, int r) ;
int main()
{

int a[20] = {2,4,7,3,2,1};
int l = 0;
int r = 5;

printf("%d ok", find(a, l, r));

}

// recursive code prefered
int find(int a[], int l, int r) {

while(l <= r) {
   
    int m = (l +r)/2;
       
    if(a[m] > a[m-1] && a[m] > a[m+1])
        return a[m+1];
   
    else if(a[m] < a[m-1] && a[m] > a[m+1])
        return a[m];
   
    else if(a[m-1] < a[m] && a[m] < a[m+1])
        return find(a, m+1, r);
   
    else if(a[m-1] > a[m] && a[m] > a[m+1])
        return find(a, l, m-1);
}

return -1;
}
       

Time Complexity: O(logn), binary search


If you find this blog somewhat helpful, please share it and Keep Visting....:)