## 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``````

Comment hidden because of low score. Click to expand.
0

But the list is not necessarily sorted.

Comment hidden because of low score. Click to expand.
0

the question says:

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

Comment hidden because of low score. Click to expand.
0

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'

Comment hidden because of low score. Click to expand.
0

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];
}

Comment hidden because of low score. Click to expand.
0

Good & simple.

Comment hidden because of low score. Click to expand.
0

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];``````

}

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;
}``````

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];
}``````

Comment hidden because of low score. Click to expand.
0

Similar thought with yours.

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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];

}
}``````

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;``````

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)``````

Comment hidden because of low score. Click to expand.
0

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"``````

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);
}``````

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)))
}``````

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";
}``````

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.

### 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.