Linkedin Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
2
of 4 vote

Assuming the list doesn't contain duplicates. It's just a simple variation of binary search.

public static char findNextChar(char[] list, char c) {
		assert list.length > 0;
		int left = 0, right = list.length - 1;
		char result = list[0];
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (list[mid] == c) {
				if (mid < list.length - 1) return list[mid+1];
				else return result;
			}
			else if (list[mid] < c) {
				left = mid + 1;
			}
			else {//list[mid] > c 
				result = list[mid];
				right = mid - 1;
			}
		}
		return result;
	}
	
	public static void main(String[] args) {
		char[] list = {'c', 'f', 'j', 'p', 'v'};
		char[] target = {'a', 'c', 'f', 'k', 'v', 'z'};
		for (char c : target) System.out.println(c + " -> " + findNextChar(list, c));
	}

Test Case:

char[] list = {'c', 'f', 'j', 'p', 'v'};

Output:

a -> c
c -> f
f -> j
k -> p
v -> c
z -> c

- chriscow January 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But the list is not necessarily sorted.

- Demo February 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the question says:

@param sortedStr : sorted list of letters, sorted in ascending order

- sh88990 April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please test your code for input char arr []={'a','c','e','g','i','j'}; and char c='f'.
O/p should be 'g' but your code gives o/p as 'i'

- Aspire November 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is my solution:
char getSmallestLarge(char [] list,char c)
{
SmallestCharacter sc=new SmallestCharacter();
return sc.BinarySearchChar(list,c,0,list.length-1);
}

char BinarySearchChar(char[] list,char c,int low,int high)
{
if(low>high)
return ' ';
if(high-low+1==2)
{
if(list[low]<=c && list[high]>c)
return list[high];

return list[0];
}
if(high-low+1==3)
{
if(list[low]==c)
return list[low+1];
if(list[low+1]==c)
return list[low+2];
if(list[low]<c && list[low+1]>c)
return list[low+1];
if(list[low+1]<c && list[low+2]>c)
return list[low+2];
//default case
return list[0];
}
int mid=low+high/2;
if(list[mid]==c)
return list[mid+1];
else if (list[mid-1]<c && list[mid]>c)
return list[mid];
else if(list[mid]<c && list[mid+1]>c)
return list[mid+1];
else if(list[mid]>c)
return BinarySearchChar(list,c,0,mid-1);
else if(list[mid]<c)
return BinarySearchChar(list,c,mid+1,high);

return list[0];
}

- Aspire November 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good & simple.

- purpleshoes November 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually it doesn't make much difference even if duplicates are allowed.

public char nextChar2(char[] list, char c) {
		if (list == null || list.length == 0)
			throw new IllegalArgumentException("Null or empty list!");
		int start = 0;
		int end = list.length - 1;
		if (c < list[0] || c >= list[list.length - 1])
			return list[0];
		while (start < end) {
			int mid = (start + end) / 2;
			if (c == list[mid]) {
				if (list[mid + 1] > c)
					return list[mid + 1];
				else 
					start = mid + 1;
			}
			else if (c < list[mid]) {
				end = mid - 1;
			}
			else
				start = mid + 1;
		}
		if (list[start] == c)
			return list[start + 1];
		return list[start];

}

- DoraShine December 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

keep two variables, one that stores the smallest character and another that stores the smallest character that is also strictly larger than the given character.

char smallest_of_strictly_larger(char* str, char c)
{
	char s = 'z'; // the smallest char
	char sl = c; // the smallest char that is strictly larger than the given c
	
	int i=0;
	while( str[i]!='\0' ) {
		if( str[i]<s )
			s = str[i];
		if( str[i]>c && (sl==c || str[i]<sl) ) 
			sl = str[i];
		i++;
	}
	return sl==c ? s : sl;
}

- daytona February 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static char find(char [] chs , char target){
		int left = 0;
		int right = chs.length - 1;
	    while(left<=right){
	      int mid = (left+right)/2;	      
	      if (chs[mid] == target){	    	
	    	 if (mid<chs.length - 1){
	    		 return chs[mid+1];
	    	 }else{
	    		 return chs[0];	 
	    	 }
	      } else if (target > chs[mid]){
	        	left = mid+1;
	      }else{
	    	right = mid -1 ;
	      }	      
	    }
	    
	    
		return left == 0? chs[0]:left==chs.length? chs[left-1]:chs[left];
	}

- Scott February 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Similar thought with yours.
However, please change your code slightly.

return left == 0? chs[0]:left==chs.length? chs[0]:chs[left];

- Chris October 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is the list sorted? Sorted ==> Binary search. Not sorted ==> linear search

- Victor February 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

char smallestChar(char sortedArr[250],char srchChar)
{
	for(int i=0;sortedArr[i]!='\0';i++)
	{
		if(srchChar=='z' )
			return sortedArr[i];
		
		if(sortedArr[i]>srchChar)
			return sortedArr[i];

	}
}

- Anonymous February 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function smallestChar(arr, char){
    var tempSmall = arr[0];
    for(var i =0,len = arr.length;i<len;i++){
        if(arr[i] > char){
             tempSmall = arr[i];
             break;
        }

    } 
return tempSmall;

- KK February 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Python,

def smallest_strictly_larger(list, target):
  list.sort(reverse=True)
  found = list[-1]       #needed for wrap-around case
  for e in list:
    if e > target:
      found = e
    else:
      break                #end prematurely
  return found

list = ["c", "f", "j", "p", "v"]
target = "d"
print smallest_strictly_larger(list, target)

- afernandezcmu March 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This works but it's not the most efficient as it's the brute force methodology. Like all of the others above, you should use binary search.

from types import ListType


def getNext(sorted_array, char):
    left = 0
    right = len(sorted_array) - 1
    result = sorted_array[0]

    assert len(sorted_array) > 0
    assert ListType(sorted_array)

    if len(sorted_array) == 1:
        return result

    while left < right:
        middle = left + (right - left) / 2
        if sorted_array[middle] == char:
            if middle < len(sorted_array) - 1:
                return sorted_array[middle+1]
            else:
                return result
        elif sorted_array[middle] < char:
            left = middle + 1
        else:
            right = middle - 1
            result = sorted_array[middle]
    return result

list = ["c", "f", "j", "p", "v"]
target = "d"

- JK February 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

do a modified binary search O(logn)

public char modBS(char[]input,int left, int right, char target){
    if(left > right){
        return input[left%input.length];
    }
    
    int mid = (left + right)/2;
    if(input[mid] == target){
        return input[(mid+1)%input.length];
    }else if(input[mid] < target){
        return modBS(input,mid+1,right,target);
    }else{
        return modBS(input,left,mid-1,target);
    }
}

public char findCharacter(char[] input, char target){
     return modBS(input,0,input.length-1,target);
}

- sh88990 April 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In scala

object SmallestChar extends App {
	def smallestChar(chars:Seq[Char], char:Char):Char = {
	  if (char>=chars.last) return chars(0)
	  def search(lower:Int, upper:Int):Char = {
	    var middle = (lower+upper)/2
	    val c = chars(middle)
	    if (c==char) return chars(middle+1)
	    if (upper-lower<=1) {
	      if (chars(lower)<char) return chars(upper)
	      else return chars(lower)
	    }
	    if (c<char) search(middle, upper)
	    else search(lower, middle)
	  }
	  search(0, chars.length)
	}
	
	"acfkvz".foreach(c=>println(smallestChar("cfjpv", c)))
	println
	"ackz".foreach(c=>println(smallestChar("cfjpv", c)))
	println
	"fcd".foreach(c=>println(smallestChar("cfk", c)))
}

- sabz July 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>

using namespace std;

char getSmallest(vector<char>& chars, char c, int l, int h, int n) {
    int m = (l+h)/2;
    if (chars[m] > c) {
        if (m > 0 && chars[m-1] > c) {
            return getSmallest(chars, c, l, m-1,n);
        } else {
            return chars[m];
        }
    } else if (chars[m] < c) {
        if (m == n-1) {
            return chars[0];
        } else {
            return getSmallest(chars, c, m+1,h,n);
        }
    } else {
        if (m == n-1) {
            return chars[0];
        } else {
            return chars[m+1];
        }
    }
}

int main() {
    vector<char> chars;
    chars.push_back('c');
    chars.push_back('f');
    chars.push_back('j');
    chars.push_back('p');
    chars.push_back('v');
    cout << "Smallest : " << getSmallest(chars, 'c',0,4,5) << "\n";
    cout << "Smallest : " << getSmallest(chars, 'z',0,4,5) << "\n";
    cout << "Smallest : " << getSmallest(chars, 'k',0,4,5) << "\n";
    cout << "Smallest : " << getSmallest(chars, 'a',0,4,5) << "\n";
    cout << "Smallest : " << getSmallest(chars, 'v',0,4,5) << "\n";
    cout << "Smallest : " << getSmallest(chars, 'j',0,4,5) << "\n";

    vector<char> chars2;
    chars2.push_back('c');
    cout << "Smallest : " << getSmallest(chars2, 'j',0,0,1) << "\n";
    cout << "Smallest : " << getSmallest(chars2, 'a',0,0,1) << "\n";
    cout << "Smallest : " << getSmallest(chars2, 'c',0,0,1) << "\n";

    chars2.push_back('d');
    cout << "Smallest : " << getSmallest(chars2, 'c',0,1,2) << "\n";
    cout << "Smallest : " << getSmallest(chars2, 'd',0,1,2) << "\n";
}

- anonymous March 04, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More